Exercise 4.13: Decoding LDPC Codes

• Return to book

Gegebene LDPC–Prüfmatrix

Die Aufgabe behandelt die Decodierung von LDPC–Codes und den Message–passing Algorithmus gemäß Kapitel 4.4.

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 VNs) $V_i$ bezeichnen die $n$ Codewortbits.
• Die Check Nodes (abgekürzt 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, i}$ der Prüfmatrix $\mathbf{H}$ (in Zeile $j$, Spalte $i$) gleich $1$ ist. Für $h_{j,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.
• Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

1

Wie viele Variable Nodes und Check Nodes sind zu berücksichtigen?

$I_{\rm VN} \ = \ $

$I_{\rm CN} \ = \ $

2

Welche der folgenden Variable Nodes und Check Nodes sind verbunden?

	$V_5$ und $C_5$.
	$V_6$ und $C_4$.
	$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 ${\rm N}(V_i)$ und ${\rm N}(C_j)$ zu?

	${\rm N}(V_1) = \{C_1, \ C_2, \ C_3, \ C_4\}$,
	${\rm N}(C_1) = \{V_1, \ V_2, \ V_3, \ V_4\}$,
	${\rm N}(V_9) = \{C_3, \ C_5, \, C_7\}$,
	${\rm 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, \ ... \ , \ 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 VND 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 CND und der Decodierung eines Single Parity–check Codes.

Musterlösung

Solution

(1) 

(2) 

(3) 

(4) 

(5)