Aufgaben:Aufgabe 4.12: Regulärer und irregulärer Tanner–Graph: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
K (Textersetzung - „* Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “)
 
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt)
Zeile 1: Zeile 1:
 
{{quiz-Header|Buchseite=Kanalcodierung/Grundlegendes zu den Low–density Parity–check Codes}}
 
{{quiz-Header|Buchseite=Kanalcodierung/Grundlegendes zu den Low–density Parity–check Codes}}
  
[[Datei:P_ID3072__KC_A_4_12_v1.png|right|frame|Vorgegebener Tanner–Graph für Code $\rm A$]]
+
[[Datei:P_ID3072__KC_A_4_12_v1.png|right|frame|Vorgegebener Tanner–Graph für Code  $\rm A$]]
Dargestellt ist ein Tanner–Graph eines Codes $\rm A$ mit
+
Dargestellt ist ein Tanner–Graph eines Codes  $\rm A$  mit
* den <i>Variable Nodes</i> (abgekürzt VNs) $V_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ V_6$, wobei $V_i$ das $i$&ndash;te Codewortbit kennzeichnet (egal, ob Informations &ndash; oder Paritybit) und der $i$&ndash;ten Spalte der Prüfmatrix entspricht;
+
* den&nbsp; <i>Variable Nodes</i>&nbsp; (abgekürzt VNs)&nbsp; $V_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ V_6$, wobei&nbsp; $V_i$&nbsp; das&nbsp; $i$&ndash;te Codewortbit kennzeichnet (egal, ob Informations&ndash; oder Paritybit) und der&nbsp; $i$&ndash;ten Spalte der Prüfmatrix entspricht;
* den <i>Check Nodes</i> (abgekürzt CNs) $C_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ C_3$, die die Zeilen der $\mathbf{H}_{\rm A}$&ndash;Matrix und damit die Prüfgleichungen repräsentieren.
+
* den&nbsp; <i>Check Nodes</i>&nbsp; (abgekürzt CNs)&nbsp; $C_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ C_3$, die die Zeilen der&nbsp; $\mathbf{H}_{\rm A}$&ndash;Matrix und damit die Prüfgleichungen repräsentieren.
  
  
Eine Verbindungslinie (englisch: <i>Edge</i>) zwischen $V_i$ und $C_j$ zeigt an, dass das $i$&ndash;te Codewortsymbol an der $j$&ndash;ten Prüfgleichung beteiligt ist. In diesem Fall ist das Element $h_{j,\hspace{0.05cm}i}$ der Prüfmatrix gleich $1$.
+
Eine Verbindungslinie&nbsp; (englisch:&nbsp; <i>Edge</i>)&nbsp; zwischen&nbsp; $V_i$&nbsp; und&nbsp; $C_j$&nbsp; zeigt an, dass das&nbsp; $i$&ndash;te Codewortsymbol an der&nbsp; $j$&ndash;ten Prüfgleichung beteiligt ist. In diesem Fall ist das Element&nbsp; $h_{j,\hspace{0.05cm}i}$&nbsp; der Prüfmatrix gleich&nbsp; $1$.
  
  
In der Aufgabe soll der Zusammenhang zwischen dem oben dargestellten Tanner&ndash;Graphen (gültig für den Code $\rm A$) und der Matrix $\mathbf{H}_{\rm A}$ angegeben werden. Außerdem ist der Tanner&ndash;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:
+
In der Aufgabe soll der Zusammenhang zwischen dem oben dargestellten Tanner&ndash;Graphen &nbsp;$($gültig für den Code&nbsp; $\rm A)$&nbsp; und der Matrix&nbsp; $\mathbf{H}_{\rm A}$&nbsp; angegeben werden. Außerdem ist der Tanner&ndash;Graph zu einer Prüfmatrix&nbsp; $\mathbf{H}_{\rm B}$&nbsp; aufzustellen, die sich aus&nbsp; $\mathbf{H}_{\rm A}$&nbsp; durch Hinzufügen einer weiteren Zeile ergibt. Diese ist so zu ermitteln, dass der zugehörige Code&nbsp; $\rm B$&nbsp; regulär ist. Das bedeutet:
* Von allen <i>Variable Nodes</i> $V_i$ (mit $1 &#8804; i &#8804; n$) gehen gleich viele Linien (<i>Edges</i>) ab, ebenso von allen <i>Check Nodes</i> $C_j$ (mit $1 &#8804; j &#8804; m$).
+
* Von allen&nbsp; <i>Variable Nodes</i>&nbsp; $V_i$&nbsp; $($mit&nbsp; $1 &#8804; i &#8804; n)$&nbsp; gehen gleich viele Linien (<i>Edges</i>) ab, ebenso von allen&nbsp; <i>Check Nodes</i>&nbsp; $C_j$&nbsp; $($mit&nbsp; $1 &#8804; j &#8804; m)$.
* Die Hamming&ndash;Gewichte aller Zeilen von $\mathbf{H}_{\rm B}$ sollen jeweils gleich sein $(w_{\rm Z})$, ebenso die Hamming&ndash;Gewichte aller Spalten $(w_{\rm S})$.
+
* Die Hamming&ndash;Gewichte aller Zeilen von&nbsp; $\mathbf{H}_{\rm B}$&nbsp; sollen jeweils gleich sein&nbsp; $(w_{\rm Z})$, ebenso die Hamming&ndash;Gewichte aller Spalten&nbsp; $(w_{\rm S})$.
* Für die Rate des zu konstruierenden regulären Codes $\rm B$ gilt dann die folgende untere Schranke:
+
* Für die Rate des zu konstruierenden regulären Codes &nbsp;$\rm B$&nbsp; gilt dann die folgende untere Schranke:
 
:$$R \ge 1 - \frac{w_{\rm S}}{w_{\rm Z}}
 
:$$R \ge 1 - \frac{w_{\rm S}}{w_{\rm Z}}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
Zeile 21: Zeile 21:
  
  
''Hinweis:''  
+
 
* Die Aufgabe gehört zum Themengebiet des Kapitels [[Kanalcodierung/Grundlegendes_zu_den_Low%E2%80%93density_Parity%E2%80%93check_Codes|Grundlegendes zu den Low&ndash;density Parity&ndash;check Codes]].
+
 
*Bezug genommen wird insbesondere auf die Seite [[Kanalcodierung/Grundlegendes_zu_den_Low–density_Parity–check_Codes#Zweiteilige_LDPC.E2.80.93Graphenrepr.C3.A4sentation_.E2.80.93_Tanner.E2.80.93Graph|Zweiteilige LDPC&ndash;Graphenrepräsentation &ndash; Tanner&ndash;Graph]].
+
 
 +
''Hinweise:''  
 +
* Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Low%E2%80%93density_Parity%E2%80%93check_Codes|Grundlegendes zu den Low&ndash;density Parity&ndash;check Codes]].
 +
*Bezug genommen wird insbesondere auf die Seite&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Low–density_Parity–check_Codes#Zweiteilige_LDPC.E2.80.93Graphenrepr.C3.A4sentation_.E2.80.93_Tanner.E2.80.93Graph|Zweiteilige LDPC&ndash;Graphenrepräsentation &ndash; Tanner&ndash;Graph]].
 
   
 
   
  
Zeile 31: Zeile 34:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
{Wieviele Zeilen $(m)$ und Spalten $(n)$ hat die Prüfmatrix $\mathbf{H}_{\rm A}$?
+
{Wieviele Zeilen&nbsp; $(m)$&nbsp; und Spalten&nbsp; $(n)$&nbsp; hat die Prüfmatrix&nbsp; $\mathbf{H}_{\rm A}$?
 
|type="{}"}
 
|type="{}"}
 
$m \hspace{0.18cm} = \ ${ 3 }
 
$m \hspace{0.18cm} = \ ${ 3 }
Zeile 38: Zeile 41:
 
{Welche Aussagen sind aufgrund des Tanner&ndash;Graphen zutreffend?
 
{Welche Aussagen sind aufgrund des Tanner&ndash;Graphen zutreffend?
 
|type="[]"}
 
|type="[]"}
+ Die Zeile 1 der $\mathbf{H}_{\rm A}$&ndash;Matrix ist &bdquo;$1 \ 1 \ 0 \ 1 \ 0 \ 0$&rdquo;.
+
+ Die Zeile 1 der&nbsp; $\mathbf{H}_{\rm A}$&ndash;Matrix ist&nbsp; &bdquo;$1 \ 1 \ 0 \ 1 \ 0 \ 0$&rdquo;.
- Die Zeile 2 der $\mathbf{H}_{\rm A}$&ndash;Matrix ist &bdquo;$1 \ 0 \ 1 \ 0 \ 0 \ 1$&rdquo;.
+
- Die Zeile 2 der&nbsp; $\mathbf{H}_{\rm A}$&ndash;Matrix ist&nbsp; &bdquo;$1 \ 0 \ 1 \ 0 \ 0 \ 1$&rdquo;.
+ Die Zeile 3 der $\mathbf{H}_{\rm A}$&ndash;Matrix ist &bdquo;$0 \ 1 \ 1 \ 0 \ 0 \ 1$&rdquo;.
+
+ Die Zeile 3 der&nbsp; $\mathbf{H}_{\rm A}$&ndash;Matrix ist&nbsp; &bdquo;$0 \ 1 \ 1 \ 0 \ 0 \ 1$&rdquo;.
  
{Welche Eigenschaften weist der Code $\rm A$ auf?
+
{Welche Eigenschaften weist der Code&nbsp; $\rm A$&nbsp; auf?
 
|type="[]"}
 
|type="[]"}
 
+ Der Code ist systematisch.
 
+ Der Code ist systematisch.
 
- Der Code ist regulär.
 
- Der Code ist regulär.
+ Die Coderate ist $R = 1/2$.
+
+ Die Coderate ist&nbsp; $R = 1/2$.
- Die Coderate ist $R = 1/3$.
+
- Die Coderate ist&nbsp; $R = 1/3$.
  
{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$?
+
{Die Matrix&nbsp; $\mathbf{H}_{\rm B}$&nbsp; ergibt sich aus&nbsp; $\mathbf{H}_{\rm A}$&nbsp; durch Hinzufügen einer weiteren Zeile. Durch welche vierte Zeile ergibt sich ein regulärer Code&nbsp; $\rm B$?
 
|type="[]"}
 
|type="[]"}
 
+ Durch Hinzufügen von &bdquo;$0 \ 0 \ 0 \ 1 \ 1 \ 1$&rdquo;.
 
+ Durch Hinzufügen von &bdquo;$0 \ 0 \ 0 \ 1 \ 1 \ 1$&rdquo;.
Zeile 55: Zeile 58:
 
- Durch Hinzufügen irgend einer anderen Zeile.
 
- Durch Hinzufügen irgend einer anderen Zeile.
  
{Welche Eigenschaften weist der Code $\rm B$ auf?
+
{Welche Eigenschaften weist der Code&nbsp; $\rm B$&nbsp; auf?
 
|type="[]"}
 
|type="[]"}
 
- Der Code ist systematisch.
 
- Der Code ist systematisch.
 
+ Der Code ist regulär.
 
+ Der Code ist regulär.
+ Die Coderate ist $R = 1/2$.
+
+ Die Coderate ist&nbsp; $R = 1/2$.
- Die Coderate ist $R = 1/3$.
+
- Die Coderate ist&nbsp; $R = 1/3$.
 
</quiz>
 
</quiz>
  
Zeile 66: Zeile 69:
 
{{ML-Kopf}}
 
{{ML-Kopf}}
 
'''(1)'''&nbsp; Die Anzahl der $\mathbf{H}_{\rm A}$&ndash;Zeilen ist gleich der Anzahl der <i>Check Nodes</i> $C_j$ im Tanner&ndash;Graphen &nbsp;&#8658;&nbsp; $\underline{m = 3}$, und die Anzahl $\underline{n = 6}$ der <i>Variable Nodes</i> $V_i$ ist gleich der Spaltenzahl.
 
'''(1)'''&nbsp; Die Anzahl der $\mathbf{H}_{\rm A}$&ndash;Zeilen ist gleich der Anzahl der <i>Check Nodes</i> $C_j$ im Tanner&ndash;Graphen &nbsp;&#8658;&nbsp; $\underline{m = 3}$, und die Anzahl $\underline{n = 6}$ der <i>Variable Nodes</i> $V_i$ ist gleich der Spaltenzahl.
 +
  
  
Zeile 81: Zeile 85:
  
 
*Im Schaubild sind die Prüfgleichungen als rote (Zeile 1), grüne (Zeile 2) bzw. blaue (Zeile 3) Gruppierung veranschaulicht.
 
*Im Schaubild sind die Prüfgleichungen als rote (Zeile 1), grüne (Zeile 2) bzw. blaue (Zeile 3) Gruppierung veranschaulicht.
 +
  
  
Zeile 88: Zeile 93:
 
* Für die ersten drei Spalten gilt: $w_{\rm S}(1) = w_{\rm S}(2) = w_{\rm S}(3) = 2$ &nbsp; &#8658; &nbsp; irregulärer Code.
 
* Für die ersten drei Spalten gilt: $w_{\rm S}(1) = w_{\rm S}(2) = w_{\rm S}(3) = 2$ &nbsp; &#8658; &nbsp; irregulärer Code.
 
* Die drei Matrixzeilen sind linear unabhängig. Damit gilt $k = n - m = 6 - 3 = 3$ und $R = k/n = 1/2$.
 
* Die drei Matrixzeilen sind linear unabhängig. Damit gilt $k = n - m = 6 - 3 = 3$ und $R = k/n = 1/2$.
 +
  
  
Zeile 102: Zeile 108:
 
\end{pmatrix}\hspace{0.05cm}.$$
 
\end{pmatrix}\hspace{0.05cm}.$$
  
Die Modifikationen sind in nebenstehender Grafik rot markiert: Durch den neu hinzugefügten <i>Check Node</i> $C_4$ und die Verbindungen mit $V_4, \ V_5$ und $V_6$ gehen nun
+
Die Modifikationen sind in nebenstehender Grafik rot markiert.
 +
 
 +
Durch den neu hinzugefügten <i>Check Node</i> $C_4$ und die Verbindungen mit $V_4, \ V_5$ und $V_6$ gehen nun
 
* von allen <i>Variable Nodes</i> $V_i$ zwei Linien ab, und
 
* von allen <i>Variable Nodes</i> $V_i$ zwei Linien ab, und
 
* von allen <i>Check Nodes</i> $C_j$ einheitlich vier.
 
* von allen <i>Check Nodes</i> $C_j$ einheitlich vier.
 +
  
 
Dies ist die Bedingung dafür, dass der  Code $\rm B$ regulär ist.
 
Dies ist die Bedingung dafür, dass der  Code $\rm B$ regulär ist.
 +
  
  

Aktuelle Version vom 10. Juli 2019, 14:25 Uhr

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