Ternary Golay kód - Ternary Golay code
Perfektní ternární kód Golay | |
---|---|
Pojmenoval podle | Marcel J. E. Golay |
Klasifikace | |
Typ | Lineární kód bloku |
Délka bloku | 11 |
Délka zprávy | 6 |
Hodnotit | 6/11 ~ 0.545 |
Vzdálenost | 5 |
Velikost abecedy | 3 |
Zápis | -kód |
Rozšířený ternární kód Golay | |
---|---|
Pojmenoval podle | Marcel J. E. Golay |
Klasifikace | |
Typ | Lineární kód bloku |
Délka bloku | 12 |
Délka zprávy | 6 |
Hodnotit | 6/12 = 0.5 |
Vzdálenost | 6 |
Velikost abecedy | 3 |
Zápis | -kód |
v teorie kódování, ternární Golay kódy jsou dva úzce spjaté kódy opravující chyby.Kód obecně známý jednoduše jako ternární Golay kód je -kód, to znamená, že je lineární kód přes trojice abeceda; the relativní vzdálenost kódu je tak velký, jak jen to může být pro ternární kód, a proto je ternární Golayův kód perfektní kód.v prodloužený ternární Golayův kód je [12, 6, 6] lineární kód získáno sečtením nulového součtu kontrolní číslice ke kódu [11, 6, 5]. Konečný teorie skupin, rozšířený ternární Golayův kód se někdy označuje jako ternární Golayův kód.[Citace je zapotřebí ]
Vlastnosti
Ternary Golay kód
Ternární Golay kód se skládá ze 36 = 729 kódových slov. Své paritní kontrolní matice je
Jakákoli dvě různá kódová slova se liší alespoň na 5 pozicích. Každé ternární slovo o délce 11 má a Hammingova vzdálenost maximálně 2 z přesně jednoho kódového slova. Kód lze také zkonstruovat jako kvadratický kód reziduí o délce 11 přes konečné pole F3 (tj., Galois Field GF (3) ).
Používá se v fotbalový bazén s 11 hrami odpovídá ternární kód Golay 729 sázek a zaručuje přesně jednu sázku s maximálně 2 špatnými výsledky.
Sada kódových slov s Hammingovou váhou 5 je 3- (11,5,4) design.
The matice generátoru dané Golayem (1949, tabulka 1.) je
The automorfická skupina (původního) ternárního kódu Golay je Skupina Mathieu M11, což je nejmenší ze sporadických jednoduchých skupin.
Rozšířený ternární kód Golay
The kompletní enumerátor hmotnosti rozšířeného ternárního kódu Golay je
The automorfická skupina rozšířeného ternárního kódu Golay je 2.M12, kde M12 je Skupina Mathieu M12.
Rozšířený ternární Golayův kód lze zkonstruovat jako rozpětí řádků a Hadamardova matice objednávky 12 přes pole F3.
Zvažte všechna kódová slova rozšířeného kódu, která mají pouze šest nenulových číslic. Sady pozic, na kterých se tyto nenulové číslice vyskytují, tvoří Steinerův systém S (5, 6, 12).
A matice generátoru pro rozšířený ternární kód Golay je
Odpovídající matice kontroly parity pro tuto matici generátoru je , kde označuje přemístit matice.
Alternativní matice generátoru pro tento kód je
A jeho matice kontroly parity je .
Tři prvky základního konečného pole jsou zde reprezentovány , spíše než . Rozumí se tomu také (tj., aditivní inverzní k 1) a . Produkty těchto prvků konečného pole jsou totožné s produkty celých čísel. Součet řádků a sloupců se vyhodnocuje modulo 3.
Lineární kombinace, nebo vektorové přidání, řádků matice vytváří vše možné slova obsažené v kódu. Toto se označuje jako rozpětí řádků. Vnitřní součin libovolných dvou řádků matice generátoru se vždy sečte na nulu. O těchto řádcích nebo vektorech se říká, že jsou ortogonální.
Maticový produkt generátoru a matice kontroly parity, , je matice všech nul a podle záměru. Ve skutečnosti je to příklad samotné definice jakékoli matice kontroly parity s ohledem na její matici generátoru.
Historie a aplikace
Ternární Golayův kód publikoval Golay (1949 ). To bylo nezávisle objeveno o dva roky dříve Finština nadšenec fotbalového bazénu Juhani Virtakallio, který jej publikoval v roce 1947 v číslech 27, 28 a 33 fotbalu časopis Veikkaaja. (Barg 1993, str.25)
Ukázalo se, že ternární kód Golay je užitečný pro přístup k toleranci chyb kvantové výpočty známý jako destilace magického stavu.[1]
Viz také
Reference
- Barg, Alexander (1993), „Na úsvitu teorie kódů“, Matematický zpravodaj, 15 (1): 20–26, doi:10.1007 / BF03025254, PAN 1199273
- Golay, M. J. E. (Červen 1949), „Poznámky k digitálnímu kódování“, Sborník IRE, 37: 657, PAN 4021352
Další čtení
- Blake, I.F. (1973), Algebraická teorie kódování: Historie a vývoj, Stroudsburg, Pensylvánie: Dowden, Hutchinson & Ross
- Conway, J. H.; Sloane, N. J. A. (1999), Balení koulí, svazy a skupinyGrundlehren der Mathematischen Wissenschaften, 290 (3. vyd.), New York: Springer-Verlag, doi:10.1007/978-1-4757-6568-7, ISBN 0-387-98585-9, PAN 1662447
- Griess, Robert L. Jr. (1998), Dvanáct sporadických skupinSpringer Monografie z matematiky, Berlín: Springer-Verlag, doi:10.1007/978-3-662-03516-0, ISBN 3-540-62778-2, PAN 1707296
- Cohen, Gérard; Honkala, Iiro; Litsyn, Simon; Lobstein, Antoine (1997), Krycí kódyMatematická knihovna v Severním Holandsku, 54, Amsterdam: Severní Holandsko, ISBN 0-444-82511-8, PAN 1453577
- Thompson, Thomas M. (1983), Od opravy chyb přes balíky koulí až po jednoduché skupinyMatematické monografie Carus, 21, Washington, DC: Mathematical Association of America, ISBN 0-88385-023-0, PAN 0749038
- ^ Prakash, Shiroman (září 2020). "Magická stavová destilace s ternárním Golayovým kódem". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 476 (2241): 20200187. arXiv:2003.02717. doi:10.1098 / rspa.2020.0187.