Трійковий код Голея

Трійкові коди Голея, в теорії кодування — це два тісно пов'язаних коди з корекцією помилок. Загалом, код відомий за назвою «трійковий код Голея» — це код $[11,6,5]_{3}$, який, по суті є лінійним кодом у трійковому алфавіті; відносна відстань коду настільки велика, настільки це можливо для трійкового коду, і, виходячи з цього, трійковий код Голея — це досконалий код.

Розширений трійковий код Голея — це [12, 6, 6] лінійний код, отриманий шляхом додавання контрольного числа з нульовою сумою до коду [11, 6, 5]. У скінченній теорії груп розширений трійковий код Голея іноді називають трійковим кодом Голея.

Властивості

Трійковий код Голея

Трійковий код Голея складається з 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 ставкам і гарантує саме одну ставку з якнайбільше двома неправильними результатами.

Набір кодових слів з вагою Геммінга 5 — це 3-(11,5,4) блок-схема.

Розширений трійковий код Голея

Повний ваговий лічильник розширеного трійкового коду — це:

$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).

Історія

Трійковий код Голея був винайдений Марселем Голеєм 1949 року. Але незалежно він був відкритий двома роками раніше фінським прихильником ставок на футбол Джуані Віртакаліо, який опублікував статтю в 1947 році у 27, 28 і 33 виданні футбольного журналу Veikkaaja. (Barg, 1993, p.25)

Див. також

• Двійковий код Голея
• Граф Берлекемпа — ван Лінта — Зейделя

Примітки

• Barg, Alexander (1993), At the dawn of the theory of codes, Mathematical Intelligencer, 15 (1): 20—26, doi:10.1007/BF03025254, ISSN 0343-6993, MR 1199273
• M.J.E. Golay, Notes on digital coding, Proceedings of the I.R.E. 37 (1949) 657
• I.F. Blake (ed.), Algebraic Coding Theory: History and Development, Dowden, Hutchinson & Ross, Stroudsburg 1973
• J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, Springer, New York, Berlin, Heidelberg, 1988.
• Robert L. Griess, Twelve Sporadic Groups, Springer, 1998.
• G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, Elsevier (1997) ISBN 0-444-82511-8
• Th. M. Thompson, From Error Correcting Codes through Sphere Packings to Simple Groups, Математична асоціація Америки 1983, ISBN 0-88385-037-0