Глава 20. Коды Голея

20.1. ВВЕДЕНИЕ

В этой главе мы завершим изучение кодов Голея, показав, что их группами автоморфизмов являются группы Матье и что эти коды единственны. Этих важных кодов всего четыре: [23, 12, 7] и [24, 12, 8] двоичные коды и [11, 6, 5] и [12, 6, 6] троичные коды, обозначенные через соответственно.

Свойства двоичных кодов Голея. Мы начнем с кода (а не с кода 23), так как его группа автоморфизмов больше и, следовательно, он является более фундаментальным. Код [24, 12, 8] может быть определен либо с помощью любой из порождающих матриц, приведенных на рис. 2.13 и в выражениях (16.41), (16.48) или (20.6), либо с помощью конструкции (теорема 12 гл. 18), либо добавлением общей проверки на четность к коду Код 4 самодуален (лемма 18 гл. 2 или теорема 7 гл. 16), веса всех его кодовых слов делятся на 4 (лемма 19 гл. 2, теорема 8 гл. 16), и его весовой спектр равен:

Слова веса 8 кода 24 образуют блоки системы Штейнера S(5, 8, 24) (следствие 23 гл. 2; см. также следствие 25 и теорему 26 гл. 2). Эти кодовые слова называются октадами, и это же название используется также для множества номеров тех восьми координат, в которых кодовое слово отлично от нуля. Пусть октада; обозначим через число октад, содержащих элементы но не содержащих Эти числа не зависят от выбора октады О (теорема 10 гл. 2) и приведены в виде таблицы на рис. 2.14. Ниже мы покажем (теорема 9), что система Штейнера единственна. Так как существует порождающая матрица кода все строки которой имеют вес 8, то отсюда следует, что октады системы порождают код 24- Этот факт используется в § 20.6 для доказательства того, что и сам код единствен (теорема 14). Кодовые слова веса 12 кода 324 называются додекадами.

Группа автоморфизмов кода содержит группу (теорема 10 гл. 16), но на самом деле равна гораздо большей группе Матье (теорема 1). Группа Матье представляет собой -транзитивную группу порядка и она порождается группой и дополнительной перестановкой задаваемой выражением

Совершенный [23, 12, 7]-код может быть получен вычеркиванием одной координаты из кода (не имеет значения, какой согласно следствию 11 гл. 16) или как квадратично вычетный код, порождающий идемпотент которого равен любому из многочленов в выражении (16.10), а порождающий многочлен задается выражением (16.4). Весовой спектр этого кода имеет вид:

Слова веса 7 кода образуют блоки системы Штейнера ), и эти слова порождают код 2з- Как код 23, так и система S(4, 7, 23) единственны (следствие 16 и упражнение (14)).

Полная группа автоморфизмов кода 23 представляет собой группу Матье (следствие 8). Она является -транзитивной группой порядка

Алгоритмы декодирования для этих кодов описаны в § 16.9.

Свойства троичных кодов Голея. Код [12, 6, 6] может быть построен либо с помощью любой из порождающих матриц, приведенных в выражениях (16.25), (16.61) или (20.13), либо добавлением общей проверки на четность к коду Код самодуален (теорема 7 гл. 16), и поэтому веса всех слов этого кода делятся на 3. Минимальное расстояние кода равно 6 (по теореме 1 гл. 16), следовательно, весовая функция Хэмминга и полная весовая функция определяются соотношением (19.6). Опорные множества (ненулевые позиции) кодовых слов веса 6 образуют 132 блока системы Штейнера ) (см. рис. 16.9). И код и система ) единственны (теорема 20 и упражнение (18)).

Группа автоморфизмов этого кода гл. 16) содержит группу, изоморфную (теорема 12 гл. 16), но на самом деле она изоморфна гораздо большей группе Матье (теорема 18). Эта группа является -транзитивной группой порядка

Совершенный -код может быть получен либо вычеркиванием одной координаты из кода (снова не имеет значения, какой), либо как квадратично-вычетный код, порождающий идемпотент и порождающий многочлен которого задаются выражениями (16.5) и (16.16). Весовая функция Хэмминга и полная весовая функция кода приведены в работе Мэллоуса и др. [892]. Опорные множества кодовых слов веса 5 образуют блоки системы Штейнера ). Код и система S(4, 5, 11) единственны (следствие 21 и упражнение (18)).