Table of Contents
Einführung in LDPC-Codes und ihre Leistung
LDPC-Codes (Low-Density Parity-Check), die Robert Gallager in seiner Dissertation 1960 entdeckt und später in den 1990er Jahren wiederentdeckt hat, sind zu einem Eckpfeiler der modernen digitalen Kommunikation geworden. Sie werden in Standards wie DVB-S2, Wi-Fi (IEEE 802.11n/ac/ax), 5G NR und Satellitenkommunikation eingesetzt. LDPC-Codes werden durch eine spärliche Paritätsprüfmatrix definiert, die einem zweigliedrigen Tannergraphen mit variablen Knoten (Codebits) und Prüfknoten (Paritätsgleichungen) entspricht. Der iterative Dekodierungsalgorithmus, typischerweise Glaubenspropagation (BP) oder eine Min-Sum-Variante, leitet Nachrichten entlang der Ränder dieses Graphen.
Die Leistung eines LDPC-Codes wird oft durch seine -Schwelle charakterisiert - den maximalen Kanalrauschpegel (oder minimalen SNR), bei dem die Wahrscheinlichkeit eines Decodierungsfehlers willkürlich nahe Null getrieben werden kann, da die Codelänge bis unendlich neigt.
Dieser Artikel bietet eine eingehende Untersuchung der Optimierung der Gradverteilung für LDPC-Codes. Wir überprüfen zuerst die Grundlagen der LDPC-Dekodierung und Schwellenwerte. Dann untersuchen wir die Rolle von Gradverteilungen und untersuchen klassische Optimierungstechniken wie Dichteentwicklung und EXIT-Diagramme. Wir passen die Diskussion anschließend auf spezifische Kanalmodelle an - binär symmetrischer Kanal (BSC), additives weißes Gauß-Rauschen (AWGN) Kanal, binärer Löschkanal (BEC) und Rayleigh-Verbleibkanäle - und zeigen, wie Verteilungen angepasst werden müssen. Schließlich berühren wir endliche Längenüberlegungen und praktisches Codedesign, unterstützt durch externe Referenzen für weitere Lektüre.
LDPC-Codes und Schwellenwerte verstehen
Ein LDPC-Code der Länge n und Dimension k wird durch eine mnH= n − definiert. Die Matrix ist spärlich: Die Zahl der Einsen ist linear in n, typischerweise O(n). In der Tanner-Graphendarstellung entsprechen variable Knoten Spalten von H und prüfen Knoten auf Zeilen. Eine Kante verbindet variablen Knoten v zu prüfen Knoten , wenn Hc,v = 1.
Der Dekodierungsalgorithmus arbeitet durch iterativen Austausch von Nachrichten entlang dieser Ränder. Für den BEC sind Nachrichten Löschungen, Bits oder unbekannte Symbole. Für symmetrische Kanäle wie BSC und AWGN sind Nachrichten Log-Likelihood-Verhältnisse (LLRs). Der Algorithmus konvergiert, wenn alle Paritätsprüfungen erfüllt sind oder nach einer maximalen Anzahl von Iterationen. Der -Schwellenwert wird über die Dichteentwicklung definiert: Für ein gegebenes Codeensemble (definiert durch Gradverteilungen) kann man den maximalen Kanalparameter (z. B. Crossover-Wahrscheinlichkeit p für BSC, Rauschvarianz σ2 für AWGN, Löschwahrscheinlichkeit ε für BEC) so berechnen, dass die Dekodierungsfehlerwahrscheinlichkeit zu Null tendiert als n → ∞. Schwellenwerte sind ein grundlegendes Maß für die asymptotische Leistung eines Ensembles und dienen als Leitfaden
Rolle der Gradverteilungen
Gradverteilungen werden typischerweise durch Polynome dargestellt. Für variable Knoten, lassen Sie λx = Σ]] ist der Bruchteil der Kanten, die auf variable Knoten des Grades ]=]]x]=1 − (∫0]]1]0111]λ[[
Die Wahl der Verteilungen beeinflusst den Fluss von extrinsischen Informationen während der Decodierung. Ein variabler Knoten von Grad dv sammelt Informationen von dv Incident Check Nodes und der Kanalbeobachtung; er sendet dann aktualisierte Nachrichten zurück. Variable Hochgrad-Knoten erhalten vielfältigere Check-Nachrichten, die die Konvergenz beschleunigen können, aber sie propagieren auch mehr Fehler, wenn die Check-Nachrichten unzuverlässig sind. Niedriggrad-Knoten sind robuster für Rauschen, aber konvergieren langsam. In ähnlicher Weise führen Prüfknoten von Grad dc eine Paritätsoperation durch; höhergradige Prüfknoten können mehr Einschränkungen verarbeiten, aber auch längere Zyklen im Graphen erzeugen, was die Leistung unter iterativer Decodierung potenziell beeinträchtigen kann.
Variable Knotengradverteilung
Die Verteilung des variablen Knotengrads hat einen starken Einfluss auf den Code-Schwellenwert ] und den Decodierungsschwellenwert . In der wegweisenden Arbeit von Luby, Mitzenmacher, Shokrollahi und Spielman (1998) auf unregelmäßigen LDPC-Codes wurde gezeigt, dass variable Knoten mit einer Mischung von Graden - einige hoch, einige niedrig - Schwellenwerte extrem nahe an der Shannon-Grenze für den BEC erreichen können. Die Intuition ist, dass hochgradige Knoten, die viele Nachrichten empfangen, schnell ihren korrekten Wert lernen und dann niedrigeren Grad-Knoten durch Prüfknoten helfen. Für den AWGN-Kanal haben unregelmäßige Verteilungen mit sorgfältiger Optimierung Schwellenwerte innerhalb von 0,0045 dB erreicht Kapazität. Gemeinsame Muster umfassen einige wenige hochgradige variable Knoten (z. B. Grad 20, 30) und viele niedriggradige Knoten (z. B. Grad 2, 3).
Überprüfen Sie die Knotengradverteilung
Check-Node-Grad sind ebenfalls wichtig, obwohl ihre Auswirkungen im Vergleich zu variablen Knoten oft sekundär sind. Für den BEC konzentriert sich die optimale Check-Node-Verteilung um einen einzigen Grad (oft 4–10), um den Schwellenwert zu maximieren, wie Shokrollahi (2002) zeigt. Für AWGN-Kanäle liegen die Check-Node-Grad-Grad typischerweise zwischen 3 und 10; höhere Grade erhöhen die Check-Node-Komplexität, können aber den Schwellenwert verbessern. Eine häufige Wahl ist eine konzentrierte Grad-Verteilung, z. B. ρ3 x2 + x3 + ... + ρxm-1). Die Optimierung muss die Erhöhung des Schwellenwerts mit der Zunahme der Dekodierungskomplexität und dem Risiko der Einführung kurzer Zyklen ausgleichen.
Optimierungsmethoden für Gradverteilungen
Die Suche nach optimalen Gradverteilungen ist ein nicht konvexes Optimierungsproblem, das mit verschiedenen analytischen und numerischen Techniken angegangen wurde: Die drei häufigsten Methoden sind Dichteentwicklung (DE), Extrinsic Information Transfer (EXIT) Charts und lineare Programmierung (LP) Approximationen.
Dichteentwicklung
Die Dichteentwicklung, eingeführt von Richardson und Urbanke (2001), verfolgt die Wahrscheinlichkeitsdichtefunktion (pdf) von Nachrichten, die während der iterativen Decodierung ausgetauscht werden, vorausgesetzt, dass ein zyklusfreier (baumähnlicher) Graph vorliegt. Für den BEC sind die Nachrichten binär (Löschung oder bekannt), so dass DE die Verfolgung der Löschwahrscheinlichkeit durch den Graphen reduziert. Für AWGN-Kanäle verfolgt DE die pdf-Datei von LLRs, die unter der symmetrischen Gaußschen Approximation die Verfolgung des Mittelwerts ]mmλx und ρx finden, die den Geschwindigkeitseinschränkungen entsprechen und den Schwellenwert maximieren. Dies wird oft unter Verwendung linearer Programmierung über diskretisierte Gradverteilungen durchgeführt, da DE für BEC als lineare Einschränkung formuliert werden kann. Für allgemeine Kanäle wird ein Differentialentwicklungs- oder Bergkletteral
AUSGANGS-Charts
Die von 10 Brink (2001) entwickelten EXIT-Diagramme stellen ein grafisches Werkzeug zur Analyse des Konvergenzverhaltens von iterativen Decodern dar. Sie zeichnen die von variablen Knoten zu Prüfknoten übertragenen gegenseitigen Informationen (MI) gegenüber MI auf, die von Prüfknoten zu variablen Knoten übertragen werden. Die resultierenden Kurven, charakteristische Kurven, dürfen sich nicht schneiden, damit die Decodierung erfolgreich ist. Die Optimierung von Gradverteilungen mit EXIT-Diagrammen beinhaltet die Anpassung des Bereichs unter der variablen Knotenkurve an den Bereich unter der Prüfknotenkurve, wobei der Bereichsunterschied mit der Lücke zur Kapazität zusammenhängt. EXIT-Diagramme sind besonders beliebt für AWGN-Kanäle, weil sie rechnerisch einfacher sind als vollständige DE und geben intuitive Einblicke. Sie beruhen jedoch auf der Gaußschen Approximation von LLR-Verteilungen, die für starkes Rauschen oder unregelmäßige Verteilungen weniger genau wird.
Lineare Programmierung und andere Ansätze
Für den BEC kann das Optimierungsproblem als lineares Programm dargestellt werden, da die DE-Bedingung auf eine lineare Ungleichheit der Koeffizienten von λ und ρ reduziert. Lineare Programmierung liefert global optimale Verteilungen (über einen gegebenen Gradsatz) effizient. Für allgemeine Kanäle sind die Einschränkungen nichtlinear, so dass Heuristiken wie simuliertes Glühen, genetische Algorithmen oder Gradienten-basierte Methoden verwendet werden. Neuere Fortschritte verwenden maschinelles Lernen (z. B. Verstärkungslernen), um den Raum der Gradverteilungen zu durchsuchen. Ein anderer Ansatz besteht darin, ein Extrinsic Information Transfer (EXIT) Diagramm zu verwenden, das mit einer Kostenfunktion auf der Grundlage der Bereichseigenschaft passt. Unabhängig von der Methode ist das Ergebnis ein Satz von Gradpaaren (dv, dc und Brüche, die den Schwellenwert für eine feste Rate und ein spezifisches Kanalmodell maximieren.
Optimierung für verschiedene Kanalmodelle
Verschiedene Kanäle haben unterschiedliche statistische Eigenschaften, die die Art der ausgetauschten Nachrichten und damit die optimale Gradverteilung beeinflussen. Im Folgenden werden vier Hauptkanalmodelle diskutiert: BEC, BSC, AWGN und Rayleigh Fading.
Binärer Erasure Channel (BEC)
Der BEC ist der einfachste nichttriviale Kanal: mit Wahrscheinlichkeit ε wird ein Bit gelöscht (unbekannt) und ansonsten korrekt empfangen. Der Schwellenwert ist der maximale ε, so dass die Dekodierung erfolgreich ist. Für den BEC sind die optimalen Gradverteilungen analytisch über lineare Programmierung bekannt. 2001 zeigten Luby et al., dass die optimale variable Knotenverteilung Kapazität erreichen kann (ε = 1 − R) asymptotisch. Die optimale variable Knotenverteilung umfasst hochgradige Knoten (z. B. Grad bis zu 50 oder 100) und einen großen Bruchteil von Grad-2-Knoten. Jedoch erzeugen Grad-2-Knoten eine "Stopping Set"-Schwachstelle bei endlichen Längen, was zu einem Fehlerboden führt. Praktische Designs für BEC (z. B. Raptor-Codes) verwenden Gradverteilungen mit nur wenigen Grad-2-Knoten und einem schweren Schwanz. Überprüfen Sie die Knotenverteilung wird typischerweise auf einen einzigen Grad konzentriert, oft dc = 4 für einen Rate 1/2
Binär symmetrischer Kanal (BSC)
Die BSC-Flips Bits unabhängig mit Wahrscheinlichkeit p sind komplexer, weil Nachrichten binär (harte Entscheidungen) in einem Hard-Decision-Decoder (z. B. Gallagers Algorithmus A/B) oder weiche Werte sind, wenn BP mit LLRs verwendet wird. Für Hard-Decision-Decoding sind Gradverteilungen oft regelmäßig (alle variablen Knoten gleichen Grades, alle Prüfknoten gleichen Grades), weil Unregelmäßigkeit wenig Gewinn bietet. Der optimale reguläre LDPC-Code für BSC unter Gallagers Algorithmus hat variablen Grad 3 und Prüfgrad 6 für Rate 1/2, Erreichung eines Schwellenwerts in der Nähe von p ≈ 0.02. Für Soft-Decision BP auf BSC (unter Verwendung von LLRs, die aus harten Bits umgewandelt werden), können unregelmäßige Verteilungen den Schwellenwert verbessern, aber der Gewinn ist bescheiden im Vergleich zu AWGN. Forschung von Chung, Forney, et al. (2001) gibt optimierte Verteilungen für BSC, die Schwellenwerte in der
AWGN-Kanal (Additiv White Gaußian Noise)
Der AWGN-Kanal ist das am meisten untersuchte Modell. Das Ziel ist es, den SNR-Schwellenwert (oft ausgedrückt als Eb/N0 für eine gegebene Coderate zu maximieren. Die Dichteentwicklung unter der Gaußschen Approximation, Richardson und Urbanke (2001) abgeleitete, optimierte Gradverteilungen für verschiedene Raten. Zum Beispiel kann ein Rate-1/2 unregelmäßiger LDPC-Code variable Knotengrade 2, 3, 6 und 10 in bestimmten Bruchteilen haben und Knotengrade 4, 5 und 6 überprüfen. Der Schwellenwert kann so niedrig wie 0,19 dB vom Shannon-Limit entfernt sein (was bei Rate 1/2 0 dB für binäre Modulation ist). Aggressivere Verteilungen mit sehr hohen variablen Knoten (bis zu 50) können die Lücke auf 0,0045 dB reduzieren, aber auf Kosten erhöhter Dekodierungskomplexität und Speicher. Moderne Standards wie 5G NR verwenden quasizyklische LDPC-Codes mit pro
Rayleigh Fading Channel (mit oder ohne CSI)
In einem Rayleigh-Überblendkanal variiert die Amplitude des empfangenen Signals aufgrund des Überblendvorgangs. Bei perfekten Kanalzustandsinformationen (CSI) am Empfänger ist der effektive Kanal ein Satz Gauß-Unterkanäle mit unterschiedlichen Verstärkungen. Die optimale Gradverteilung muss sich an die Überblendstatistiken anpassen. Wie von Hou, Siegel und Milstein (2003) gezeigt, können unregelmäßige LDPC-Codes mit optimierten Gradverteilungen Schwellenwerte erreichen, die den durchschnittlichen gegenseitigen Informationen des Überblendkanals nahe kommen. Die Haupterkenntnis ist, dass variable Knoten, die tiefe Überblendungen erfahren, mehr Schutz vor verbundenen Prüfknoten benötigen, was bedeutet, dass eine hohe Verteilung erforderlich ist, um Informationen zu bündeln. Die optimale Verteilung ist schwerer ausgelastet als bei AWGN; hochgradige Knoten (z. B. 20-30) erscheinen häufiger. Prüfknotengrade sind typischerweise um 4-8 konzentriert. Für Systeme ohne CSI (nicht kohärentes Überblendvorgang) ist das Problem anspruchsvoller und Gradverteilungen werden oft für spezifische Dopplerspreads mit EXIT-Diagrammen optimiert. Untersuchungen von A. Grant und anderen haben gezeigt, dass übereinstimmende
Fortgeschrittene Themen in der Gradverteilungsoptimierung
Finite-Length-Effekte und Fehler-Etage
Asymptotische Schwellenwerte führen zum Design, aber praktische Codes haben endliche Längen ]n (z. B. 648 bis 1944 Bits in 5G). Bei endlichen Längen wird der Fehlerboden - ein Bereich mit sehr geringer Fehlerwahrscheinlichkeit, der mit SNR nicht schnell abnimmt - kritisch. Der Fehlerboden von LDPC-Codes wird hauptsächlich durch kleine Stopp-Sets (für BEC) oder Trapping-Sets (für AWGN) verursacht. Gradverteilungen mit vielen variablen Knoten mit niedrigem Grad (insbesondere Grad 2) sind anfällig für solche Strukturen. Um den Fehlerboden zu mildern, muss die Optimierung Einschränkungen für den Graphenumfang (minimale Zykluslänge) und die spektralen Eigenschaften des Codes enthalten. Einige Ansätze übernehmen eine multi-objektive Optimierung: Maximieren Sie den Schwellenwert bei gleichzeitiger Minimierung der Anzahl kleiner Trapping-Sets. Dies führt oft zu Verteilungen mit weniger Grad-2-Knoten und einem konzentrierteren variablen Knotengrad. Protographenbasierte LDPC-Codes, die den Code durch eine kleine Basismatrix definieren, die angehoben wird, ermöglichen eine
Durchführungsbedenken
Während Hochgrad-Knoten die Schwellenwerte verbessern, erhöhen sie die Dekodierkomplexität. Für jede Iteration ist die Anzahl der Operationen pro Kante proportional zum Grad. Ein variabler Knoten mit Grad 30 erfordert 30 Additionen (für LLR-Updates) pro Iteration, verglichen mit 3 für einen Grad-3-Knoten. In der Hardware begrenzen Speicher- und Bandbreitenbeschränkungen oft den maximalen Grad auf etwa 10-20. In ähnlicher Weise erhöhen hohe Prüfknotengrade die Anzahl der Min-Summen- oder Summenproduktoperationen. Viele praktische Kodierer (z. B. für Wi-Fi) verwenden einen eingeschränkten Satz von Graden: variable Grade nur 2, 3, 4, 6 und 10; Prüfgrad nur 4-8. Optimierung unter solchen Einschränkungen ist ein aktiver Bereich. Ein weiteres Problem ist der Coderatenverlust aufgrund der Notwendigkeit von Paritätsbits. Die Designrate aus der Gradverteilungsformel kann geringfügig von der tatsächlichen Rate abweichen nach Graphenkonstruktion. Es muss darauf geachtet werden, dass die Verteilungsgleichungen konsistent sind.
Code Design Beispiele
Zur Veranschaulichung sei ein Rate-1/2 LDPC-Code für den AWGN-Kanal betrachtet. Unter Verwendung linearer Programmierung mit Dichteentwicklung wird oft die folgende Verteilung (von Richardson & amp; Urbanke, 2001) zitiert:
| Variable degree | Fraction of edges |
|---|---|
| 2 | 0.289 |
| 3 | 0.171 |
| 6 | 0.486 |
| 10 | 0.055 |
Und die Knotenverteilung überprüfen: ρ(x) = 0,497 x3 + 0,503 x4 (d.h. Bruchteile von Kanten, die auf den 4. und 5. Grad der Knoten einfallen). Dieses Ensemble hat einen Schwellenwert von Eb/N0 = 0,19 dB. Im Gegensatz dazu hat ein regulärer (3,6) Code einen Schwellenwert von etwa 0,7 dB. Das unregelmäßige Design gewinnt um 0,5 dB. Für den BEC ist eine optimale Rate-1/2-Verteilung (Shokrollahi, 2002):
| Variable degree | Fraction of edges |
|---|---|
| 2 | 0.420 |
| 3 | 0.020 |
| 10 | 0.010 |
| 100 | 0.550 |
Die Verteilung der Prüfknoten konzentriert sich auf Grad 4 (100%). Der Schwellenwert ist ε = 0,499, was der Kapazität von 0,5 sehr nahe kommt.
Schlussfolgerung
Die Optimierung von Gradverteilungen ist ein leistungsfähiger Weg, um den Schwellenwert von LDPC-Codes zu maximieren, indem sie sie an die Shannon-Grenze für verschiedene Kanalmodelle heranführt. Die Wahl von variablen und überprüfenden Knotengradprofilen bestimmt den Informationsfluss während der iterativen Decodierung und muss auf die Rauscheigenschaften des Kanals zugeschnitten werden. Für Löschkanäle ergibt lineare Programmierung nahezu optimale Verteilungen mit variablen Graden mit großem Ausmass. Für AWGN und Fading-Kanäle leiten Dichteentwicklung und EXIT-Diagramme das Design, was oft zu unregelmäßigen Profilen mit wenigen hochgradigen Knoten führt. Praktische Einschränkungen wie endliche Länge, Fehlerpegel und Decodierungskomplexität setzen Grenzen, auf denen Verteilungen realisierbar sind, was die Optimierung zu einem Kompromiss zwischen asymptotischer Leistung und Implementierbarkeit macht.
Während sich Kommunikationsstandards zu höherem Durchsatz und niedrigerer Latenz entwickeln, geht die Nachfrage nach optimierten LDPC-Codes weiter. Jüngste Forschung untersucht maschinelle Lernbasierte Optimierung, Protographenmodifikationen und kombinierte Grad- und Umfangsoptimierung. Das Verständnis der Grundlagen der Gradverteilungsoptimierung befähigt Ingenieure, bessere Codes für drahtlose, Satelliten- und Speichersysteme der nächsten Generation zu entwerfen. Für weitere Informationen siehe das klassische Lehrbuch FLT:0" "Moderne Coding-Theorie" von Richardson und Urbanke FLT:2 "Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes" von Chung et al. FLT:3 (2001) und die umfassende Umfrage FLT: 4 "A Decade of LDPC Codes" von Johnson und Weller FLT: 5 . Für praktische Implementierungsdetails sind die 5G-Standardspezifikationen verfügbar von FLT: 6 . 38.212 FLT: 7 .