Exercise 4.12: Regular and Irregular Tanner Graph
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
Musterlösung
(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:
- $${ \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$.
(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$.
