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

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

Определение. Расширенный код Голея имеет порождающую матрицу, показанную на рис. 2.13.

Рис. 2.13. Порождающая матрица расширенного кода Голея Столбцы перенумерованы следующим образом: размера в правой части рисунка представляет собой матрицу

Двоичная -матрица находящаяся в правой части этой порождающей матрицы, получается из матрицы Адамара типа Пейли (см. рис. 2.1 и 2.5). Отсюда сразу следует, что сумма любых двух строк матрицы имеет вес 6. Следовательно, сумма любых двух строк матрицы имеет вес 8.

Лемма 18. Код § 24 является самодуальным; Доказательство. Если две (не обязательно различные) строки то Следовательно, каждая строка матрицы ортогональна всем другим строкам, и поэтому Но ранг матрицы равен 12, поэтому код 24 имеет размерность 12 и, следовательно,

Лемма Каждое кодовое слово кода 24 имеет вес, кратный 4.

(ii). Код 24 содержит кодовое слово Доказательство. Утверждение (i) совпадает с упражнением (38) из гл. 1. Для доказательства утверждения (ii) надо сложить все строки матрицы

Лемма 20. Код 24 инвариантен относительно перестановки координат которая меняет местами две половины кодового слова. Более точно: если код 24 содержит кодовое слово где то он также содержит и кодовое слово где

Доказательство. Перестановка переводит строку с номером 0 матрицы в последовательность

, которая, как легко проверить, является суммой строк с номерами 0, 2, 6, 7, 8, 10, 11 и, следовательно принадлежит коду. Подобным образом поступим со строками матрицы имеющими номера от 1 до 10. Последнюю строку перестановка переводит в последовательность 112012, которая представляет собой дополнение последней строки и поэтому по лемме 19 принадлежит коду.

Замечание. Из этой леммы вытекает, что если код 24 содержит кодовое слово с весами то он также содержит кодовое слово с весами

По лемме 19 возможными весами кодовых слов в коде § 24 являются числа 0, 4, 8, 12, 16, 20, 24.

Если вектор и имеет вес 20, то вектор и имеет вес 4. Мы покажем сейчас, что кодовых слов веса 4 нет в коде и, следовательно, нет слов веса 20.

Лемма 21. Код 24 не содержит кодовых слов веса 4. Доказательство. Для любого кодового слова из 24 получаем, что По лемме 20 мы можем предположить, что кодовое слово веса 4 принадлежит одному из следующих двух типов:

Условие (1) невозможно, так как если то или 12. Условие (2) также невозможно, ибо если то вектор равен сумме одной или двух строк с прибавлением, возможно, последней строки. В каждом из этих случаев согласно абзацу, предшествующему лемме 18.

Таким образом, в коде 24 встречаются веса 0, 8, 12, 16, 24. Обозначим через - число кодовых слов веса Тогда Каждой левой части кодового слова соответствуют две возможные правые части Если то (в силу леммы 21) и (иначе , что снова противоречит лемме 21), так что или 12. Если то подобными же рассуждениями получаем, что Продолжая таким образом, мы получим следующие возможности для весового распределения слов в коде

По лемме 20 число а равно числу кодовых векторов типа которое равно

Следовательно, и поэтому Таким образом, мы показали, что весовой спектр кода 24 имеет вид

Теорема 22. Любой двоичный вектор веса 5 и длины 24 покрывается точно одним кодовым словом веса 8 из

Доказательство. Предположим, что вектор веса 5 покрывается двумя кодовыми словами веса 8; тогда что приводит к противоречию. Кроме того, каждое кодовое слово веса

8 покрывает векторов веса 5, которые все различны, и, значит,

Следствие 23. В расширенном коде Голея кодовые слова веса 8 образуют систему Штейнера . Отсюда согласно следствию 14 получаем системы Штейнера .

Условимся кодовые слова веса 8 и 12 в коде называть соответственно октадами и додекадами.

Теорема 24. Индексы блоковых пересечений для системы Штейнера, образованной октадами, приведены на рис. 2.14.

Рис. 2.14. Индексы блоковых пересечений схемы, образованной октадами расширенного кода Голея

Следствие 25. Кодовые слова веса 16 в коде 24 образуют -схему, и соответствующий треугольник Паскаля получается отражением рис. 2.14 относительно середины.

Доказательство. Данная схема является дополнительной к схеме, образованной октадами.

Теорема 26. В коде 24 додекады образуют -схему. Предположим, что элементы образуют октаду. Временно злоупотребляя используемыми обозначениями, положим равным числу додекад, содержащих и не содержащих элементов для всех значений Тогда эти параметры изображены на рисю 2.15.

Доказательство. Покажем сначала, что Действительно, имеется очевидное 1-1-соответствие между додекадами, содержащими элементы (которые не могут содержать или и октадами, содержащими но не содержащими элементов Поэтому согласно рис. 2.14 параметр

Отсюда следует, что до декад содержат элементы так что Поэтому додекады образуют -схему. Теперь оставшуюся часть таблицы можно заполнить с помощью теоремы 9 и свойства Паскаля.

Рис. 2.15. Обобщенные индексы блоковых пересечений схемы, образованной додекадами кода Голея и

В гл. 6 мы дадим достаточное условие того, что все кодовые слова фиксированного веса произвольного кода образуют -схему, которое включает эти результаты как частный случай.

Упражнения. (12). Показать, что код Голея приводит также к следующим схемам:

(13). Показать, что 4096 смежных классов кода имеют следующие весовые спектры:

Определение. Нерасширенный код Голея длины получается выбрасыванием последней координаты из каждого

кодового слова кода . В гл. 16 мы увидим, что выбрасывание любой координаты из кода приводит к эквивалентному коду.

Теорема 27. Код является [23, 12, 7]-кодом с весовым спектром:

Доказательство. Доказательство следует непосредственно из рис. 2.14. Например, кодовые слова веса 7 в коде представляют собой октады кода , у которых последняя координата равна 1; число их равно

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

Доказательство. Так как минимальное расстояние кода равно 7, то все смежные классы с лидерами веса не более 3 отличны друг от друга (по теореме 2 гл. 1). Число таких смежных классов равно

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