Алгоритм 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").
Если есть возможность, поделитесь информацией на данный счет.

[Fast]

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

На память, могу ошибаться: для формирования полиномов используют разложение (XстепN - 1) в расширеном поле GF(2степ32). Вариантов получается много. Лит-ру сказать не могу, надо искать что-то вроде полей Галуа.
Для систематических блоковых кодов, образованных добавлением CRC-32 к инф.части, строится весовой спектр и рассчитывается вероятность необнаруженной ошибки (в формулу входят весовые компоненты. начиная с 32-й). Вероятность ошибки декодирования для них не считают, т.к. CRC-32 используется в системах ARQ (переспроса). Искать нужно теорему Мак-Вильямс о дуальности весового спектра расстояний для линейных блоковых кодов.
Для всех полиномов весовой спектр разный, в зависимости от его формы существует различная вероятность необнаруженной ошибки (как характеристики кода!) для данной длины кода. Для CRC-32 обнаруживаются все ошибки кратности (32-1), далее с какой-то вероятностью ошибки большей кратности. И чем больше смещен спектр в область "тяжелых" составляющих (т.е. большего веса), тем меньше вероятность необнаруженной ошибки для более "легких" составляющих. Вкратце так.

Исправляющая способность 3-4 бита, т.к. мин. рассояние для кодовых слов =8 (определяется только степенью полинома), поэтому для исправления CRC-32 не используют, только для обнаружения. Исправление осущ. за счет переспроса по каналу обратной связи.
см. Теория кодов, исправляющих ошибки
Задачи очень ресурсоемкие, давно уже решены. Все просто ислользуют CRC-32 из рекомендованного перечня с хор. спектр. хар-ми.

Для оценки вероятности ошибки в канале связи(КС) используется формула, в кот. входят
- закон распр. ошибок в КС
- С/Ш
- составляющие весового спектра используемого кода. Вообще-то, обычно используются аппрокс. формулы для блоковых кодов с верхней и нижей границами для вероятности ошибки, чтоб не мучиться. Года 2-3 назад видел статью в ППИ (проблемы передачи информации) про границу Блиновского, да вообще, тут много всего.. Лит-ру поищу, потом кину.

[Z0Rk]

То есть прямая задачка формирования полинома по заданным вероятностям обнаружения различных типов ошибок в аналитическом виде все-таки решаема, я правильно Вас понял? Опыт работы в полях Галуа имеется, то есть все опредялеяется, как всегда, жопочасами .

Вообще-то, обычно используются аппрокс. формулы для блоковых кодов с верхней и нижей границами для вероятности ошибки, чтоб не мучиться. Года 2-3 назад видел статью в ППИ (проблемы передачи информации) про границу Блиновского, да вообще, тут много всего.. Лит-ру поищу, потом кину.

Если есть такая возможность буду весьма благодарен .

[Fast]

То есть прямая задачка формирования полинома по заданным вероятностям обнаружения различных типов ошибок  в аналитическом виде все-таки решаема, я правильно Вас понял?

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

также как по синдрому ошибки CRC нельзя получить вектор ошибки, а только набор векторов кратности 1,2,3 и т.д. а далее по критерию (макс.правдоподобия) оставляем вектор с мин.весом

[Anton_org]

Вот замечательная программка, правда под Солярис.
Позволяет получать VHDL код по полиному и длине входного слова. Помимо CRC можно сгенерить кодировщик БЧХ и, вроде, что-то еще (работал с ней давно, Соляриса нет сейчас).

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

 genenc_v1_2_tar.gz ( 43.58 килобайт ) Кол-во скачиваний: 93

 

[basileus]

Совершенно верно- поля Галуа.
Я даже где-то (уж и не упомню где) видел программку,
выдающую все пары полиномов для
заданной размерности поля.
(читай -разрядности полинома)

[Z0Rk]

2basileus
Каких полиномов? формирующих для CRC32?
Если "да" то говорите где искать программу...

[evgeniy_s]

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

Посмотри этот материал и список литературы в нём - там достаточно хорошо объясняется принцип вычисления CRC-кода и дан конкретный пример:
 crcW2003.rar ( 52.06 килобайт ) Кол-во скачиваний: 791

Что касается начальной инициализации, то единицами регистр инициализируется для того, чтобы первые нули сообщения были охвачены CRC-кодом. Если этого не сделать, то алгоритм начнёт работать только после появления первой единицы - вне зависимости от реализации. Поэтому во всех спецификациях (например, RapidIO, PCI Express) требуют начальной инициализации регистров единицами.
В качестве литературы по циклическим избыточным кодам, а также по формированию полиномов рекомендую следующие:
1. Никитин Г.И. Помехоустойчивые циклические коды : Учеб. пособие/ Г.И.Никитин,С.С.Поддубный. -СПб., 1998.-71 с. :ил.
2. Евдонин А.М. Циклическое кодирование : Учеб. пособие/ А.М.Евдонин. -Челябинск: Изд-во ЮУрГУ, 1997.-59 с. :ил.
3. Когновицкий О.С. Основы циклических кодов : Учеб. пособие 2305/ О.С.Когновицкий. -Л., 1990.-64 с.
4. Смирнов А.С. Основы теории кодирования. Линейные групповые и циклические коды : Учеб.пособие/ А.С.Смирнов. -СПб, 1998.-148 с.
Когда-то на заре появления RapidIO мне пришлось сделать для физического уровня CRC-кодер/декодер по приведённой в прилагаемом файле методике. После перехода на PCI Express по этой же методике (чуть усовершенствовав реализацию) сделал новый CRC-кодер/декодер - на Xilinx'е вот уже несколько лет работает безукоризненно (время прохождения конвейера 1 такт, частота 125 МГц).