Exercise 4.12: Regular and Irregular Tanner Graph

Vorgegebener Tanner–Graph für Code $\rm A$

Dargestellt ist ein Tanner–Graph eines Codes $\rm A$ mit

den Variable Nodes (abgekürzt VNs) $V_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ V_6$, wobei $V_i$ das $i$–te Codewortbit kennzeichnet (egal, ob Informations – oder Paritybit) und der $i$–ten Spalte der Prüfmatrix entspricht;
den Check Nodes (abgekürzt CNs) $C_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ C_3$, die die Zeilen der $\mathbf{H}_{\rm A}$–Matrix und damit die Prüfgleichungen repräsentieren.

Eine Verbindungslinie (englisch: Edge) zwischen $V_i$ und $C_j$ zeigt an, dass das $i$–te Codewortsymbol an der $j$–ten Prüfgleichung beteiligt ist. In diesem Fall ist das Element $h_{j,\hspace{0.05cm}i}$ der Prüfmatrix gleich $1$.

In der Aufgabe soll der Zusammenhang zwischen dem oben dargestellten Tanner–Graphen (gültig für den Code $\rm A$) und der Matrix $\mathbf{H}_{\rm A}$ angegeben werden. Außerdem ist der Tanner–Graph zu einer Prüfmatrix $\mathbf{H}_{\rm B}$ aufzustellen, die sich aus $\mathbf{H}_{\rm A}$ durch Hinzufügen einer weiteren Zeile ergibt. Diese ist so zu ermitteln, dass der zugehörige Code $\rm B$ regulär ist. Das bedeutet:

Von allen Variable Nodes $V_i$ (mit $1 ≤ i ≤ n$) gehen gleich viele Linien (Edges) ab, ebenso von allen Check Nodes $C_j$ (mit $1 ≤ j ≤ m$).
Die Hamming–Gewichte aller Zeilen von $\mathbf{H}_{\rm B}$ sollen jeweils gleich sein $(w_{\rm Z})$, ebenso die Hamming–Gewichte aller Spalten $(w_{\rm S})$.
Für die Rate des zu konstruierenden regulären Codes $\rm B$ gilt dann die folgende untere Schranke:

$$R \ge 1 - \frac{w_{\rm S}}{w_{\rm Z}} \hspace{0.05cm}.$$

Hinweis:

Die Aufgabe gehört zum Themengebiet des Kapitels Grundlegendes zu den Low–density Parity–check Codes.
Bezug genommen wird insbesondere auf die Seite Zweiteilige LDPC–Graphenrepräsentation – Tanner–Graph.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

Musterlösung

Solution

(1) Die Anzahl der $\mathbf{H}_{\rm A}$–Zeilen ist gleich der Anzahl der Check Nodes $C_j$ im Tanner–Graphen ⇒ $\underline{m = 3}$, und die Anzahl $\underline{n = 6}$ der Variable Nodes $V_i$ ist gleich der Spaltenzahl.

(2) Richtig sind die Antworten 1 und 3 im Gegensatz zur Aussage 2:

Die zweite $\mathbf{H}_{\rm A}$–Zeile lautet vielmehr „$1 \ 0 \ 1 \ 0 \ 1 \ 0$”. Somit liegt dieser Aufgabe die folgende Prüfgleichung zugrunde:

Zugrunde liegende Prüfgleichungen

$${ \boldsymbol{\rm H}}_{\rm A} = \begin{pmatrix} 1 &1 &0 &1 &0 &0\\ 1 &0 &1 &0 &1 &0\\ 0 &1 &1 &0 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$

Im Schaubild sind die Prüfgleichungen als rote (Zeile 1), grüne (Zeile 2) bzw. blaue (Zeile 3) Gruppierung veranschaulicht.

(3) Richtig sind die Lösungsvorschläge 1 und 3:

Die $\mathbf{H}$–Matrix endet mit einer $3 × 3$–Diagonalmatrix ⇒ systematischer Code.
Damit sind die Hamming–Gewichte der drei letzten Spalten $w_{\rm S}(4) = w_{\rm S}(5) = w_{\rm S}(6) = 1$.
Für die ersten drei Spalten gilt: $w_{\rm S}(1) = w_{\rm S}(2) = w_{\rm S}(3) = 2$ ⇒ irregulärer Code.
Die drei Matrixzeilen sind linear unabhängig. Damit gilt $k = n - m = 6 - 3 = 3$ und $R = k/n = 1/2$.

Modifizierter Tanner–Graph für den Code $\rm B$

(4) Richtig ist der Lösungsvorschlag 1:

Betrachtet man den bisherigen Tanner–Graphen, so erkennt man die Richtigkeit von Lösungsvorschlag 1.
Durch Hinzufügen der Zeile „$0 \ 0 \ 0 \ 1 \ 1 \ 1$” zur $\mathbf{H}_{\rm A}$–Matrix erhält man:

$${ \boldsymbol{\rm H}}_{\rm B} = \begin{pmatrix} 1 &1 &0 &1 &0 &0\\ 1 &0 &1 &0 &1 &0\\ 0 &1 &1 &0 &0 &1\\ 0 &0 &0 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$

Die Modifikationen sind in nebenstehender Grafik rot markiert: Durch den neu hinzugefügten Check Node $C_4$ und die Verbindungen mit $V_4, \ V_5$ und $V_6$ gehen nun

von allen Variable Nodes $V_i$ zwei Linien ab, und
von allen Check Nodes $C_j$ einheitlich vier.

Dies ist die Bedingung dafür, dass der Code $\rm B$ regulär ist.

(5) Richtig sind die Lösungsvorschläge 2 und 3:

Die Konstruktion in Teilaufgabe (4) liefert einen regulären Code.
Die Hamming–Gewichte der Zeilen bzw. Spalten sind $w_{\rm Z} = 3$ und $w_{\rm S} = 2$.
Damit ergibt sich als untere Schranke für die Coderate:

$$R \ge 1 - \frac{w_{\rm S}}{w_{\rm Z}} = 1 - {2}/{3} = 1/3 \hspace{0.05cm}.$$

Durch die $\mathbf{H}$–Manipulation ändert sich nichts an der Generatormatrix $\mathbf{G}$.
Gesendet wird weiterhin der gleiche Code mit der Coderate $R = 1/2$.

	Der Code ist systematisch.
	Der Code ist regulär.
	Die Coderate ist $R = 1/2$.
	Die Coderate ist $R = 1/3$.

	Der Code ist systematisch.
	Der Code ist regulär.
	Die Coderate ist $R = 1/2$.
	Die Coderate ist $R = 1/3$.

	Die Zeile 1 der $\mathbf{H}_{\rm A}$–Matrix ist „$1 \ 1 \ 0 \ 1 \ 0 \ 0$”.
	Die Zeile 2 der $\mathbf{H}_{\rm A}$–Matrix ist „$1 \ 0 \ 1 \ 0 \ 0 \ 1$”.
	Die Zeile 3 der $\mathbf{H}_{\rm A}$–Matrix ist „$0 \ 1 \ 1 \ 0 \ 0 \ 1$”.

	Durch Hinzufügen von „$0 \ 0 \ 0 \ 1 \ 1 \ 1$”.
	Durch Hinzufügen von „$1 \ 1 \ 1 \ 1 \ 1 \ 1$”.
	Durch Hinzufügen irgend einer anderen Zeile.