BCH-Code

Zyklischer Blockcode mit frei wählbarer Fehlerkorrekturstärke — überwindet die feste Ein-Bit-Korrektur und die 31-Bit-Obergrenze des Hamming-Codes.

Der BCH-Code (nach seinen Erfindern Bose, Ray-Chaudhuri und Hocquenghem) ist ein zyklischer, fehlerkorrigierender Blockcode, der den Hamming-Code in zwei zentralen Punkten verallgemeinert: Die Anzahl der korrigierbaren Bitfehler $t$ pro Codewort ist frei wählbar (statt fest bei $t=1$), und die Codewortlänge ist nicht auf $n \le 31$ begrenzt. Der Preis dafür: eine deutlich abstraktere Konstruktion und ein komplexeres Dekodierverfahren.

1. Warum Hamming nicht immer reicht

Hamming-Codes haben unabhängig von der gewählten Blockgröße stets eine Minimaldistanz $d_{\min}=3$ — sie korrigieren also immer nur einen Bitfehler pro Codewort, egal wie viele Redundanzbits investiert werden. Für Anwendungen mit höherer Fehlerdichte (z. B. NAND-Flash-Speicher mit zunehmender Zellendichte, oder stark gestörte Funkkanäle) reicht das nicht aus — hier wird eine wählbare Korrekturstärke $t=2,3,4,\dots$ benötigt. Genau das leistet die BCH-Konstruktion, ohne die grundlegende Idee der Polynomdivision aus dem CRC-Code zu verlassen.

2. Konstruktionsprinzip

Die Kodierung eines BCH-Codeworts ist nichts Neues: Sie funktioniert exakt wie beim CRC-Code — Nachricht mit Nullen auffüllen, durch ein Generatorpolynom $G(x)$ teilen, den Rest anhängen (siehe dort Abschnitt 1 für die anschauliche Rest-beim-Teilen-Erklärung). Der gesamte Unterschied zwischen einem "gewöhnlichen" zyklischen Code und einem BCH-Code steckt allein in der Wahl von $G(x)$: BCH verwendet ein Generatorpolynom, das nach einer festen Konstruktionsvorschrift so zusammengesetzt ist, dass es eine garantierte Fehlerkorrekturfähigkeit von $t$ Bits mit sich bringt — statt eines beliebigen oder nur auf Fehlererkennung optimierten Polynoms.

Man kann sich diese Konstruktionsvorschrift wie ein Baukasten-Rezept vorstellen: Für eine gewünschte Codewortlänge $n$ und Korrekturstärke $t$ liefert eine vorgefertigte Tabelle ("Zutatenliste") eine Handvoll kleiner Bausteinpolynome. $G(x)$ entsteht einfach durch Multiplikation dieser Bausteine — man muss die Tabelle also nur ablesen und die Bausteine miteinander malnehmen, nicht von Grund auf herleiten:

Codewortlänge und Feldgröße festlegen: $n = 2^m - 1$ für ein gewähltes $m$.
Gewünschte Korrekturstärke $t$ wählen; die Entwurfsdistanz ist $d = 2t+1$.
Für die Wahl $t$ liefert die Bausteintabelle (fachsprachlich: Tabelle minimaler Polynome für die gewählte Feldgröße $m$) die passenden Bausteine.
$G(x)$ ist das Produkt dieser Bausteine — dadurch entsteht automatisch ein Generatorpolynom, das eine $t$-Bit-Fehlerkorrektur garantiert.

Warum genau diese Bausteintabelle funktioniert, lässt sich nur mit Arithmetik in einem endlichen Zahlkörper (Galois-Feld $\text{GF}(2^m)$) beweisen. Für die praktische Anwendung reicht das Baukasten-Bild aus Schritt 1–4: Tabelle ablesen, Bausteine multiplizieren, fertig ist $G(x)$. Die anschließende Kodierung mit diesem $G(x)$ ist dann wieder genauso simpel wie beim CRC-Code.

Exkurs: Was ist $\text{GF}(2^m)$?

Für unser Beispiel mit $m=4$ hat $\text{GF}(16)$ 16 Elemente: die Null und 15 weitere, die sich alle als Potenzen eines einzigen Erzeugerelements $\alpha$ schreiben lassen — $\alpha^0, \alpha^1, \alpha^2, \dots, \alpha^{14}$. Danach schließt sich der Kreis: $\alpha^{15} = \alpha^0 = 1$. Das ist auch der Grund, warum unser BCH-Beispiel eine Codewortlänge von genau $n=15$ hat — sie entspricht exakt der Zykluslänge des Erzeugers.

Jede Potenz $\alpha^i$ lässt sich zugleich als 4-Bit-Muster schreiben. Die Rechenregel dahinter legt ein festes Grundpolynom fest, z. B. $p(x) = x^4+x+1$, wofür gilt $\alpha^4 = \alpha + 1$ — statt eines Übertrags in eine fünfte Bitstelle wird also immer wieder auf die ersten vier Potenzen zurückgeführt (vergleichbar mit einer Uhr, die nach 15 Stunden wieder bei 0 anfängt):

Potenz	4-Bit-Muster	Potenz	4-Bit-Muster
$\alpha^0$	0001	$\alpha^8$	0101
$\alpha^1$	0010	$\alpha^9$	1010
$\alpha^2$	0100	$\alpha^{10}$	0111
$\alpha^3$	1000	$\alpha^{11}$	1110
$\alpha^4$	0011	$\alpha^{12}$	1111
$\alpha^5$	0110	$\alpha^{13}$	1101
$\alpha^6$	1100	$\alpha^{14}$	1001
$\alpha^7$	1011	$\alpha^{15}=\alpha^0$	0001

Bsp.: Für $p(x)=x^4+x+1$ ergibt die Multiplikation mit $\alpha$ bei jedem Schritt exakt die oben gelistete Tabelle, und der Zyklus schließt sich nach 15 Schritten wieder bei $\alpha^{15}=\texttt{0001}=\alpha^0$.

Die "minimalen Polynome" aus Schritt 3 oben sind nichts anderes als: das kleinstmögliche Polynom mit 0/1-Koeffizienten, das eine bestimmte Potenz $\alpha^i$ als Nullstelle hat. Für $\alpha^1$ ist das genau unser Grundpolynom $p(x)=x^4+x+1$ — deshalb taucht es in Tabelle 1 des Whitepapers als minimales Polynom für $i=1$ auf. Für die BCH-Konstruktion braucht man die minimalen Polynome mehrerer aufeinanderfolgender ungerader Potenzen ($\alpha^1, \alpha^3, \alpha^5$ für $t=3$); ihr Produkt ergibt $G(x)$ aus Abschnitt 3.

3. Konkretes Beispiel: BCH(15,5), $t=3$

Bsp.: Für $m=4$ (also $n=2^4-1=15$) und eine gewünschte Korrekturstärke von $t=3$ liefert die Konstruktion aus Abschnitt 2 das Generatorpolynom $G(x) = x^{10}+x^8+x^5+x^4+x^2+x+1$ (Bitfolge 10100110111, Grad 10). Mit $n=15$ und $r=10$ Prüfbits verbleiben $k = n-r = 5$ Nutzdatenbits — man spricht vom BCH(15,5)-Code.

Größe	Wert
$m$ (Feldgröße)	4
$n$ (Codewortlänge)	15
$t$ (korrigierbare Bitfehler)	3
$r$ (Prüfbits)	10
$k$ (Nutzdatenbits)	5

4. Kodierung: dieselbe Polynomdivision wie CRC

Die Kodierung eines BCH(15,5)-Codeworts läuft exakt wie in CRC-Code, Abschnitt 1 beschrieben: die 5 Nachrichtenbits um 10 Nullen erweitern, durch $G(x)$ teilen, den Rest als 10 Prüfbits anhängen.

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

5. Dekodierung: Syndrom-Tabelle statt direkter Formel

Das Syndrom ist ein Prüfwert, der sich allein aus dem empfangenen Codewort berechnen lässt (beim BCH- wie beim CRC-Code: der Rest bei erneuter Division durch $G(x)$) und anzeigt, ob ein Fehler vorliegt — bei 0 keiner, bei einem Wert ungleich 0 ein erkannter Fehler. Beim Hamming-Code verrät das 3-Bit-Syndrom die Fehlerposition direkt als Binärzahl — ein Trick, der nur bei $t=1$ funktioniert. Bei $t=3$ gibt es dagegen $\binom{15}{1}+\binom{15}{2}+\binom{15}{3} = 15+105+455 = 575$ mögliche Ein-, Zwei- und Dreibit-Fehlermuster (plus den fehlerfreien Fall) — zu viele, um sie noch direkt aus einer kurzen Binärzahl abzulesen. Der allgemeine Ausweg — gültig für jeden linearen Blockcode, nicht nur BCH — ist ein simples Nachschlagewerk, die Syndrom-Tabelle: Statt die Fehlerposition zu berechnen, wird sie einmalig für alle möglichen Fehler vorab bestimmt und danach nur noch nachgeschlagen:

Für jedes mögliche Fehlermuster mit Gewicht $\le t$ — das Gewicht ist einfach die Anzahl der gekippten Bits, ein Fehler an 3 Positionen hat also Gewicht 3 — wird sein Syndrom vorab berechnet: der Rest der Division des Fehlermusters durch $G(x)$ (dieselbe Rechenoperation wie bei der Kodierung).
Diese Zuordnung Syndrom → Fehlermuster wird in einer Tabelle abgelegt.
Beim Empfang wird das Syndrom des empfangenen Worts berechnet und in der Tabelle nachgeschlagen — der Treffer liefert direkt das zu korrigierende Fehlermuster.

Bsp.: Für den BCH(15,5)-Code aus Abschnitt 3 wurden alle 576 Fehlermuster mit Gewicht 0 bis 3 (über die 15 Bitpositionen) durchprobiert — jedes einzelne erzeugt ein eindeutiges Syndrom, keine zwei verschiedenen Muster kollidieren. Das bestätigt die garantierte $t=3$-Fehlerkorrektur des Codes rechnerisch. Ein testweise eingefügter Dreifachfehler an den Positionen 1, 6 und 10 wird über das Syndrom korrekt auf genau diese drei Positionen zurückgeführt und vollständig korrigiert.

6. Simulator: Kodierung, Fehler und Syndrom-Korrektur

BCH(15,5), $t=3$: Codewort, Fehler und Korrektur per Syndrom-Tabelle

5 Nutzdatenbits anklicken, um die Nachricht zu ändern — die 10 Prüfbits werden automatisch neu berechnet. Auf bis zu 3 Bits im 15-Bit-Codewort klicken, um Fehler zu simulieren; die Syndrom-Tabelle (576 vorab berechnete Fehlermuster) lokalisiert und korrigiert sie. Bei mehr als 3 gleichzeitigen Fehlern versagt die Korrektur — wie bei jedem Code mit endlichem $t$.

Nutzdaten (5 Bit, klicken zum Ändern):

Codewort (15 Bit, auf ein Bit klicken für simulierten Fehler):

Syndrom: 0000000000

Kein Fehler.

Bit = 1 Bit = 0 simulierter Fehler von der Syndrom-Tabelle als Fehler identifiziert

7. Praktischer Einsatz

Amateurfunksatelliten (AMSAT): Viele Amateurfunksatelliten sichern ihre Telemetrie- und Frame-Rahmen mit Golay-Codes ab — einer mit BCH eng verwandten zyklischen Codefamilie mit fest definierter Fehlerkorrekturstärke, gut geeignet für kurze, feste Rahmenlängen. Ein Beispiel ist das Maveric-Projekt mit Golay-Framing auf einem 9600-bps-GMSK-Downlink. BCH selbst kommt seltener direkt in Amateurfunk-Protokollen zum Einsatz, dafür umso häufiger in der Hardware, mit der SDR-Empfangsketten arbeiten (siehe NAND-Flash unten).

NAND-Flash-Speicher (SSDs): Mit wachsender Zellendichte (MLC, TLC, QLC) steigt die Rohfehlerrate beim Auslesen deutlich — Flash-Controller setzen deshalb BCH-Codes mit $t$ im Bereich von 4 bis weit über 40 ein, weit jenseits dessen, was ein Hamming-Code leisten könnte.

Satellitenkommunikation (DVB-S2): Der DVB-S2-Standard für Satellitenfernsehen nutzt einen BCH-Code als äußeren Code in Verkettung mit einem LDPC-Code als inneren Code, um die geforderte extrem niedrige Restfehlerrate bei begrenzter Sendeleistung zu erreichen.

Weitere ECC-Anwendungen mit hoher Fehlerdichte: Überall dort, wo Hamming-Codes an ihre $t=1$-Grenze stoßen, aber weiterhin Vorwärtsfehlerkorrektur (FEC) ohne Rückkanal benötigt wird — etwa in Speicherzellen mit hoher Bitfehlerrate oder stark gestörten Übertragungskanälen.

8. Grenzen

Komplexere Dekodierung: Während die Kodierung so einfach ist wie beim CRC-Code, benötigt die Dekodierung für größere $n$ und $t$ in der Praxis effiziente Algorithmen (Berlekamp-Massey, Peterson-Gorenstein-Zierler) statt einer brute-force aufgebauten Syndrom-Tabelle — die hier gezeigte Tabellenmethode wird für große Codes schnell unpraktikabel (Anzahl der Einträge wächst kombinatorisch mit $t$).
Galois-Feld-Arithmetik nötig: Die eigentliche Konstruktion des Generatorpolynoms (Abschnitt 2, Schritt 3) erfordert Rechnen in einem endlichen Körper — Hardware- oder Software-Aufwand, den einfachere Codes wie Hamming oder CRC nicht benötigen.
Wie jeder Code mit endlichem $t$: Mehr als $t$ gleichzeitige Fehler in einem Codewort werden entweder gar nicht mehr zuverlässig lokalisiert oder (schlimmer) fälschlich auf ein falsches, aber gültig aussehendes Muster korrigiert — dieselbe grundsätzliche Grenze wie beim Hamming-Code, nur bei höherer Fehlerdichte erreicht.