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

• Zurück zum Buch

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

Hinweise:

• Die Aufgabe gehört zum Kapitel  Grundlegendes zu den Low–density Parity–check Codes.
• Bezug genommen wird insbesondere auf die Seite  Zweiteilige LDPC–Graphenrepräsentation – Tanner–Graph.

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

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