Table of Contents
LDPC-Codes (Low Density Parity Check) sind zu einem Eckpfeiler moderner digitaler Kommunikationssysteme geworden, was eine zuverlässige Datenübertragung nahe der Shannon-Grenze ermöglicht. Diese Codes wurden erstmals 1963 von Robert Gallager in seiner Dissertation vorgestellt und später in den 1990er Jahren wiederentdeckt. Diese Codes sind heute integraler Bestandteil von Standards wie DVB-S2, Wi-Fi (IEEE 802.11n/ac/ax), 5G NR und Deep Space Communications. Die Möglichkeit, die Coderate anzupassen, d.h. das Verhältnis von Informationsbits zu insgesamt übertragenen Bits, ist für die Anpassung an unterschiedliche Kanalbedingungen und Servicequalitätsanforderungen unerlässlich. Zwei primäre Techniken zur Anpassung der Coderate ohne Neugestaltung der gesamten Codestruktur sind Punktierung und Verkürzung. Beide Methoden verändern die effektive Coderate, während sie die gleiche zugrunde liegende LDPC-Matrix nutzen, was Flexibilität für ratenkompatible Systeme bietet. Dieser Artikel untersucht die Prinzipien, Implementierungsdetails und praktische Kompromisse von Punktierung und Verkürzung im Rahmen von LDPC-Codes.
Grundlagen der LDPC-Codes
Ein LDPC-Code ist ein linearer Blockcode, der durch eine sparse Parity-Check-Matrix H der Größe mn definiert wird. Die Sparsity von H bedeutet, dass sie sehr wenige Einsen enthält, was eine effiziente iterative Dekodierungsalgorithmen ermöglicht, die typischerweise als Glaubenspropagation (auch bekannt als Summenproduktalgorithmus) auf einer Tanner-Graphendarstellung durchgeführt werden. Im Tanner-Graphen entsprechen variable Knoten den n Bits eines Codeworts und Prüfknoten entsprechen den mH Valid Codewords erfüllen alle Parity-Check-Gleichungen: ]Hc[[FLT:
Die Coderate R wird durch [n – m] gegeben, was den Bruchteil eines Codeworts darstellt, das Originalinformationen trägt. Eine höhere Coderate bedeutet weniger Redundanz (mehr Durchsatz), während eine niedrigere Coderate eine stärkere Fehlerkorrektur (mehr Zuverlässigkeit) liefert.
Warum Code-Raten anpassen?
Kommunikationskanäle variieren im Laufe der Zeit aufgrund von Überblendungen, Störungen und Rauschen. Eine einzelne Coderate kann nicht alle Bedingungen optimal bedienen: unter guten Bedingungen maximiert eine hohe Rate den Datendurchsatz; unter schlechten Bedingungen sorgt eine niedrige Rate für einen zuverlässigen Empfang. Adaptive Codierungs- und Modulationssysteme (ACM-Systeme) benötigen daher ratenkompatible Codes. Durch Durchführen und Verkürzen können derselbe Codierer und Decoder mehrere Raten unterstützen, wodurch die Hardwarekomplexität und der Speicherbedarf reduziert werden.
Die Puncturing Technik
Die Pünktlichkeit ist eine Methode, um die effektive Coderate zu erhöhen, indem einige Bits eines Codewortes nach dem Codieren selektiv entfernt (nicht übertragen) werden. In der Regel wird ein hochfrequenter Muttercode zuerst unter Verwendung einer LDPC-Matrix erzeugt; dann wird eine Teilmenge der Paritätsbits (oder gelegentlich systematische Bits) vor dem Senden verworfen. Der Empfänger, der sich des Punktierungsmusters bewusst ist, behandelt die fehlenden Bits als Löschungen und versucht, das ursprüngliche Codewort unter Verwendung der verbleibenden Bits und der vollständigen Paritätsprüfmatrix wiederherzustellen.
Mathematisch gesehen führt das Punktieren von FLT:6 p FLT:7 p FLT:7 p FLT:7 p FLT:9 n - p FLT:9 n - p . Der Decoder arbeitet jedoch immer noch mit dem vollen FLT:12 n LRLs - Bit variable Node Set - die punktierten variablen Nodes werden mit maximalen Unsicherheiten initialisiert, was eine Löschung anzeigt. Während der iterativen Dekodierung können Nachrichten von Prüfknoten Informationen über die gelöschten Nodes liefern, was oft eine erfolgreiche Wiederherstellung ermöglicht, wenn die Anzahl der punktierten Bits nicht zu groß ist relativ zu der Fehlerkorrekturfähigkeit des Codes.
Punktierung Muster und Design Überlegungen
Die Leistung eines punktierten LDPC-Codes hängt stark davon ab, welche Bits punktiert werden. Zufällige Punktierungen können die Leistung beeinträchtigen, da sie die Struktur des Codes, insbesondere bei kurzen Blocklängen, unterbrechen können.
- Regelmäßige Punktierung: Entfernen Sie Bits nach einem festen periodischen Muster.
- Spaltengewichtsbasierte Punktierung: Priorisieren Sie die Punktierung variabler Knoten mit geringerem Spaltengewicht (weniger Verbindungen zu Knoten prüfen), da sie weniger zur Dekodierung beitragen.
- Wiederherstellungsbewusste Punktierung: Entwerfen Sie das Muster so, dass punktierte Knoten schnell wiederhergestellt werden können - typischerweise indem Sie sicherstellen, dass jeder punktierte Knoten mit mindestens einem Prüfknoten verbunden ist, dessen andere Nachbarn alle übertragen werden (dh ein "Wiederherstellungsprüfknoten").
Ein wichtiges Konzept ist der -Wiederherstellungsbaum: Nach einer bestimmten Anzahl von Dekodierungs-Iterationen kann die LLR eines punktierten Variablenknotens aufgrund extrinsischer Informationen von Prüfknoten ungleich Null werden. Je tiefer der Wiederherstellungsbaum ist, desto mehr Iterationen werden benötigt. Für ratenkompatible Familien werden "Stechstufen" oft vorberechnen, um eine Reihe von Zielraten mit minimaler Leistungsminderung zu erreichen. Zum Beispiel definiert der DVB-S2-Standard eine Reihe von Punktierungsmustern für seine LDPC-Codes, um mehrere Coderaten aus einem einzigen Muttercode zu erzeugen.
Auswirkungen auf die Dekodierungskomplexität
Die Anzahl der für die Konvergenz erforderlichen Iterationen kann jedoch aufgrund der anfänglichen Löschungen zunehmen. Der Decoder muss das Punktierungsmuster kennen, um LLRs entsprechend zu initialisieren. Insgesamt ist Punktierung eine Methode mit geringer Komplexität, um höhere Raten zu erzielen, was sie in adaptiven Systemen beliebt macht.
Die Verkürzungstechnik
Die Verkürzung wird verwendet, um die effektive Coderate zu verringern, wodurch der Code robuster wird. Bei der Verkürzung werden einige der Informationsbits vor der Kodierung auf einen bekannten Wert (normalerweise Null) gesetzt, und diese Bits werden nicht übertragen. Nur die verbleibenden Informationsbits und alle Paritätsbits werden gesendet. Der Empfänger, der weiß, welche Positionen verkürzt wurden, behandelt die bekannten Bits als zusätzliche Nebeninformationen während der Decodierung.
Betrachten wir einen Muttercode mit k information bits und n total bits (rate k/n). Wenn wir s bits verkürzen, besteht das tatsächlich übertragene Codewort aus k – s]n – k übertragenen Bits. Die effektive Rate wird (k – s) / (n – s), was niedriger ist als die Muttercoderate. Der Decoder verwendet die vollständige Paritätsprüfmatrix, initialisiert jedoch die LLRs der verkürzten variablen Knoten auf einen sehr hohen (oder sehr niedrigen) Wert, der das bekannte Bit repräsentiert - und liefert effektiv perfekte Kanalinformationen für diese Positionen. Dies stärkt die Paritätsprüfbeschränkungen und verbessert die Fehlerkorrektur.
Umsetzung und Leistung
Die Verkürzung ist in der Praxis einfach: Der Kodierer setzt die gewählten Informationsbit-Positionen einfach auf Null (oder einen beliebigen bekannten Wert) und codiert dann wie üblich. Am Decoder werden die LLRs für diese variablen Knoten auf +∞ (für eine bekannte Null bei binärer Phasenumtastung) oder die entsprechende große Größe gesetzt. Da diese Bits mit Sicherheit bekannt sind, dienen sie als Ankerpunkte, die dem iterativen Decoder helfen, Unsicherheiten in anderen Bits zu lösen.
Ein wesentlicher Vorteil der Verkürzung besteht darin, dass keine Änderung der Paritätsprüfmatrix oder des Decodierungsalgorithmus erforderlich ist. Die Codestruktur bleibt intakt, aber die Coderate wird effektiv gesenkt. Im Gegensatz zum Punktieren, das Löschungen einführt, die aufgelöst werden müssen, fügt die Verkürzung perfekte Informationen hinzu. Dadurch sind Leistungsverbesserungen im Allgemeinen glatter als diejenigen, die durch die Senkung der Rate über andere Methoden (wie die direkte Verwendung eines niedrigeren Muttercodes) erreicht werden.
Trade-Offs und Interaktionen mit Puncturing
Verkürzung und Punktierung werden oft kombiniert, um eine feinkörnige Anpassung der Rate zu erreichen. Beispielsweise kann ein System einen Muttercode mit Rate 1/2 verwenden, dann Punktierung anwenden, um die Rate gegen 2/3 oder 3/4 zu erhöhen, und gleichzeitig Verkürzung anwenden, um die Rate gegen 1/3 oder 1/4 zu senken. Dieser duale Ansatz ermöglicht es einem einzelnen Decoder, einen breiten Bereich von Raten abzudecken. Die Kombination muss jedoch sorgfältig entworfen werden: Wenn viele Bits sowohl verkürzt als auch punktiert sind (was redundant wäre), kann die Leistung leiden. Typischerweise verkürzen Systeme entweder Informationsbits, um die Rate zu senken, oder Punktionsparitätsbits, um die Rate zu erhöhen, aber nicht beide auf den gleichen Bits.
Ein gängiges Szenario, bei dem beide Techniken zum Einsatz kommen, ist die inkrementale Redundanz (IR) hybride automatische Wiederholungsanforderung (HARQ), wobei zunächst ein hochfrequentes punktiertes Codewort gesendet wird. Bei einem Ausfall der Decodierung werden zusätzliche Paritätsbits (die zuvor punktiert wurden) in nachfolgenden Retransmissionen übertragen - dies ist im Wesentlichen ein IR-Schema, das auf Punktierung basiert.
Vergleich von Punktur und Verkürzung
| Aspect | Puncturing | Shortening |
|---|---|---|
| Effect on code rate | Increases rate (less redundancy) | Decreases rate (more redundancy) |
| Bits removed/not transmitted | Parity (or systematic) bits are omitted | Information bits are set to known value and omitted |
| State at decoder | Punctured bits are erasures (LLR=0) | Shortened bits have perfect LLR (large magnitude) |
| Performance trade-off | Higher rate → less error correction; may need more iterations | Lower rate → stronger error correction; increased overhead |
| Complexity | Same decoder graph; increased iterations possible | Same decoder graph; no extra iterations needed |
| Design challenge | Puncturing pattern must be optimized to avoid error floor | Minimal design effort; works well for small shortening amounts |
| Common use | Adaptive rate increase, ARQ, rate-compatible families | Fine rate reduction, code shortening for specific block sizes |
Anwendungen in modernen Standards
Sowohl Punktierung als auch Verkürzung werden in den wichtigsten Kommunikationsstandards eingesetzt. In DVB-S2 und seiner Erweiterung DVB-S2X werden LDPC-Codes mit einer Rate von 1/4 bis 9/10 unterstützt. Diese werden aus einem gemeinsamen Satz von Muttercodes abgeleitet, die Punktierung und Verkürzung verwenden. Der Standard definiert spezifische Muster, um jede Zielrate zu erreichen, wodurch eine nahezu optimale Leistung gewährleistet wird. In ähnlicher Weise verwendet 5G NR LDPC-Codes für den Datenkanal, mit Basisgraphen (BG1 und BG2), die die Ratenkompatibilität unterstützen.
In Wi-Fi 802.11n/ac/ax sind LDPC-Codes optional, aber weit verbreitet. Der Standard definiert eine Reihe von Coderaten (1/2, 2/3, 3/4, 5/6) für jede Blocklänge. Diese Raten werden erreicht, indem man von einem Rate-1/2-Muttercode ausgeht und durch Punktierung höhere Raten erhält, oder indem man durch Verkürzung niedrigere Raten erhält (obwohl Verkürzung in diesem Zusammenhang weniger üblich ist).
Weltraummissionen, wie sie von der NASA mit dem CCSDS-Standard durchgeführt werden, beruhen auch auf LDPC-Codes mit Punktierung und Verkürzung für Telemetrie- und Befehlsverbindungen. Die Fähigkeit, die Coderate anzupassen, ohne den Hardware-Decoder zu ändern, ist für Langzeitmissionen von unschätzbarem Wert, bei denen die Kanalbedingungen unvorhersehbar sind.
Performance-Metriken und Optimierung
Bei der Entwicklung eines ratenkompatiblen Systems mit Punktierung und Verkürzung bewerten Ingenieure die Bitfehlerrate (BER) und die Frame Error Rate (FER) als Funktionen des Signal-Rausch-Verhältnisses (SNR). Das Ziel ist es, sich dem Shannon-Grenzwert für jede effektive Rate zu nähern. Durch Punktierung wird typischerweise eine kleine Strafe im Vergleich zu einem dedizierten Muttercode derselben Rate eingeführt, aber die Strafe kann durch sorgfältiges Musterdesign minimiert werden. Durch Verkürzung, da bekannte Bits hinzugefügt werden, wird oft sehr nahe an einem natürlichen Low-Rate-Code derselben Dimension gearbeitet.
Eine weitere wichtige Metrik ist der -Fehlerboden - der Bereich bei hohem SNR, in dem die Fehlerrate aufgrund von Trapping-Sets oder kleinen Zyklen im Tanner-Graphen abflacht. Puncturing kann den Fehlerboden erhöhen, wenn er schlecht konzipiert ist, insbesondere für LDPC-Codes mit moderaten Blocklängen.
Forscher haben viele Algorithmen zur gemeinsamen Optimierung von Punktionsmustern vorgeschlagen, einschließlich Dichteentwicklung, extrinsischen Informationstransfer-Diagrammen (EXIT) und genetischen Algorithmen. Zum Beispiel bietet die Arbeit von Ha, Kim und McLaughlin ()"Rate-Compatible Punctured Low-Density Parity-Check Codes With Short Block Lengths", IEEE Transactions on Information Theory, 2004) einen grundlegenden Rahmen für die Gestaltung guter Punktionsmuster. Ebenso kann zur Verkürzung der Effekt auf die extrinsischen Nachrichten des Decoders unter Verwendung der Dichteentwicklung analysiert werden, um keine Verschlechterung zu gewährleisten.
Schlussfolgerung
Durch das Ausblenden und Verkürzen der Coderate von LDPC-Codes, ohne dass mehrere verschiedene Kodierer und Decoder-Implementierungen erforderlich sind, wird die effektive Rate erhöht, indem Bits weggelassen und in Löschungen am Decoder umgewandelt werden, während durch das Verkürzen die Rate verringert wird, indem Informationsbits an bekannte Werte angepasst und nicht übertragen werden. Beide Methoden bewahren die Kernstruktur der LDPC-Matrix und ermöglichen eine flexible Ratenkompatibilität für adaptive Kommunikationssysteme. Moderne Standards wie DVB-S2, 5G NR und Wi-Fi beruhen auf diesen Techniken, um eine robuste Leistung über einen breiten Bereich von Kanalbedingungen zu bieten. Mit den kontinuierlichen Fortschritten in der Musteroptimierung und dem Decoderdesign bleiben punktierte und verkürzte LDPC-Codes ein lebendiges Forschungsgebiet und ein praktischer Eckpfeiler der digitalen Kommunikation.