Троичные коды Голея (Mjkncudy tk;d Iklyx)

Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

[править | править код]

Литература

[править | править код]
  • 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.