[Fast 0]

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

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

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

<{POST_SNAPBACK}>

На память, могу ошибаться: для формирования полиномов используют разложение (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 0]

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

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

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

[Fast 0]

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

Сам хотел такого, но увы, это невозможно

Отображение спектральных составляющих на вероятность нелинейно, отсюда получите множество решений (полиномов), среди кот. все равно надо будет отбирать по критерию подходящие.

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

 

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

:)

[Anton_org 0]

Вот замечательная программка, правда под Солярис.

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

genenc_v1_2_tar.gz

[basileus 0]

Совершенно верно- поля Галуа.

Я даже где-то (уж и не упомню где) видел программку,

выдающую все пары полиномов для

заданной размерности поля.

(читай -разрядности полинома)

[Z0Rk 0]

2basileus

Каких полиномов? формирующих для CRC32?

Если "да" то говорите где искать программу... ;)

[evgeniy_s 0]

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

 

Посмотри этот материал и список литературы в нём - там достаточно хорошо объясняется принцип вычисления CRC-кода и дан конкретный пример:

crcW2003.rar

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