Binarny kod Golaya

macierz generatora
binarnego kodu Golaya
Nazwany po	Marcel JE Golay
Klasyfikacja
Typ	Liniowy kod blokowy
Długość bloku	24
Długość wiadomości	12
Wskaźnik	12/24 = 0,5
Dystans	8
Rozmiar alfabetu	2
Notacja	${\ Displaystyle [24,12,8] _ {2}}$ -kod

Idealny binarny kod Golaya
Nazwany po	Marcel JE Golay
Klasyfikacja
Typ	Liniowy kod blokowy
Długość bloku	23
Długość wiadomości	12
Wskaźnik	23/12 ~ 0,522
Dystans	7
Rozmiar alfabetu	2
Notacja	${\ Displaystyle [23,12,7] _ {2}}$ -kod

W matematyce i inżynierii elektronicznej binarny kod Golaya jest rodzajem liniowego kodu korygującego błędy używanego w komunikacji cyfrowej . Binarny kod Golaya, wraz z trójskładnikowym kodem Golaya , ma szczególnie głęboki i interesujący związek z teorią skończonych grup sporadycznych w matematyce. Kody te zostały nazwane na cześć Marcela JE Golaya , którego artykuł przedstawiający je z 1949 roku został nazwany przez ER Berlekampa „najlepszą pojedynczą opublikowaną stroną” w teorii kodowania.

Istnieją dwa ściśle powiązane binarne kody Golaya. Rozszerzony binarny kod Golaya , G ₂₄ (czasami nazywany po prostu „kodem Golaya” w teorii grup skończonych) koduje 12 bitów danych w 24-bitowym słowie w taki sposób, że każdy 3-bitowy błąd może zostać poprawiony lub dowolny 7-bitowy kod można wykryć błędy bitowe. Drugi, doskonały binarny kod Golaya , G ₂₃ , ma słowa kodowe o długości 23 i jest uzyskiwany z rozszerzonego binarnego kodu Golaya przez usunięcie jednej współrzędnej (odwrotnie, rozszerzony binarny kod Golaya jest uzyskiwany z doskonałego binarnego kodu Golaya przez dodanie bit parzystości ). W standardowej notacji kodowania kody mają parametry [24, 12, 8] i [23, 12, 7], odpowiadające odpowiednio długości słowa kodowego, wymiarowi kodu i minimalnej odległości Hamminga między dwoma słowami kodowymi.

Definicja matematyczna

W kategoriach matematycznych rozszerzony binarny kod Golaya G24 składa się z 12-wymiarowej liniowej podprzestrzeni W przestrzeni V = F242 ^różnią
_{24 -bitowych słów ,} tak że dowolne dwa różne elementy W się co najmniej 8 współrzędnymi. W nazywamy kodem liniowym, ponieważ jest to przestrzeń wektorowa. W sumie W zawiera 4096 = 2 ¹² elementów.

• Elementy W nazywane są słowami kodowymi . Można je również opisać jako podzbiory zbioru 24 elementów, gdzie dodawanie definiuje się jako różnicę symetryczną podzbiorów.
• W rozszerzonym binarnym kodzie Golaya wszystkie słowa kodowe mają wagi Hamminga 0, 8, 12, 16 lub 24. Słowa kodowe o wadze 8 nazywane są oktadami , a słowa kodowe o wadze 12 nazywane są dodekadami .
• Oktady kodu G ₂₄ są elementami systemu S(5,8,24) Steinera . Jest 759 = 3 × 11 × 23 oktad i 759 ich uzupełnień. Wynika z tego, że jest 2576 = 2 ⁴ × 7 × 23 dwunastolatków.
• Dwie oktady przecinają się (mają wspólne jedynki) we współrzędnych 0, 2 lub 4 w binarnej reprezentacji wektorowej (są to możliwe rozmiary przecięć w reprezentacji podzbioru). Oktada i dodekad przecinają się w 2, 4 lub 6 współrzędnych.
• Aż do ponownego oznakowania współrzędnych, W jest unikalny.

Binarny kod Golaya, G _{23 ,} jest idealnym kodem . Oznacza to, że sfery o promieniu trzech wokół słów kodowych tworzą partycję przestrzeni wektorowej. G ₂₃ jest 12-wymiarową podprzestrzenią przestrzeni F
²³ ₂ .

Grupa automorfizmów doskonałego binarnego kodu Golaya G ₂₃ (oznaczająca podgrupę grupy S ₂₃ permutacji współrzędnych F
²³ ₂ , które pozostawiają niezmiennik G ₂₃ ), to grupa Mathieu ${\ Displaystyle M_ {23}}$ . Grupą automorfizmu rozszerzonego binarnego kodu Golaya jest $.$ Mathieu rzędu 2 × 3 ³ × 5 × 7 × 11 ^× 23 ${\ Displaystyle M_ {24}}$ jest przechodnia na oktadach i na dodekadach. Pozostałe grupy Mathieu występują jako stabilizatory jednego lub kilku elementów W .

Konstrukcje

• ₀ Kod leksykograficzny : Uporządkuj wektory w V leksykograficznie (tj. zinterpretuj je jako 24-bitowe binarne liczby całkowite bez znaku i przyjmij zwykłą kolejność). Począwszy od w = 0 zdefiniuj w ₁ , w ₂ , ..., w ₁₂ stosując regułę, że w _n jest najmniejszą liczbą całkowitą, która różni się od wszystkich liniowych kombinacji poprzednich elementów co najmniej ośmioma współrzędnymi. Wtedy W można zdefiniować jako rozpiętość w ₁ , ..., w ₁₂ .
• Grupa Mathieu : Witt w 1938 roku opublikował konstrukcję największej grupy Mathieu, której można użyć do skonstruowania rozszerzonego binarnego kodu Golaya.
• Kwadratowy kod pozostałości : rozważ zbiór N kwadratowych niereszt (mod 23). Jest to 11-elementowy podzbiór grupy cyklicznej Z / 23Z . Rozważ translacje t + N tego podzbioru. Rozszerz każdą translację do 12-elementowego zestawu S _t dodając element ∞. Wtedy oznakowanie elementów bazowych V przez 0, 1, 2, ..., 22, ∞, W można zdefiniować jako rozpiętość słów S _t wraz ze słowem składającym się ze wszystkich wektorów bazowych. (Doskonały kod uzyskuje się pomijając ∞.)
• Jako kod cykliczny : doskonały kod G ₂₃ można skonstruować poprzez faktoryzację pola binarnego GF (2): $Displaystyle x ^ {23} -1}$ \
  $${\ Displaystyle x ^ {23} -1 = (x-1) (x ^ {11} + x ^ {9} + x ^ {7} + x ^ {6} + x ^ {5} + x + 1 )(x^{11}+x^{10}+x^{6}+x^{5}+x^{4}+x^{2}+1).}$$
  Jest to kod wygenerowany przez ${\ Displaystyle \ lewo (x ^ {11} + x ^ {10} + x ^ {6} +x^{5}+x^{4}+x^{2}+1\prawo)}$ . Do wygenerowania kodu można użyć dowolnego z nieredukowalnych czynników stopnia 11.
• Konstrukcja Turyna z 1967 r., „Prosta konstrukcja binarnego kodu Golaya”, która zaczyna się od kodu Hamminga o długości 8 i nie wykorzystuje reszt kwadratowych mod 23.
• Z systemu Steinera S(5,8,24) , składającego się z 759 podzbiorów 24-zbioru. Jeśli ktoś zinterpretuje wsparcie każdego podzbioru jako słowo kodowe 0-1 o długości 24 (z wagą Hamminga 8), są to „oktady” w binarnym kodzie Golaya. Cały kod Golaya można otrzymać przez wielokrotne pobieranie różnic symetrycznych podzbiorów, czyli dodawanie binarne. Łatwiejszy sposób na zapisanie systemu Steinera wzgl. oktady to Miracle Octad Generator firmy RT Curtis, który wykorzystuje określoną zgodność 1: 1 między 35 partycjami zestawu 8 na dwa zestawy 4 i 35 partycjami skończonej przestrzeni wektorowej ${\ displaystyle \ mathbb {F} _{2}^{4}}$ na 4 płaszczyzny. Obecnie często stosuje się kompaktowe podejście heksakodu Conwaya, które wykorzystuje tablicę kwadratowych komórek 4 × 6.
• Zwycięskie pozycje w matematycznej grze Mogul: pozycja w Mogul to rząd 24 monet. Każda tura polega na przerzucaniu od jednej do siedmiu monet w taki sposób, że najbardziej wysunięta na lewo z odwróconych monet przechodzi od głowy do ogona. Pozycje przegrane to te, na których nie ma legalnego ruchu. Jeśli orzeł zostanie zinterpretowany jako 1, a reszka jako 0, to przejście do słowa kodowego z rozszerzonego binarnego kodu Golaya gwarantuje, że będzie można wymusić wygraną.
• Macierz generatora dla binarnego kodu Golaya to IA , gdzie I to macierz identyczności 12×12, a A to dopełnienie macierzy sąsiedztwa dwudziestościanu .

Wygodna reprezentacja

Wygodnie jest używać formatu „ Miracle Octad Generator ”, ze współrzędnymi w tablicy składającej się z 4 wierszy i 6 kolumn. Dodawanie bierze różnicę symetryczną. Wszystkie 6 kolumn ma taką samą parzystość, która jest równa parzystości w górnym rzędzie.

Podział 6 kolumn na 3 pary sąsiednich tworzy trio . Jest to podział na 3 zestawy oktad. Podgrupa, rzutowa specjalna grupa liniowa PSL(2,7) x S ₃ trio podgrupy M ₂₄ jest użyteczna do generowania bazy. PSL(2,7) permutuje oktady wewnętrznie, równolegle. S ₃ permutuje 3 oktady cieleśnie.

Podstawa zaczyna się od oktadu T:

0 1 1 1 1 1

1 0 0 0 0 0

1 0 0 0 0 0

1 0 0 0 0 0

i 5 podobnych oktad. Suma N wszystkich 6 tych słów kodowych składa się z samych jedynek. Dodanie N do słowa kodowego tworzy jego uzupełnienie.

Griess (s. 59) stosuje etykietowanie:

∞ 0 |∞ 0 |∞ 0

3 2 |3 2 |3 2

5 1 |5 1 |5 1

6 4 |6 4 |6 4

PSL(2,7) jest naturalnie liniową grupą ułamkową generowaną przez (0123456) i (0∞)(16)(23)(45). Cykl 7 działa na T, dając podprzestrzeń zawierającą również elementy bazowe

0 1 1 0 1 0

0 0 0 0 0 0

0 1 0 1 0 1

1 1 0 0 0 0

I

0 1 1 0 1 0

0 1 0 1 0

1 1 1 0 0 0 0

0 0 0 0 0 0

Wynikowa 7-wymiarowa podprzestrzeń ma 3-wymiarową przestrzeń ilorazową po zignorowaniu ostatnich 2 oktad.

Istnieją 4 inne słowa kodowe o podobnej strukturze, które uzupełniają podstawę 12 słów kodowych dla tej reprezentacji W.

W ma podprzestrzeń o wymiarze 4, symetryczną pod PSL(2,7) x S ₃ , rozpiętą przez N i 3 dodekady utworzone z podzbiorów {0,3,5,6}, {0,1,4,6} i {0,1,2,5}.

Praktyczne zastosowania kodów Golaya

Misje kosmiczne NASA

Korekta błędów była kluczowa dla transmisji danych w sondach Voyager 1 i 2, szczególnie dlatego, że ograniczenia pamięci narzucały praktycznie natychmiastowe wyładowywanie danych, nie pozostawiając drugiej szansy. Setki kolorowych zdjęć Jowisza i Saturna podczas ich przelotów w latach 1979, 1980 i 1981 zostałyby przesłane w ramach ograniczonego pasma telekomunikacyjnego. Transmisja obrazu kolorowego wymagała trzy razy więcej danych niż obrazów czarno-białych, więc kod Reeda-Mullera korygujący 7 błędów , który był używany do przesyłania czarno-białych obrazów Marinera, został zastąpiony znacznie wyższą szybkością transmisji danych Golay (24,12 8) kod.

Łączność radiowa

Amerykańskie standardy wojskowe MIL-STD-188 dotyczące automatycznego ustanawiania łącza w systemach radiowych o wysokiej częstotliwości określają użycie rozszerzonego (24,12) kodu Golaya do korekcji błędów w przód .

Zobacz też

• Krata Leecha
• Kod liniowy

Źródła

•    Conway, John Horton ; Sloane, Neil JA (1999), Opakowania sferyczne, kraty i grupy , Grundlehren der Mathematischen Wissenschaften, tom. 290 (wyd. 3), Berlin, Nowy Jork: Springer-Verlag , ISBN 978-0-387-98585-5 , MR 0920369
•   Curtis, RT (1976). „Nowe podejście kombinatoryczne do M ₂₄ ”. Mathematical Proceedings of Cambridge Philosophical Society . 79 (1): 25–42. Bibcode : 1976MPCPS..79...25C . doi : 10.1017/S0305004100052075 . S2CID 122860631 .
•   Greferath, Marcus (2003). „Kody Golaya” . W Proakis, John G. (red.). Encyklopedia telekomunikacji . Wileya. doi : 10.1002/0471219282.eot371 . ISBN 0471219282 .
•   Griess, Robert L. (1998). Dwanaście Sporadycznych Grup . Skoczek. P. 167. ISBN 978-3-540-62778-4 .
•   Pless, Vera (1998), Wprowadzenie do teorii kodów korygujących błędy (wyd. 3), John Wiley & Sons, ISBN 978-0-471-19047-9
•   Roman, Steven (1996), Teoria kodowania i informacji , Absolwent tekstów z matematyki nr 134, Springer-Verlag, ISBN 0-387-97812-7
•   Thompson, Thomas M. (1983). Od kodów korygujących błędy, przez opakowania sferyczne, po proste grupy . Monografie matematyczne Carusa. Tom. 21. Amerykańskie Stowarzyszenie Matematyczne. ISBN 978-0-88385-023-7 .
• Turyn, Richard J.; i in. (1967). Badania mające na celu opracowanie algebraicznej teorii kodów (sekcja VI) (PDF) (raport). Laboratoria badawcze Cambridge Sił Powietrznych. Zarchiwizowane od oryginału (PDF) w dniu 30 października 2018 r.