LDPC-Code (Low-Density Parity-Check)

Hamming, BCH und Golay sind lineare Blockcodes: Eine Prüfmatrix $H$ legt fest, welche Bitkombinationen gültige Codewörter sind. Der LDPC-Code (Low-Density Parity-Check, 1962 von Robert Gallager erfunden) funktioniert nach demselben Grundprinzip. Der Unterschied steckt in zwei Dingen: wie groß und dünn besetzt $H$ ist, und wie decodiert wird.

1. Warum LDPC anders decodiert als Hamming/BCH/Golay

Hamming, BCH und Golay sind kurz genug, um jedem möglichen Fehlermuster direkt über eine Tabelle (das Syndrom) eine Korrektur zuzuordnen — bei Golay(23,12) sind das noch überschaubare 2048 Einträge. LDPC-Codes sind dagegen sehr viel länger: hunderte bis zehntausende Bit. Bei so langen Codes gibt es astronomisch viele mögliche Fehlermuster — eine Tabelle ist schlicht unmöglich.

Die Lösung hat zwei Teile:

• Die Prüfmatrix $H$ wird bewusst dünn besetzt (low density) konstruiert — jede Zeile und Spalte enthält nur wenige Einsen, egal wie groß der Code insgesamt ist.
• Decodiert wird nicht über eine Tabelle, sondern iterativ: Bits und Prüfgleichungen tauschen mehrfach Nachrichten aus, bis eine gültige Lösung gefunden ist. Das Verfahren heißt Message Passing bzw. Belief Propagation.

2. Tanner-Graph: Bits und Prüfgleichungen als Netzwerk

Die Struktur eines LDPC-Codes lässt sich als Tanner-Graph zeichnen — ein zweigeteilter Graph mit zwei Arten von Knoten:

• Variable Nodes: ein Knoten pro Codebit
• Check Nodes: ein Knoten pro Prüfgleichung (Zeile von $H$)

Eine Kante verbindet Variable Node $j$ mit Check Node $i$ genau dann, wenn $H_{ij}=1$ ist — Bit $j$ geht also in diese Prüfgleichung ein. „Low density" bedeutet konkret: Jeder Knoten hat nur wenige Kanten (Grad), und zwar unabhängig von der Gesamtgröße des Codes — bei einem LDPC-Code mit 10.000 Bit hat ein einzelnes Bit typischerweise trotzdem nur 3–6 Nachbarn, nicht Tausende. Genau das macht die iterative Decodierung recheneffizient: Jeder Knoten muss nur mit seiner kleinen, festen Nachbarschaft kommunizieren, nicht mit dem gesamten Codewort.

3. Konkretes Beispiel: ein (12,6)-LDPC-Code

Für dieses Beispiel dient ein kleiner, selbst konstruierter Code mit $n=12$ Codebits, $k=6$ Nutzdatenbits und $m=6$ Prüfgleichungen. Das Verhältnis $R = k/n$ heißt Rate — sie gibt an, welcher Anteil des übertragenen Codeworts tatsächlich Nutzdaten sind (der Rest ist Redundanz für die Fehlerkorrektur). Bei diesem Beispiel ist $R = 6/12 = 1/2$: Für jedes Nutzbit wird ein zusätzliches Redundanzbit mitgesendet — dieselbe Rate wie beim Faltungscode-Beispiel dieser Serie. Eine niedrigere Rate (mehr Redundanz je Nutzbit) verbessert die Fehlerkorrektur, kostet aber Bandbreite bzw. Datenrate — genau der Coding-Gain-vs-Noise-Gain-Kompromiss von der Codes-Übersicht.

$$ H = \begin{pmatrix} 0&0&1&0&0&0&1&0&0&0&1&1\\ 0&1&1&0&0&1&1&0&0&1&0&0\\ 1&0&1&0&0&0&0&0&1&0&0&1\\ 0&0&0&1&1&0&0&1&1&1&0&0\\ 1&1&0&1&1&1&0&0&0&0&0&0\\ 0&1&0&0&1&0&0&1&0&0&1&1 \end{pmatrix} $$

Jede Prüfgleichung (Zeile) hat nur 4–5 Einsen, jedes Bit (Spalte) taucht nur in 2–3 Prüfgleichungen auf — deutlich weniger als die bis zu 72 möglichen Einsen einer „vollen" $6\times12$-Matrix. Genau das ist mit „low density" gemeint. $H$ hat vollen Rang 6 (alle 6 Prüfgleichungen liefern unabhängige Information, keine ist aus den anderen ableitbar), und der Code hat Minimaldistanz $d_{\min}=3$ — dieselbe Kennzahl wie Hamming(7,4): Ein einzelner Bitfehler pro Codewort ist damit garantiert korrigierbar.

Bei einem echten LDPC-Code mit tausenden Bit bleibt das Spaltengewicht ähnlich klein (3–6), nur die Blocklänge wächst um Größenordnungen. Jedes Bit hat also immer nur wenige Nachbarn — egal wie groß der Code ist.

4. Kodierung: ein durchgerechnetes Beispiel

Die 6 Nutzdatenbits dieses Codes liegen an den Positionen 5, 7, 8, 9, 10, 11 des 12-Bit-Codeworts; die restlichen Positionen (0, 1, 2, 3, 4, 6) tragen Prüfbits, die aus den Nutzdaten berechnet werden — bei diesem zufällig konstruierten $H$ sind das keine zusammenhängenden Blöcke wie bei den bisherigen Codes dieser Serie, sondern verstreute Positionen; das ändert an der Funktionsweise nichts.

Für die Nutzdaten 1 0 1 1 0 1 (an den Positionen 5, 7, 8, 9, 10, 11) ergibt die Kodierung über die aus $H$ abgeleitete Generatormatrix das vollständige Codewort:

(fett: die 6 Nutzdatenbits, wie oben eingegeben). Die Probe $H \cdot x^T = 0$ bestätigt: Alle 6 Prüfgleichungen sind erfüllt, das Codewort ist gültig.

5. Decodierung: Bit-Flipping (vereinfachtes Message Passing)

Das einfachste Message-Passing-Verfahren für LDPC-Codes ist das Bit-Flipping (Gallager 1962, sogenannter „harter" Algorithmus): Es arbeitet nur mit 0/1-Werten, nicht mit Wahrscheinlichkeiten, und lässt sich deshalb ohne größeren Aufwand nachvollziehen.

1. Berechne das Syndrom — welche der 6 Prüfgleichungen sind verletzt?
2. Zähle für jedes Bit, an wie vielen der verletzten Prüfgleichungen es beteiligt ist.
3. Kippe alle Bits, die an den meisten verletzten Prüfgleichungen beteiligt sind (bei Gleichstand: alle gleichzeitig).
4. Wiederhole ab Schritt 1, bis das Syndrom komplett null ist oder eine maximale Anzahl Durchläufe erreicht ist.

Die Grundidee: Ein Bit, das an mehreren verletzten Prüfgleichungen gleichzeitig hängt, ist ein wahrscheinlicherer Kandidat für den tatsächlichen Fehler als eines, das nur an einer einzigen verletzten Gleichung beteiligt ist — genau das macht sich Schritt 2 zunutze, ohne dass Wahrscheinlichkeiten explizit berechnet werden müssen.

6. Simulator: Codewort, Fehler und Bit-Flipping-Decodierung

7. Praktischer Einsatz

FT8/FT4 (Amateurfunk, Schwachsignalbetrieb): Wie im Herangehensweise-Artikel beschrieben, sichert FT8 seine 77 Nutzdatenbits (plus 14 Bit CRC, macht 91 Bit) mit einem LDPC(174,91)-Code ab — 174 übertragene Codebits also für 91 Nutzbit, Rate ≈ 0,52. Zusammen mit blockweiser, nicht-kohärenter Synchronisation über bekannte Costas-Tonfolgen ermöglicht das noch Decodierung bei knapp unter −20 dB SNR.

DVB-S2 (digitales Satellitenfernsehen): DVB-S2 war 2005 der erste Standard, der LDPC-Codes einsetzte — kombiniert mit einem äußeren BCH-Code, der die seltenen, aber nicht ganz auszuschließenden Restfehler des LDPC-Decoders auffängt. Je nach gewählter Coderate (zwischen 1/4 und 9/10, je nach Empfangsbedingungen wählbar) erreicht diese Kombination einen Abstand von nur 0,7–1 dB zur theoretischen Shannon-Grenze.

WLAN (IEEE 802.11n/ac/ax): LDPC-Codes mit Blocklängen von 648, 1296 oder 1944 Bit (Coderaten 1/2 bis 5/6) sind in 802.11n und 802.11ac als optionale, leistungsfähigere Alternative zum verpflichtenden Faltungscode vorgesehen; in 802.11ax gehören sie neben dem Faltungscode zu den je nach Betriebsmodus vorgeschriebenen Verfahren.

8. Grenzen

• Kleine Codes sind der ungünstigste Fall für LDPC: Der eigentliche Vorteil von LDPC — Fehlerkorrektur nahe der Shannon-Grenze — entsteht erst bei Blocklängen von hunderten bis tausenden Bit. Am (12,6)-Beispiel oben zeigt sich das deutlich: Bei einem zusätzlichen zweiten Bitfehler (statt nur einem) konvergiert das Bit-Flipping in den meisten Fällen gar nicht erst zu einem gültigen Codewort, und in einem nennenswerten Teil der übrigen Fälle landet es unbemerkt bei einem falschen, aber gültigen Codewort — ein stiller Fehler, den die Prüfgleichungen selbst nicht mehr erkennen. Bei echten LDPC-Codes mit tausenden Bit ist die statistische Basis für die iterative Korrektur ungleich breiter, weshalb sie dort zuverlässig weit über die durch $d_{\min}$ formal garantierte Korrekturstärke hinaus funktioniert — ein Effekt, der sich an einem derart kleinen Beispiel nicht zeigen lässt.
• Hard-Decision Bit-Flipping ist die schwächste Decodiervariante: Reale Systeme (FT8, DVB-S2, WLAN) nutzen Soft-Decision Sum-Product/Belief Propagation mit Log-Likelihood-Ratios statt harter 0/1-Bit-Flips (siehe Kasten in Abschnitt 5) und erreichen dadurch einen deutlich besseren Fehlerschutz bei gleicher Codelänge.
• Iterative Decodierung kostet Zeit: Anders als eine einzelne Syndrom-Tabellenabfrage bei Hamming/BCH/Golay braucht LDPC-Decodierung mehrere Durchläufe über den gesamten Tanner-Graph — die Latenz wächst mit der Anzahl der bis zur Konvergenz nötigen Iterationen, nicht mit einer festen, vorhersagbaren Rechenzeit.

9. Wie entsteht so eine Prüfmatrix in der Praxis?

In der Praxis wird eine LDPC-Prüfmatrix nach einem von mehreren etablierten Verfahren gezielt konstruiert, nicht zufällig gesucht:

• Reguläre Zufallskonstruktion (Gallager, 1962): ein zufälliger Tanner-Graph mit fest vorgegebenem Grad je Knotentyp (jedes Bit z. B. immer genau 3 Nachbarn, jede Prüfgleichung immer genau 6). Bei den großen Blocklängen, für die LDPC gedacht ist, liefert das statistisch fast immer einen brauchbaren Code — anders als bei meinem kleinen (12,6)-Beispiel, wo die Zufallssuche noch gezielt nachprüfen musste.
• Irreguläre Codes und Dichte-Evolution (Luby, Richardson/Urbanke, späte 1990er): Statt eines einheitlichen Grads bekommt jeder Knotentyp eine gezielt optimierte Gradverteilung — manche Bits mit vielen, andere mit wenigen Nachbarn. Die Dichte-Evolution ist dabei eine analytische Methode, die für eine gegebene Gradverteilung vorhersagt, wie nah der Decoder an die Shannon-Grenze herankommt, noch bevor ein konkreter Code gebaut wird. So lassen sich Gradverteilungen finden, die auf einen Bruchteil eines dB an das theoretische Optimum herankommen.
• PEG-Algorithmus (Progressive Edge Growth): baut den Tanner-Graphen gezielt Kante für Kante auf und vermeidet dabei kurze Zyklen (den sogenannten Girth des Graphen). Kurze Zyklen sind der Hauptgrund, warum Message Passing schlecht konvergiert: Eine Nachricht läuft dann im Kreis und verstärkt sich selbst, statt echte neue Information von anderen Teilen des Graphen einzusammeln.
• Quasi-zyklische LDPC-Codes (QC-LDPC): der in Hardware tatsächlich verwendete Ansatz — WLAN, DVB-S2 und 5G nutzen ihn alle. Statt völlig frei konstruiert zu werden, setzt sich $H$ aus lauter kleinen quadratischen Blöcken zusammen, von denen jeder eine zirkulant verschobene Einheitsmatrix ist — eine Einheitsmatrix (Einsen nur auf der Diagonale), bei der die Diagonale um eine feste Anzahl Spalten „im Kreis" verschoben wurde. Ein solcher Block lässt sich in Hardware als simples Schieberegister mit fester Verschiebeweite realisieren, statt als beliebig verdrahtete Logik — das macht Encoder und Decoder deutlich effizienter. Es erklärt z. B. auch, warum die 802.11n-Blocklängen (648/1296/1944 Bit) genau diese Zahlen sind: Vielfache einer festen Untermatrixgröße.

Woher weiß man, welchen Code man nehmen soll? Für den Praxisfall — ein Gerät soll einem Standard entsprechen — entwirft man keinen eigenen Code: Der Standard selbst legt die exakte Prüfmatrix fest, meist als Tabelle im Anhang. ETSI EN 302 307 (DVB-S2) listet die vollständigen LDPC-Matrizen für jede Coderate in Anhang B; der IEEE-802.11-Standard tabelliert für 802.11n/ac die zirkulanten Verschiebewerte für jede Kombination aus Blocklänge und Rate; 3GPP TS 38.212 legt für 5G NR zwei feste „Base Graphs" fest, aus denen sich alle unterstützten Blocklängen ableiten. Bei FT8 ist die LDPC(174,91)-Matrix Teil der WSJT-X-Quelldateien und damit für jede Implementierung exakt vorgegeben. Man implementiert also die im Standard veröffentlichte Matrix nach, statt eine eigene zu konstruieren — genau wie beim CRC-Generatorpolynom im CRC-Code-Artikel, nur mit einer sehr viel größeren Tabelle. Für eigene, nicht standardgebundene Projekte greift man stattdessen auf fertige Referenzimplementierungen zurück, statt bei null anzufangen — GNU Radios gr-dvbs2- bzw. gr-fec-Module etwa bringen bereits fertige, getestete LDPC-Encoder/Decoder-Blöcke mit den Standard-Matrizen aus DVB-S2 mit.