Aufgaben:Exercise 4.13: Decoding LDPC Codes

• Return to book

Gegebene LDPC–Prüfmatrix

Die Aufgabe behandelt die  Iterative Decodierung von LDPC–Codes  gemäß dem  Message–passing Algorithmus.

Ausgangspunkt ist die dargestellte  $9 &times 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 Kapitel  Grundlegendes zu den Low–density Parity–check Codes.
• Bezug genommen wird insbesondere auf die Seite  Iterative Decodierung von LDPC–Codes.

Fragebogen

1 Wie viele  Variable Nodes $(I_{\rm VN})$  und  Check Nodes $(I_{\rm CN})$  sind zu berücksichtigen?

$I_{\rm VN} \ = \ $

$I_{\rm CN} \ = \ $

2 Welche der folgenden  Check Nodes  und  Variable Nodes  sind verbunden?

	$C_4$  und  $V_6$.
	$C_5$  und  $V_5$.
	$C_6$  und  $V_4$.
	$C_6$  und  $V_i$  für  $i > 9$.
	$C_j$  und  $V_{j-1}$  für  $j > 6$.

3 Welche Aussagen treffen bezüglich der Nachbarn  $N(V_i)$  und  $N(C_j)$  zu?

	$N(V_1) = \{C_1, \ C_2, \ C_3, \ C_4\}$,
	$N(C_1) = \{V_1, \ V_2, \ V_3, \ V_4\}$,
	$N(V_9) = \{C_3, \ C_5, \, C_7\}$,
	$N(C_9) = \{V_3, \ V_5, \ V_7\}$.

4 Welche Aussagen treffen für den  Variable Node Decoder  (VND) zu?

	Zu Beginn (Iteration 0) werden die  $L$–Werte der Knoten  $V_1, \hspace{0.05cm} \text{...} \hspace{0.05cm}, \ V_n$  entsprechend den Kanaleingangswerten  $y_i$  vorbelegt.
	Für den VND stellt  $L(C_j → V_i)$  Apriori–Information dar.
	Es gibt Analogien zwischen dem  Variable Node Decoder  und der Decodierung eines Single Parity–check Codes.

5 Welche Aussagen treffen für den  Check Node Decoder  (CND) zu?

	Der CND liefert am Ende die gewünschten Aposteriori–$L$–Werte.
	Für den CND stellt  $L(C_j → V_i)$  Apriori–Information dar.
	Es gibt Analogien zwischen dem  Check Node Decoder  und der Decodierung eines Single Parity–check Codes.

Musterlösung

Solution

(1)  Der Variable Node $\rm (VN)$ $V_i$ steht für das $i$–te Codewortbit, so dass $I_{\rm VN}$ gleich der Codewortlänge $n$ ist.

• Aus der Spaltenzahl der $\mathbf{H}$–Matrix erkennt man $I_{\rm VN} = n \ \underline{= 12}$.
• Für die Menge aller Variable Nodes kann man somit allgemein schreiben: ${\rm VN} = \{V_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , V_i, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ V_n\}$.
• 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, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ C_j, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ 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.

Tanner–Graph für das vorliegende Beispiel

Richtig sind die Lösungsvorschläge 1, 2 und 5:

• Das Matrixelement $h_{5,\hspace{0.05cm}5}$ (Spalte 5, Zeile 5) ist $1$  
  ⇒   rote Verbindung.
• Das Matrixelement $h_{4,\hspace{0.05cm} 6}$ (Spalte 4, Zeile 6) ist $1$  
  ⇒   blaue Verbindung.
• Das Matrixelement $h_{6, \hspace{0.05cm}4}$ (Spalte 6, Zeile 4) ist $0$  
  ⇒   keine Verbindung.
• Es gilt $h_{6,\hspace{0.05cm} 10} = h_{6,\hspace{0.05cm} 11} = 1$. Aber $h_{6,\hspace{0.05cm}12} = 0$  
  ⇒   es bestehen nicht alle drei Verbindungen.
• Es gilt $h_{7,\hspace{0.05cm}6} = h_{8,\hspace{0.05cm}7} = h_{9,\hspace{0.05cm}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 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$.

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.

(4)  Richtig sind die Lösungsvorschläge 1 und 2, wie aus der entsprechenden Theorieseite hervorgeht:

• Zu Beginn der Decodierung  $($sozusagen bei der Iteration $I=0)$  werden die $L$–Werte der Variable Nodes  ⇒  $L(V_i)$ mit 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.
• Die Antwort 3 ist falsch. Richtig wäre vielmehr: Es gibt Analogien zwischen dem VND–Algorithmus und der Decodierung eines Repetition Codes (Wiederholungscodes).

(5)  Richtig ist nur der Lösungsvorschlag 3, weil

• die endgültigen Aposteriori–$L$–Werte vom VND abgeleitet werden, nicht vom CND,
• der $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.