Golay-Code

Der binäre Golay-Code, 1949 von Marcel J. E. Golay veröffentlicht, ist neben dem Hamming-Code einer von nur zwei bekannten binären perfekten Codes mit praktischer Bedeutung. „Perfekt" ist hier keine Werbeformulierung, sondern ein präziser mathematischer Begriff (siehe Abschnitt 3): Der Code nutzt seine Redundanz restlos aus, ohne eine einzige Syndromkombination zu verschwenden — genau wie Hamming(7,4) für einen Bitfehler, nur dass der binäre Golay-Code $(23,12)$ gleich drei gleichzeitige Bitfehler pro Codewort korrigiert.

1. Wo Hamming und BCH an ihre Grenzen stoßen

Hamming-Codes korrigieren immer nur einen Bitfehler, unabhängig von der Blockgröße (siehe Hamming-Code, Abschnitt 5). Der BCH-Code löst das: beliebige Korrekturstärke $t$, beliebige Codewortlänge — aber BCH-Codes verschwenden bei den meisten Parameterkombinationen etwas Redundanz, sie sind nicht "perfekt" im mathematischen Sinne. Der binäre Golay-Code ist ein seltener Glücksfall: Für die feste Kombination $n=23$, $k=12$, $t=3$ trifft die Konstruktion exakt den theoretisch bestmöglichen Punkt — es gibt keinen binären Code mit diesen Parametern, der irgendetwas effizienter machen könnte.

2. Konstruktion: dieselbe Polynomdivision wie CRC und BCH

Auch der Golay-Code ist ein zyklischer Code und wird genauso kodiert wie CRC- und BCH-Codes: Nachricht um $r$ Nullen erweitern, durch das feste Generatorpolynom $G(x)$ teilen, den Rest als Prüfbits anhängen. Das feste Generatorpolynom für den binären $(23,12)$-Golay-Code lautet:

$$G(x) = x^{11}+x^9+x^7+x^6+x^5+x+1$$

als Bitfolge 101011100011 (Grad 11). Mit $n=23$ und $r=11$ Prüfbits verbleiben $k=n-r=12$ Nutzdatenbits.

Bsp.: Für die Nachricht 101100111010 (12 Bit) ergibt die Division durch $G(x)$ das Codewort 10110011101011011100000 (23 Bit) — eine erneute Division dieses Codeworts durch $G(x)$ liefert exakt den Rest 0.

3. Perfekter Code: warum keine Syndromkombination verschwendet wird

Mit $r=11$ Prüfbits gibt es $2^{11}=2048$ mögliche Syndrome (siehe BCH-Code, Abschnitt 5 für die Erklärung des Syndrom-Tabellen-Prinzips). Ein Syndrom steht entweder für „kein Fehler" oder für genau ein korrigierbares Fehlermuster. Die Frage ist: Wie viele Fehlermuster mit Gewicht $\le 3$ gibt es über $n=23$ Bitpositionen?

$$\binom{23}{0}+\binom{23}{1}+\binom{23}{2}+\binom{23}{3} = 1+23+253+1771 = 2048$$

Ein testweise eingefügter Dreifachfehler an den Positionen 3, 11 und 21 (0-indiziert) wird über das Syndrom korrekt auf genau diese drei Positionen zurückgeführt und vollständig korrigiert.

4. Simulator: Kodierung, Fehler und Syndrom-Korrektur

5. Praktischer Einsatz

Digitaler Sprechfunk (DMR): Der DMR-Standard (ETSI TS 102 361), der auch im Amateurfunk (u. a. DMR-MARC, BrandMeister) verbreitet ist, nutzt für Teile seines Steuerkanals einen verkürzten Golay(20,8,7)-Code — eine an kürzere Datenfelder angepasste Variante desselben Konstruktionsprinzips. Neben Golay kommen dort je nach Feld auch Hamming- und Quadratic-Residue-Codes zum Einsatz (siehe Hamming-Code, Abschnitt 8).

Amateurfunksatelliten (AMSAT): Wie bereits im BCH-Code-Artikel erwähnt, sichern mehrere Amateurfunksatelliten ihre Telemetrie- und Frame-Rahmen mit Golay-Codes ab — etwa das Maveric-Projekt mit Golay-Framing auf einem 9600-bps-GMSK-Downlink.

Voyager-Raumsonden (historisch): Die erweiterte Variante, der Golay(24,12,8)-Code (ein zusätzliches Gesamtparitätsbit, analog zum SECDED-Prinzip aus dem Hamming-Artikel), wurde von der NASA für die Bildübertragung der Voyager-1- und Voyager-2-Missionen eingesetzt — ein Beleg dafür, wie lange dieselbe 1949 entwickelte Konstruktion praktisch relevant blieb.

6. Grenzen

• Nur eine „perfekte" Parameterkombination: Die perfekte Ausnutzung aus Abschnitt 3 gilt exakt für $n=23$, $k=12$, $t=3$ (bzw. $n=24,k=12,t=4$ für die erweiterte Variante) — anders als BCH lässt sich der binäre Golay-Code nicht auf beliebige Korrekturstärken oder Codewortlängen skalieren.
• Feste, nicht triviale Konstruktion: Wie bei BCH ist die Wahl des Generatorpolynoms nicht offensichtlich, sondern das Ergebnis einer festen mathematischen Konstruktion (verwandt mit quadratischen Resten modulo 23) — für andere Parameter lässt sich dieselbe Eleganz nicht einfach nachbauen.
• Wie jeder Code mit endlichem $t$: Mehr als 3 gleichzeitige Fehler in einem Codewort werden nicht mehr zuverlässig lokalisiert — dieselbe grundsätzliche Grenze wie bei Hamming und BCH, hier bei $t=3$ statt $t=1$ erreicht.