б.б. коды хэмминга как циклические коды 133

qmi =={q\) Sj + 1

для некоторого Sj, поскольку q"~i- 1 делится на q - 1. Следовательно, суммируя по /, получаем

nmiq- 1)1; Sj-,

так что п я q - 1 взаимно просты тогда и только тогда, когда т ид - 1 взаимно просты. □

Согласно доказанной теореме, коды Хэмминга над GF (q) длины п = {q - \)l{q- 1) являются циклическими, если т ид - 1 взаимно просты. В § 3.4 мы рассматривали, однако, некоторые коды Хэмминга, для которых т и q - 1 не взаимно просты. Для этих кодов такое циклическое построение не работает. Простейшим их примером является (21,18)-код Хэмминга над GF (4). Этот код нельзя описать через порождающий многочлен. Однако большинство представляющих интерес кодов Хэмминга являются циклическими.

В качестве примера циклического кода Хэмминга рассмотрим (85,81)-код над GF (4), для которого выпишем порождающий многочлен. Это построение реализуется в поле GF (256) и сводится к нахождению минимального многочлена над GF (4) элемента р = а. Элементами порядка 3 в поле GF (256) являются только а и а™, так что в поле GF (256) поле GF (4) таково:

GF (4) = {О, 1, а™}.

Множеством сопряженных элементов, содержащих Р, относительно поля GF (2) является

{Р, р, P P Р P= p« p-j.

Но нам нужны сопряженные относительно поля GF (4) элементы, а они образуют множество

{Р, Р*, Р", Р**}.

Следовательно, искомый порождающий многочлен равен g (X) = (X - Р) (X - Р) (X ~ Р") (х - Р**) = (х - а») (х ~ а}) (х - аь) (х - а").

Раскрыв скобки, мы получим многочлен, все коэффициенты которого принадлежат полю GF (4). Таким образом, дальше нам уже не понадобится структура поля GF (256). Теперь поступим следующим образом. Используя примитивный многочлен р (х) = = х» + X* + х + х + 1, имеем = + о. + + 1. Неоднократно повторяя эту подстановку или используя таблицу

логарифмов для умножения в поле GF (256) (в обоих случаях вычисления займут примерно час), находим

g- (х) = х + + а?-">х + 1.

Наконец, поскольку мы уже оставили работу в поле GF (256), то заменим обозначения на более естественные для поля GF(4) и получим

g{x) х + х + Зх + I.

Это и есть искомый порождающий многочлен (85,81)-кода Хэмминга над полем GF (4).

5.6. ЦИКЛИЧЕСКИЕ КОДЫ, ИСПРАВЛЯЮЩИЕ ДВЕ ОШИБКИ

В предыдущем параграфе было дано описание кодов Хэмминга как циклических кодов, порождающие многочлены которых имеют KOperfb в соответствующем расширении основного поля. Описанные коды исправляют одну ошибку. Сейчас мы возвращаемся к исправляющим две ошибки кодам над полем GF (2). Пусть длина кода имеет вид п = 2" - 1 для некоторого т, и пусть а - примитивный элемент поля GF (2"). Мы рассмотрим те двоичные коды, для которых а и являются корнями порождающих многочленов, и покажем, что такие коды позволяют исправлять две ошибки.

Пусть g (х) - многочлен наименьшей степени, для которого а и из GF (2") являются корнями. Описав процедуру декодирования, позволяющую исправлять все одиночные и двойные ошибки, мы докажем, что минимальное расстояние этого кода равно по меньшей мере 5.

Принятое слово записывается многочленом степени п - 1 вида

v(x) = a(x)g(x) +е(х),

где е (х) содержит не более двух ненулевых коэффициентов, поскольку мы рассматриваем случай исправления не более двух ошибок. Таким образом, или е (х) = О, или е (х) = х, или е (х) = = х- + х. Целые числа I и I маркируют позиции, в которых произошли ошибки. Для маркировки ошибочных позиций мы будем также использовать элементы поля GF (2"). Элемент поля а соответствует компоненте с номером i. В этой роли элементы поля называются локаторами. Обозначим Хх = к и = а. Так как длина кода п равна порядку элемента а, то локаторы Ху и Х определяются однозначно. Если произошла только одна ошибка, то положим Х = 0; если ошибок не произошло, то Xi = X,= 0.

Б.6. коды, ИСПРАВЛЯЮЩИЕ ДВЕ ОШИБКИ 136

- Пусть Si = V (а) и Sg = V (с?). Эти элементы, известные также под названием компонент синдрома, вычисляются непосредственно по принятому слову V (х). Так как а и являются корнями g (х), то Si = е (а) и S3 = е (а). Предположим, что произошли две ошибки: = a + a, S3 = а + a". Но это в точности дает систему двух уравнений относительно двух неизвестных Xi и Х2 в поле GF (2"):

5i = Xi + Х2, S3 = -1 + xl-

Если может произойти не более двух ошибок, то величина Si равна нулю тогда и только тогда, когда не произошло ни одной ошибки. Декодер должен продолжать работу в том случае, когда Si отлично от нуля. Если выписанная система из двух нелинейных уравнений однозначно разрешима относительно Х и Х, то две ошибки могут быть исправлены, и минимальное расстояние рассматриваемого кода равно по меньшей мере 5.

Прямого очевидного способа решения такой системы нет. Один из методов состоит во введении нового многочлена, определяемого так, чтобы локаторы ошибок были его корнями:

{X - Xi) (х - Х) =х + {Xi -f X,) X + XiX.

Если мы сумеем найти коэффициенты этого многочлена, то, разложив его на линейные множители, мы сможем найти Х и Xg. Но над расширением поля GF (2)

•S? -- S3 = XXi -j- XfX] = SiX\X2

Таким образом,

{х + Xi) (х + Х2) =х + 5,х + (S? + 5з)/51,

и Si Ф О, если произошли одна или две ошибки. Многочлен в правой части нам известен, поскольку известны 5 и S3. Локаторы ошибок являются корнями этого многочлена, а корни любого многочлена над полем определяются однозначно. Следовательно, код исправляет две ошибки.

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

Рассмотренные в настоящем параграфе коды, исправляющие две ошибки, служат иллюстрацией того, как построить цикли-