Источник статьи - embedded.ifmo.ru
2. Необходимость использования сложных алгоритмов.
3. Основная идея CRC-алгоритмов.
5. Двоичная арифметика без переноса.
8. Особенности различных алгоритмов.
При передаче сообщений по низкокачественным каналам связи, возможно внесение искажений в эти сообщения, и поэтому необходимо предусмотреть методы, с помощью которых приемник сможет определить, были ли ошибки при передаче. При обнаружении ошибок, приемник может запросить повторную передачу сообщения. Для обнаружения применяются методы контрольных сумм. Передатчик подсчитывает некоторое значение, называемое контрольной суммой, являющееся функцией сообщения, и добавляет его в конец сообщения. Приемник использует ту же функцию для подсчета контрольной суммы, и сравнивает полученное значение с записанным в конце сообщения. Например, в качестве контрольной суммы можно взять сумму байт сообщения по модулю 256.
| Сообщение | 06 | 23 | 04 | |
| Сообщение с контрольной суммой | 06 | 23 | 04 | 33 |
| Сообщение после передачи | 06 | 27 | 04 | 33 |
В этом примере возникла ошибка во втором байте, и вместо числа 23 было передано число 27. Такую ошибку приемник может определить, вычислив контрольную сумму (37) и сравнив ее с полученной (33). Если бы сбой произошел в четвертом байте - в самой контрольной сумме, то верное сообщение было бы забраковано. Но главная опасность в том, что ошибка может произойти как в самом сообщении, так и в контрольной сумме, причем таким образом, что контрольная сумма от неверного сообщения совпадет с неверно переданной контрольной суммой. К сожалению, полностью избежать такой ситуации нельзя, можно лишь уменьшать вероятность ее возникновения, увеличивая длину контрольной суммы.
Существуют различные методы обнаружения ошибок, некоторые из которых преобразуют сообщение, дополняя его избыточной информацией. Методы CRC (Cyclic Redundancy Codes) относятся к методам, которые оставляют без изменения исходный текст сообщения, добавляя контрольную сумму в конец.
Рассмотрим предыдущий пример в ситуации, когда ошибка не может быть обнаружена:
| Сообщение | 06 | 23 | 04 | |
| Сообщение с контрольной суммой | 06 | 23 | 04 | 33 |
| Сообщение после передачи | 06 | 27 | 04 | 37 |
Вероятность возникновения такой ошибки - 1/256. Для улучшения детекции ошибок можно перейти от 8-битной контрольной суммы к 16-битной, т.е. суммируя по модулю 65536. Это, очевидно, уменьшит вероятность пропуска ошибки до 1/65536. Но в данном примере увеличение длины контрольной суммы не позволит отловить ошибку. Происходит это в результате того, что при использовании в качестве контрольной функции операции сложения, почти каждый байт исходного сообщения влияет только на один байт контрольной суммы, вне зависимости от ее длины. Поэтому, помимо длины контрольной суммы, обращают внимание на такой фактор как хаотичность: формула должна позволять любому байту сообщения изменять любое количество бит контрольной суммы.
Тем не менее в основе контрольной функции CRC-алгоритмов тоже лежит арифметическая операция - деление. Последовательность бит исходного сообщения рассматривается как огромное двоичное число, производится его целочисленное деление на фиксированное значение, и остаток берется в качестве контрольной суммы.
Схема деления методов CRC несколько отличается от обычной. В этом пункте приводятся некие идеи, позволяющие глубже понять сущность применяемых схем.
В связи с алгоритмами CRC часто можно встретить термин "полиномиальный". Говорят, что данный CRC алгоритм использует некий полином, и.т.п. И, вообще, говорят, что CRC алгоритмы используют полиномиальную арифметику. Что же это такое?
Делимое, делитель, частное и остаток рассматриваются не как положительные целые, а как полиномы с двоичными коэффициентами. То есть число записывается в виде двоичной строки, биты которой служат коэффициентами полинома. Например числу 23 (010111b) отвечает полином:
1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0, или проще:
x^4 + x^2 + x^1 + x^0
Мы можем осуществлять арифметические операции, понимая их как операции над полиномами. Например, умножим 13 (01101b) на 11 (01011b):
(x^3 + x^2 + x^0)(x^3 + x^1 + x^0) =
(x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0) =
x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0
Для того, чтобы получить в ответе 143, мы должны в качестве x взять 2 и привести коэффициенты к двоичным, перенеся 1 из 3*x^3 в старшие разряды. Получаем:
x^7 + x^3 + x^2 + x^1 + x^0 , что соответствует 010001111b = 143
Это обычная арифметика, просто основание системы счисления здесь выписано явно. Суть в том, что если мы не знаем х, то мы не можем производить переносы. Мы не знаем, что 3*x^3 это то x^4+x^3, потому что мы не знаем, что х = 2. В полиномиальной арифметике отношения между коэффициентами не определены, и коэффициенты при разных степенях полностью изолированы.
Можно придумать различные типы полиномиальной арифметики, определяя правила работы с коэффициентами. Для нас важна одна из схем - "полиномиальная арифметика по модулю 2", где все коэффициенты вычисляются по модулю 2, и отсутствуют переносы. Возвращаясь к предыдущему примеру:
(x^3 + x^2 + x^0)(x^3 + x^1 + x^0) =
(x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0) =
x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 =
x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0
В дальнейшем мы не будем упоминать полиномиальное представление, поскольку это может только усложнить изложение, и будем говорить об эквивалентной системе, назывемой "двоичная арифметика без переноса".
Как нетрудно заметить с отменой переноса исчезают и различия между сложением и вычитанием. Для каждой позиции есть 4 варианта:
То есть, фактически, сложение и вычитание в CRC-арифметике эквивалентны операции XOR, которая является обратной самой себе, и это очень удобно.
Объединение сложения и вычитания приводит также к исчезновению строгого отношения порядка. Действительно, то что 1010b больше чем 10b остается верным, но уже нет причин полагать, что 1010b больше чем 1001b. Поэтому вводится слабое отношение порядка: число X больше числа Y если номер позиции старшей 1-ы числа X больше номера позиции старшей 1-ы числа Y ( этот номер, отсчитываемый с 0, называется длиной числа ). Умножение и деление выполняются по обычным схемам с учетом новых операций сложения и вычитания.
1101
x 1011
----
1101
1101.
0000..
1101...
-------
1111111
Полезно ввести понятия кратности и делимости. Будем говорить, что число A кратно числу B ( или A делится на B) в смысле CRC-арифметики, если A можно получить складывая (XOR) результаты различных сдвигов ( влево) числа B. Например, 0111010110b кратно 011b:
0111010110
= .......11.
+ ....11....
+ ...11.....
.11.......
Однако 0111010111b нельзя составить из сдвигов 011b, поэтому говорят, что 0111010111b не делится на 011b.
Теперь, когда построена CRC-арифметика, мы можем интерпретировать вычисление CRC как взятие остатка от деления. В этом пункте мы обсудим некоторые детали и приведем пример.
Во первых, необходимо выбрать делитель. Его длина должна на один бит превосходить требуемую длину CRC. То есть, для получения CRC16 необходимо взять 17-битный делитель (в соответствии с данным выше определением его длина будет равна 16-и). Поскольку остаток должен быть меньше делителя (иначе можно выполнить деление еще раз), мы получим CRC требуемой длины.
Взяв произвольный делитель, мы придем к некоему CRC-алгоритму. Однако не все делители дают хорошие результаты, поэтому следует с осторожностью подходить к их выбору.
Перед делением сообщение дополняют W нулями ( где W - длина делителя)
| Исходное сообщение | 1101011011 |
| Делитель | 10011 |
| Дополненное сообщение | 11010110110000 |
1100001010 = Частное ( которое никого не интересует )
_______________
10011 ) 11010110110000 = (1101011011 + 0000)
10011,,.,,....
-----,,.,,....
10011,.,,....
10011,.,,....
-----,.,,....
00001.,,....
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
-----,....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = Остаток = CRC
CRC дописывается в конец, так что передаваемое сообщение будет таким: 11010110111110. Приемник может либо:
Далее мы будем использовать второй способ.
Итак операции которые необходимо произвести, при использовании CRC-алгоритмов:
Вопрос о правильном выборе делителя крайне нетривиален. В большинстве случаев лучше положиться на стандартные испытанные значения. В этом разделе не содержится исчерпывающих сведений по выбору делителя, его цель, скорее, в том, чтобы отбить желание выдумывать собственные делители.
Во-первых отметим, что передаваемое сообщение Т кратно делителю. Действительно, последние W бит сообщения T - остаток от деления сообщения M' на делитель. То есть Т=М'+CRC ( + означает сложение, а не добавление в конец ), а поскольку сложение одновременно является вычитанием, то оно "уменьшает" M' до ближайшего кратного G.
Теперь предположим, что сообщение пришло с ошибками. Это можно записать так T+E, где E - вектор ошибки. Приемник делит T+E на G. Поскольку T mod G = 0, то (T+E) mod G = E mod G. Поэтому способность метода отлавливать специфические ошибки будет определяться количеством E кратных G, поскольку такие помехи не могут быть обнаружены.
Перечислим некоторые типы ошибок, которые мы в первую очередь можем ожидать при передаче.
Приводим ниже наиболее известные делители ( в скобках номера единичных битов ):
16 бит: (16,12,5,0) [стандарт X25]
(16,15,2,0) ["CRC-16"]
32 бит: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]
Основная задача данного обзора - дать полную спецификацию CRC-16. Этот вариант - один из наиболее простых из класса CRC. Он полностью укладывается в теоретическую модель, описанную выше. Однако тема связанная с алгоритмами CRC этим далеко не исчерпывается. Например, реализация этих алгоритмов составляет отдельный вопрос, не менее, а, скорее, и более сложный чем теоретические основы. На первый взгляд с реализацией не может возникнуть никаких вопросов, поскольку операции XOR и SHL включены в систему команд любого процессора, что позволяет создать простую и эффективную реализацию на машинном языке. Однако в последнее время стали популярными сложные алгоритмы, далеко отстоящие от обычной чхемы деления. В первую очередь это так называемая табличная реализация и ее модификации, цель которых в переходе от цикла по всем битам к циклу по большим порциям данных - байтам, словам, и.т.д. Особенности различных реализаций привели к новым модификациям самого алгоритма. Появились такие понятия как начальное и конечное значения.
Начальное ( стартовое ) значение записывается в аккумулятор перед началом генерации CRC. Алгоритм CRC16 в инициализирует аккумулятор нулем, выполняя обыкновенную схему деления. Однако выбор нулевого стартового значения не самый удачный. Нетрудно видеть, что нули в начале сообщения являются "слепым пятном" алгоритма ( т. е. их число не повлияет на значение контрольной суммы ), и, в то же время, такие сообщения достаточно часто встречаются. Введение начального значения, которое с точки зрения схемы деления эквивалентно дописыванию в начало сообщения ненулевого значения позволяет обойти эту проблему.
Конечное значение просто складывается (XOR) с остатком деления.
Модификация CRC16/CITT использует стартовое значение FFFFh. Алгоритм CRC32 использует FFFFFFFFh в качестве начального и конечного значений.