Алгоритм CRC-32 Опции

[maksya]

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

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

Единственный толковый источник, обнаруженный мной - это "Элементарное руководство по CRC алгоритмам обнаружения ошибок" Ross N. Williams (в переводе на русский). Файл на всякий случай прикладываю к сообщению, вдруг кому пригодиться. Но там рассматриваются общие вопросы. Мне же необходимо выработать точный алгоритм. И реализовать его на VHDL.

Если кто в этой теме разбирается - просьба откликнуться.

Прикрепленные файлы

 crcguide.pdf ( 199.59 килобайт ) Кол-во скачиваний: 472

 

[makc]

Думаю это поможет http://www.easics.be/webtools/crctool

[jojo]

Кое-что положил в
/upload/CODE/crclib_toolbox

[aal]

Вот кусочек для CRC 16. Может аналогично и CRC 32 сделать.

char test_flash(void)
{
unsigned char const __flash *mem;
unsigned int val; // Polinom 0x11021
unsigned char CRC_Low=0; // low 8 bits of CRC
unsigned char CRC_High=0; // high 8 bits of CRC
unsigned char carry;
mem=0;
for(val=0;val<FLASHEND-1;val++)
{
carry = CRC_High ^ *mem++;
carry = carry ^ (carry>>4);
CRC_High = CRC_Low ^ (carry<<4) ^ (carry>>3);
CRC_Low = carry ^ (carry<<5);
}
CRC=CRC_High << 8 + CRC_Low;
if (CRC_Low==*mem++ && CRC_High==*mem) return(0);
else return(1);
}

[Esquire]

ALL

Мне же необходимо выработать точный алгоритм. И реализовать его на VHDL.

Т.е. человеку требуется реализовать алгоритм аппаратно на ПЛИС, скорее всего, в режиме реального времени. Другими словами, программные реализации со сдвигами битов не катят - для этого применяются параллельные (табличные) алгоритмы, аналогичные указанному makc.

[maksya]

Думаю это поможет http://www.easics.be/webtools/crctool

Штука конечно интересная. Код генерится довольно простой, но хотелось бы разобраться в самом алгоритме. Так сказать докопаться до сути. В коде приведена функция, подсчитывающая новое значение NewCRC на основе входных данных и предыдущего значения CRC. Но начальное значение регистра CRC не предусмотрено (видимо это предлагается делать самому уже в своем коде). Да и непонятно на основании чего выведены выражения для подсчета CRC.

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

Но все-равно спасибо за помощь.

[makc]

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

Пример моей модели идет в приложении к письму. Написано довольно давно и на C++, но разобраться можно - ничего сверхъестественного там нет.

Прикрепленные файлы

 CRC2Parallel.rar ( 10.13 килобайт ) Кол-во скачиваний: 257

 

[aal]

2 Esquire

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

Алгоритм не я придумал. Где то в сети нашёл и пользую....

[Esquire]

aal
Все зависит от конкретных требований проекта: у меня обрабатываемый поток в максимуме примерно 800 Мбит/с, отсюда и табличный алгоритм.
В приложениях, не требующих вычисления контрольных сумм в реальном времени, можно поиграться и со сдвигами, и вообще вычислять CRC программным способом .

maksya
У Вильямса алгоритмы описаны неплохо, хотя при первом прочтении может показаться, что несколько туманно.
Проще всего будет раздобыть несколько исходников вычисления CRC-32 на языке высокого уровня и, пользуясь ими как практическим пособием, а Вильямсом - как теоретическим, постичь таинство вычисления контрольных сумм , после чего заняться трансляцией выбранного алгоритма на HDL.

[CeDeX]

Тут у меня файлец валялся на винте.
Мож кому сгодиться для ознакомления.
Фидо (с)

Прикрепленные файлы

 CRC_FAQ.TXT ( 32.51 килобайт ) Кол-во скачиваний: 605

 

[derun]

«A Painless Guide to CRC Error Detection Algorithms» Ross N. Williams перевод на русский (167кБ)

[basileus]

Может, моё изложение на пальцах тебе поможет реализовать это на VHDL.
Каждый ненулевой бит в потоке вносит возмущение в поток. След этого
возмущения распространяется в потоке. Конечное возмущение и есть CRC.
Начальное возмущение вносится, чтобы полностью нулевые потоки
различной длины имели различное конечное возмущение.
След единичного возмущение для каждой позиции при параллельной
обработке получить легко. Инициализируем СКС 000 и подаём единичное воздействие в нужной позиции. Полученная CRC и есть след. Для нескольких
бит -CRC есть сумма по модулю 2 их CRC.
Надеюсь, понятно, как это реализовать аппаратно. Не нужно громоздких
таблиц. Для N разрядной порции M разрядного CRC достаточно N M
разрядных регистров и Mразрядный N+1 входовых сумматор по модулю 2.
Т.е. Для байтной обработки потока и 32 разрядной CRC - 8 32 разрядных
регистров и 32 разрядный девяти входовый сумматор. (Это для полинома
общего случая). В реале регистры можно заменить логической функцией.
Если возникли вопросы могу добавить.

[Esquire]

basileus
Есть ли литература, в которой описан указанный метод расчета CRC32?

[Porychik Kize]

Посмотри на Xilinx.com - XAPP209. К нему прилагается скрипт на PERL-е crcgen.pl. Я из него сгенерил Verilog-код для подсчета CRC32 for IEEE802.3 с 4-битным входом (передача данных от MAC в PHY). Вроде бы результат работы совпадает с контрольным примером, приведенным Ross N.Williams-ом для "CRC-32" (хотя с этим я как раз сейчас окончательно и разбираюсь).

Прикрепленные файлы

 xapp209__2__CRC32.pdf ( 116.82 килобайт ) Кол-во скачиваний: 230

 

[Z0Rk]

Дабы не начинать новый топик, позвольте мне задать следующий вопрос...
Как формировать образующие полиномы для алгоритма CRC-32?
ИМХО каждый из полиномов оптимизирован для обнаружения определенной совокупности ошибок (одиночных, двойных, пакетных) и таким образом ориентирован на определнный канал передачи данных или систему хранения информации.
Также встает вопрос оценки вероятности ошибки... как её оценивать?
В известной литературе есть ссылки на источники, но заполучить их не удается (Tanenbaum "Computer Networks").
Если есть возможность, поделитесь информацией на данный счет.