[maksya 0]

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

 

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

 

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

 

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

crcguide.pdf

[makc 192]

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

[jojo 0]

Кое-что положил в

/upload/CODE/crclib_toolbox

[aal 0]

Вот кусочек для 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 0]

ALL

 

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

 

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

[maksya 0]

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

<{POST_SNAPBACK}>

 

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

 

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

 

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

[makc 192]

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

 

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

CRC2Parallel.rar

[aal 0]

2 Esquire

 

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

 

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

[Esquire 0]

aal

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

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

 

maksya

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

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

[CeDeX 0]

Тут у меня файлец валялся на винте.

Мож кому сгодиться для ознакомления.

Фидо (с)

CRC_FAQ.TXT

[derun 0]

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

[basileus 0]

Может, моё изложение на пальцах тебе поможет реализовать это на VHDL.

Каждый ненулевой бит в потоке вносит возмущение в поток. След этого

возмущения распространяется в потоке. Конечное возмущение и есть CRC.

Начальное возмущение вносится, чтобы полностью нулевые потоки

различной длины имели различное конечное возмущение.

След единичного возмущение для каждой позиции при параллельной

обработке получить легко. Инициализируем СКС 000 и подаём единичное воздействие в нужной позиции. Полученная CRC и есть след. Для нескольких

бит -CRC есть сумма по модулю 2 их CRC.

Надеюсь, понятно, как это реализовать аппаратно. Не нужно громоздких

таблиц. Для N разрядной порции M разрядного CRC достаточно N M

разрядных регистров и Mразрядный N+1 входовых сумматор по модулю 2.

Т.е. Для байтной обработки потока и 32 разрядной CRC - 8 32 разрядных

регистров и 32 разрядный девяти входовый сумматор. (Это для полинома

общего случая). В реале регистры можно заменить логической функцией.

Если возникли вопросы могу добавить.

[Esquire 0]

basileus

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

[PorychikKize 4]

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

xapp209__2__CRC32.pdf

[Z0Rk 0]

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

Как формировать образующие полиномы для алгоритма CRC-32?

ИМХО каждый из полиномов оптимизирован для обнаружения определенной совокупности ошибок (одиночных, двойных, пакетных) и таким образом ориентирован на определнный канал передачи данных или систему хранения информации.

Также встает вопрос оценки вероятности ошибки... как её оценивать?

В известной литературе есть ссылки на источники, но заполучить их не удается :( (Tanenbaum "Computer Networks").

Если есть возможность, поделитесь информацией на данный счет.