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

[maksya]

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

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

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

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

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

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

 

[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 назад видел статью в ППИ (проблемы передачи информации) про границу Блиновского, да вообще, тут много всего.. Лит-ру поищу, потом кину.