При передачи данных по линиям связи, используется контрольная сумма, рассчитанная по некоторому алгоритму. Алгоритм часто сложный, конечно, он обоснован математически, но очень уж неудобен при дефиците ресурсов, например при программировании микроконтроллеров.

Чтобы упростить алгоритм, без потери качества, нужно немного «битовой магии», что интересная тема сама по себе.
Без контрольной суммы, передавать данные опасно, так как помехи присутствуют везде и всегда, весь вопрос только в их вероятности возникновения и вызываемых ими побочных эффектах. В зависимости от условий и выбирается алгоритм выявления ошибок и количество данных в контрольной сумме. Сложнее алгоритм, и больше контрольная сумма, меньше не распознанных ошибок.

Причина помех на физическом уровне, при передаче данных.

Вот пример самого типичного алгоритма для микроконтроллера, ставшего, фактически, промышленным стандартом с 1979 года.

Расчет контрольной суммы для протокола Modbus void crc_calculating(unsigned char puchMsg, unsigned short usDataLen) /*##Расчёт контрольной суммы##*/ { { unsigned char uchCRCHi = 0xFF ; /* Инициализация последнего байта CRC */ unsigned char uchCRCLo = 0xFF ; /* Инициализация первого байта CRC */ unsigned uIndex ; /* will index into CRC lookup table */ while (usDataLen—) /* pass through message buffer */ { uIndex = uchCRCHi ^ *puchMsg++ ; /* Расчёт CRC */ uchCRCLo = uchCRCLo ^ auchCRCHi ; uchCRCHi = auchCRCLo ; } return (uchCRCHi << 8 | uchCRCLo) ; /* Table of CRC values for high–order byte */ static unsigned char auchCRCHi = { 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40 }; /* Table of CRC values for low–order byte */ static char auchCRCLo = { 0x00, 0xC0, 0xC1, 0x01, 0xC3, 0x03, 0x02, 0xC2, 0xC6, 0x06, 0x07, 0xC7, 0x05, 0xC5, 0xC4, 0x04, 0xCC, 0x0C, 0x0D, 0xCD, 0x0F, 0xCF, 0xCE, 0x0E, 0x0A, 0xCA, 0xCB, 0x0B, 0xC9, 0x09, 0x08, 0xC8, 0xD8, 0x18, 0x19, 0xD9, 0x1B, 0xDB, 0xDA, 0x1A, 0x1E, 0xDE, 0xDF, 0x1F, 0xDD, 0x1D, 0x1C, 0xDC, 0x14, 0xD4, 0xD5, 0x15, 0xD7, 0x17, 0x16, 0xD6, 0xD2, 0x12, 0x13, 0xD3, 0x11, 0xD1, 0xD0, 0x10, 0xF0, 0x30, 0x31, 0xF1, 0x33, 0xF3, 0xF2, 0x32, 0x36, 0xF6, 0xF7, 0x37, 0xF5, 0x35, 0x34, 0xF4, 0x3C, 0xFC, 0xFD, 0x3D, 0xFF, 0x3F, 0x3E, 0xFE, 0xFA, 0x3A, 0x3B, 0xFB, 0x39, 0xF9, 0xF8, 0x38, 0x28, 0xE8, 0xE9, 0x29, 0xEB, 0x2B, 0x2A, 0xEA, 0xEE, 0x2E, 0x2F, 0xEF, 0x2D, 0xED, 0xEC, 0x2C, 0xE4, 0x24, 0x25, 0xE5, 0x27, 0xE7, 0xE6, 0x26, 0x22, 0xE2, 0xE3, 0x23, 0xE1, 0x21, 0x20, 0xE0, 0xA0, 0x60, 0x61, 0xA1, 0x63, 0xA3, 0xA2, 0x62, 0x66, 0xA6, 0xA7, 0x67, 0xA5, 0x65, 0x64, 0xA4, 0x6C, 0xAC, 0xAD, 0x6D, 0xAF, 0x6F, 0x6E, 0xAE, 0xAA, 0x6A, 0x6B, 0xAB, 0x69, 0xA9, 0xA8, 0x68, 0x78, 0xB8, 0xB9, 0x79, 0xBB, 0x7B, 0x7A, 0xBA, 0xBE, 0x7E, 0x7F, 0xBF, 0x7D, 0xBD, 0xBC, 0x7C, 0xB4, 0x74, 0x75, 0xB5, 0x77, 0xB7, 0xB6, 0x76, 0x72, 0xB2, 0xB3, 0x73, 0xB1, 0x71, 0x70, 0xB0, 0x50, 0x90, 0x91, 0x51, 0x93, 0x53, 0x52, 0x92, 0x96, 0x56, 0x57, 0x97, 0x55, 0x95, 0x94, 0x54, 0x9C, 0x5C, 0x5D, 0x9D, 0x5F, 0x9F, 0x9E, 0x5E, 0x5A, 0x9A, 0x9B, 0x5B, 0x99, 0x59, 0x58, 0x98, 0x88, 0x48, 0x49, 0x89, 0x4B, 0x8B, 0x8A, 0x4A, 0x4E, 0x8E, 0x8F, 0x4F, 0x8D, 0x4D, 0x4C, 0x8C, 0x44, 0x84, 0x85, 0x45, 0x87, 0x47, 0x46, 0x86, 0x82, 0x42, 0x43, 0x83, 0x41, 0x81, 0x80, 0x40 }; } }

Не слабый такой код, есть вариант без таблицы, но более медленный (необходима побитовая обработка данных), в любом случае способный вынести мозг как программисту, так и микроконтроллеру. Не во всякий микроконтроллер алгоритм с таблицей влезет вообще.
Давайте разберем алгоритмы, которые вообще могут подтвердить целостность данных невысокой ценой.

Бит четности (1-битная контрольная сумма)

На первом месте простой бит четности. При необходимости формируется аппаратно, принцип простейший, и подробно расписан в википедии. Недостаток только один, пропускает двойные ошибки (и вообще четное число ошибок), когда четность всех бит не меняется. Можно использовать для сбора статистики о наличии ошибок в потоке передаваемых данных, но целостность данных не гарантирует, хотя и снижает вероятность пропущенной ошибки на 50% (зависит, конечно, от типа помех на линии, в данном случае подразумевается что число четных и нечетных сбоев равновероятно).
Для включения бита четности, часто и код никакой не нужен, просто указываем что UART должен задействовать бит четности. Типично, просто указываем:
включение бита четности на микроконтроллере void setup(){ Serial.begin(9600,SERIAL_8N1); // по умолчанию, бит четности выключен; Serial1.begin(38400,SERIAL_8E1); // бит четности включен Serial.println(«Hello Computer»); Serial1.println(«Hello Serial 1»); }
Часто разработчики забывают даже, что UART имеет на борту возможность проверки бита четности. Кроме целостности передаваемых данных, это позволяет избежать устойчивого срыва синхронизации (например при передаче данных по радиоканалу), когда полезные данные могу случайно имитировать старт и стоп биты, а вместо данных на выходе буфера старт и стоп биты в случайном порядке.

8-битная контрольная сумма

Если контроля четности мало (а этого обычно мало), добавляется дополнительная контрольная сумма. Рассчитать контрольную сумму, можно как сумму ранее переданных байт, просто и логично
Естественно биты переполнения не учитываем, результат укладываем в выделенные под контрольную сумму 8 бит. Можно пропустить ошибку, если при случайном сбое один байт увеличится на некоторое значение, а другой байт уменьшится на то же значение. Контрольная сумма не изменится. Проведем эксперимент по передаче данных. Исходные данные такие:

1. Блок данных 8 байт.
2. Заполненность псевдослучайными данными Random($FF+1)
3. Случайным образом меняем 1 бит в блоке данных операцией XOR со специально подготовленным байтом, у которого один единичный бит на случайной позиции.
4. Повторяем предыдущий пункт 10 раз, при этом может получится от 0 до 10 сбойных бит (2 ошибки могут накладываться друг на друга восстанавливая данные), вариант с 0 сбойных бит игнорируем в дальнейшем как бесполезный для нас.

Передаем виртуальную телеграмму N раз. Идеальная контрольная сумма выявит ошибку по количеству доступной ей информации о сообщении, больше информации, выше вероятность выявления сбойной телеграммы. Вероятность пропустить ошибку, для 1 бита контрольной суммы:
.
Для 8 бит:
,
на 256 отправленных телеграмм с ошибкой, одна пройдет проверку контрольной суммы. Смотрим статистику от виртуальной передачи данных, с помощью простой тестовой программы:
Статистика1: 144 (тут и далее — вероятность прохождения ошибки)
1: 143
1: 144
1: 145
1: 144
1: 142
1: 143
1: 143
1: 142
1: 140
Общее число ошибок 69892 из 10 млн. итераций, или 1: 143.078
Или условный КПД=55%, от возможностей «идеальной» контрольной суммы. Такова плата за простоту алгоритма и скорость обработки данных. В целом, для многих применений, алгоритм работоспособен. Используется одна операция сложения и одна переменная 8-битовая. Нет возможности не корректной реализации. Поэтому алгоритм и применяется в контроллерах ADAMS, ICP, в составе протокола DCON (там дополнительно может быть включен бит четности, символы только ASCI, что так же способствует повышению надежности передачи данных и итоговая надежность несколько выше, так как часть ошибок выявляется по другим, дополнительным признакам, не связанных с контрольной суммой).
Не смотря на вероятность прохождения ошибки 1:143, вероятность обнаружения ошибки лучше, чем 1:256 невозможна теоретически. Потери в качестве работы есть, но не всегда это существенно. Если нужна надежность выше, нужно использовать контрольную сумму с большим числом бит. Или, иначе говоря, простая контрольная сумма, недостаточно эффективно использует примерно 0.75 бита из 8 имеющихся бит информации в контрольной сумме.
Для сравнения применим, вместо суммы, побитовое сложение XOR. Стало существенно хуже, вероятность обнаружения ошибки 1:67 или 26% от теоретического предела. Упрощенно, это можно объяснить тем, что XOR меняет при возникновении ошибке еще меньше бит в контрольной сумме, ниже отклик на единичный битовый сбой, и повторной ошибке более вероятно вернуть контрольную сумму в исходное состояние.
Так же можно утверждать, что контрольная сумма по XOR представляет из себя 8 независимых контрольных сумм из 1 бита. Вероятность того, что ошибка придется на один из 8 бит равна 1:8, вероятность двойного сбоя 1:64, что мы и наблюдаем, теоретическая величина совпала с экспериментальными данными.
Нам же нужен такой алгоритм, чтобы заменял при единичной ошибке максимальное количество бит в контрольной сумме. Но мы, в общей сложности, ограниченны сложностью алгоритма, и ресурсами в нашем распоряжении. Не во всех микроконтроллерах есть аппаратный блок расчета CRC. Но, практически везде, есть блок умножения. Рассчитаем контрольную сумму как произведение последовательности байт, на некоторую «магическую» константу:
CRC=CRC + byte*211
Константа должна быть простой, и быть достаточно большой, для изменения большего числа бит после каждой операции, 211 вполне подходит, проверяем:
Статистика1: 185
1: 186
1: 185
1: 185
1: 193
1: 188
1: 187
1: 194
1: 190
1: 200
Всего 72% от теоретического предела, небольшое улучшение перед простой суммой. Алгоритм в таком виде не имеет смысла. В данном случае теряется важная информация из отбрасываемых старших 8..16 бит, а их необходимо учитывать. Проще всего, смешать функцией XOR с младшими битами 1..8. Приходим к еще более интенсивной модификации контрольной суммы, желательно с минимальным затратами ресурсов. Добавляем фокус из криптографических алгоритмов

CRC=CRC + byte*211 CRC= CRC XOR (CRC SHR 8); // «миксер» битовый, далее его применяем везде CRC=CRC AND $FF; //или просто возвращаем результат как 8, а не 16 бит

• Промежуточная CRC для первого действия 16-битная (после вычислений обрезается до 8 бит) и в дальнейшем работаем как с 8-битной, если у нас 8-битный микроконтроллер это ускорит обработку данных.
• Возвращаем старшие биты и перемешиваем с младшими.

Проверяем:
Статистика1: 237
1: 234
1: 241
1: 234
1: 227
1: 238
1: 235
1: 233
1: 231
1: 236
Результат 91% от теоретического предела. Вполне годится для применения.
Если в микроконтроллере нет блока умножения, можно имитировать умножение операций сложения, смещения и XOR. Суть процесса такая же, модифицированный ошибкой бит, равномерно «распределяется» по остальным битам контрольной суммы.
CRC := (CRC shl 3) + byte; CRC := (CRC shl 3) + byte; CRC:=(CRC XOR (CRC SHR 8)) ; // как и в предыдущем алгоритме
Результат:
Статистика1: 255
1: 257
1: 255
1: 255
1: 254
1: 255
1: 250
1: 254
1: 256
1: 254
На удивление хороший результат. Среднее значение 254,5 или 99% от теоретического предела, операций немного больше, но все они простые и не используется умножение.
Если для внутреннего хранения промежуточных значений контрольной суммы отдать 16 бит переменную (но передавать по линии связи будем только младшие 8 бит), что не проблема даже для самого слабого микроконтроллера, получим некоторое улучшение работы алгоритма. В целом экономить 8 бит нет особого смысла, и 8-битовая промежуточная переменная использовалась ранее просто для упрощения понимания работы алгоритма.
Статистика1: 260
1: 250
1: 252
1: 258
1: 261
1: 255
1: 254
1: 261
1: 264
1: 262
Что соответствует 100.6% от теоретического предела, вполне хороший результат для такого простого алгоритма из одной строчки:
CRC:=CRC + byte*44111; // все переменные 16-битные
Используется полноценное 16-битное умножение. Опять же не обошлось без магического числа 44111 (выбрано из общих соображений без перебора всего подмножества чисел). Более точно, константу имеет смысл подбирать, только определившись с предполагаемым типом ошибок в линии передачи данных.
Столь высокий результат объясняется тем, что 2 цикла умножения подряд, полностью перемешивают биты, что нам и требовалось. Исключением, похоже, является последний байт телеграммы, особенно его старшие биты, они не полностью замешиваются в контрольную сумму, но и вероятность того, что ошибка придется на них невелика, примерно 4%. Эта особенность практически ни как не проявляется статистически, по крайней мере на моем наборе тестовых данных и ошибке ограниченной 10 сбойными битами. Для исключения этой особенности можно делать N+1 итераций, добавив виртуальный байт в дополнение к имеющимся в тестовом блоке данных (но это усложнение алгоритма).
Вариант без умножения с аналогичным результатом. Переменная CRC 16-битная, данные 8-битные, результат работы алгоритма — младшие 8 бит найденной контрольной суммы:
CRC := (CRC shl 2) + CRC + byte; CRC := (CRC shl 2) + CRC + byte; CRC:=(CRC XOR (CRC SHR 8));
Результат 100.6% от теоретического предела.
Вариант без умножения более простой, оставлен самый минимум функций, всего 3 математических операции:
CRC:=byte + CRC; CRC:=CRC xor (CRC shr 2);
Результат 86% от теоретического предела.
В этом случае потери старших бит нет, они возвращаются в младшую часть переменной через функцию XOR (битовый миксер).
Небольшое улучшение в некоторых случаях дает так же:

• Двойной проход по обрабатываемым данным. Но ценой усложнения алгоритма (внешний цикл нужно указать), ценой удвоения времени обработки данных.
• Обработка дополнительного, виртуального байта в конце обрабатываемых данных, усложнения алгоритма и времени работы алгоритма практически нет.
• Использование переменной для хранения контрольной суммы большей по разрядности, чем итоговая контрольная сумма и перемешивание младших бит со старшими.

Результат работы рассмотренных алгоритмов, от простых и слабых, к сложным и качественным:

16-битная контрольная сумма

Далее, предположим что нам мало 8 бит для формирования контрольной суммы.

Следующий вариант 16 бит, и теоретическая вероятность ошибки переданных данных 1:65536, что намного лучше. Надежность растет по экспоненте. Но, как побочный эффект, растет количество вспомогательных данных, на примере нашей телеграммы, к 8 байтам полезной информации добавляется 2 байта контрольной суммы.
Простые алгоритмы суммы и XOR, применительно к 16-битной и последующим CRC не рассматриваем вообще, они практически не улучают качество работы, по сравнению с 8-битным вариантов.
Модифицируем алгоритм для обработки контрольной суммы разрядностью 16 бит, надо отметить, что тут так же есть магическое число 8 и 44111, значительное и необоснованное их изменение ухудшает работу алгоритма в разы.
CRC:=CRC + byte16*44111; //все данные 16-битные CRC:=CRC XOR (CRC SHR 8);
Результат:
Статистика1: 43478
1: 76923
1: 83333
1: 50000
1: 83333
1: 100000
1: 90909
1: 47619
1: 50000
1: 90909
Что соответствует 109% от теоретического предела. Присутствует ошибка измерений, но это простительно для 10 млн. итераций. Так же сказывается алгоритм создания, и вообще тип ошибок. Для более точного анализа, в любом случае нужно подстраивать условия под ошибки в конкретной линии передачи данных.
Дополнительно отмечу, что можно использовать 32-битные промежуточные переменные для накопления результата, а итоговую контрольную сумму использовать как младшие 16 бит. Во многих случаях, при любой разрядности контрольной суммы, так несколько улучшается качество работы алгоритма.

32-битная контрольная сумма

Перейдем к варианту 32-битной контрольной суммы. Появляется проблема со временем отводимым для анализа статистических данных, так как число переданных телеграмм уже сравнимо с 2^32. Алгоритм такой же, магические числа меняются в сторону увеличения
CRC:=CRC+byte32*$990C9AB5; CRC:=CRC XOR (CRC SHR 16);
За 10 млн. итераций ошибка не обнаружена. Чтобы ускорить сбор статистики обрезал CRC до 24 бит:
CRC = CRC AND $FFFFFF;
Результат, из 10 млн. итераций ошибка обнаружена 3 раза
Статистика1: 1000000
1: no
1: no
1: no
1: 1000000
1: no
1: 1000000
1: no

1: no
1: no
Вполне хороший результат и в целом близок к теоретическому пределу для 24 бит контрольной суммы (1:16777216). Тут надо отметить что функция контроля целостности данных равномерно распределена по всем битам CRC, и вполне возможно их отбрасывание с любой стороны, если есть ограничение на размер передаваемой CRC.
Для полноценных 32 бит, достаточно долго ждать результата, ошибок просто нет, за приемлемое время ожидания.
Вариант без умножения:
CRC := (CRC shl 5) + CRC + byte; CRC := (CRC shl 5) + CRC; CRC:=CRC xor (CRC shr 16);
Сбоя для полноценной контрольной суммы дождаться не получилось. Контрольная сумма урезанная до 24 бит показывает примерно такие же результаты, 8 ошибок на 100 млн. итераций. Промежуточная переменная CRC 64-битная.

64-битная контрольная сумма

Ну и напоследок 64-битная контрольная сумма, максимальная контрольная сумма, которая имеет смысл при передачи данных на нижнем уровне:
CRC:=CRC+byte64*$5FB7D03C81AE5243; CRC:=CRC XOR (CRC SHR 8); // магическое число 1..20
Дождаться ошибки передачи данных, до конца существования вселенной, наверное не получится 🙂

Метод аналогичный тому, какой применили для CRC32 показал аналогичные результаты. Больше бит оставляем, выше надежность в полном соответствии с теоретическим пределом. Проверял на младших 20 и 24 битах, этого кажется вполне достаточным, для оценки качества работы алгоритма.
Так же можно применить для 128-битных чисел (и еще больших), главное подобрать корректно 128-битные магические константы. Но это уже явно не для микроконтроллеров, такие числа и компилятор не поддерживает.

В целом метод умножения похож на генерацию псевдослучайной последовательности, только с учетом полезных данных участвующих в процессе.
Рекомендую к использованию в микроконтроллерах, или для проверки целостности любых переданных данных. Вполне рабочий метод, уже как есть, не смотря на простоту алгоритма.
Мой проект по исследованию CRC на гитхаб.
Далее интересно было бы оптимизировать алгоритм на более реальных данных (не псевдослучайные числа по стандартному алгоритму), подобрать более подходящие магические числа под ряд задач и начальных условий, думаю можно еще выиграть доли процента по качеству работы алгоритма. Оптимизировать алгоритм по скорости, читаемости кода (простоте алгоритма), качеству работы. В идеале получить и протестировать образцы кода для всех типов микроконтроллеров, для этого как-раз и нужны примеры с использованием умножения 8, 16, 32 битных данных, и без умножения вообще.

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

Мир сейчас полностью зависит от хранения и передачи цифровых данных. Самолеты, фондовые рынки, системы безопасности, скороварки – современная жизнь быстро обрушится в хаос, если мы не сможем обеспечить точность в постоянно текущем и необъятно огромном потоке из единиц и нулей.

Есть две основные задачи, связанные с поддержанием целостности наших цифровых данных. Первое – это избегать в первую очередь ошибок; эта цель включает в себя множество инженерных практик, которые способствуют надежной передаче и приему цифровых данных. Но, несмотря на все наши усилия, ошибки возможны, и это приводит нас ко второй задаче: обнаружение ошибок. Если система может обнаруживать ошибки, она также может компенсировать эти ошибки, просто отбросив сомнительные данные или запросив повторную передачу.

Выбор метода обнаружения ошибок

Если вы знакомы с битом четности, который иногда используется в связи через UART, вы что-то знаете об обнаружении ошибок. Но бит четности является довольно жалким механизмом обнаружения ошибок; на самом деле, насколько я могу судить, большинство методов обнаружения ошибок более или менее жалки по сравнению с циклическим избыточным кодом (CRC, cyclic redundancy check), который явно стал доминирующим подходом – некоторые крупные имена в цифровой связи (включая CAN, USB и Ethernet) используют CRC как часть своего протокола передачи данных.

Структура пакета данных USB

Эффективный, но не простой

Эта короткая статья не является местом для изучения подробностей вычислений и производительности CRC. Суть в том, что двоичный «многочлен» применяется к потоку данных таким образом, чтобы генерировать контрольную сумму, которая, скорее всего, изменится, если один или несколько битов сообщении были изменены.

Этот «многочлен» представляет собой просто математически удобный способ обращения к определенной последовательности битов. Например:

\(x^{16}+x^{12}+x^5+1=0001\ 0000\ 0010\ 0001\)

Это широко используемый полином «CCITT». Это полином 16-го порядка, что означает, что соответствующее двоичное число имеет ширину 16 бит, и что итоговая контрольная сумма CRC будет иметь ширину 16 бит. (Обратите внимание, что коэффициент для члена высшего порядка считается равным 1 и опускается в двоичной версии.) Члены, которые не отображаются в математическом выражении, имеют в качестве коэффициента двоичный 0.

Обнаружение ошибок проще и эффективнее с аппаратным CRC модулем; это схема из технического описания EFM8LB1 показывает работу CRC периферии в микроконтроллере EFM8 Laser Bee

Два CRC, не один

Создание CRC только для исходного сообщения вам не поможет. Ключом к реализации обнаружения ошибок CRC является обеспечение того, чтобы и передатчик, и приемник генерировали контрольную сумму одним и тем же способом.

Передатчик генерирует контрольную сумму для передаваемых данных и включает ее в исходное сообщение, а приемник генерирует собственную контрольную сумму с использованием полученных данных. Если сообщение приемника не совпадает с сообщением передатчика, весьма вероятно, что контрольные суммы будут отличаться; таким образом, приемник считает данные ошибочными, если контрольные суммы CRC не совпадают.

Куда двигаться дальше

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

В следующих статьях мы рассмотрим подробности исправления ошибок на базе CRC.

Теги

CRC (циклический избыточный код)Исправление ошибокКонтрольная суммаОбнаружение ошибокЦифровая связь Сохранить или поделиться

№ 2(26) 2010

А. Н. Мальчуков, А. Н. Осокин

Быстрое вычисление контрольной суммы CRC: таблица против матрицы

Контрольная сумма — это некоторое значение, вычисленное для последовательности байт данных с помощью определенного алгоритма, которое используется на приемной стороне для подтверждения корректности полученных данных. В статье рассматривается быстродействующий алгоритм вычисления контрольной суммы, легко реализуемый на комбинационных схемах.

Введение

Первоначально контрольная сумма использовалась в системах с наличием обратной связи (переспроса) для обнаружения ошибок, возникающих в зашум-ленных каналах связи. Позднее, с развитием криптографических хеш-функций (алгоритмов хеширования), контрольные суммы стали использоваться для подтверждения целостности и подлинности данных. Обычно контрольная сумма посылается Учитывается) в конце сообщения:

<блокданных> контрольная суммах В настоящее время существует множество алгоритмов получения контрольной суммы: сложение байтов, CRC (англ. cyclic redundancy check — избыточный циклический код), MD5, SHA и т.д. CRC традиционно используется в проводных и беспроводных протоколах передачи данных (Ethernet, Bluetooth, ZigBee, CAN, Fibre Channel и т.д.) для контроля целостности управляющих фрагментов или кадров данных. Далее речь пойдет об алгоритмах вычисления контрольных сумм CRC.

«Стандартный» алгоритм

Под «стандартным» алгоритмом подразумевается алгоритм, вычисляющий контрольную сумму CRC побитно, т. е. в каждом такте (итерации) данные последовательно продвигаются в некотором регистре на один

бит, и в итоге в этом регистре получают контрольную сумму. Этот алгоритм широко известен по его аппаратной реализации на регистрах с обратной связью (рис. 1).

На рис. 1 схематично показана работа простого алгоритма. Для СРС8 его можно описать следующим образом.

Начало. Регистр (массив) 8 бит содержит нулевое значение, данные поступают в регистр через его младший разряд к старшим, начиная со старшего разряда данных последовательным сдвигом.

Шаг 1. Сдвигаем данные в регистре на один бит от младших к старшему разряду, в младший разряд регистра заносится бит из потока данных.

Шаг 2. Если выдвинутый бит из 8 разряда регистра равен 0, переходим на шаг 4.

Шаг 3. Складываем по модулю два выдвинутый бит с разрядами регистра 1, 2, 3 и результат записываем в соответствующие ячейки регистра, т.е. фактически инвертируем содержимое 1,2иЗ разрядов регистра.

Шаг 4. Если еще не все биты поступили в регистр из потока данных, переходим на шаг 1.

Конец. В регистре содержится контрольная сумма СРС8.

При вычислении контрольной суммы СРС8 для последовательности битов данных в конец добавляют 8 нулей. При проверке контрольной суммы через регистр пропускают последовательность битов данных вместе с контрольной суммой в конце. В итоге

№ 2(26) 2010

Рис. 1. Схематичное представление работы стандартного алгоритма на примере CRC8 (.х8 + х2 + х+ 1); стрелка со знаком © обозначает сложение по модулю два выдвинутого бита с разрядом регистра, на который указывает стрелка и запись результата в эту же ячейку регистра

проверки нулевое значение регистра соответствует безошибочному приему. Если регистр содержит ненулевое значение, то произошло искажение данных в информационном блоке и/или в контрольной сумме.

Данный алгоритм вычисления контрольной суммы CRC8 требует выполнения множества итераций, что существенно замедляет процесс вычисления. Для ускорения вычисления контрольной суммы CRC в предложен табличный алгоритм, в котором данные сдвигаются не по 1 биту за итерацию, апо8 бит (байту).

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

При последовательном сдвиге данных по байту (вместо одного бита) за итерацию (такт) необходимо знать изменения, которые должны были бы произойти в течение 8 сдвигов при обычном алгоритме (для CRC8 — инвертирование трех младших разрядов в случае единичного значения выдвинутого разряда), поэтому эти изменения нужно предварительно вычислить и занести в таблицу (которая потребует соответствующего своим размерам объема памяти запоминающего устройства при программной или аппаратной реализации). Адресом в такой таблице будет служить содержимое регистра до сдвига (выталкиваемый байт при сдвиге). Далее содержимое таблицы складывается по модулю два со значением регистра, в котором содержится байт данных после сдвига (рис. 2).

Рис. 2. Схематичное представление работы

табличного алгоритма на примере СЯС8 (х8+х2+х+1)

Табличный алгоритм вычисления контрольной суммы СРС8 можно описать следующим образом.

Начало. Регистр (массив) 8 бит содержит нулевое значение, данные поступают в регистр, начиная со старшего разряда данных последовательным сдвигом побайтно.

Шаг 1. Сдвигаем данные в регистре на один байт от младших к старшему разряду, в регистр заносится новый байт из потока данных.

Шаг 2. Выдвинутый из регистра байт задает адрес в предварительно подготовленной таблице.

Шаг 3. Выбранный по заданному адресу из таблицы байт складывается по модулю два с регистром.

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Шаг 4. Если еще не все байты прошли через регистр из потока данных, переходим на шаг 1.

Конец. В регистре содержится контрольная сумма СРС8.

Процесс вычисления и проверки контрольной суммы не отличается от обычного алгоритма. В связи с тем, что в табличном алгоритме вместо побитового сдвига каждую итерацию данные сдвигаются на байт, длина потока данных должна быть кратной 8 битам, т.е. байту.

Однако, вместо использования таблицы из 256 байтов (для СРС8) можно обойтись матрицей в 8×8 бит (8 байт), которая легко реализуется на комбинационных схемах.

№ 2(26) 2010

Матричный алгоритм

Процесс вычисления и проверки контрольной суммы CRC8 в матричном алгоритме осуществляется так же, как и в табличном, только вместо таблицы используется операция умножения вектора (выдвинутый байт) на матрицу (рис. 3). Матрица была специальным образом сформирована для кодового слова длиной 16 битов и образующего полинома х8+х2+х+1 .

Также необходимо отметить, что в результате умножения вектора на матрицу получаем значение, идентичное содержимому таблицы по соответствующему адресу в табличном алгоритме. На нашем примере: 11000111 © 11100000 © 00011100 © 00000111 = 00111100.

Для удобства восприятия работа алгоритмов вычисления контрольной суммы была рассмотрена на примере CRC8, однако, наибольшее распространение получила контрольная сумма CRC32. Она используется для обнаружения ошибок, подтверждения целостности и подлинности данных в сетевом протоколе передачи данных IEEE 802.3; в стандартах цифрового кодирования видео и аудио сигналов MPEG-2; в формате хранения графической информации PNG; в алгоритмах сжатия данных RAR, ZIP

Рис. 3. Схематичное представление работы матричного алгоритма на примере СЯС8 (х8+х2+х+~\)

и др.; в устройствах хранения данных с интерфейсом SATA, UDMA; в стандартах обеспечения совместимости Unix-подобных ОС POSIX; в протоколе управления системами хранения данных, серверами и клиентами ¡SCSI; в модели обмена аэронавигационной информации AIXM и т.д.

Однобайтовый сдвиг

Выше был представлен быстродействующий матричный алгоритм вычисления контрольной суммы CRC8 при обработке одного байта за итерацию, в котором вместо одного бита за итерацию через результирующий регистр проходит 8 бит данных. Для CRC32 алгоритм будет тем же, за исключением матрицы, с помощью которой производится вычисление контрольной суммы (рис. 4).

При программной реализации матричного алгоритма вычисления контрольной суммы CRC32 для хранения матрицы потребуется объем запоминающего устройства равный 32 байтам, в случае реализации алгоритма, предложенного в работе , потребуется 1024 байта.

При аппаратной реализации матричного алгоритма вычисления контрольной суммы CRC32 запоминающего устройства не требуется, вместо этого на комбинационных схемах воспроизводится умножение вектора на матрицу по модулю два (рис. 5).

На рис. 5 обозначено ВБХ — бит X выдвинутого байта; РХХ — бит XX из регистра после сдвига; 3-РХХ — данный бит будет записан на место XX бита в регистр по завершению итерации.

Стоит отметить, что в устройствах хранения данных широко применяется практика работы с блоками данных, равных не одному байту, а 1024 байтам, 4096 байтам и даже 1 048576 байтам (1 Мб). Контрольная сумма вычисляется для целого блока. В та-

Ьаит после сдвига

Данные

матрица

№ 2(26) 2010

ких случаях блоки данных являются кратными 2, 4, 8 байтам, что в свою очередь позволяет быстрее вычислить контрольную сумму за счет обработки не одного байта за итерацию, а 2, 4 или 8 байтов. Рассмотрим пример обработки 4 байтов за итерацию.

Четырехбайтовый сдвиг

В случае вычисления контрольной суммы СРС32 сразу для 4 байтов данных за итерацию матрица будет иметь большее количество строк — 32 вместо 8 (рис. 3).

В этом случае при программной реализации матричного алгоритма вычисления контрольной суммы СРС32 для хранения матрицы потребуется объем запоминающего, устройства равный 128 байтам, а в случае реализации алгоритма, предложенного в работе , потребуется 16 Гб.

Также можно заметить, что на рис. 4 и 6 первые 8 строк в матрице совпадают. Это особенность алгоритма матричного деления — для одного образующего полинома матрица существует одна, количество строк зависит от длины блока данных, поэтому на рис. 4 представлена укороченная версия матрицы с рис. 6.

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

На рис. 7 показан пример реализации блока умножения вектора на матрицу по модулю два для данного случая. Обозначения те же, что и на рис. 5.

Заключение

Предложенный матричный алгоритм вычисления контрольной суммы CRC позволяет обходиться без использования запоминающего устройства при аппаратной реализации. А при программной реализации (например, при реализации на DSP) необходимый объем памяти для хранения матрицы значительно меньше, чем требуется для хранения таблицы при использовании табличного алгоритма. Например, для CRC8

Рис. 5. Пример аппаратной реализации блока умножения вектора на матрицу по модулю два

№ 2(26) 2010

при вычислении по одному байту за итерацию матричному алгоритму потребуется 8 байтов, табличному — 256 байтов; при вычислении по два байта за итерацию матричному алгоритму потребуется 16 байтов, табличному — 64 Кб; при вычислении по 4 байта за итерацию матричному — 32 байта, табличному — 4 Гб; для СРС32 при вычислении по одному байту за итерацию матричному алгоритму потребуется 32 байта, табличному — 1024 байта (1 Кб); при вычислении по два байта за итерацию матричному алгоритму потребуется 64 байта, а табличному —

256 Кбайтов; при вычислении по 4 байта за итерацию матричному — 128 байтов, а табличному — 16 Гб.

Предлагаемый матричный алгоритм быстрого вычисления контрольной суммы CRC актуален при использовании более длиной контрольной суммы (CRC8, 16, 32, 64, 128). Особенно он полезен в случаях, когда блоки данных кратны 2, 3, 4 байтам и т.д., что позволяет быстрее вычислять контрольную сумму CRC.

Ускорение за счет использования сдвига на большее количество битов влечет за со-

Рис. 6. Схематичное представление работы матричного алгоритма вычисления СЯС32 при сдвиге по 4 байта за итерацию

№ 2(26) 2010

бой серьезный рост объема требуемой памяти запоминающего устройства для алгоритма из работы и лишь небольшой рост объема требуемой памяти (для хранения матрицы) при программной реализации или незначительное усложнение комбинационной схемы при аппаратной реализации для предлагаемого матричного алгоритма.

Совместное использование ускоренного метода вычисления контрольных сумм CRC с быстродействующими кодеками помехоустойчивых полиномиальных кодов позволит обнаруживать ошибки большей кратности, которые кодек помехоустойчивого полиномиального кода не способен исправлять.

Также возможно использование матричного алгоритма в микроконтроллерах жестких дисков для обеспечения проверки на целостность больших блоков данных с помощью новых, более длинных контрольных сумм CRC, например, CRC256 или CRC512.

Работа выполнена на кафедре вычислительной техники института «Кибернетический центр» Томского политехнического университета и поддержана грантом «У. M. Н. И. К» Фонда содействия развитию малых форм предприятий в научно-технической сфере.

Описок литературы

Р32

=1

ВБ6

ВБ9

ВБ10

ВБ12

ВБ16

ВБ24

ВБ25

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

ВБ26

ВБ28

ВБ29

ВБЗО

ВБ31

ВБ32

Р31

ВБ5

ВБ8

ВБ9

ВБ11

ВБ15

ВБ23

ВБ24

ВБ25

ВБ27

ВБ28

ВБ29

ВБЗО

ВБ31