nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

О выборе самого подходящего CRC-кода

Каюсь, что в вопросе выбора полинома для CRC я исходил из "моды": взял попросту самый популярный из CRC-16, под названием CCITT, 0x1021. Другие названия (в зависимости от выбора начального значения, инверсии битов на входе и на выходе): AUG-CCITT, GENIBUS, MCRF4XX, RIELLO, TMS37157, CRC-A, KERMIT, X-25 и X-MODEM, и это только то, что знает crccalc.com.

Сейчас решил всё-таки поискать, а в чём же, собственно, разница, и какой было бы лучше всего выбрать мне для поставленной задачи: МКО (Mil-Std 1553) со своими проверками чётности, от 1 до 32 слов данных (каждое слово 16 бит), ошибки предполагаются случайными и довольно редкими (вероятность 10-7).

Бешеную активность в этом направлении (исследование CRC) развил Филипп Купман (https://users.ece.cmu.edu/~koopman/crc/). Информации очень много, она "утрамбована", вроде бы наконец разобрался, что с ней делать.

Основная идея: выбрать такой код, который для твоего размера сообщения даст наибольшую возможную дистанцию Хэмминга, т.е позволит ГАРАНТИРОВАННО обнаружить как можно больше неправильных битов.


Дистанция Хэмминга на его сайте везде сокращена до HD. HD=1 - это "незащищённые данные", т.е даже одна ошибка не обнаруживается. HD=2 значит обнаружение ошибки хотя бы в одном бите, по сути "чётность". HD=3 - обнаружение двух ошибок, HD=4 - трёх ошибок, и так далее.

Вообще ЛЮБОЙ CRC-код обязан обнаружить одну ошибку, то есть иметь хотя бы HD=2, и эта одна ошибка будет обнаружена на произвольно длинном сообщении. В этом ничего удивительного быть не должно, т.к один-единственный бит чётности это сделает.

С обнаружением двух ошибок
в длиннющих последовательностях всё изучено довольно хорошо. Для этого хорошо подходят неприводимые (irreducible, иногда prime, а также primitive) полиномы. Если используется CRC на таком полиноме, в N бит (сам полином N+1 бит, но значение CRC - это по сути остаток от деления на полином, поэтому занимает N бит), две ошибки будут гарантированно обнаружены в сообщении длиной до 2N-N-1 бит. Например, для CRC-16, выбрав такой полином, можно обеспечить обнаружение 2 ошибок в сообщении до 65519 бит, или в 4094 слова по 16 бит.

Говорится также, что и 3 ошибки такие полиномы обнаруживают довольно часто. Вот перечислены рекомендуемые полиномы для HD=3: https://users.ece.cmu.edu/~koopman/crc/hd3.html
Нас интересует CRC-16, там видим несколько вариантов. Во второй графе для всех указана максимальная длина сообщения, в котором они обнаружат 2 ошибки, везде одинаковая, 65519. В третьей графе указывается, например, для первого варианта, что при длине сообщения до 1149 бит будет гарантированно обнаруживаться 3 ошибки, а для второго - при длине до 119 бит (маловато) - и 4 ошибки.

Следующий довольно изученный вариант - это неприводимый полином, помноженный на x+1. При этом работа на длинных сообщениях ухудшается, зато на более коротких появляется возможность обнаруживать НЕЧЁТНОЕ КОЛИЧЕСТВО ОШИБОК. Т.е, две ошибки обнаруживает, как и прежде, но ещё 3, и 5, и 7. Надо сказать, для нас это очень неплохо, поскольку биты чётности, которые всунуты в каждое слово, передаваемое по МКО, практически гарантируют, что если уж дошло дело до проверки CRC (ни одно слово не было забраковано по чётности), то ошибок будет нечётное количество. Единственное исключение - если ошибка допущена в самом бите чётности, который на проверку CRC уже не идёт. Именно таким полиномом является выбранный нами, CCITT, 0x1021. В "зоопарке" он приведён: http://users.ece.cmu.edu/~koopman/crc/crc16.html

Чтобы максимально всё запутать, здесь повсюду полиномы записываются по-другому. Этот CCITT мы находим в конце предпоследнего "абзаца":
(0x8810; 0x11021) <=> (0x8408; 0x10811) {32751,32751} | gold | (*op) CCITT-16


Он записан сначала как 0x8810. Это товарищ Купман в своё время решил для полинома x16+x12+x5+1 не записывать финальную единичку как "саму собой разумеющеюся", то есть 0x8810 = 1000_1000_0001_0000 - здесь указаны коэффициенты для степеней от 16 до 1 соответственно.
Затем, через запятую, он привёл значение 0x11021, здесь единичка уже включена, а ещё в явном виде включена единичка при x16, которую в привычной нам записи 0x1021 не приводят, потому как без неё полином будет уже не 16-й степени, и остаток от деления на него даст меньше 16 бит.

Затем то же самое ещё записали с реверсом битов - ну пущай.

Далее, в фигурных скобках приводится максимальная длина сообщения, для которой достигается HD=3, затем HD=4 (т.е 2 ошибки, затем 3 ошибки). Значение одинаковое: 32751 бит, нас устраивает!

gold - это ссылка на проверку "в лоб", что данные значения достигаются (я так понял). (*op) - это как раз означает неприводимый полином (p, prime или primitive), помноженный на x+1 (o, что означает odd).

Так что полином неплохой.

Но можно ли ещё лучше обнаруживать ошибки, если нам не нужна длина сообщения 32751 бит, а хватит 496 бит?

Если посмотреть в Summary tables на https://users.ece.cmu.edu/~koopman/crc/, мы увидим, что HD=4 (обнаружение до 3 ошибок) можно сделать до длины сообщения 32751 бит, а HD=5 (обнаружение до 4 ошибок) - только до длины в 241 бит, маловато будет!

Выходит, гарантированного обнаружения до 4 ошибок на сообщении в 496 бит мы достичь не можем. Но можно ли максимально поднять вероятность их обнаружения?

Для этого надо открыть "простыню", например для нашего полинома CCITT вот она: http://users.ece.cmu.edu/~koopman/crc/c16/0x8810.txt
Открываю её в экселе, выбрав в качестве разделителя tabulation (tab). Имеем колонки HW(2), HW(3), HW(4) и так далее, это Hamming Weight, количество сочетаний ошибок, которые не будут обнаружены. Например, когда нас интересует 4 ошибки, они могут быть "расставлены" по сообщению C4496 = 2491434660 различными способами. А если посмотреть на HW(4) для тех же 496 бит, там будет 83617 случаев. То есть, вероятность пропустить 4 ошибки на самом деле довольно мала, 83617 / 2491434660 ≈ 0,0034%.

А как поведёт себя полином, который рекомендуется здесь: https://users.ece.cmu.edu/~koopman/crc/c16/0xd175.txt (рекомендуют его в этом списке: https://users.ece.cmu.edu/~koopman/crc/hd4.html )

Напротив 496 бит мы находим количество пропущенных ошибок: 83614, аж НА 3 СЛУЧАЯ меньше! Вообще ни о чём...


В общем, мне повезло: ровно в моём случае этот полином CCITT действительно хорошо подходит. Для более коротких сообщений или для более длинных лучше подошли бы другие. А здесь мы имеем гарантированное обнаружение до 3 ошибок, а также любого их нечётного количества, и вероятность 99,997% обнаружить 4 ошибки.
Tags: ПЛИС, математика, работа, странные девайсы
Subscribe

Recent Posts from This Journal

  • Тестируем atan1 на QuatCore

    Пора уже перебираться на "железо" потихоньку. Решил начать с самого первого алгоритма, поскольку он уже был написан на ассемблере. В программу внёс…

  • Формулы приведения, что б их... (и atan на ТРЁХ умножениях)

    Формулу арктангенса на 4 умножениях ещё немножко оптимизировал с помощью алгоритма Ремеза: Ошибка уменьшилась с 4,9 до 4,65 угловой секунды, и…

  • Алгоритм Ремеза в экселе

    Вот и до него руки дошли, причина станет ясна в следующем посте. Изучать чужие библиотеки было лениво (в том же BOOSTе сам чёрт ногу сломит), писать…

  • atan на ЧЕТЫРЁХ умножениях

    Мишка такой человек — ему обязательно надо, чтоб от всего была польза. Когда у него бывают лишние деньги, он идёт в магазин и покупает какую-нибудь…

  • Ай да Пафнутий Львович!

    Решил ещё немного поковыряться со своим арктангенсом. Хотел применить алгоритм Ремеза, но начал с узлов Чебышёва. И для начала со своего "линейного…

  • atan(y/x) на двух умножениях!

    Чего-то никак меня не отпустит эта тема, всё кажется, что есть очень простой и эффективный метод, надо только его найти! Сейчас вот такое…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 3 comments