Exercise 4.13: Decoding LDPC Codes
Die Aufgabe behandelt die Iterative Decodierung von LDPC–Codes gemäß dem Message–passing Algorithmus.
Ausgangspunkt ist die dargestellte $9 × 12$–Prüfmatrix $\mathbf{H}$, die zu Beginn der Aufgabe als Tanner–Graph dargestellt werden soll. Dabei ist anzumerken:
- Die Variable Nodes (abgekürzt $\rm VNs$) $V_i$ bezeichnen die $n$ Codewortbits.
- Die Check Nodes (abgekürzt $\rm CNs$) $C_j$ stehen für die $m$ Prüfgleichungen.
- Eine Verbindung zwischen $V_i$ und $C_j$ zeigt an, dass das Matrixelement $h_{j,\hspace{0.05cm} i}$ der Prüfmatrix $\mathbf{H}$ (in Zeile $j$, Spalte $i$) gleich $1$ ist. Für $h_{j,\hspace{0.05cm}i} = 0$ gibt es keine Verbindung zwischen $V_i$ und $C_j$.
- Als die Nachbarn $N(V_i)$ von $V_i$ bezeichnet man die Menge aller Check Nodes $C_j$, die mit $V_i$ im Tanner–Graphen verbunden sind. Entsprechend gehören zu $N(C_j)$ alle Variable Nodes $V_i$ mit einer Verbindung zu $C_j$.
Die Decodierung erfolgt abwechselnd bezüglich
- den Variable Nodes ⇒ Variable Nodes Decoder (VND), und
- den Check Nodes ⇒ Check Nodes Decoder (CND).
Hierauf wird in den Teilaufgaben (5) und (6) Bezug genommen.
Hinweise:
- Die Aufgabe gehört zum Themengebiet des Kapitels Grundlegendes zu den Low–density Parity–check Codes.
- Bezug genommen wird insbesondere auf die Seite Iterative Decodierung von LDPC–Codes.
- Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Fragebogen
Musterlösung
Der Check Node ${\rm (CN)} \ C_j$ steht für die $j$–Prüfgleichung, und für die Menge aller Check Nodes gilt: ${\rm CN} = \{C_1, \ ... \ , \ C_j, \ ... \ , \ C_m\}$. Aus der Zeilenzahl der $\mathbf{H}$–Matrix ergibt sich $I_{\rm CN} \ \underline {= m = 9}$.
(2) Die Ergebnisse können aus dem nachfolgend skizzierten Tanner–Graphen abgelesen werden.
Richtig sind die Lösungsvorschläge 1, 2 und 5:
- Das Matrixelement $h_{5,5}$ (Spalte 5, Zeile 5) ist $1$ ⇒ rote Verbindung.
- Das Matrixelement $h_{4, 6}$ (Spalte 4, Zeile 6) ist $1$ ⇒ blaue Verbindung.
- Das Matrixelement $h_{6, 4}$ (Spalte 6, Zeile 4) ist $0$ ⇒ keine Verbindung.
- Es gilt $h_{6, 10} = h_{6, 11} = 1$. Aber $h_{6,11} = 0$ ⇒ es bestehen nicht alle drei Verbindungen.
- Es gilt $h_{7,6} = h_{8,7} = h_{9,8} = 1$ ⇒ grüne Verbindungen.
(3) Es handelt sich um einen regulären LDPC–Code mit
- $w_{\rm Z}(j) = 4 = w_{\rm Z}$ für $1 ≤ j ≤ 9$,
- $w_{\rm S}(i) = 3 = w_{\rm S}$ für $1 ≤ i ≤ 12$.
Die Antworten 1 und 4 können schon allein deshalb nicht richtig sein, da
- die Nachbarschaft $N(V_i)$ eines jeden Variable Nodes $V_i$ genau $w_{\rm S} = 3$ Elemente beinhaltet, und
- die Nachbarschaft $N(C_j)$ eines jeden Check Nodes $C_j$ genau $w_{\rm Z} = 4$ Elemente.
Die Antworten 2 und 3 sind richtig, wie aus der ersten Zeile bzw. der neunten Spalte der Prüfmatrix $\mathbf{H}$ hervorgeht. Der Tanner–Graph bestätigt diese Ergebnisse:
- Von $C_1$ gibt es Verbindungen zu $V_1, \ V_2, \ V_3$, und $V_4$.
- Von $V_9$ gibt es Verbindungen zu $C_3, \ C_5$, und $C_7$.
(4) Richtig sind die Lösungsvorschläge 1 und 2, wie aus der entsprechenden Theorieseite hervorgeht:
- Zu Beginn der Decodierung (sozusagen: Iteration 0) werden die $L$–Werte der Variable Nodes ⇒ $L(V_i)$ entsprechend den Kanaleingangswerten vorbelegt.
- Später (ab der Iteration $I = 1$) wird im VND das vom CND übermittelte Log–Likelihood–Verhältnis $L(C_j → V_i)$ als Apriori–Information berücksichtigt.
- Antwort 3 ist falsch. Richtig wäre vielmehr: Es gibt Analogien zwischen dem VND–Algorithmus und der Decodierung eines Repetition Codes.
(5) Richtig ist nur der Lösungsvorschlag 3, weil
- die endgültigen Aposteriori–$L$–Werte vom VND abgeleitet werden, nicht vom CND,
- die $L$–Wert $L(C_j → V_i)$ für den CND extrinsische Information darstellt, und
- es tatsächlich Analogien zwischen dem CND–Algorithmus und der SPC–Decodierung gibt.