Golay-Code

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

Die Bezeichnung Golay-Code steht für zwei eng verwandte Codes, welche eine herausragende Stellung in der Codierungstheorie einnehmen. Sie sind (abgesehen von trivialen Codes und Wiederholungs-Codes) bis auf Isomorphie die einzigen beiden perfekten Codes, die mehr als einen Fehler korrigieren können.^[1] Sie sind nach dem Schweizer Elektroingenieur Marcel J. E. Golay benannt. In beiden Fällen handelt es sich um einen quadratischen Rest-Code und damit insbesondere um einen zyklischen Code und einen linearen Code.

Der binäre Golay-Code G 23 {\displaystyle G_{23}} ist definiert als der binäre quadratische Reste-Code der Länge 23. Als linearer Code hat er die Parameter ( n , k , d ) = ( 23 , 12 , 7 ) {\displaystyle (n,k,d)=(23,12,7)} . Das bedeutet, dass der Code ein 12-dimensionaler Untervektorraum des 23-dimensionalen Vektorraums F 2 23 {\displaystyle \mathbb {F} _{2}^{23}} mit der minimalen Hamming-Distanz 7 ist. Es folgt t = ⌊ d − 1 2 ⌋ = 3 {\displaystyle t=\left\lfloor {\tfrac {d-1}{2}}\right\rfloor =3} . Der Code ist also 3-fehlerkorrigierend.

Die Parameter erfüllen die Gleichung

q k ∑ i = 0 t ( n i ) ( q − 1 ) i = q n {\displaystyle q^{k}\sum _{i=0}^{t}{n \choose i}(q-1)^{i}=q^{n}}

Deshalb ist der binäre Golay-Code G 23 {\displaystyle G_{23}} perfekt.

Hängt man dem binären Golay-Code G 23 {\displaystyle G_{23}} ein Paritätsbit an, so erhält man den erweiterten binären Golay-Code G 24 {\displaystyle G_{24}} mit den Parametern ( n , k , d ) = ( 24 , 12 , 8 ) {\displaystyle (n,k,d)=(24,12,8)} . Dieser Code ist doppelt gerade, d. h. alle Codewörter haben ein durch 4 teilbares Hamming-Gewicht.

Die Automorphismengruppe des erweiterten binären Golay-Codes ist die Mathieugruppe M 24 {\displaystyle M_{24}} , eine sporadische Gruppe.

Der ternäre Golay-Code G 11 {\displaystyle G_{11}} ist definiert als der ternäre quadratische Reste-Code der Länge 11. Als linearer Code hat er die Parameter ( n , k , d ) = ( 11 , 6 , 5 ) {\displaystyle (n,k,d)=(11,6,5)} . Das bedeutet, dass der Code ein 6-dimensionaler Untervektorraum des 11-dimensionalen Vektorraums F 3 11 {\displaystyle \mathbb {F} _{3}^{11}} mit dem Mindestabstand 5 ist. Es folgt t = ⌊ d − 1 2 ⌋ = 2 {\displaystyle t=\left\lfloor {\tfrac {d-1}{2}}\right\rfloor =2} . Der Code ist also 2-fehlerkorrigierend. Auch hier erfüllen die Parameter die oben genannte Gleichung, also ist auch der ternäre Golay-Code G 11 {\displaystyle G_{11}} perfekt.

1. ↑ ER Berlekamp: Decoding the Golay code. In: Technical Report 32-1526. Band XI. California Institut of Technology, Pasadena, California 15. Oktober 1972, S. 83.