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

[maksya]

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

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

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

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

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

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

 

[Esquire]

basileus
Есть ли литература, в которой описан указанный метод расчета 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 МГц).