Троичные коды Голея

Троичные коды Голея — это два тесно связанных исправляющих ошибки кода. Код, известный просто как троичный код Голея — это $[11,6,5]_{3}$-код, то есть это линейный код над троичным алфавитом. Относительное расстояние кодов максимально для троичных кодов, а следовательно, троичный код Голея является совершенным кодом. Расширенный троичный код Голея является линейным кодом [12, 6, 6], который получается путём добавления контрольного числа (дающего нулевую сумму) к коду [11, 6, 5]. В Теории конечных групп расширенный троичный код Голея иногда называется просто троичным кодом Голея.

Свойства

Троичный код Голея

Совершенный троичный код Голея
Назван в честь	Марсель Голей
Тип	блочный код
Длина блока	11
Длина сообщения	6
Доля	6/11 ~ 0.545
Расстояние	5
Размер алфавита	3
Обозначение	$[11,6,5]_{3}$

Троичный код Голея состоит из 3⁶ = 729 кодовых слов. Его матрица проверки на чётность

$\left[{\begin{array}{ccccccccccc}1&1&1&2&2&0&1&0&0&0&0\\1&1&2&1&0&2&0&1&0&0&0\\1&2&1&0&1&2&0&0&1&0&0\\1&2&0&1&2&1&0&0&0&1&0\\1&0&2&2&1&1&0&0&0&0&1\end{array}}\right].$

Любое из двух различных кодовых слов отличаются по меньшей мере в 5 позициях. Любое троичное слово длины 11 имеет расстояние Хэмминга, не превосходящее 2 ровно от одного кодового слова. Код можно построить как квадратично-вычетный код длины 11 над конечным полем F₃.

Используемый в футбольных тотализаторах с 11 играми, троичный код Голея соответствует 729 ставкам и гарантирует ровно одну ставку с максимум 2 неправильными оценками.

Множество кодовых слов с весом Хэмминга 5 является блок-схемой 3-(11,5,4).

Расширенный троичный код Голея

Расширенный троичный код Голея
Назван в честь	Марсель Голей
Тип	блочный код
Длина блока	12
Длина сообщения	6
Доля	6/12 = 0.5
Расстояние	6
Размер алфавита	3
Обозначение	$[12,6,6]_{3}$

Полный весовой энумератор расширенного троичного кода Голея

$x^{12}+y^{12}+z^{12}+22\left(x^{6}y^{6}+y^{6}z^{6}+z^{6}x^{6}\right)+220\left(x^{6}y^{3}z^{3}+y^{6}z^{3}x^{3}+z^{6}x^{3}y^{3}\right).$

Группой автоморфизмов расширенной троичной группы кодов является 2.M₁₂, где M₁₂ — группа Матьё M12.

Расширенный троичный код Голея можно построить как строки матрицы Адамара порядка 12 над полем F₃.

Рассмотрим все кодовые слова расширенного кода, которые имеют шесть ненулевых цифр. Множества позиций, в которых эти ненулевые цифры оказываются, образуют систему Штейнера S(5, 6, 12).

История

Троичный код Голея открыл Голей. Код независимо открыл двумя годами ранее финский энтузиаст футбольных тотализаторов Юхани Виртакаллио, который опубликовал его в 1947 году в выпусках 27, 28 и 33 футбольного журнала Veikkaaja.

См. также

• Двоичный код Голея

Литература

• Alexander Barg. At the dawn of the theory of codes // The Mathematical Intelligencer. — 1993. — Т. 15, вып. 1. — С. 20–26. — ISSN 0343-6993. — doi:10.1007/BF03025254.
• Golay M.J.E. Notes on digital coding // Proceedings of the I.R.E.. — 1949. — Т. 37. — С. 657.
• Algebraic Coding Theory: History and Development / Blake I.F. (ed.). — Stroudsburg: Dowden, Hutchinson & Ross, 1973.
• J. H. Conway, N. J. A. Sloane. Sphere Packings, Lattices and Groups. — New York, Berlin, Heidelberg: Springer, 1988.
• Robert L. Griess. Twelve Sporadic Groups. — Springer, 1998.
• Cohen G., Honkala I., Litsyn S., Lobstein A. Covering Codes. — Elsevier, 1997. — ISBN 0-444-82511-8.
• Th. M. Thompson. From Error Correcting Codes through Sphere Packings to Simple Groups. — The Mathematical Association of America, 1983. — ISBN 0-88385-037-0.