Zum Inhalt springen
Zurück zu den Suchergebnissen

Low-Density Parity-Check Codes (LDPC)

Eingeführt von
Robert Gallager
Jahr
1962
Typ
linear error-correcting code
Familie
Coding theory

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

LDPC-Codes, 1962 von Robert Gallager erfunden und in den 1990er Jahren von MacKay wiederentdeckt, sind lineare fehlerkorrigierende Codes, die durch dünnbesetzte Paritätsprüfmatrizen definiert werden.

Sie erreichen eine Leistung innerhalb von 0,4 dB an der Shannon-Grenze mit iterativer Belief-Propagation-Dekodierung und sind zum Standard für moderne drahtlose Kommunikation (WiFi-6, 5G NR, Digital Video Broadcasting) geworden. Im Gegensatz zu Turbo-Codes weisen LDPC-Codes eine elegantere graphentheoretische Struktur und eine ausgereiftere theoretische Analyse auf.

Die Intuition hinter der Methode

Standardmäßige lineare Codes verwenden dicht besetzte Paritätsprüfmatrizen, was die Dekodierung rechenintensiv macht. LDPC-Codes kehren dies um: Die Paritätsprüfmatrix ist dünnbesetzt (die meisten Einträge sind Null), sodass jede Paritätsprüfung nur eine Handvoll Bits betrifft. Am Empfänger wird ein bipartiter Graph konstruiert, bei dem Variablenknoten die übertragenen Bits und Prüfknoten die Paritätsbedingungen darstellen. Die Dekodierung wird zu einer iterativen Nachrichtenübermittlung auf diesem Graphen: Jeder Variablenknoten sammelt Informationen von seinen Nachbarn, aktualisiert seine Annahme über den Bitwert und sendet verfeinerte Schätzungen zurück. Die Dünnbesetztheit gewährleistet eine schnelle Konvergenz und eine Leistung nahe der Shannon-Grenze.

Geschichte

Gallager erfand die LDPC-Codes 1962, aber die Theorie hinkte der praktischen Implementierung hinterher. 1995 entdeckte MacKay sie wieder und zeigte ihre Leistung nahe der Shannon-Grenze durch Simulationen. Umfangreiche Forschung in den 2000er Jahren entwickelte effiziente Kodierungs-, Dekodierungs- und Graphenkonstruktionsalgorithmen. LDPC-Codes wurden in WiFi-6 (802.11ax, 2021) und dem 5G NR-Standard (2018) übernommen. Sie sind in neuen Systemen aufgrund besserer Leistung und saubererer Struktur verbreiteter als Turbo-Codes.

Wann wird sie eingesetzt?

LDPC-Codes werden in modernen Systemen aufgrund besserer Leistung und einfacherer Architektur gegenüber Turbo-Codes bevorzugt. Verwenden Sie LDPC für weite SNR-Bereiche (kein Schwellenwertabfall); sie funktionieren gut von niedrigem bis hohem SNR. LDPC ist der Standard für WiFi-6, Satelliten- und 5G NR-Kommunikation. Vermeiden Sie LDPC nur, wenn die Kompatibilität mit älteren Systemen Turbo-Codes erfordert. LDPC eignet sich auch für sehr kurze Pakete (>30 Bit), da die Codestruktur trennbar ist.

Grenzen und Hinweise

  • Graphenkonstruktion und Matrixspeicherung werden bei sehr langen Codes (>10.000 Bit) komplex
  • Leistung empfindlich gegenüber kleinskaligen Graphenstrukturen (Girths, Absorbing Sets); erfordert sorgfältiges Design
  • Belief Propagation geht von einem Graphen mit Schleifen aus, aber Graphen haben Zyklen; Konvergenz zur optimalen Lösung nicht garantiert
  • Die Dekodierlatenz (Iterationen) wächst logarithmisch mit dem SNR; nicht latenzfrei wie einige klassische Codes
  • Die Quantisierung von Nachrichten (in Festkomma-Hardware) beeinflusst die Leistung; sorgfältige Bit-Zuweisung erforderlich

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Leistung innerhalb von 0,4 dB an der Shannon-Grenze (etwas besser als Turbo-Codes)
  • Einfachere graphentheoretische Struktur; sauberere theoretische Analyse als bei Turbo-Codes
  • Iterative Dekodierung vermeidet schwellenwertartiges Verhalten (im Gegensatz zu Turbo-Codes)
  • Flexible Code-Gestaltung durch Graphenkonstruktion; einfache Anpassung an spezifische Anwendungen
  • Effiziente parallele Dekodierhardware; Nachrichtenübermittlung eignet sich für VLSI-/GPU-Implementierung
  • Funktioniert gut für lange und mäßig kurze Codewörter

Anwendungen

  • WiFi-6 (802.11ax): drahtlose Hochdurchsatz-Lokalnetzwerke, bei denen LDPC eine zuverlässige Datenübertragung gewährleistet
  • 5G NR: Kanalcodierung für Daten- und Steuerkanäle, ersetzt Turbo-Codes aus 4G
  • Satellitenkommunikation: digitales Video-Broadcasting (DVB-S2) und Tiefraummissionen unter Verwendung von LDPC mit langen Codewörtern
  • Powerline Communications (PLC): robuste Datenübertragung über verrauschte Stromnetze
  • Flash-Speichersysteme: Fehlerkorrektur für NAND-Flash-Speicher ohne Verschleiß durch häufiges Auffrischen

So funktioniert es

So funktioniert es

1

Informationsbits werden unter Verwendung einer dünnbesetzten Paritätsprüfmatrix H kodiert; die kodierten Bits sind die Lösung für H*c = 0 (mod 2), wobei c das Codewort ist.

2

Die Paritätsprüfmatrix H ist dünnbesetzt strukturiert (z. B. hat jede Zeile/Spalte ein konstantes geringes Gewicht von 3-5). Diese Struktur wird für eine effiziente Kodierung genutzt.

3

Kodierte Bits werden über einen verrauschten Kanal übertragen; die empfangenen Bits sind Soft Values (Likelihood-Verhältnisse oder Log-Likelihood-Verhältnisse).

4

Ein bipartiter Graph wird konstruiert: linke Knoten = Variablenknoten (Bits), rechte Knoten = Prüfknoten (Paritätsgleichungen). Kanten verbinden Variablen mit den Prüfungen, in denen sie vorkommen.

5

Iterative Belief Propagation: Variablenknoten aggregieren Nachrichten von Prüfknoten, aktualisieren Bitschätzungen und senden verfeinerte Nachrichten zurück. Nach Iterationen werden harte Entscheidungen getroffen; wenn Paritätsprüfungen erfüllt sind, ist die Dekodierung erfolgreich.

Häufige Fallstricke

  • Verwendung eines schlecht entworfenen dünnbesetzten Graphen mit kurzen Zyklen; kleine Zyklen führen dazu, dass Belief Propagation oszilliert
  • Übermäßiges Iterieren über die Konvergenz hinaus; unnötige Iterationen verschwenden Energie ohne Verbesserung
  • Annahme, dass die Min-Sum-Dekodierung so gut ist wie die Sum-Product-Dekodierung; Approximationen führen zu Leistungsverlusten, insbesondere bei niedrigem SNR
  • Vernachlässigung von Effekten endlicher Länge; Graphen, die für asymptotische Analysen entworfen wurden, können bei kurzen Paketen schlechter abschneiden
  • Nichtberücksichtigung der Quantisierung in der Hardware-Implementierung; Gleitkomma-Simulation unterscheidet sich von der Festkomma-Realität

Häufig gestellte Fragen

Was macht die LDPC-Dekodierung im Vergleich zu allgemeinen linearen Codes so effizient?

Die Dünnbesetztheit der Paritätsprüfmatrix bedeutet, dass jedes Bit nur an wenigen Paritätsprüfungen beteiligt ist. Bei der Dekodierung ist die Nachrichtenübermittlung auf dem bipartiten Graphen linear in der Anzahl der Kanten, nicht in der Codelänge. Bei dichten Codes würde die Dekodierung eine Matrixinversion erfordern, die kubisch in der Codelänge ist. Die Dünnbesetztheit macht die Dekodierung quasi-linear und praktisch für lange Codes.

Was ist ein Absorbing Set und warum ist es wichtig?

Ein Absorbing Set ist eine kleine Untermenge des Graphen, die die Belief-Propagation-Dekodierung einfangen und die Konvergenz zur korrekten Lösung verhindern kann. Sie sind eine Hauptursache für den Error Floor (den nicht-exponentiellen Abfall der Bitfehlerrate bei niedrigem SNR). Code-Designer vermeiden kurze Absorbing Sets durch sorgfältige Graphenkonstruktion; Analysetools (z. B. Stopping Set Analysis) identifizieren problematische Strukturen.

Wie verhält sich LDPC im Vergleich zu Polar Codes?

Beide erreichen eine Leistung nahe der Shannon-Grenze. Polar Codes haben eine rekursive Struktur und eine nachweisbare Optimalität unter sukzessiver Dekodierung bei unendlicher Codelänge. LDPC-Codes sind flexibler und haben empirisch eine bessere Leistung bei endlicher Länge. 5G NR verwendet Polar Codes für Steuerkanäle (kurze Pakete) und LDPC für Datenkanäle (lange Pakete), um die Stärken jedes Codes zu nutzen.

Warum ist der Girth des Graphen bei LDPC-Codes wichtig?

Der Girth ist die Länge des kürzesten Zyklus im bipartiten Graphen. Kurze Zyklen (Girth < 6) führen dazu, dass die Belief Propagation korrelierte Informationen verwendet (Nachrichten kehren zurück), was die Leistung verschlechtert. Codes mit hohem Girth (Girth ≥ 6) brechen Korrelationen besser auf. Codes werden oft so entworfen, dass der Girth unter Berücksichtigung von Dünnbesetztheitsbeschränkungen maximiert wird.

Verwandte Methoden

Quellen

  1. Gallager, R. G. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1), 21-28.

    DOI-Referenz öffnen
    Kopiert.
  2. Richardson, T. J., & Urbanke, R. L. (2001). The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2), 599-618.

    DOI-Referenz öffnen
    Kopiert.