Aufgabe 4.12: Regulärer und irregulärer Tanner–Graph

Vorgegebener Tanner–Graph für Code A

Dargestellt ist ein Tanner–Graph eines Codes A mit

den Variable Nodes (abgekürzt VNs) $V_1, \ ... \ , \ 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, \ ... \ , \ 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,i}$ der Prüfmatrix gleich $1$.

In der Aufgabe soll der Zusammenhang zwischen dem oben dargestellten Tanner–Graphen (gültig für den Code 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 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 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.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

Musterlösung

(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$, während 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$.

(4)

Modifizierter Tanner–Graph für den Code B

Betrachtet man den bisherigen Tanner–Graphen, so erkennt man, dass der Lösungsvorschlag 1 richtig ist. Durch Hinzufügen der Zeile „$0 \ 0 \ 0 \ 1 \ 1 \ 1$” richtig ist. 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.

(5) Die der 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_[[:Vorlage:\rm S]]}{w_[[:Vorlage:\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$. Richtig sind demnach die Lösungsvorschläge 2 und 3.

	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 erste Zeile der $\mathbf{H}_{\rm A}$–Matrix ist „$1 \ 1 \ 0 \ 1 \ 0 \ 0$”..
	Die zweite Zeile der $\mathbf{H}_{\rm A}$–Matrix ist „$1 \ 0 \ 1 \ 0 \ 0 \ 1$”.
	Die dritte Zeile 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.