Exercise 4.12: Regular and Irregular Tanner Graph
From LNTwww
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.
Fragebogen
Musterlösung
(1)
(2)
(3)
(4)
(5)
