Der LDPC-Code (englisch Low-Density Parity-Check Code, zu Deutsch Code mit geringer Dichte der Paritätsprüfung, auch Gallager-Code) ist ein Blockcode zur Vorwärtsfehlerkorrektur, dessen Prüfmatrix nur wenige Einsen enthält. Er wurde 1962 von Robert G. Gallager im Rahmen seiner Dissertation am MIT entwickelt, geriet danach jahrzehntelang in Vergessenheit und erlebte ab 2001 eine Renaissance, weil er sich mit vertretbarem Aufwand nahe der Shannon-Grenze betreiben lässt.
Idee: dünn besetzte Prüfmatrix
Ein LDPC-Code ist über eine Paritätsprüfmatrix H definiert, für die jedes gültige Codewort b die Gleichung H · bT = 0 erfüllt. Das Besondere ist die low density: Die Matrix ist nur spärlich mit Einsen besetzt, sodass jedes Prüfbit nur wenige Nutzbits verbindet. Diese Struktur lässt sich als Tanner-Graph darstellen, in dem Variablenknoten (Codebits) und Prüfknoten (Gleichungen) abwechseln.
Iterative Decodierung
Der Empfänger decodiert nicht in einem Durchgang, sondern iterativ: Beim Belief-Propagation-Verfahren (auch Sum-Product-Algorithmus) tauschen die Knoten des Tanner-Graphen über mehrere Runden Wahrscheinlichkeiten beziehungsweise Log-Likelihood-Ratios aus. Jede Iteration erhöht die Zuverlässigkeit der Schätzung. In der Praxis kommt oft die vereinfachte Min-Sum-Variante zum Einsatz, die mit geringerem Aufwand fast dieselbe Leistung erreicht.
Anwendungen
- DVB-S2 (Satellitenfernsehen): LDPC als innerer Code, Reed-Solomon/BCH als äußerer Code
- WLAN nach IEEE 802.11n/ac/ax (Wi-Fi 4 bis 6)
- 5G-NR-Datenkanäle (PDSCH/PUSCH) mit den Base-Graphs BG1 und BG2
- 10-Gigabit-Ethernet (10GBASE-T) und moderne SSD-Controller (NAND-Flash)
Verwandte Grundlagen: Kanalcodierung, Polar-Code, Fountain-Code.