Trójskładnikowy kod Golaya

Doskonały trójskładnikowy kod Golaya
Nazwany po	Marcel JE Golay
Klasyfikacja
Typ	Liniowy kod blokowy
Długość bloku	11
Długość wiadomości	6
Wskaźnik	6/11 ~ 0,545
Dystans	5
Rozmiar alfabetu	3
Notacja	${\ Displaystyle [11,6,5] _ {3}}$ -kod

Rozszerzony trójskładnikowy kod Golaya
Nazwany po	Marcel JE Golay
Klasyfikacja
Typ	Liniowy kod blokowy
Długość bloku	12
Długość wiadomości	6
Wskaźnik	6/12 = 0,5
Dystans	6
Rozmiar alfabetu	3
Notacja	${\ Displaystyle [12,6,6] _ {3}}$ -kod

W teorii kodowania trójskładnikowe kody Golaya są dwoma blisko spokrewnionymi kodami korygującymi błędy . Kod ogólnie znany po prostu jako $Golaya$ to -kod znaczy to liniowy nad alfabetem ; względna odległość kodu jest tak duża, jak to tylko możliwe dla kodu trójskładnikowego, a zatem trójskładnikowy kod Golaya jest doskonały kod . Rozszerzony trójskładnikowy kod Golaya to liniowy kod [12, 6, 6] uzyskany przez dodanie cyfry kontrolnej o sumie zerowej do kodu [11, 6, 5]. W teorii grup skończonych rozszerzony trójskładnikowy kod Golaya jest czasami określany jako trójskładnikowy kod Golaya.

Nieruchomości

Trójskładnikowy kod Golaya

Trójskładnikowy kod Golaya składa się z 3 ⁶ = 729 słów kodowych. Jego macierz kontroli parzystości to

${\ Displaystyle \ lewo [{\ zacząć {tablica} {cccccc| ccccc} 2&2&2&1&1&0&1&0&0&0&0\\2&2&1&2&0&1&0&1&0&0&0\\2&1&2&0&2&1&0&0&1&0&0\\2&1&0&2&1&2&0&0&0&1&0\\2&0&1 &1&2&2&0&0&0&0&1\end{array}}\right].}$

Dowolne dwa różne słowa kodowe różnią się co najmniej 5 pozycjami. Każde potrójne słowo o długości 11 ma odległość Hamminga co najwyżej 2 od dokładnie jednego słowa kodowego. Kod można również skonstruować jako _kod reszty kwadratowej o długości 11 nad skończonym ciałem F3 ( tj. polem Galois GF(3) ).

Używany w puli piłkarskiej z 11 meczami, trójskładnikowy kod Golay odpowiada 729 zakładom i gwarantuje dokładnie jeden zakład z maksymalnie 2 błędnymi wynikami.

Zbiór słów kodowych o wadze Hamminga 5 to projekt 3-(11,5,4) .

Macierz generatora podana przez Golaya (1949, tabela 1.) to

${\ Displaystyle \ lewo [{\ zacząć {tablica} {cccccc| ccccc} 1&0&0&0&0&0&1&1&1&1&1\\0&1&0&0&0&0&1&1&2&2&0\\0&0&1&0&0&0&1&2&1&0&2\\0&0&0&1&0&0&2&1&0&1&2\\0&0&0 &0&1&0&2&0&1&2&1\\0&0&0&0&0&1&0&2&2&1&1\\\koniec{tablica}}\prawo].}$

Grupą automorfizmu ( oryginalnego) trójskładnikowego kodu Golaya jest grupa Mathieu M11 , która jest najmniejszą ze sporadycznych grup prostych.

Rozszerzony trójskładnikowy kod Golaya

Pełny moduł wyliczający wagi rozszerzonego trójskładnikowego kodu Golaya to

${\ Displaystyle x ^ {12} + y ^ {12} + z ^ {12} + 22 \ lewo (x ^ {6} y ^ {6} + y ^ {6} z ^ {6} + z ^ { 6}x^{6}\prawo)+220\lewo(x^{6}y^{3}z^{3}+y^{6}z^{3}x^{3}+z^{ 6}x^{3}y^{3}\prawo).}$

Grupa automorfizmu rozszerzonego trójskładnikowego kodu Golaya to 2. M ₁₂ , gdzie M ₁₂ to grupa Mathieu M12 .

Rozszerzony trójskładnikowy kod Golaya można skonstruować jako rozpiętość wierszy macierzy Hadamarda rzędu 12 nad ciałem F ₃ .

Rozważ wszystkie słowa kodowe rozszerzonego kodu, które mają tylko sześć niezerowych cyfr. Zbiory pozycji, w których występują te niezerowe cyfry, tworzą system Steinera S (5, 6, 12).

Macierz generatora dla rozszerzonego trójskładnikowego kodu Golaya to

${\ Displaystyle \ lewo [{\ rozpocząć {tablica} {ccccccccccccc} 1&0&0&0&0&0&|&0&1&1&1&1&1\\0&1&0&0&0&0&|&1&0&1&2&2&1\\0&0&1&0&0&0&|&1&1&0&1&2&2\\0&0&0&1&0&0&|&1& 2&1&0&1&2\\0&0&0&0&1&0&|&1&2&2&1&0&1\\0&0&0&0&0&1&|&1&1&2&2&1&0\\\koniec{tablica} }\right]=[I_{6}|B].}$

Odpowiednia macierz kontroli parzystości dla tej macierzy generatora to ${\ Displaystyle [-B | I_ {6}] ^ {T}}$ , gdzie ${\ displaystyle T}$ oznacza transpozycję macierzy.

Alternatywną macierzą generatora dla tego kodu jest

${\ Displaystyle \ lewo [{\ rozpocząć {tablica} {rrrrrrrrrrrrrr} 1&0&0&0&0&0&|&0&1&1&1&1&1\\0&1&0&0&0&0&|&1&0&1&-1&-1&1\\0&0&1&0&0&0&|&1&1&0&1&-1&-1\\0&0&0&1&0&0& |&1&-1&1&0&1&-1\\0&0&0&0&1&0&|&1& -1&-1&1&0&1\\0&0&0&0&0&1&|&1&1&-1&-1&1&0\\\end{tablica}}\right]=[I_{6}|B_{alt}].}$

A jej macierz kontroli parzystości to ${\ Displaystyle [-B_ {alt}|I_ {6}] ^ {T}}$ .

Trzy elementy podstawowego pola skończonego są tutaj reprezentowane przez ${\ Displaystyle \ {0,1, -1 \}}$ , a nie przez ${\ Displaystyle \ {0, 1,2\}}$ . Rozumie się $1$ tj . odwrotność ${\ Displaystyle -2 = (-1) + (-1) = 1}$ . Iloczyny tych elementów pola skończonego są identyczne z iloczynami liczb całkowitych. Sumy wierszy i kolumn są oceniane modulo 3.

Liniowe kombinacje lub dodawanie wektorów rzędów macierzy daje wszystkie możliwe słowa zawarte w kodzie. Nazywa się to rozpiętością rzędów . Iloczyn wewnętrzny dowolnych dwóch wierszy macierzy generatora zawsze będzie sumował się do zera. O tych rzędach lub wektorach mówi się, że są ortogonalne .

Iloczyn macierzowy generatora i macierzy kontroli parzystości, ${\ Displaystyle [I_ {6} | B_ {alt}] \, [-B_ {alt} | I_ {6}] ^ {T}}$ 6 $\ Displaystyle 6 \ razy 6 }$ macierz wszystkich zer i celowo. Rzeczywiście, jest to przykład samej definicji dowolnej macierzy kontroli parzystości w odniesieniu do jej macierzy generatora.

Historia i zastosowania

Trójskładnikowy kod Golaya został opublikowany przez Golaya ( 1949 ). Została niezależnie odkryta dwa lata wcześniej przez fińskiego entuzjastę bilarda piłkarskiego Juhani Virtakallio, który opublikował ją w 1947 roku w numerach 27, 28 i 33 magazynu piłkarskiego Veikkaaja . ( Barg 1993 , s.25)

Wykazano, że trójskładnikowy kod Golaya jest przydatny w podejściu do odpornych na uszkodzenia komputerów kwantowych , znanym jako destylacja stanu magicznego .

Zobacz też

• Wykres Berlekampa – van Linta – Seidela
• Binarny kod Golaya

•   Barg, Alexander (1993), „U zarania teorii kodów”, The Mathematical Intelligencer , 15 (1): 20–26, doi : 10.1007 / BF03025254 , MR 1199273
•   Golay, MJE (czerwiec 1949), „Notes on digital coding” (PDF) , Proceedings of the IRE , 37 : 657, MR 4021352 , zarchiwizowane z oryginału (PDF) w dniu 19 kwietnia 2015 r.

Dalsza lektura

• Blake, IF (1973), Algebraic Coding Theory: History and Development , Stroudsburg, Pensylwania: Dowden, Hutchinson & Ross
•    Conway, J.H .; Sloane, NJA (1999), Opakowania sferyczne, kraty i grupy , Grundlehren der Mathematischen Wissenschaften, tom. 290 (wyd. 3), Nowy Jork: Springer-Verlag, doi : 10.1007/978-1-4757-6568-7 , ISBN 0-387-98585-9 , MR 1662447
•    Griess, Robert L. Jr. (1998), Dwanaście grup sporadycznych , Springer Monografie z matematyki , Berlin: Springer-Verlag, doi : 10.1007/978-3-662-03516-0 , ISBN 3-540-62778-2 , MR 1707296
•    Cohen, Gerard; Honkala, Iiro; Litsyn, Szymon; Lobstein, Antoine (1997), Kody obejmujące , North-Holland Mathematical Library, tom. 54, Amsterdam: Holandia Północna, ISBN 0-444-82511-8 , MR 1453577
•    Thompson, Thomas M. (1983), Od kodów korekcji błędów przez opakowania sferyczne do prostych grup , Monografie matematyczne Carus, tom. 21, Washington, DC: Mathematical Association of America, ISBN 0-88385-023-0 , MR 0749038