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

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

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

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

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

m = 2^t-1
Например, если q(x) = x³+x²+1 (t=3), то m = 2^t – 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) = (x⁴+x+1)(x⁷+1) = x¹¹+x⁸+x⁷+x⁴+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.

Декодирование кодов Файра

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

Tags: кодирование, коды файра

Эта статья написана в Вторник, Сентябрь 29th, 2009 at 19:50 в разделе Задачи программирования. Вы можете подписаться на обновления комментариев к статье - RSS 2.0. Вы можете оставить комментарий, или послать пинг со своего сайта.