Целостность данных, CRC

Контрольная сумма

И возвращать байт суммы. Создадим и заполним структуру данными и прогоним через эту функцию. В последний байт структуры запишем контрольную сумму:

Теперь можно передать структуру приёмнику! Пример “синтетический”, так как кому и каким способом передавать данные мы не рассматриваем. Хотя, можно отправить по Serial, например с одной Ардуины на другую, как в уроке по парсингу Serial:

Далее на приёмнике примем данные:

Теперь нужно убедиться в том, что данные верны. Для этого прогоним их через ту же суммирующую функцию, но без учёта последнего байта, так как он сам является суммой:

Если значение совпадёт с переданным rxData.hash – данные верны! Дополним предыдущий код:

И по условию можем выполнять какие-то действия, например применить полученные данные к устройству или проигнорировать их. Достоинства контрольной суммы:

Недостатки контрольной суммы:

Низкая надёжность заключается в том, что контрольная сумма не учитывает порядок байтов в посылке, то есть не является уникальным “отпечатком” всех данных. Например, данные повредились так, что из вот такого пакета

Превратились в такой:

CRC (cyclic redundancy code) – циклический избыточный код. Алгоритм тоже выдаёт некое “число” при прохождении через него потока байтов, но учитывает все предыдущие данные при расчёте. Как работает данный алгоритм мы рассматривать не будем, об этом можно почитать на Википедии или здесь. Рассмотрим реализацию CRC 8 бит по стандарту Dallas, он используется в датчиках этой фирмы (например DS18b20 и домофонные ключи iButton). Данная реализация должна работать на всех платформах, так как это чисто C++ без привязки к архитектуре (компилятор сам разберётся):

Финальный пример. Передатчик:

Также коллега поделился реализацией данного алгоритма на ассемблере для AVR, она работает чуть быстрее и весит чуть легче, что может быть критично например для ATtiny:

Функция используется точно так же, как предыдущая.

Источник

Циклический избыточный код

Содержание

Алгоритм CRC [ ]

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

Каждому конечному двоичному набору данных взаимооднозначно сопоставляется двоичный многочлен , последовательность коэффициентов которого представляет из себя исходную последовательность. Например, десятичное число 90 (1011010 в двоичной записи) соответствует многочлену:

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

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

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

— контрольный код многочлена . — исходный многочлен. — порождающий многочлен. — степень порождающего многочлена.

Умножение осуществляется приписыванием нулей к входной последовательности, что улучшает качество хэширования для коротких входных последовательностей.

Ниже представлены реализации получения некоторых CRC для многочленов степени 8 (CRC-8), 16 (CRC-16) и 32 (CRC-32).

Формализованный алгоритм расчёта CRC16 [ ]

Для получения контрольной суммы, необходимо сгенерировать полином. Основное требование к полиному: его степень должна быть равна длине контрольной суммы в битах. При этом старший бит полинома обязательно должен быть равен “1”.

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

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

Источник

Алгоритм контрольного суммирования CRC

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

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

Выбор длины порождающего многочлена, кратной байту, позволяет ускорить работу программы по контрольному суммированию, обеспечивая достаточную надежность полученного результата. Например, контрольное суммирование CRC-32 в пределе позволяет получить надежность порядка: 2 32 = 4.294.967.296. Что в принципе позволяет, практически со 100% вероятностью, обнаруживать сбои при хранении и передаче данных.

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

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

Полиномиальная арифметика по модулю 2 — это один из видов арифметики, используемый для решения задач в определенной предметной области и отличающийся от привычной, двоичной арифметики с циклическим переносом, отсутствием переносов и вычислением всех коэффициентов по модулю 2.

Таким образом, вычитание полиномов сводится к операции «исключающего или» с элементами полинома, имеющими одну и ту же степень, а, следовательно, мы можем заменить вычитание полиномов на операцию «исключающие или», с сопоставленными им бинарными последовательностями. Рассмотрим это утверждение на примере вычитания из полинома Х 4 + X 2 +1 полинома Х 3 + X 2 (операцию «исключающее или» обзначим значком ‘^’, как это принято в языке Си ):

Используя описанную выше возможность замены полинома на бинарную последовательность, рассмотрим алгоритм подсчета контрольной суммы CRC8:

Исходный массив данных: 1001 0110 0100 1011.

Порождающий многочлен: 1101 0101.

Аналогичным способом подсчитываются контрольные суммы CRC-16, CRC-32, CRC-64 и т.д. Как видите, алгоритмы очень просты и легко реализуются на любой ЭВМ.

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

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

Источник

Русские Блоги

Подробная проверка CRC (с примером кода)

Проверка CRC или проверка циклическим избыточным кодом (Cyclic Redundancy Check) предназначена для вычисления набора проверочных кодов на основе данных, которые используются для проверки того, были ли данные изменены или переданы ошибки во время передачи данных. Сначала рассмотрим две концепции, которые будут использоваться позже.

1. Принцип проверки CRC

Давайте воспользуемся конкретным примером для объяснения: для данного набора данных A: 10110011 (двоичный) выберите делитель B: 11001.

2. Генераторный полином

Основные принципы проверки CRC объясняются в главе 1. Обычно мы называем выбранный делитель «порождающим полиномом». Фактически, выбор порождающих полиномов основан на определенных критериях. Если выбор не удачный, вероятность обнаружения ошибок будет намного ниже. К счастью, эта проблема давно изучается специалистами, нам, пользователям, достаточно использовать существующие результаты. В следующей таблице показаны некоторые стандартные полиномы генератора CRC, которые можно использовать напрямую.

Стандартный полином генератора CRC

имя	Генераторный полином	Стенография
CRC-4	x4+x+1	0x03
CRC-8	x8+x5+x4+1	0x31
CRC-8	x8+x2+x1+1	0x07
CRC-8	x8+x6+x4+x3+x2+x1	0x5E
CRC-12	x12+x11+x3+x+1	0x080F
CRC-16	x16+x15+x2+1	0x8005
CRC16-CCITT	x16+x12+x5+1	0x1021
CRC-32	x32+x26+x23+. +x2+x+1	0x04C11DB7

3. Возьмите проверку CRC-16 в качестве примера, чтобы объяснить реализацию программирования.

3.3.1 Провести верификацию в полном соответствии с принципом CRC

Проверка CRC-16 часто используется в реальной инженерии, то есть полином генератора выбирается как 0x8005. По принципу проверки CRC, упомянутому ранее, этапы реализации программирования следующие: ( Обратите внимание, что этот прямой метод не используется в реальном программировании. Если вы не хотите его видеть, вы можете перейти к 3.3.2. ）

У этого прямого метода есть недостаток, то есть добавление 0 перед строкой не влияет на значение проверки, что не соответствует нашим ожиданиям. Например, мы хотим проверить 1 байт 1001 1100, а теперь добавить 1 байт 0 вперед, чтобы получить 2 байта 0000 0000 1001 1100. В результате два полученных контрольных значения совпадают. Поэтому в практических приложениях в процесс проверки CRC были внесены некоторые изменения: » Начальное значение остатка ”、“ XOR результата ”、“ Инверсия входных данных «с» Инверсия выходных данных «Четыре концепции.

3.3.2 Процесс проверки CRC, обычно используемый в инженерии

Таблица 3-1 Общие модели параметров CRC

Название алгоритма CRC	Полиномиальная формула	ширина	Полином (шестнадцатеричный)	Начальное значение (шестнадцатеричное)	Значение результата XOR (шестнадцатеричное)	Обратное входное значение	Инверсия выходного значения
CRC-4/ITU	x4 + x + 1	4	03	00	00	true	true
CRC-5/EPC	x4 + x3 + 1	5	09	09	00	false	false
CRC-5/ITU	x5 + x4 + x2 + 1	5	15	00	00	true	true
CRC-5/USB	x5 + x2 + 1	5	05	1F	1F	true	true
CRC-6/ITU	x6 + x + 1	6	03	00	00	true	true
CRC-7/MMC	x7 + x3 + 1	7	09	00	00	false	false
CRC-8	x8 + x2 + x + 1	8	07	00	00	false	false
CRC-8/ITU	x8 + x2 + x + 1	8	07	00	55	false	false
CRC-8/ROHC	x8 + x2 + x + 1	8	07	FF	00	true	true
CRC-8/MAXIM	x8 + x5 + x4 + 1	8	31	00	00	true	true
CRC-16/IBM	x16 + x15 + x2 + 1	16	8005	0000	0000	true	true
CRC-16/MAXIM	x16 + x15 + x2 + 1	16	8005	0000	FFFF	true	true
CRC-16/USB	x16 + x15 + x2 + 1	16	8005	FFFF	FFFF	true	true
CRC-16/MODBUS	x16 + x15 + x2 + 1	16	8005	FFFF	0000	true	true
CRC-16/CCITT	x16 + x12 + x5 + 1	16	1021	0000	0000	true	true
CRC-16/CCITT-FALSE	x16 + x12 + x5 + 1	16	1021	FFFF	0000	false	false
CRC-16/x5	x16 + x12 + x5 + 1	16	1021	FFFF	FFFF	true	true
CRC-16/XMODEM	x16 + x12 + x5 + 1	16	1021	0000	0000	false	false
CRC-16/DNP	x16 + x13 + x12 + x11 + x10 + x8 + x6 + x5 + x2 + 1	16	3D65	0000	FFFF	true	true
CRC-32	x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1	32	04C11DB7	FFFFFFFF	FFFFFFFF	true	true
CRC-32/MPEG-2	x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1	32	04C11DB7	FFFFFFFF	00000000	false	false

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

Я скомпилировал здесь общий код в соответствии с указанным выше методом, включая CRC-8, CRC-16 и CRC-32. код показан ниже:

При вызове просто передайте соответствующие параметры.

3.3.3 Улучшенный процесс проверки CRC

Код в 3.3.2 универсален, но видно, что эффективность невысока. В качестве примера возьмем функцию crc16. Необходимо определить, нужно ли перевернуть байт. В конце также необходимо определить, нужно ли его перевернуть. Это займет время. Если нужно перевернуть, тогда функция инверсии займет больше времени. Как можно повысить эффективность? На практике мы часто используем конкретный метод проверки, поэтому мы можем написать отдельный код вместо универсального, чтобы сэкономить время на две смены суждений. В качестве примера возьмем crc16 / MAXIM. И начало, и конец нужно поменять местами, что можно опустить после улучшения. Конкретные операции заключаются в следующем:

Читатели могут сравнить разницу между функцией crc16 и функцией crc16_MAXIM в общем коде.

4. Возьмите проверку CRC-8 в качестве примера, чтобы объяснить метод справочной таблицы.

Метод поиска по таблице быстрый, но таблица занимает часть памяти, то есть место для времени.

Чтобы облегчить понимание метода справочной таблицы, сначала посмотрите на 3.3.2. U8 crc8 (u8 * addr, int num, CRC_8 type) в CRC.c функция. Для удобства наблюдения я поместил эту функцию отдельно ниже:

Итоговая таблица выглядит следующим образом:

Следует отметить, что таблица, используемая в методе справочной таблицы, зависит от полинома, поэтому при использовании другого полинома необходимо повторно создать соответствующую таблицу. Итак, многочлен 0x07 u8 crc8 Функция может быть переписана следующим образом с помощью метода таблицы поиска:

Вы можете видеть, что 16-я строка кода заменяет цикл for и берет значение непосредственно из таблицы, что намного быстрее. На практике вам нужно записать таблицу в виде массива перед кодом, чтобы код мог искать таблицу.

5. Возьмите проверку CRC-16 в качестве примера, чтобы объяснить метод справочной таблицы.

Метод поиска в таблице crc16 аналогичен методу поиска в таблице crc8. Он также первым создает таблицу, а затем использует эту таблицу для замены цикла for.

5.1. Создать таблицу

Возьмем для примера код CRC16 из 3.3.3. Сначала сгенерируйте таблицу, каждый элемент этой таблицы составляет 2 байта, всего 256 элементов. Но вам нужно разделить эту таблицу на две таблицы, где старший байт помещается в crcLowTable, а младший байт помещается в crcHighTable (я не понимаю, почему это делается, но метод поиска таблицы может быть достигнут таким образом ). Сгенерированный код таблицы выглядит следующим образом:

Сгенерированная таблица выглядит следующим образом:

5.2. Реализация метода справочной таблицы

Когда у вас есть форма, вы можете реализовать метод поиска (почему используются 15-17 строк кода, я не знаю почему, это может включать переворот, приветствуйте великих богов для руководства в области комментариев), код выглядит следующим образом:

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

Источник

Простой расчет контрольной суммы

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

Чтобы упростить алгоритм, без потери качества, нужно немного «битовой магии», что интересная тема сама по себе.

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

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

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

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

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

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

На первом месте простой бит четности. При необходимости формируется аппаратно, принцип простейший, и подробно расписан в википедии. Недостаток только один, пропускает двойные ошибки (и вообще четное число ошибок), когда четность всех бит не меняется. Можно использовать для сбора статистики о наличии ошибок в потоке передаваемых данных, но целостность данных не гарантирует, хотя и снижает вероятность пропущенной ошибки на 50% (зависит, конечно, от типа помех на линии, в данном случае подразумевается что число четных и нечетных сбоев равновероятно).
Для включения бита четности, часто и код никакой не нужен, просто указываем что UART должен задействовать бит четности. Типично, просто указываем:

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

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

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

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

.

,

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

Или условный КПД=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. Но, практически везде, есть блок умножения. Рассчитаем контрольную сумму как произведение последовательности байт, на некоторую «магическую» константу:

Константа должна быть простой, и быть достаточно большой, для изменения большего числа бит после каждой операции, 211 вполне подходит, проверяем:

Всего 72% от теоретического предела, небольшое улучшение перед простой суммой. Алгоритм в таком виде не имеет смысла. В данном случае теряется важная информация из отбрасываемых старших 8..16 бит, а их необходимо учитывать. Проще всего, смешать функцией XOR с младшими битами 1..8. Приходим к еще более интенсивной модификации контрольной суммы, желательно с минимальным затратами ресурсов. Добавляем фокус из криптографических алгоритмов

Результат 91% от теоретического предела. Вполне годится для применения.

Если в микроконтроллере нет блока умножения, можно имитировать умножение операций сложения, смещения и XOR. Суть процесса такая же, модифицированный ошибкой бит, равномерно «распределяется» по остальным битам контрольной суммы.

На удивление хороший результат. Среднее значение 254,5 или 99% от теоретического предела, операций немного больше, но все они простые и не используется умножение.

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

Что соответствует 100.6% от теоретического предела, вполне хороший результат для такого простого алгоритма из одной строчки:

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

Столь высокий результат объясняется тем, что 2 цикла умножения подряд, полностью перемешивают биты, что нам и требовалось. Исключением, похоже, является последний байт телеграммы, особенно его старшие биты, они не полностью замешиваются в контрольную сумму, но и вероятность того, что ошибка придется на них невелика, примерно 4%. Эта особенность практически ни как не проявляется статистически, по крайней мере на моем наборе тестовых данных и ошибке ограниченной 10 сбойными битами. Для исключения этой особенности можно делать N+1 итераций, добавив виртуальный байт в дополнение к имеющимся в тестовом блоке данных (но это усложнение алгоритма).

Вариант без умножения с аналогичным результатом. Переменная CRC 16-битная, данные 8-битные, результат работы алгоритма — младшие 8 бит найденной контрольной суммы:

Результат 100.6% от теоретического предела.

Вариант без умножения более простой, оставлен самый минимум функций, всего 3 математических операции:

Результат 86% от теоретического предела.

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

Небольшое улучшение в некоторых случаях дает так же:

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

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

Следующий вариант 16 бит, и теоретическая вероятность ошибки переданных данных 1:65536, что намного лучше. Надежность растет по экспоненте. Но, как побочный эффект, растет количество вспомогательных данных, на примере нашей телеграммы, к 8 байтам полезной информации добавляется 2 байта контрольной суммы.

Простые алгоритмы суммы и XOR, применительно к 16-битной и последующим CRC не рассматриваем вообще, они практически не улучают качество работы, по сравнению с 8-битным вариантов.

Модифицируем алгоритм для обработки контрольной суммы разрядностью 16 бит, надо отметить, что тут так же есть магическое число 8 и 44111, значительное и необоснованное их изменение ухудшает работу алгоритма в разы.

Что соответствует 109% от теоретического предела. Присутствует ошибка измерений, но это простительно для 10 млн. итераций. Так же сказывается алгоритм создания, и вообще тип ошибок. Для более точного анализа, в любом случае нужно подстраивать условия под ошибки в конкретной линии передачи данных.

Дополнительно отмечу, что можно использовать 32-битные промежуточные переменные для накопления результата, а итоговую контрольную сумму использовать как младшие 16 бит. Во многих случаях, при любой разрядности контрольной суммы, так несколько улучшается качество работы алгоритма.

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

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

За 10 млн. итераций ошибка не обнаружена. Чтобы ускорить сбор статистики обрезал CRC до 24 бит:

Результат, из 10 млн. итераций ошибка обнаружена 3 раза

Вполне хороший результат и в целом близок к теоретическому пределу для 24 бит контрольной суммы (1:16777216). Тут надо отметить что функция контроля целостности данных равномерно распределена по всем битам CRC, и вполне возможно их отбрасывание с любой стороны, если есть ограничение на размер передаваемой CRC.

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

Вариант без умножения:

Сбоя для полноценной контрольной суммы дождаться не получилось. Контрольная сумма урезанная до 24 бит показывает примерно такие же результаты, 8 ошибок на 100 млн. итераций. Промежуточная переменная CRC 64-битная.

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

Ну и напоследок 64-битная контрольная сумма, максимальная контрольная сумма, которая имеет смысл при передачи данных на нижнем уровне:

Дождаться ошибки передачи данных, до конца существования вселенной, наверное не получится 🙂

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

Так же можно применить для 128-битных чисел (и еще больших), главное подобрать корректно 128-битные магические константы. Но это уже явно не для микроконтроллеров, такие числа и компилятор не поддерживает.

Комментарии

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

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

Мой проект по исследованию CRC на гитхаб.

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

Источник