Комментарии 26
Спасибо за статью. Полезно и по делу.
109% от теоретического предела — неплохо, а больше можно ?
Самое интересное, что можно, на специально подобранном потоке данных, или при малом числе экспериментальных данных (хотя там и "теоретический предел" будет другим, но это существенное усложнение теории, эти случаи можно рассмотреть отдельно). Самый простой пример:
- Передали одно сообщение с ошибкой. Ошибка распознана, 100% распознанных ошибок, при теоретическом пределе для 1 битной контрольной суммы 50%.
- Некоторая специфическая линия связи, в которой только 1 сбойный бит в сообщении. Например лаборатория, где периодически включают мощный лазер на 0.2 миллисекунды (он потребляет большое количество энергии и вызывает помехи), как-раз чтобы вызвать сбой в передаче 1 бита. Контрольная сумма из 1 бита, так же обнаружит 100% ошибок. Более сложная контрольная сумма, в этом случае не нужна. Что-то подобное в серверных модулях памяти с ECC, где тоже для контроля ошибок выделяют 1 бит, и этого достаточно. Обычно, конечно, количество ошибок в сообщении, распределяется по нормальному или похожим законам, когда помеха искажает группу бит, непредсказуемой длины.
Тогда, наверное, все-таки, не теоретический предел, а мат. ожидание вероятности обнаружения ?
Да, так будет грамотнее, но появляется неоднозначность (это более абстрактный термин), математическое ожидание вероятности обнаружения какой именно величины имеется ввиду? Математическое ожидание вероятности обнаружения ошибки каждого алгоритма относительно математического ожидания вероятности обнаружение ошибки "идеального" алгоритма при заданных условиях эксперимента. Мне кажется, это несколько затруднит понимание статьи инженерам. Основной упор тут сделан не на математическую теорию (теория, объясняющая всё нюансы, будет очень сложна, сравнима с криптографическим анализом). Основная тема — поиск эффективного алгоритма, и для оценки качества его работы придуман специфический параметр, который находится простым моделированием.
Аббривеатурой CRC называется вполне определенное семейство алгоритмов. То, что рассмотрено в статье, это не CRC, это можно называть просто контрольной суммой или checksum.
Да, действительно, даже в Википедии в статье "Циклический избыточный код" есть пометка что "CRC-16-Fletcher" это "не CRC; см. Fletcher's checksum", или она же хеш-функция, rolling checksum, с отдельной статьей в Википедии "Adler-32".
Да, CRC задумывался как код для коррекции ошибок. А здесь просто хеш функция.
CRC != Код Хэмминга.
И кстати, кто сторожит сторожей?
Коды коррекции ошибок (хоть Хемминга, хоть Рида-Соломона) способны обнаруживать заданное количество ошибок как в исходных данных, так и в подписи.
А контрольная сумма может пропустить двойную ошибку — одно повреждение данных и одно суммы.
Коды коррекции ошибок (хоть Хемминга, хоть Рида-Соломона) способны обнаруживать заданное количество ошибок как в исходных данных, так и в подписи.
А контрольная сумма может пропустить двойную ошибку — одно повреждение данных и одно суммы.
Коды коррекции ошибок раздувают исходное сообщение, а контрольные суммы — нет.
Сторожей сторожить не нужно, они сторожат себя сами. Вероятность того, что контрольная сумма, например 0xD1D1 превратится именно в 0x1E3F, и ни какое другое число, очень мала, примерно 1/65536. Если такая вероятность недопустима, тогда просто увеличивается число бит контрольной суммы, надежность обнаружения ошибок растет экспоненциально.
Это зависит от алгоритма расчёта контрольной суммы.
Если изменение какого-то 1 бита данных приводит к изменению 1 бита подписи, то вот мы и получаем класс недиагностируемых 2-битовых ошибок.
Коды Хэмминга, CRC и т.п. как раз отличаются тем, что любой 1 бит данных меняет сразу много (около половины) битов подписи.
Обычные суммы, даже с множителями, более тщательно следят за младшими битами в байтах, и более расслабленно — за старшими.
Поэтому диагностика ошибок становится сильно неравномерной.
Напрашивается очевидная контрмера: сделать так, чтобы старшие биты байтов оказывали влияние на младшие биты суммы. Это операции деления (сдвига) или взятия остатка по основанию, не кратному степени 2.
Но так мы плавно подойдём к идее вычисления циклического избыточного кода. Аббревиатура которого хорошо нам известна :)
Если изменение какого-то 1 бита данных приводит к изменению 1 бита подписи, то вот мы и получаем класс недиагностируемых 2-битовых ошибок.
Коды Хэмминга, CRC и т.п. как раз отличаются тем, что любой 1 бит данных меняет сразу много (около половины) битов подписи.
Обычные суммы, даже с множителями, более тщательно следят за младшими битами в байтах, и более расслабленно — за старшими.
Поэтому диагностика ошибок становится сильно неравномерной.
Напрашивается очевидная контрмера: сделать так, чтобы старшие биты байтов оказывали влияние на младшие биты суммы. Это операции деления (сдвига) или взятия остатка по основанию, не кратному степени 2.
Но так мы плавно подойдём к идее вычисления циклического избыточного кода. Аббревиатура которого хорошо нам известна :)
Обычные суммы, даже с множителями, более тщательно следят за младшими битами в байтах, и более расслабленно — за старшими.
Поэтому диагностика ошибок становится сильно неравномерной.
Я бы отметил, что за младшим битом последнего байта обрабатываемого сообщения. Первые, старшие байты многократно перемешиваются с запасом. Проблему можно решить, добавив в цикл 1-2 холостых прохода (например, вместо 8 байт, обрабатываем виртуальный девятый), это не усложнит алгоритм и не скажется на быстродействии. Попробую попозже собрать статистику по этому вопросу. Тут, скорее всего, проблема может вылезти на больших контрольных суммах, где высока "ответственность" каждого бита, контрольная сумма 16, 32 бита и старше.
Из всего вами перечисленного, взятие остатка по основанию как-раз самая трудоемкая операция, только на готовых аппаратных блоках и ПЛИС хорошо считать ))
Да похоже задумывался он всё-таки для обнаружения ошибок (cyclic redundancy CHECK). Однако CRC (как и Рид-Соломон) это подмножество БЧХ. Только цели у них несколько разные (при одинаковом расстоянии Хэмминга). Используя CRC можно корректировать ошибки, никто не запрещает, однако эффективность (время/ресурсы) поиска и коррекции ошибочного символа будет хуже, чем у БЧХ-кода сконструированного специально для обнаружения и коррекции. Впрочем и тут есть нюансы: например при «поточной» коррекции ошибок использование CRC-кода будет вычислительней не менее эффективно (а аппаратная реализация и более эффективной), чем типично «блочного» Рида-Соломона.
Однако я удивлён, почему столько минусов моему комментарию. Похоже их ставят люди, которые не знают, не имели практики использования существующего применения CRC. Хотя в школе\университете и книгах всё подробно рассказывается. И коррекция ошибок на аппаратном уровне очень легко реализуется. И в большинстве случаев её бывает достаточно.
Сомнителен смысл использования своих алгоритмов расчета контрольной суммы, существует же алгоритм crc и используется везде где только можно.
По скорости исполнения кода у вас с таблицей выйдет тоже самое, что и умножение 8 бит на магическую константу в вашем примере, по эффективности выше в разы.
Хранить 256 байт данных во флэше для crc8 не так уж и тяжко.
Да и наконец в документации проще написать, используется crc16 полином такой то, гораздо меньше вероятность как вы говорите вынести мозг и микроконтроллеру и программисту, чем сказать "мы тут все 2 раза умножаем на 44111 потом складываем и обрезаем до 8 бит"
По скорости исполнения кода у вас с таблицей выйдет тоже самое, что и умножение 8 бит на магическую константу в вашем примере, по эффективности выше в разы.
Хранить 256 байт данных во флэше для crc8 не так уж и тяжко.
Да и наконец в документации проще написать, используется crc16 полином такой то, гораздо меньше вероятность как вы говорите вынести мозг и микроконтроллеру и программисту, чем сказать "мы тут все 2 раза умножаем на 44111 потом складываем и обрезаем до 8 бит"
Кроме алгоритма CRC, широко используется просто контрольная сумма (протокол DCON), скорее всего в силу простоты, там уже, действительно сложно ошибиться.
Есть контрольная сумма Флетчера с модификацией Adler-32, не хватило программистом одной только CRC (причем не на микроконтроллерах, а на мощных современных ПК).
В микроконтроллере ATtiny13a, всего флеша 1024 байта, под таблицу замен 256 байт отдать может не получиться, да и зачем тратить лишние 256 байт, если есть возможность не тратить.
CRC16 полином такой-то, это по сути указать (чтобы избежать неоднозначности):
Лично для меня CRC сложнее, чем контрольная сумма по единственной формуле в цикле
Эффективность обнаружения ошибок сравнима, отличия в доле процента.
И для больших чисел CRC не применяется:
Есть контрольная сумма Флетчера с модификацией Adler-32, не хватило программистом одной только CRC (причем не на микроконтроллерах, а на мощных современных ПК).
Данный алгоритм расчёта контрольной суммы отличается от CRC32 производительностью. Adler-32 используется в библиотеке Zlib. Rolling checksum версия функции используется в утилите rsync.
В микроконтроллере ATtiny13a, всего флеша 1024 байта, под таблицу замен 256 байт отдать может не получиться, да и зачем тратить лишние 256 байт, если есть возможность не тратить.
CRC16 полином такой-то, это по сути указать (чтобы избежать неоднозначности):
- Степень порождающего контрольную сумму многочлена (width);
- Сам производящий полином (poly). Для того, чтобы записать его в виде значения, его сначала записывают как битовую последовательность, при этом старший бит опускается — он всегда равен 1. К примеру, многочлен x^8+x^4+1 в данной нотации будет записан числом 00010001.
- Стартовые данные (init), то есть значения регистров на момент начала вычислений;
- Флаг (RefIn), указывающий на начало и направление вычислений. Существует два варианта: False — начиная со старшего значащего бита (MSB-first), или True — с младшего (LSB-first);
- Флаг (RefOut), определяющий, инвертируется ли порядок битов регистра при входе на элемент XOR;
- Число (XorOut), с которым складывается по модулю 2 полученный результат;
- Значение CRC (check) для строки «123456789».
Лично для меня CRC сложнее, чем контрольная сумма по единственной формуле в цикле
CRC:=CRC + byte*44111;Эффективность обнаружения ошибок сравнима, отличия в доле процента.
И для больших чисел CRC не применяется:
Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время вытеснены криптографическими хеш-функциями.
Существуют и другие алгоритмы, да, но это единичные случаи.
Я к чему, пока я пишу это сообщение при чтении с винчестера через satа используется crc32, при использовании любого pci устройства используется crc32, сейчас отправлю сообщение и в IP протоколе будет использоваться то же самое crc32. Modbus и еще масса промышленных стандартов поддерживают в виде контрольной суммы циклически избыточный код.
Все что вы описали по LitleEndian и.т.п. это характеристика протокола передачи и не относится к контрольной сумме любого типа. Все остальные параметры применимы опять же к любой контрольной сумме и если не описаны, опускаются, как в вашем варианте CRC:=CRC + byte*44111 не видно xor out.
А в тему тиньки с 1 кб флэша, так можно и 8051 использовать, но зачем если любой CortexM0 стоит и дешевле и может больше
http://www.compel.ru/infosheet/ATMEL/ATtiny13-20SU/
http://www.compel.ru/infosheet/ST/STM32F030K6T6TR/
Я к чему, пока я пишу это сообщение при чтении с винчестера через satа используется crc32, при использовании любого pci устройства используется crc32, сейчас отправлю сообщение и в IP протоколе будет использоваться то же самое crc32. Modbus и еще масса промышленных стандартов поддерживают в виде контрольной суммы циклически избыточный код.
Все что вы описали по LitleEndian и.т.п. это характеристика протокола передачи и не относится к контрольной сумме любого типа. Все остальные параметры применимы опять же к любой контрольной сумме и если не описаны, опускаются, как в вашем варианте CRC:=CRC + byte*44111 не видно xor out.
А в тему тиньки с 1 кб флэша, так можно и 8051 использовать, но зачем если любой CortexM0 стоит и дешевле и может больше
http://www.compel.ru/infosheet/ATMEL/ATtiny13-20SU/
http://www.compel.ru/infosheet/ST/STM32F030K6T6TR/
Вот пример сложностей, что возникают с CRC32 в STM32, целая статья, достаточно интересная, по хождению по граблям:
http://we.easyelectronics.ru/STM32/crc32-na-stm32-kak-na-kompe-ili-na-kompe-kak-na-stm32.html
Аппаратный блок кроме плюсов, имеет недостаток — фиксированный алгоритм, может быть несовместимость с алгоритмом работающим в устройстве на другой стороне линии связи (список необходимых параметров я приводил, и все они должны совпадать). То же самое может быть с SPI, UART, иногда проще программно их реализовать, чем разбираться особенностями аппаратной реализации, при специфических особенностях оборудования это всплывает иногда (несовместимость аппаратная).
При использовании CRC:=CRC + byte*44111 разработчик не столкнется и с 1% сложностей описанных в статье. Человеко-часы разработчика сэкономлены, побочных эффектов нет, разве это плохой результат?
http://we.easyelectronics.ru/STM32/crc32-na-stm32-kak-na-kompe-ili-na-kompe-kak-na-stm32.html
Все знают, что в STM32F1xx, STM32F2xx, STM32F4xx есть аппаратный блок CRC32 с полиномом 0x04C11DB7.
И он, в общем-то, работает. Но только контрольная сумма почему-то не совпадает с таковой, рассчитанной софтварно.
Аппаратный блок кроме плюсов, имеет недостаток — фиксированный алгоритм, может быть несовместимость с алгоритмом работающим в устройстве на другой стороне линии связи (список необходимых параметров я приводил, и все они должны совпадать). То же самое может быть с SPI, UART, иногда проще программно их реализовать, чем разбираться особенностями аппаратной реализации, при специфических особенностях оборудования это всплывает иногда (несовместимость аппаратная).
При использовании CRC:=CRC + byte*44111 разработчик не столкнется и с 1% сложностей описанных в статье. Человеко-часы разработчика сэкономлены, побочных эффектов нет, разве это плохой результат?
Нам же нужен такой алгоритм, чтобы заменял при единичной ошибке максимальное количество бит в контрольной сумме. Но мы, в общей сложности, ограниченны сложностью алгоритма, и ресурсами в нашем распоряжении. Не во всех микроконтроллерах есть аппаратный блок расчета CRC. Но, практически везде, есть блок умножения.
Микроконтроллер, которому трудно программно подсчитать циклическую контрольную сумму, но при этом в нём есть блок умножения? Можете привести пример такого микроконтроллера?
Да сколько угодно — все AVR без блока CRC. В процессе вычисления настоящей CRC умножение не используется, а побитовое вычисление CRC (впрямую) действительно весьма длительный процесс и если Вы не можете применять заранее подготовленную таблицу (в целях экономии памяти или из религиозных соображений), то блок умножения Вам ничем не поможет.
http://catethysis.ru/stm32-crc/
А если нужен другой полином CRC32, или 64-битная контрольная сумма, в случае если надежность CRC32 не устраивает?
Конкретно в STM32 значение N = 32, и применяется полином вида X^32 + X^26 + X^23 + X^22 + X^16 + X^12 + X^11 + X^10 + X^8 + X^7 + X^5 + X^4 + X^2 + X + 1, который можно записать в виде 0x4C11DB7.
А если нужен другой полином CRC32, или 64-битная контрольная сумма, в случае если надежность CRC32 не устраивает?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Простой расчет контрольной суммы