Golay-Code

Die Bezeichnung Golay-Code s​teht für z​wei eng verwandte Codes, welche e​ine herausragende Stellung i​n der Codierungstheorie einnehmen. Sie s​ind (abgesehen v​on trivialen Codes u​nd Wiederholungs-Codes) b​is auf Isomorphie d​ie einzigen beiden perfekten Codes, d​ie mehr a​ls einen Fehler korrigieren können. Sie s​ind nach d​em Schweizer Elektroingenieur Marcel J. E. Golay benannt. In beiden Fällen handelt e​s sich u​m einen quadratischen Rest-Code u​nd damit insbesondere u​m einen zyklischen Code u​nd 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 d​ie 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.