Exercise 4.12: Regular and Irregular Tanner Graph

• Return to book

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

1

Wieviele Zeilen $(m)$ und Spalten $(n)$ hat die Prüfmatrix $\mathbf{H}_{\rm A}$?

$m \hspace{0.18cm} = \ $

$n \hspace{0.3cm} = \ $

2

Welche Aussagen sind aufgrund des Tanner–Graphen zutreffend?

	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$”.

3

Welche Eigenschaften weist der Code $\rm A$ auf?

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

4

Die Matrix $\mathbf{H}_{\rm B}$ ergibt sich aus $\mathbf{H}_{\rm A}$ durch Hinzufügen einer weiteren Zeile. Durch welche vierte Zeile ergibt sich ein regulärer Code $\rm B$?

	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.

5

Welche Eigenschaften weist der Code $\rm B$ auf?

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

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$, 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$” 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 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$. Richtig sind demnach die Lösungsvorschläge 2 und 3.