(?) + lf) + (f) + (r)

213

Это равенство представляет собой необходимое (но не достаточное) условие существования совершенного исправляющего тройные ошибки (23, 12)-кода над GF (2), так как: 1) число точек внутри сферы декодирования задается записанным в квадратных скобках выражением, 2) всего имеется 2 таких сфер и 3) все пространство содержит 2 точек. Следовательно, можно ожидать существования (23, 12, 7)-кода. Такой код, названный кодом Голея, действительно существует. Он удовлетворяет границе Хэмминга из задачи 1.5 со знаком равенства.

Код Голея занимает уникальное и важное место в теории кодирования. В силу такой хорошей упаковки сфер не удивительно, что код Голея тесно связан со многими математическими объектами, и поэтому его можно использовать для перехода от изучения теории кодирования к глубоким задачам теории групп и других областей математики. Однако встав на практическую точку зрения, вероятно, справедливо было бы заметить, что из-за малой длины код Голея, по-видимому, не найдет дальнейших конкретных приложений.

Определим код Голея как двоичный циклический код через его порождающий многочлен.

ным равенством (х) = Ь2 (х) противоречит выбору двух разных пакетов.

Таким образом, два различных пакета (х) и xibz (х) длины t и менее всегда принадлежат разным смежным классам, и, следовательно, код способен исправлять пакеты длины t и менее. □

В качестве примера кода Файра выберем m = f = 10 и положим р (х) равным примитивному многочлену степени 10. Тогда е ~ 2" - 1, и мы получаем (19437, 19408)-код, исправляющий все пакеты ошибок длины 10 и менее.

Коды Файра являются высокоскоростными кодами с малой (при т = i) избыточностью п - k. В этих случаях избыточность равна 3/- 1,»что превышает границу Рейгера только на t- 1. Метод перемежения позволяет строить из кодов Файра более длинные коды, исправляющие более длинные пакеты ошибок. Эти коды являются лучшими известными высокоскоростными кодами, исправляющими пакеты ошибок. В следующей главе мы увидим, что для этих кодов известны очень простые способы построения декодеров.

5.8. ДВОИЧНЫЙ КОД ГОЛЕЯ

Любой, кто займется исследованием таблицы биномиальных коэффициентов, может заметить, что

5.8. двоичный код ГОЛЕЯ 143

- Пусть g (х) и g (х) - следующие взаимные многочлены: g (х) == + х° + х« + X + х + х + 1, g (х) = х" + х + х + х« + х + X + 1.

Простым вычислением проверяется, что

(х - I) g (х) g (х) = х-1,

так что в качестве порождающего многочлена циклического (23, 12)-кода можно использовать как g (х), так и g (х).Мы воспользуемся многочленом g (х). Проведенное в начале параграфа комбинаторное рассуждение показывает, что минимальное расстояние этого кода не может быть больше 7. Мы сейчас докажем, что оно равно по меньшей мере 7, однако это доказательство не будет одновременно столь элементарным и кратким, как предыдущее. Можно было бы выписать матрицу Н и проверить, что никакие шесть ее столбцов не являются линейно зависимыми, но из-за больших размеров матрицы это неудобно. Поэтому мы проведем доказательство непосредственно, хотя оно и окажется длинным (длина этого доказательства показывает, насколько трудным может быть вычисление минимального веса в коде).

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

1) в коде нет слов веса 4 или меньше;

2) в коде нет слов веса 2, 6, 10, 14, 18 и 22;

3) в коде нет слов веса 1, 5, 9, 13, 17 и 21.

Совместно эти три утверждения означают, что минимальный вес кода равен по меньшей мере 7. Так как мы уже видели, что он не может быть больше 7, то заключаем, что он в точности равен 7.

Начнем с рассмотрения корней многочленов g (х) я g (х) в соответствующем расширении поля GF (2). Сделаем это не впрямую, а построив минимальные многочлены некоторых элементов из G/(2048), которые затем окажутся равными g (х) и g{x). Если а - примитивный элемент поля, то в силу разложения 2047 = = 23 X 89 и элемент поля р = а, и обратный ему элемент р"* имеют порядок 23. Пусть f (х) и f (х) - минимальные многочлены элементов р и Р~* соответственно.

Согласно теореме 5.3.6, минимальный многочлен элемента р равен

/ (х) = (X - р) (X - р) (X - р*) ... (х - р-),

где все показатели степеней приводятся по модулю 23 и 2- 2- = = 1 mod 23). Сопряженными являются элементы множества

В = (р, p р*, р«, р р«, p p р«, pь

которых всего 11, так что степень многочлена f [х) равна 11. Аналогично минимальный многочлен элемента 3~* равен

f (Х) = (Х - (Х - р-) (X - Р-*) ...{х- р-2"),

а множество сопряженных элементов равно

В = {р-1, p- р-*, р-«, р-1«, р- р-1«, р-», p- р-«, р-1-}.

Вместе множества В я В содержат 22 элемента поля, порядок каждого из которых равен 23; следовательно,

{X ~ 1) f (х) f (х) -х--1,

причем, согласно теореме о единственности разложения, это разложение единственно. Но мы видели, что такое же разложение имеет место для порождающих многочленов g (х) я g (х) кода Голея. Следовательно, эти порождающие многочлены представляют собой минимальные многочлены элементов а я а" из поля GF (2048).

Лемма 5.8.J. Код Голея не содержит ненулевых кодовых слов веса 4 и менее.

Доказательство. Так как элементы р, р, Р и Р принадлежат множеству В, то они являются корнями каждого кодового многочлена. Следовательно, каждое кодовое слово удовлетворяет равенству сН = О, где

"1 р рг . . . р2-"

1 р2 р* . . . р21

1 рз ре . . . р2о

.1 р ps . . . р1«

и, таким образом, с является кодовым словом кода с проверочной матрицей Н. Но любые четыре столбца матрицы Н образуют ненулевую матрицу, кратную матрице Вандермонда, определитель которой, как известно, отличен от нуля, если все элементы ее первой строки различны (это будет доказано в § 7.2). Следовательно, согласно следствию 3.2.3, Н является проверочной матрицей кода, минимальный вес в котором равен по меньшей мере 5. □

Следующая лемма утверждает, что код Голея не содержит слов веса 2, 6, 10, 14, 18 и 22.

Лемма 5.8.2. Если вес слова Голея четен, то он кратен 4.

Доказательство. Пусть с {х) = а {х) g (х) - кодовое слово, вес которого четен:

с(х) =-- CiX\