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

Трійкові коди Голея, в теорії кодування — це два тісно пов'язаних коди з корекцією помилок. Загалом, код відомий за назвою «трійковий код Голея» — це код $[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(x^6{y}^6+y^6{z}^6+z^6{x}^6)+220(x^6{y}^3{z}^3+y^6{z}^3{x}^3+z^6{x}^3{y}^3).$

Автоморфізм груп розширеного трійкового коду Голея — це 2.M₁₂, де M₁₂ являє собою Шаблон:Нп.

Розширений код Голлея може бути збудований як пропуск рядків матриці Адамара 12-го порядку у полі F₃.

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

Історія

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

Див. також

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

Примітки

• Шаблон:Citation
• M.J.E. Golay, Notes on digital coding, Proceedings of the Шаблон:Iw 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.
• Шаблон:Iw, Twelve Sporadic Groups, Springer, 1998.
• G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering Codes, Elsevier (1997) Шаблон:ISBN
• Th. M. Thompson, From Error Correcting Codes through Sphere Packings to Simple Groups, Математична асоціація Америки 1983, Шаблон:ISBN