Golay-Code

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

Generatormatrix für den erweiterten binären Golay-Code

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

Die Parameter erfüllen die Gleichung

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

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

Der erweiterte binäre Golay-Code

Hängt man dem binären Golay-Code ${\displaystyle G_{23}}$ ein Paritätsbit an, so erhält man den erweiterten binären Golay-Code ${\displaystyle G_{24}}$ mit den Parametern ${\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 ${\displaystyle M_{24}}$, eine sporadische Gruppe.

Der ternäre Golay-Code

Der ternäre Golay-Code ${\displaystyle G_{11}}$ ist definiert als der ternäre quadratische Reste-Code der Länge 11. Als linearer Code hat er die Parameter ${\displaystyle (n,k,d)=(11,6,5)}$. Das bedeutet, dass der Code ein 6-dimensionaler Untervektorraum des 11-dimensionalen Vektorraums ${\displaystyle \mathbb {F} _{3}^{11}}$ mit dem Mindestabstand 5 ist. Es folgt ${\displaystyle t=\left\lfloor {\frac {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 ${\displaystyle G_{11}}$ perfekt.

Einzelnachweise

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.