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

From LNTwww

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:



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

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