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

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

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

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

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

Пусть следующие взаимные многочлены:

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

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

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

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

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

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

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

Начнем с рассмотрения корней многочленов в соответствующем расширении поля GF (2). Сделаем это не впрямую, а построив минимальные многочлены некоторых элементов из которые затем окажутся равными Если а — примитивный элемент поля, то в силу разложения и элемент поля и обратный ему элемент имеют порядок . Пусть минимальные многочлены элементов и соответственно.

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

где все показатели степеней приводятся но модулю Сопряженными являются элементы множества

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

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

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

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

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

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

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

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

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

Доказательство. Пусть с кодовое слово, вес которого четен:

где число коэффициентов равных единице, четно. Тогда с и поэтому к — 1 делит с Но не делит следовательно,

для некоторого Определим взаимный многочлен:

Поскольку с для некоторого имеем

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

Ниже мы используем это равенство, а сейчас вычислим с отметив, что произведение многочленов может быть записано в виде свертки:

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

Второе слагаемое равно нулю, так как , в поле и по предположению число коэффициентов равных единице, четно. В последнем слагаемом сделаем подстановку и в обоих слагаемых заменим на Тогда

Далее заменим на I во втором слагаемом и положим в первом слагаемом и во втором. Это дает

Но с кратно многочлену и следовательно,

Это равенство должно выполняться при сложении по модулю 2. Следовательно, при целочисленном сложении при каждом в левой части должно получаться четное число:

для некоторых чисел Левая часть не меняется при замене на Следовательно, Таким образом, суммирование по дает

для некоторого . Наконец, левую часть можно переупорядочить. Положим в первом слагаемом и во втором; тогда

что вырождается в

Так как двоичные компоненты отличны от нуля в позициях, отсюда следует, что

В силу четности это означает, что кратно 4, что и доказывает лемму.

Теперь можно перейти к доказательству следующей теоремы.

Теорема 5.8.3. Код Голея является совершенным кодом, исправляющим три ошибки.

Доказательство. Как уже было указано в начале этого параграфа, необходимо только доказать, что минимальное расстояние равно по меньшей мере 7. В силу леммы 5.8.1 оно равно по меньшей мере 5, а в силу леммы 5.8.2 оно не может быть равно 6. Таким образом, необходимо только доказать, что код не содержит слов веса 5.

Рассмотрим кодовое слово в действительности так как Таким образом, коду принадлежит слово, все компоненты которого равны 1. Прибавление этого кодового слова к любому кодовому слову веса дает кодовое слово веса Тогда, согласно лемме 5.8.2, в коде не содержится слов с весами, равными 21, 17, 13, 9, 5 и 1; в частности, не содержится слов веса 5. Теорема доказана.

Отметим, что из доказательства теоремы следует также, что все веса слов в коде Голея исчерпываются числами 0, 7, 8, 11, 12, 15, 16 и 23. Просчитанное на ЭВМ число слов каждого веса приведено в табл. 5.3.

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

Таблица 5.3 (см. скан) Веса слов кода Голея