Коды Файра

Почему-то в Интернете очень мало нашел информации на русском по данному коду, а появилась в нем необходимость. Выкладываю здесь алгоритм, а так же теоретическую выписку из книги:

Березюк Н.Т. Кодирование информации. Двоичные коды / Н.Т. Березюк. – Харьков: Вища шк., 1978. – 252 с.
Коды Файра страницы 207-208.

Для любителей электронной литературы подсказка: скачать книжку “Березюк Н.Т. Кодирование информации.” можно на торрентах.

Наиболее известным циклическим кодом, исправляющим одиночные пачки ошибок, являеться двоичный код Файра, причем для этого требуется небольшое число проверочных символов.

Образующий полином данного кода P(x) = q(x) (xc+1), где q(x) – неприводимый многочлен степени t, принадлежащий степени m; с – простое число, которое не делиться на m без остатка.
Многочлен q(x) принадлежит некоторой степени m, если m – наименьшее положительное число такое, что двучлен (xm+1) делится на q(x) без остатка. Для любого t существует, по крайней мере, один неприводимый многочлен q(x) степени t, принадлежащий показателю степени

m = 2t-1

Например, если q(x) = x3+x2+1 (t=3), то m = 2t – 1 = 7 и число c может принимать значения, которые не делятся на семь, т.е. 15, 16, 17, 18, 19, 20, 22, 23 и т.д.
Длина кода Файра равна наименьшему общему кратному чисел c и m т.е.

n = НОК (c, m)

Число проверочных информационных символов

k= n- c –t

Можно получить код меньший длины с тем же числом проверочных символов, если пользоваться методом получения укороченных циклических кодов. При использовании кодов Файра можно исправить любую одиночную пачку ошибок длины b или меньше и одновременно обнаружить любую пачку ошибок длины l >= b или меньше , если c>=b+l-1 и t>=b.
Если применять эти коды только для обнаружения ошибок, можно обнаружить любую комбинацию из двух пачек ошибок, длина наименьшей из которых не превосходит t, а сумма длин обеих пачек не превосходит (с+1), а также любую одиночную пачку ошибок с длиной, не превосходящей числа проверочных символов r = c + t.
Пример:
Код Файра порождается полиномом P(x) = (x4+x+1)(x7+1) = x11+x8+x7+x4+x+1.
Определить параметры кода.
Так как t=4, c=7, то , используя формулы, получаем m=24-1=15, n=НОК(7,15)=7*15 = 105 r=4+7=11; k=105-11=94.
Этот код может быть использован, например, для исправления пачки ошибок длины b=4 или меньше и обнаружения любой пачки ошибок длины l<=4 или для исправления пачек ошибок длины b=2 или меньше и обнаружения пачек ошибок длины l<=6. Если использовать этот код исключительно для обнаружения ошибок, можно обнаружить любую одиночную пачку ошибок длины <=(4+7) и любую комбинацию из двух пачек ошибок, длина наименьшей из который не превосходит t=4, а сумма их длин не превосходит c+1=8.

В некоторых источниках, как например в “М. Вернер Основы Кодирования.” Упоминается еще одно произношение / написание этого кода – код Файера.

При декодировании производится раздельное деление принятой кодовой комбинации на полином P(x) и на полином (xc+1).

В результате такого деления получаются остатки R1(x) и R2(x), которые будут нулевыми, если ошибок не было. Если же прошла одиночная пачка ошибок длиной b, то остатки будут отличны от нуля и не равны между собой.

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

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

Блок схема алгоритма декодирования:

Коды Файера


По данной тематике я лично использовал следующую литературу:

1. Н.Т. Березюк Кодирование информации. Двоичные коды. Харьков – Вища Школа , 1978, 252 с.
2. М. Вернер Основы кодирования. Учебник для ВУЗов. Москва: Техносфера, 2004. -288с.
3. В.И. Дмитриев Прикладная теория информации. – М.: 1989. – 332с.
4. Золотарёв В.В., Овечкин Г.В. Помехоустойчивое кодирование. Методы и алгоритмы : Справочник / Под. Ред. чл.-кор. РАН Ю.Б. Зубарева. – М.: Горячая линия-Телеком, 2004. – 126с.
5. Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ. – М.: Мир, 1986. – 576 с., ил.