CRC-16

Курсовая работа
Петров Дмитрий, 3 курс, группа КБ-301, мат-мех УрГУ, 2003 год.
Руководитель - М. Баклановский

  1. Введение
  2. Способы обнаружения искажений в пакете
  3. СRC-арифметика
  4. Стандарты для CRC-полиномов
  5. Алгоритм
  6. Требования к CRC-полиномам
  7. Исследование
  8. Приложение 1. Примеры
  9. Приложение 2. Другие CRC-полиномы
  10. Приложение 3. Аббревиатуры
  11. Библиография и ссылки
  12. Утилита для вычисления СRC (Скачать)

Введение.

С развитием технологии стали возникать все более и более интересные вещи. Так оказалось, что отправляя, файл по модему, или же копируя его с дискеты мы не можем быть уверены в том, что мы получим то, что хотели и без искажений. Как только был обнаружен этот факт (а это было уже довольно давно) разработчики программного и аппаратного обеспечения решили внедрят различные алгоритмы обнаружения ошибок в полученном сообщении. Но так или иначе практически каждый алгоритм обладал рядом недостатков. В ходе отбора стали применяться алгоритмы CRC (Циклических избыточных сумм). CRC обладает рядом преимуществ и, вообще, на CRC наложены достаточно жестокие требования, чтобы он мог обнаруживать разнообразные виды ошибок. Цель данной работы исследовать известные алгоритмы нахождения CRC 16 бит и узнать действительно ли выполняются те требования, которые накладывались на него при разработке. Следует сразу отметить, что CRC отнюдь не ограничиваются 16-ю битами, применяются (или же применялись) так же CRC 8, 10, 24 и 32 бит, но CRC 16-бит оказались наиболее удобными для исследования в силу их длины.

Возникновение ошибки из-за шума можно показать так:

  1. Изначальный сигнал, который посылается отправителем.

    2. Начальный сигнал

  2. В линии возникает помеха, некий шум.

    3. Шум

  3. В итоге шум налагается на сигнал, и получатель видит искаженную информацию.

    4. В итоге получим такую вот штуку

Способы обнаружения искажений в пакете.

Чтобы обнаружить искаженную информацию существует и применяется несколько способов, которые добавляют лишнюю информацию, по которой получатель может определить была ли ошибка.

  1. Посимвольный контроль четности.
    2. С каждым байтом передается дополнительный бит, принимающего единичное значение по четному или нечетному количеству единичных битов в байте. Может использоваться два типа контроля четности - на четность и нечетность. Не самый эффективный способ обнаружения ошибок. Этот вид контроля обычно реализуется аппаратно в устройствах связи.
    Пример.10010010.0, 0 добавили (проверка на нечетность) получают: 10110010.0, ошибка обнаружена получают: 11110010.0, ошибка не обнаружена

  2. Поблочный контроль четности.
    3. Размер блока заранее установлен. В этой схеме контроля для каждой позиции разрядов в символах блока (поперек блока) рассчитываются свои биты четности, которые добавляются в виде обычного символа в конец блока. При этом схема продольного контроля по прежнему предполагает наличие у каждого из этих символов дополнительного бита четности. По сравнению с посимвольным контролем обладает большими возможностями, но используется редко, т.к. не реализуется эффективно аппаратно, в отличии от посимвольного контроля.

    Поблочный контроль четности.

  3. Вычисление контрольных сумм.
    4. В простейшем виде контрольная сумма - это арифметическая сумма двоичных значений контролируемого блока символов. Но этот метод обладает практически теми же недостатками, что и предыдущие, а именно нечувствителен к четному числу ошибок.

  4. Контроль циклически избыточным кодом.
    5. CRC - Cyclic Redundancy Code. Это гораздо более мощный и широко используемый метол обнаружения ошибок при передаче информации. Он обеспечивает высокую вероятность обнаружения ошибок. Основная идея вычисления CRC заключается в следующем. Исходная последовательность байтов представляется единой последовательностью битов. Эта последовательность делится на некоторое фиксированное двоичное число. Интерес представляется остаток от деления, который и является значение CRC.

Вообще вышеизложенные способы являются хэш-фуенкциями, т.е.: Хэш функцией называется математическая, либо другая функция, которая преобразует входные данные произвольной длины в данные фиксированной длины (значение хэш функции). Как правило, выходные данные хеш-функции имеют меньший размер, чем входные. Как правило, в качестве хеш-функций выступают односторонние функции. Главная задача хеш-функции состоит в том, чтобы по выходным данным невозможно было восстановить входные. Например для проверки пароля можно проверять его соответствие хэшу. В этом случае не требуется хранить пароль в открытом виде. Пример простейшей хеш-функции - сумма всех элементов массива. [7] CRC и является односторонней хэш-функцией.

CRC-арифметика.

Что же такое особенное есть в CRC, что позволяет обнаруживать большую часть ошибок? Это безусловно метод его нахождения. Для нахождения CRC используется специальная CRC-арифметика, которая является полиномиальной арифметикой по модулю 2. Т.е. битовое значение 1001001112=16710 может быть представлено в виде: 1*x^8+0*x^7+0*x^6+1*x^5+0*x^4+0*x^3+1*x^2+1*x^1+1. Для того чтобы получить искомое значение, можно подставить x=2. Эта арифметика обладает одним весьма не маловажным свойством - операции сложения и вычитания идентичны, и поэтому можно оставить лишь одну операцию, т.е.

	_1001011
	 1100010
	 -------
	 0101001

Сложение и вычитание ведется по следующим правилам: 0-0=0, 0-1=1, 1-0=1, 1-1=0. Таким образом можно заметить, что результат вычитания в арифметике без переносов, аналогичен операции XOR. Для нашего рассмотрения особый интерес представляет операция деления, так как в основе любого алгоритма вычисления CRC лежит представление исходного сообщения в виде огромного двоичного числа, делении его на другое двоичное число и использование остатка от этого деления в качестве значения CRC. Говоря иначе: M - исходное сообщение, n - степень порождающего полинома, G - порождающий полином, тогда CRC - это остаток от M*x^n/G.

Например, сообщение M=0x54, G=0x11021 (Xmodem). M'=0101,0100,0000,0000,0000,0000 G=1,0001,0000,0010,0001 

	
	010101000000000000000000|00010001000000100001
         10001000000100001	|частное никого не интересует
	------------------------  
         00100000000100001000000
           10001000000100001
	------------------------
           000010000101001010000
	       10001000000100001
	------------------------
	       00001101001110001
      	       0001,1010,0111,0001=0x1a71 - остаток от деления
После получения этого остатка - остаток добавляется в конец передаваемого сообщения и сообщение передается. Есть 2 способа обнаружения ошибок:
  1. Приемник может получить сообщение отделить последние 16 бит, посчитать CRC оставшегося и сравнить с тем 16 битами.
  2. Или же приемник может поделить полученное сообщение на G, и таким образом обнаружить ошибку

Стандарты для CRC-полиномов.

Несколько протоколов определяют CRC-полиномы используемые для обнаружения ошибок: CCITT X.25, BiSynch, SDLC, HDLC. Они определяют полином и метод нахождения остатка. Используемые полиномы:

  1. CRC X.25 (CCITT), X-modem:x16 + x12 + x5 + 1
  2. CRC-16 (Bisynch): x16 + x15 + x2 + 1
Не все протоколы используют обычную схему нахождения остатка, так, например, рассмотрим CCITT X.25. S=0x54, G=0x11021, n=16. В приложении CCITT сначала меняется порядок битов сообщения, т.е. S=0x54 становится S=0x2a. К тому же начальное значение CRC инициализируется единицами. Это тоже, что XOR первых 16-ти бит с 16-ю единицами. 

	110101011111111100000000 |10001000000100001 
	10001000000100001	 |частное не имеет значения 
	-------------------------
	010111011110111110000000
         10001000000100001
	-------------------------
  	 00110011110011111000000
      	   10001000000100001
	-------------------------
           010001110010111010000
            10001000000100001
	-------------------------
            00000110010011011000
Остаток равен 0110,0100,1101,1000. Последовательность бит так же меняется, т.е. 0001,1011,0010,0110. Затем результат обращается и две восьмерки битов меняются местами, Итак CRC=1101100111100100, или CRC=0xd9e4.

Протокол Xmodem был разработан специально для программного применения. Он использовал тот же полином, что CCITT X.25. Протокол Xmodem использует обычный алгоритм нахождения CRC. И поэтому довольно просто в применении там, где невозможно реализовать таблицы.

Надо отметить, что различные стандарты так же имеет различные отклонения от обычной математической реализации. Многие стандарты инициализируют начальное значение CRC в единицы, но Xmodem, BiSynch - в нули. Старый CCITT стандарт так же инициализировал в нули, на X.25 инициализирует в единицы. Многие утилиты использующие алгоритм Xmodem'а так же инициализируют начальное значение в 1'ы. Особенности X.25 были показаны выше. Между прочим, существует множество модификаций протокола Xmodem, но не один из них не менял полином. [4] В SDLC и HDLC используется тот же алгоритм и тот же полином, что и в CCITT X.25.

Упомяну о других CRC полиномах. Существуют и стандартизированы CRC полиномы разрядности - 8, 10, 24, 32. Полиномы меньшей разрядности используются там, где передаваемые сообщения малы, тогда как полиномы разрядности 24 могут обнаружить ошибку в сообщения длины свыше одного мегабайта, а 32 уже свыше 256 мегабайт.

Алгоритм.

В самом алгоритме вычисления CRC нет ничего сложного, его можно на любом языке, потому что операции XOR и SHL встроены практически в любой язык. Коротко весь алгоритм можно записать так:

G - полином, M - битовое сообщение.

  1. Дополнить исходное сообщение 16-ю нулями. M'=M*x16.
  2. Инициализировать начальное значение CRC 0x0000.
  3. Выполнять операцию сдвиг влево последовательности бит сообщения M' до тех пор, пока бит в ячейке (ячейка - то место, где изначально находился старший бит M') не станет равным единице или количество бит станет меньше чем в делителе.
  4. Если старший бит станет равным единице, то производим операцию XOR между сообщением и полиномом. И повторяем шаг 2.
  5. То что в конце остается от последовательности M' и называется CRC.
  6. Возможно потребуется обратить результат.
В случае зеркального алгоритма применяемого при вычислении CCITT X.25 и IBM Bisynch CRC есть некоторые отличия, а именно M - не само сообщение, а его зеркальное отражение и еще в X.25 начальное значение - инициализируется в 0xffff - это всего лишь операция XOR первых 16 бит сообщения с 0xffff. Во всем остальном алгоритм работает так же.

Таким образом, алгоритм вычисления CRC имеет несколько параметров:

Следует отметить, что старшая единица в полиноме не имеет значения. И поэтому очень часто вместо, например, 0x11021 можно видеть запись 0x1021.

Как мы получаем таблиный алгоритм

E=((A |сдвиги| XOR B) |сдвиги| XOR C) |сдвиги|

В силу ассоциативности операции XOR можно представить:
F=|сдвиги| XOR ( B |сдвиги| XOR C |сдвиги| XOR D)
E=A XOR F

Таким образом, можно заметить, что количество сдвигов полностью зависит от старшего байта. Величина F полностью предсказуема и определяется значением байта и значением полинома. Следовательно, для одного полинома величина F может принимать 256 значений. Значит, все значения величины F можно свести в одну таблицу. Это ускорит процесс вычисления CRC в несколько раз, потому что таблица вычисляется лишь один раз и в отличии от прямого алгоритма не надо сдвигать каждый бит и тем более последовательность бит дополнять нулями. Так же следует отметить, что единственный разумный способ работать с зеркальным алгоритмом вычисления CRC.

Табличный алгоритм.

G - полином, М - байтовое сообщение.

  1. Вычислить значение в таблице для каждого байта от 0x00 до 0xff:
    • Производится сдвиг влево на 8 бит (из 0x001a -> 0x1a00).
    • Выполнять 8 раз операцию сдвиг влево, причем, если старший бит равен 1, то производится XOR с полиномом G.
    • Все что осталось от двух байт - становится значением в таблице.
  2. Просматривается каждый байт сообщения M:
    • Над старшим байтом текущего значения CRC и текущим байтом сообщения выполняется операция XOR - это индекс в таблице.
    • Младший байт текущего значения CRC сдвигается влево на 8 и становится старшим, затем объединяется по XOR со значением таблицы - это становится новым значением CRC.
  3. В результате получено значение CRC.

Зеркальный алгоритм работает так же, но с незначительными изменениями:

G - полином, М - байтовое сообщение.

  1. Вычислить значение в таблице для каждого байта от 0x00 до 0xff:
    • Выполнять 8 раз операцию сдвиг вправо, причем, если младший бит равен 1, то производится XOR с полиномом G.
    • Все что осталось от двух байт - становится значением в таблице.
  2. Текущее значение CRC = 0xffff, если CCITT и CRC=0x0000, если BiSynch.
  3. Просматривается каждый байт сообщения M:
    • Над младший байтом текущего значения CRC и текущим байтом сообщения выполняется операция XOR - это индекс в таблице.
    • Старший байт текущего значения CRC сдвигается вправо на 8 и становится младшим, затем объединяется по XOR со значением таблицы - это становится новым значением CRC.
  4. В результате получено значение CRC.
  5. (Для CCITT X.25) Меняется старший и младший байт CRC местами и результат обращается (операция логического отрицания).
Безусловно, это не все существующие на данный момент алгоритмы CRC, но все остальные, так или иначе, являются модификациями табличного алгоритма. И преследуют следующие цели: Рассмотрев алгоритм CRC16 можно его модифицировать, как для полиномов большей степени, так и для полиномов меньшей степени.

Требования к CRC-полиномам.

Используемые в расчетах полиномы, данны в шестнадцатеричном формате. *- вообще-то это то же, что CRC-16 (BISYNCH), но использует обычный математический алгоритм нахождения CRC, а следовательно не нуждается в обращении. Неизвестно стандарта, в котором бы он использовался и не удивительно, что он дает худшие результаты.

Выбор полинома весьма непростое дело. Итак, из каких соображений находят полином. Передаваемое сообщение T=M'+CRC, где M' - исходное сообщение с добавленными 15-ю нулями в конец, а CRC - остаток от деления. Поскольку сложение также и вычитание - M' уменьшается до ближайшего кратного к делителю G. Если сообщение пришло с ошибками, т.е. T'=T+E, тогда приемник просто T' делит на G, получая (T+E)modG=E mod G, т.к. T mod G=0. Т.е. качество качество полинома определяется количеством E кратных ему.

    Эти полиномы были найдены такими, чтобы выполнялись условия:
  1. Обнаруживать ошибку в 1-бите. Для этого в полиноме должно быть больше 1-й единицы.
  2. Обнаруживать ошибки в 2-х различных битах для пакетов длины меньше, чем 215 бит. Надо подобрать G для которые не кратны числам типа 011, 0101, 01001, и.т.д.
  3. Обнаруживать ошибки в нечетном количестве бит. Для этого в G должно быть четное количество единичных бит.
  4. Обнаруживать идущие подряд ошибочные биты длины меньше 17. E=000…011…10…000. Вектор ошибок можно представить в виде: E=(100…00)*(111…1). Если в G младший бит единица, то левый множитель не кратен G, и если G длиннее правого множителя, то ошибка будет отловлена.
  5. Обнаруживать идущие подряд ошибочные биты длины 17, кроме 1/215.
  6. Обнаруживать все другие ошибки, кроме 1/216.
Сразу же следует отметить, что выполнение этих всех условий одновременно, задача нереальная, да к тому же и не нужная. Какая бы ошибка во время передачи не возникала - она локальна, точнее сказать она - скорее всего, локальна. От возникновения нескольких ошибок в результате помехи спасает уменьшение размеров передаваемых пакетов, так что в каждом пакете лишь одна ошибка (один ли несколько подряд идущих ошибочных битов). Поэтому при нахождении CRC-полиномов было сделано одно допущение - если возникла ошибка, то она локальна (ну разве что в теории CRC-полиномы могут обнаружить 2 однобитные ошибки и нечетное количество ошибок, но на практике все несколько хуже).

Концепция сдвига вносит некоторые ограничения. Поскольку степени x - это ненулевые элементы 216, если сдвиг начался с некоторого ненулевого состояния, то в это же состояние мы вернемся через 215 шагов и не раньше. Таким образом, возникает ограничение на размер сообщения - 4094 байта.

Исследование.

Было проведено исследование. Цель, которого состояла в том, чтобы узнать выполняются ли на самом деле условия наложенные на полиномы. Для этого использовалось 105 строк длины 5 байт, содержащих цифры от 0 до 9. Значение CRC для каждой такой строки было получено при помощи написанной мной программы, которую можно скачать здесь.

В этом исследованим понадобилось обрабатывать большие объемы данных с довольно хорошей скоростью. Наиболее подходящим для этого инструментом стал MS Visual FoxPro 6.0. Были созданы базы данных, которые вы можете скачать здесь . Названия файлов говорят, сами за себя, чего не скажешь о названиях столбцов. Итак:

Можно заметить, что кое-какие из этих столбоцов являются вспомогательными, поэтому в некоторых таблицах присутствуют не все эти столбцы.

    Просмотрев значения, на которых получены одинаковые CRC было обнаружено следующее:
  1. Xmodem (0x1021, инициализируется 0).
  2. CRC-16* (0x8005, инициализируется 0)
  3. X.25 (0x8408, инициализируется в 0xffff)
  4. CRC-16 (0xa001, инициализируется в 0)
Из данного исследования можно сделать определенные выводы. Больше всего удивляет расхождение с теорией по нечетному количеству ошибочных бит. С нечетным количеством различных бит совпадений было не меньше, а больше и это несмотря на то, что такого вообще быть не должно! Другое дело, что нечетное количество одиночных ошибочных бит почему-то пропуcкают, как X25 и X-modem, однако не пропускает полином IBM Все прекрасно ловят группы ошибочных бит, здесь нареканий никаких.

Полином CRC-16 был разработан для бисинхронной передачи данных довольно известной в узких кругах компанией IBM. И как они могли допустить совпадение CRC в 2 сообщениях с двумя различными битами? Но если присмотреться можно заметить, что если два бита есть и совпадает CRC, то они находятся на расстоянии в 1 бит. Всегда, по крайней мере? для 40 бит. Можно подумать, что для полинома CRC-16 служат кратными полиномы вроде (0..01010..0). Но таких полиномов в массе гораздо меньше, чем всех остальных. Вполне возможно, что CRC-16 может отловить все остальные, не отлавливая этот конкретный случай.

Так почему же используется всего 2 полинома? Дело в том, что при улучшении каких-то показателей по отдельным пунктам, ухудшаются остальные, а нахождение максимально лучшего полинома может стать своего рода "шаманством", недаром ведь полиномы называют "magic word", что значит магическое слово. Можно взглянуть на эти два применяемых в индустрии полинома и, казалось бы, что X.25 и Xmodem находят CRC гораздо лучше, но судить рано, ведь может быть при больших объемах все будет несколько иначе.

Приложение 1. Примеры.

При написании утилиты столкнулся с тем, что тяжело найти примеры с вычисленными для них CRC. Поэтому привожу данную таблицу.

CRC значения представлены в 16-ричном формате, значение после 0x и есть 16 бит значения CRC.
Строка Xmodem CRC-16* CRC-16 CCITT X.25
"abcdefgh" 0xabff 0x7d68 0x7429 0xa8a6
"T" 0x1a71 0x81fb 0xff01 0xd9e4
"THE,QUICK,BROWN,FOX,0123456789" 0x0498 0x38da 0xb96e 0x6e20
"TeSt" 0xaaae 0x7ce1 0xf83c 0xe8ab

Так же значения CRC совпадают с примерами из [1]

Приложение 2. Другие CRC-полиномы.

Приложение 3. Аббревиатуры.

Библиография.

  1. Craig Watson, "CRC info" [Online]
  2. Владимир Замятин, Алексей Эстрекин, "CRC-алгоритмы обнаружения ошибок" [Online]
  3. Assembler: практикум/ В. Юров - СПб.: Питер, 2002
  4. Stuart Baker, "Kermit and Xmodem -- A Comparison" [Online]
  5. CISCO Networking Academy Course [Online]
  6. Основы компьютерных сетей. : Пер. с англ. - М.: Издательский дом "Вильямс", 2002.
  7. Passwords.ru [Online]
  8. http://doc.lipetsk.ru/book.itep.ru/2/27/erdet_27.htm

Утилита для вычисления CRC.

Для целей, поставленных в данной курсовой работе я написал программку для вычисления различных стандартных 16-ти битных CRC.

Здесь вы ее можете скачать

О замеченных ошибках и опечатках просьба сообщить. Буду признателен.

2003 г., Екатеринбург.