Kanalcodierung/Grundlegendes zu den Low–density Parity–check Codes: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(6 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 8: Zeile 8:
 
== Einige Charakteristika der LDPC–Codes ==
 
== Einige Charakteristika der LDPC–Codes ==
 
<br>
 
<br>
Die <i>Low&ndash;density Parity&ndash;check Codes</i> &ndash; kurz LDPC&ndash;Codes &ndash; wurden bereits Anfang der 1960er Jahre erfunden und gehen auf die Dissertation [Gal63]<ref name ='Gal63'>Gallager, R. G.: ''Low–density Parity–check Codes.'' MIT Press, Cambridge, MA, 1963.</ref> von [https://de.wikipedia.org/wiki/Robert_Gray_Gallager Robert G. Gallager] zurück.<br>
+
Die&nbsp; <i>Low&ndash;density Parity&ndash;check Codes</i>&nbsp; &ndash; kurz &nbsp;'''LDPC&ndash;Codes'''&nbsp; &ndash; wurden bereits Anfang der 1960er Jahre erfunden und gehen auf die Dissertation&nbsp; [Gal63]<ref name ='Gal63'>Gallager, R. G.: ''Low–density Parity–check Codes.'' MIT Press, Cambridge, MA, 1963.</ref> von&nbsp; [https://de.wikipedia.org/wiki/Robert_Gray_Gallager Robert G. Gallager]&nbsp; zurück.<br>
  
Die Idee kam allerdings aufgrund der damaligen Prozessorentechnologie um einige Jahrzehnte zu früh. Schon drei Jahre nach Berrou's Erfindung der Turbocodes 1993 erkannten dann allerdings [https://de.wikipedia.org/wiki/David_MacKay David J. C. MacKay] und [https://en.wikipedia.org/wiki/Radford_M._Neal Radford M. Neal] das riesige Potential der LDPC&ndash;Codes, wenn man diese ebenso wie die Turbocodes iterativ symbolweise decodiert. Sie erfanden die LDPC&ndash;Codes quasi neu.<br>
+
Die Idee kam allerdings aufgrund der damaligen Prozessorentechnologie um einige Jahrzehnte zu früh. Schon drei Jahre nach Berrou's Erfindung der Turbocodes 1993 erkannten dann allerdings&nbsp; [https://de.wikipedia.org/wiki/David_MacKay David J. C. MacKay]&nbsp; und&nbsp; [https://en.wikipedia.org/wiki/Radford_M._Neal Radford M. Neal]&nbsp; das riesige Potential der LDPC&ndash;Codes, wenn man diese ebenso wie die Turbocodes iterativ symbolweise decodiert. Sie erfanden die LDPC&ndash;Codes quasi neu.<br>
  
Wie aus dem Namensbestandteil &bdquo;Parity&ndash;check&rdquo; bereits hervorgeht, handelt es sich bei diesen Codes um lineare Blockcodes entsprechend den Ausführungen im [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#.23_.C3.9CBERBLICK_ZUM_ERSTEN_HAUPTKAPITEL_.23|ersten  Hauptkapitel ]]. Deshalb gilt auch hier:
+
Wie aus dem Namensbestandteil &bdquo;Parity&ndash;check&rdquo; bereits hervorgeht, handelt es sich bei diesen Codes um lineare Blockcodes entsprechend den Ausführungen im&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#.23_.C3.9CBERBLICK_ZUM_ERSTEN_HAUPTKAPITEL_.23|ersten  Hauptkapitel ]]. Deshalb gilt auch hier:
*Das Codewort ergibt sich aus dem Informationswort $\underline{u}$ (dargestellt mit $k$ Binärsymbolen) und der [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix| Generatormatrix]] $\mathbf{G}$ der Dimension $k &times; n$ zu $\underline{x} = \underline{u} \cdot \mathbf{G}$ &nbsp;&#8658;&nbsp; Codewortlänge $n$.<br>
+
*Das Codewort ergibt sich aus dem Informationswort&nbsp; $\underline{u}$&nbsp; (dargestellt mit&nbsp; $k$&nbsp; Binärsymbolen) und der&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix| Generatormatrix]]&nbsp; $\mathbf{G}$&nbsp; der Dimension&nbsp; $k &times; n$&nbsp; zu&nbsp; $\underline{x} = \underline{u} \cdot \mathbf{G}$ &nbsp; &#8658; &nbsp; Codewortlänge&nbsp; $n$.<br>
  
*Die Prüfgleichungen ergeben sich aus der Identität $\underline{x} \cdot \mathbf{H}^{\rm T} &equiv; 0$, wobei $\mathbf{H}$ die Prüfmatrix bezeichnet. Diese besteht aus $m$ Zeilen und $n$ Spalten. Während im ersten Kapitel grundsätzlich $m = n -k$ gegolten hat, fordern wir für die LPDC&ndash;Codes lediglich noch $m &#8805; n -k$.<br><br>
+
*Die Prüfgleichungen ergeben sich aus der Identität&nbsp; $\underline{x} \cdot \mathbf{H}^{\rm T} &equiv; 0$, wobei&nbsp; $\mathbf{H}$&nbsp; die Prüfmatrix bezeichnet. Diese besteht aus&nbsp; $m$&nbsp; Zeilen und&nbsp; $n$&nbsp; Spalten. Während im ersten Kapitel grundsätzlich&nbsp; $m = n -k$&nbsp; gegolten hat, fordern wir für die LPDC&ndash;Codes lediglich noch&nbsp; $m &#8805; n -k$.<br><br>
  
Ein gravierender Unterschied zwischen einem LDPC&ndash;Code und einem herkömmlichen Blockcode nach der Beschreibung im ersten Kapitel ist, dass die Prüfmatrix $\mathbf{H}$ nur spärlich mit Einsen besetzt ist.<br>
+
Ein gravierender Unterschied zwischen einem LDPC&ndash;Code und einem herkömmlichen Blockcode nach der Beschreibung im ersten Kapitel ist, dass die Prüfmatrix&nbsp; $\mathbf{H}$&nbsp; nur spärlich mit Einsen besetzt ist&nbsp;  (&bdquo;''Low–density''&rdquo;).<br>
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 1:}$&nbsp; Die Grafik zeigt beispielhaft die Prüfmatrizen $\mathbf{H}$ für  
+
$\text{Beispiel 1:}$&nbsp; Die Grafik zeigt beispielhaft die Prüfmatrizen&nbsp; $\mathbf{H}$&nbsp; für  
*den Hamming&ndash;Code mit Codelänge $n = 15, \ m = 4$ &nbsp; &#8658; &nbsp; $k = 11$ Informationsbits,<br>
+
*den Hamming&ndash;Code mit Codelänge&nbsp; $n = 15, \ m = 4$ &nbsp; &#8658; &nbsp; $k = 11$&nbsp; Informationsbits,<br>
  
*den LDPC&ndash;Code aus [Liv15]<ref name='Liv15'>Liva, G.: ''Channels Codes for Iterative Decoding.'' Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.</ref> der Länge $n = 12$ und mit $m = 9$ Prüfgleichungen &nbsp; &#8658; &nbsp; $k &#8805; 3$.<br><br>
+
*den LDPC&ndash;Code aus&nbsp; [Liv15]<ref name='Liv15'>Liva, G.: ''Channels Codes for Iterative Decoding.'' Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.</ref>&nbsp; der Länge&nbsp; $n = 12$&nbsp; und mit&nbsp; $m = 9$&nbsp; Prüfgleichungen &nbsp; &#8658; &nbsp; $k &#8805; 3$.<br><br>
  
 
[[Datei:P ID3065 KC T 4 4 S1a v3 einfacher Rahmen.png|center|frame|Prüfmatrizen eines Hamming–Codes und eines LDPC–Codes|class=fit]]
 
[[Datei:P ID3065 KC T 4 4 S1a v3 einfacher Rahmen.png|center|frame|Prüfmatrizen eines Hamming–Codes und eines LDPC–Codes|class=fit]]
  
*In der linken Grafik beträgt der Anteil der Einsen $32/60 \approx 53.3\%$, wohingegen in der rechten Grafik der Einsen&ndash;Anteil mit $36/108 = 33.3\%$ geringer ist.  
+
*In der linken Grafik beträgt der Anteil der Einsen&nbsp; $32/60 \approx 53.3\%$, wohingegen in der rechten Grafik der Einsen&ndash;Anteil mit&nbsp; $36/108 = 33.3\%$&nbsp; geringer ist.  
 
*Bei den für die Praxis relevanten LDPC&ndash;Codes (großer Länge) ist der Einsen&ndash;Anteil noch deutlich niedriger.<br>}}<br>
 
*Bei den für die Praxis relevanten LDPC&ndash;Codes (großer Länge) ist der Einsen&ndash;Anteil noch deutlich niedriger.<br>}}<br>
  
 +
Wir analysieren nun die beiden Prüfmatrizen anhand der Rate und des Hamming&ndash;Gewichts:<br>
 +
*Die Rate des betrachteten Hamming&ndash;Codes (linke Grafik) ist&nbsp; $R = k/n = 11/15 \approx 0.733$. Das Hamming&ndash;Gewicht einer jeden der vier Zeilen ist&nbsp; $w_{\rm Z}= 8$, während die Hamming&ndash;Gewichte&nbsp; $w_{\rm S}(i)$&nbsp; der Spalten zwischen 1 und 4 variieren. Für die Spalten&ndash;Laufvariable gilt hier: &nbsp; $1 &#8804; i &#8804; 15$.
  
Wir analysieren nun die beiden Prüfmatrizen anhand der Rate und des Hamming&ndash;Gewichts:<br>
+
*Beim betrachteten LDPC&ndash;Code gibt es in allen Zeilen vier Einsen &nbsp; &#8658; &nbsp; $w_{\rm Z} = 4$&nbsp; und in allen Spalten drei Einsen &nbsp; &#8658; &nbsp; $w_{\rm S} = 3$. Die Codebezeichnung&nbsp; $(w_{\rm Z}, \ w_{\rm S})$&nbsp; LDPC&ndash;Code verwendet genau diese Parameter. Beachten Sie die unterschiedliche Nomenklatur zum &bdquo;$(n, \ k, \ m)$ Hamming&ndash;Code&rdquo;.
*Die Rate des betrachteten Hamming&ndash;Codes (linke Grafik) ist $R = k/n = 11/15 \approx 0.733$. Das Hamming&ndash;Gewicht einer jeden der vier Zeilen ist $w_{\rm Z}= 8$, während die Hamming&ndash;Gewichte $w_{\rm S}(i)$ der Spalten zwischen 1 und 4 variieren. Für die Spalten&ndash;Laufvariable gilt hier: $1 &#8804; i &#8804; 15$.
 
  
*Beim betrachteten LDPC&ndash;Code gibt es in allen Zeilen vier Einsen &nbsp;&#8658;&nbsp; $w_{\rm Z} = 4$ und in allen Spalten drei Einsen &#8658; $w_{\rm S} = 3$. Die Codebezeichnung $(w_{\rm Z}, \ w_{\rm S})$ LDPC&ndash;Code verwendet genau diese Parameter. Beachten Sie die unterschiedliche Nomenklatur zum &bdquo;$(n, \ k, \ m)$ Hamming&ndash;Code&rdquo;.
+
*Man spricht hier von einem&nbsp; <b>regulären LDPC&ndash;Code</b>, da alle Zeilengewichte&nbsp; $w_{\rm Z}(j)$&nbsp; für&nbsp; $1 &#8804; j &#8804; m$&nbsp; konstant gleich&nbsp; $w_{\rm Z}$ sind und auch alle Spaltengewichte $($mit den Indizes&nbsp; $1 &#8804; i &#8804; n)$&nbsp; gleich sind: &nbsp;  $w_{\rm S}(i) = w_{\rm S} = {\rm const.}$ Ist diese Bedingung nicht erfüllt, so liegt ein <i>irregulärer LDPC&ndash;Code</i> vor.
  
*Man spricht hier von einem <i>regulären LDPC&ndash;Code</i>, da alle Zeilengewichte $w_{\rm Z}(j)$ für $1 &#8804; j &#8804; m$ konstant gleich $w_{\rm Z}$ sind und auch alle Spaltengewichte (mit den Indizes $1 &#8804; i &#8804; n$) gleich sind: &nbsp;  $w_{\rm S}(i) = w_{\rm S} = {\rm const.}$ Ist diese Bedingung nicht erfüllt, so liegt ein <i>irregulärer LDPC&ndash;Code</i> vor.
 
  
*Für die Coderate kann man allgemein (wenn $k$ nicht bekannt ist) nur eine Schranke angeben: &nbsp; <b>$R &#8805; 1 - w_{\rm S}/w_{\rm Z}$</b>. Das Gleichheitszeichen gilt dann, wenn alle Zeilen von $\mathbf{H}$ linear unabhängig sind &nbsp;&#8658;&nbsp; $m = n \, &ndash; k$. Dann ergibt sich die herkömmliche Gleichung:  
+
{{BlaueBox|TEXT=
 +
$\text{Merkmal der LDPC-Codes}$&nbsp; 
 +
Für die Coderate kann man allgemein&nbsp; (wenn&nbsp; $k$&nbsp; nicht bekannt ist)&nbsp; nur eine Schranke angeben: &nbsp;  
 +
:$$R &#8805; 1 - w_{\rm S}/w_{\rm Z}.$$  
 +
*Das Gleichheitszeichen gilt dann, wenn alle Zeilen von&nbsp; $\mathbf{H}$&nbsp; linear unabhängig sind &nbsp; &#8658; &nbsp; $m = n \, &ndash; k$. Dann ergibt sich die herkömmliche Gleichung:  
 
:$$R = 1 -  w_{\rm S}/w_{\rm Z} = 1 - m/n = k/n.$$
 
:$$R = 1 -  w_{\rm S}/w_{\rm Z} = 1 - m/n = k/n.$$
  
*Dagegen gilt für die Coderate eines irregulären LDPC&ndash;Codes und auch für den links skizzierten $(15, 11, 4)$ Hammingcode:
+
*Dagegen gilt für die Coderate eines irregulären LDPC&ndash;Codes und auch für den links skizzierten &nbsp;$(15, 11, 4)$ Hammingcode:
  
::<math>R \ge 1 - \frac{{\rm E}[w_{\rm S}]}{{\rm E}[w_{\rm Z}]}
+
:$$R \ge 1 - \frac{ {\rm E}[w_{\rm S}]}{ {\rm E}[w_{\rm Z}]}
 
\hspace{0.5cm}{\rm mit}\hspace{0.5cm}
 
\hspace{0.5cm}{\rm mit}\hspace{0.5cm}
 
{\rm E}[w_{\rm S}] =\frac{1}{n} \cdot  \sum_{i = 1}^{n}w_{\rm S}(i)
 
{\rm E}[w_{\rm S}] =\frac{1}{n} \cdot  \sum_{i = 1}^{n}w_{\rm S}(i)
 
\hspace{0.5cm}{\rm und}\hspace{0.5cm}
 
\hspace{0.5cm}{\rm und}\hspace{0.5cm}
 
{\rm E}[w_{\rm Z}] =\frac{1}{m} \cdot  \sum_{j = 1}^{ m}w_{\rm Z}(j)
 
{\rm E}[w_{\rm Z}] =\frac{1}{m} \cdot  \sum_{j = 1}^{ m}w_{\rm Z}(j)
\hspace{0.05cm}.</math>
+
\hspace{0.05cm}.$$
  
:Da beim Hamming&ndash;Code die $m = n \, &ndash; k$ Prüfgleichungen linear voneinander unabhängig sind, kann das &bdquo;$&#8805;$&rdquo;&ndash;Zeichen durch das Gleichheitszeichen ersetzt werden, was gleichzeitig $R = k/n$ bedeutet.<br><br>
+
:Da beim Hamming&ndash;Code&nbsp; die&nbsp; $m = n - k$&nbsp; Prüfgleichungen linear voneinander unabhängig sind, kann das &nbsp;&bdquo;$&#8805;$&rdquo;&ndash;Zeichen durch das Gleichheitszeichen ersetzt werden, was gleichzeitig&nbsp; $R = k/n$&nbsp; bedeutet.}}<br>
  
Weitere Informationen zu diesem Thema finden Sie in der [[Aufgaben:4.11_Analyse_von_Pr%C3%BCfmatrizen| Aufgabe 4.11]] und in der [[Aufgaben:4.11Z_Coderate_aus_der_Pr%C3%BCfmatrix| Aufgabe 4.11Z]].
+
Weitere Informationen zu diesem Thema finden Sie in&nbsp; [[Aufgaben:4.11_Analyse_von_Pr%C3%BCfmatrizen| Aufgabe 4.11]]&nbsp; und&nbsp; [[Aufgaben:4.11Z_Coderate_aus_der_Pr%C3%BCfmatrix| Aufgabe 4.11Z]].
  
 
== Zweiteilige LDPC–Graphenrepräsentation – Tanner–Graph ==
 
== Zweiteilige LDPC–Graphenrepräsentation – Tanner–Graph ==
 
<br>
 
<br>
Alle wesentlichen Merkmale eines LDPC&ndash;Codes sind in der Prüfmatrix $\mathbf{H} = (h_{j,\hspace{0.05cm}i})$ enthalten und lassen sich durch einen so genannten <span style="font-weight: bold;">Tanner&ndash;Graphen</span> darstellen. Es handelt sich um eine <i>Bipartite Graph Representation</i>, wobei die deutsche Übersetzung von &bdquo;bipartite&rdquo; in etwa &bdquo;zweiteilig&rdquo; lautet. Bevor wir beispielhafte Tanner&ndash;Graphen genauer betrachten und analysieren, müssen zuerst noch einige geeignete Beschreibungsgrößen definiert werden:
+
Alle wesentlichen Merkmale eines LDPC&ndash;Codes sind in der Prüfmatrix&nbsp; $\mathbf{H} = (h_{j,\hspace{0.05cm}i})$&nbsp; enthalten und lassen sich durch einen so genannten &nbsp;'''Tanner&ndash;Graphen'''&nbsp; darstellen. Es handelt sich um eine &nbsp;<i>Bipartite Graph Representation</i>, wobei die deutsche Übersetzung von &bdquo;bipartite&rdquo; in etwa &bdquo;zweiteilig&rdquo; lautet. Bevor wir beispielhafte Tanner&ndash;Graphen genauer betrachten und analysieren, müssen zuerst noch einige geeignete Beschreibungsgrößen definiert werden:
*Die $n$ Spalten der Prüfmatrix $\mathbf{H}$ stehen jeweils für ein Codewortbit. Da jedes Codewortbit sowohl ein Informationsbit als auch ein Prüfbit sein kann, hat sich hierfür die neutrale Bezeichnung <b>Varibale Node</b> (VN) durchgesetzt. Das $i$&ndash;te Codewortbit wird $V_i$ genannt und die Menge aller <i>Variable Nodes</i> (VNs) ist $\{V_1, \ \text{...}\hspace{0.05cm} , \ V_i, \ \text{...}\hspace{0.05cm} , \ V_n\}$.<br>
+
*Die&nbsp; $n$&nbsp; Spalten der Prüfmatrix&nbsp; $\mathbf{H}$&nbsp; stehen jeweils für ein Codewortbit. Da jedes Codewortbit sowohl ein Informationsbit als auch ein Prüfbit sein kann, hat sich hierfür die neutrale Bezeichnung&nbsp; <b>Varibale Node</b>&nbsp; (VN) durchgesetzt. Das&nbsp; $i$&ndash;te Codewortbit wird&nbsp; $V_i$&nbsp; genannt und die Menge aller&nbsp; <i>Variable Nodes</i>&nbsp; (VNs) ist $\{V_1, \ \text{...}\hspace{0.05cm} , \ V_i, \ \text{...}\hspace{0.05cm} , \ V_n\}$.<br>
  
*Die $m$ Zeilen von $\mathbf{H}$ beschreiben jeweils eine Prüfgleichung (englisch: <i>Parity&ndash;check Equation</i>). Wir bezeichnen im folgenden eine solche Prüfgleichung als <b>Check Node</b> (CN). Die Menge aller <i>Check Nodes</i> (CNs) ist $\{C_1, \ \text{...}\hspace{0.05cm} , \ C_j, \ \text{...}\hspace{0.05cm} , \ C_m\}$, wobei $C_j$ die Prüfgleichung der $j$&ndash;ten Zeile angibt.<br>
+
*Die&nbsp; $m$&nbsp; Zeilen von&nbsp; $\mathbf{H}$&nbsp; beschreiben jeweils eine Prüfgleichung (englisch:&nbsp; <i>Parity&ndash;check Equation</i>). Wir bezeichnen im folgenden eine solche Prüfgleichung als&nbsp; <b>Check Node</b>&nbsp; (CN). Die Menge aller&nbsp; <i>Check Nodes</i>&nbsp; (CNs) ist&nbsp; $\{C_1, \ \text{...}\hspace{0.05cm} , \ C_j, \ \text{...}\hspace{0.05cm} , \ C_m\}$, wobei&nbsp; $C_j$&nbsp; die Prüfgleichung der&nbsp; $j$&ndash;ten Zeile angibt.<br>
  
*Im Tanner&ndash;Graphen werden die $n$ <i>Variable Nodes</i> $V_i$ als Kreise und die $m$ <i>Check Nodes</i> $C_j$ als Quadrate dargestellt. Ist das Matrixelement in Zeile $j$ und Spalte $i &#8658; h_{j,\hspace{0.05cm}i} = 1$, so gibt es eine Verbindungslinie (englisch: <i>Edge</i>) zwischen dem <i>Variable Node</i> $V_i$ und dem <i>Check Node</i> $C_j$.<br><br>
+
*Im Tanner&ndash;Graphen werden die&nbsp; $n$&nbsp; <i>Variable Nodes</i>&nbsp; $V_i$&nbsp; als Kreise und die&nbsp; $m$&nbsp; <i>Check Nodes</i>&nbsp; $C_j$ als Quadrate dargestellt. Ist das Matrixelement in Zeile&nbsp; $j$&nbsp; und Spalte&nbsp; $i \hspace{0.15cm} &#8658; \hspace{0.15cm} h_{j,\hspace{0.05cm}i} = 1$, so gibt es eine Verbindungslinie (englisch:&nbsp; <i>Edge</i>) zwischen dem <i>Variable Node</i>&nbsp; $V_i$&nbsp; und dem <i>Check Node</i>&nbsp; $C_j$.<br><br>
  
 
[[Datei:P ID3069 KC T 4 4 S2a v3.png|right|frame|Einfaches Beispiel für einen Tanner–Graphen|class=fit]]  
 
[[Datei:P ID3069 KC T 4 4 S2a v3.png|right|frame|Einfaches Beispiel für einen Tanner–Graphen|class=fit]]  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Beispiel 2:}$&nbsp; Zur Verdeutlichung obiger Begriffe ist rechts ein beispielhafter Tannergraphen  mit  
 
$\text{Beispiel 2:}$&nbsp; Zur Verdeutlichung obiger Begriffe ist rechts ein beispielhafter Tannergraphen  mit  
*den <i>Variable Nodes</i> (kurz: VNs) $V_1$ bis $V_4$, und<br>
+
*den <i>Variable Nodes</i>&nbsp; (kurz:&nbsp; VNs)&nbsp; $V_1$&nbsp; bis&nbsp; $V_4$, und<br>
*den <i>Check Nodes</i> (kurz: CNs) $C_1$ bis $C_3$.<br><br>
+
*den <i>Check Nodes</i>&nbsp; (kurz:&nbsp; CNs)&nbsp; $C_1$&nbsp; bis&nbsp; $C_3$<br><br>
  
 
angegeben. Der zugehörige Code hat allerdings keinerlei praktische Bedeutung.  
 
angegeben. Der zugehörige Code hat allerdings keinerlei praktische Bedeutung.  
  
 
Man erkennt aus der Grafik:
 
Man erkennt aus der Grafik:
*Die Codelänge ist $n = 4$ und es gibt $m = 3$ Prüfgleichungen. Damit hat die Prüfmatrix $\mathbf{H}$ die Dimension $3&times;4$.<br>
+
*Die Codelänge ist&nbsp; $n = 4$&nbsp; und es gibt&nbsp; $m = 3$&nbsp; Prüfgleichungen. Damit hat die Prüfmatrix&nbsp; $\mathbf{H}$&nbsp; die Dimension&nbsp; $3&times;4$.<br>
  
*Es gibt insgesamt sechs Verbindungslinien (englisch: <i>Edges</i>). Damit sind sechs der zwölf Elemente $h_{j,\hspace{0.05cm}i}$ von $\mathbf{H}$ Einsen.<br>
+
*Es gibt insgesamt sechs Verbindungslinien (englisch:&nbsp; <i>Edges</i>). Damit sind sechs der zwölf Elemente&nbsp; $h_{j,\hspace{0.05cm}i}$&nbsp; von&nbsp; $\mathbf{H}$&nbsp; Einsen.<br>
  
*Bei jedem <i>Check Node</i> kommen zwei Linien an. Das bedeutet: Die Hamming&ndash;Gewichte aller Zeilen gleich sind:  &nbsp; $w_{\rm S}(j) = 2 = w_{\rm S}$.<br>
+
*Bei jedem <i>Check Node</i>&nbsp; kommen zwei Linien an &nbsp; &rArr; &nbsp; Die Hamming&ndash;Gewichte aller Zeilen gleich sind:  &nbsp; $w_{\rm S}(j) = 2 = w_{\rm S}$.<br>
  
*Von den Knoten $V_1$ und $V_4$ gibt es jeweils nur einen Übergang zu einem <i>Check Node</i>, von $V_2$ und $V_3$ dagegen zwei. Aus diesem Grund handelt es sich um einen <i>irregulären Code</i>.<br><br>
+
*Von den Knoten&nbsp; $V_1$&nbsp; und&nbsp; $V_4$&nbsp; gibt es jeweils nur einen Übergang zu einem <i>Check Node</i>, von&nbsp; $V_2$&nbsp; und&nbsp; $V_3$&nbsp; dagegen zwei. <br>Aus diesem Grund handelt es sich um einen <i>irregulären Code</i>.<br><br>
  
 
Die Prüfmatrix lautet demnach:
 
Die Prüfmatrix lautet demnach:
  
:<math>{ \boldsymbol{\rm H} } =
+
::<math>{ \boldsymbol{\rm H} } =
 
\begin{pmatrix}
 
\begin{pmatrix}
 
1 &1 &0 &0\\  
 
1 &1 &0 &0\\  
Zeile 89: Zeile 93:
 
\end{pmatrix}\hspace{0.05cm}.</math>}}<br>
 
\end{pmatrix}\hspace{0.05cm}.</math>}}<br>
  
 +
{{GraueBox|TEXT= 
 +
$\text{Beispiel 3:}$&nbsp; Es folgt nun ein praxisrelevanteres Beispiel. In der&nbsp; [[Aufgaben:4.11_Analyse_von_Pr%C3%BCfmatrizen|Aufgabe 4.11]]&nbsp; wurden zwei Prüfmatrizen analysiert:
 +
*Der Coder entsprechend der Matrix&nbsp; $\mathbf{H}_1$&nbsp; ist systematisch. Die Codeparameter sind&nbsp; $n = 8, \ k = 4$&nbsp; und&nbsp; $m = 4$ &nbsp; &#8658; &nbsp;  Rate $1/2$. Der Code ist irregulär, da die Hamming&ndash;Gewichte nicht für alle Spalten gleich sind. In der Grafik ist diese &bdquo;irreguläre&nbsp; $\mathbf{H}$&ndash;Matrix&rdquo; oben angegeben.<br>
  
{{GraueBox|TEXT= 
+
*Unten angegeben ist die &bdquo;reguläre&nbsp; $\mathbf{H}$&ndash;Matrix&rdquo; entsprechend der Matrix&nbsp; $\mathbf{H}_3$&nbsp; in Aufgabe 4.11. Die Zeilen sind Linearkombinationen der oberen Matrix. Für diesen nicht systematischen Coder gilt mit&nbsp; $w_{\rm S} = 2$&nbsp; und&nbsp; $w_{\rm Z} = 4$&nbsp; für die Rate: &nbsp; $R \ge 1 - w_{\rm S}/w_{\rm Z} =  1/2$.
$\text{Beispiel 3:}$&nbsp; Es folgt nun ein praxisrelevanteres Beispiel. In der [[Aufgaben:4.11_Analyse_von_Pr%C3%BCfmatrizen|Aufgabe 4.11]] wurden zwei Prüfmatrizen analysiert:
 
*Der Coder entsprechend der Matrix $\mathbf{H}_1$ ist systematisch. Die Codeparameter sind $n = 8, \ k = 4$ und $m = 4$ &nbsp; &#8658; &nbsp; Rate $1/2$. Der Code ist irregulär, da die Hamming&ndash;Gewichte nicht für alle Spalten gleich sind. In der Grafik ist diese &bdquo;irreguläre $\mathbf{H}$&ndash;Matrix&rdquo; oben angegeben.<br>
 
  
*Unten angegeben ist die &bdquo;reguläre $\mathbf{H}$&ndash;Matrix&rdquo; entsprechend der Matrix $\mathbf{H}_3$ in [[Aufgaben:4.11_Analyse_von_Pr%C3%BCfmatrizen|Aufgabe 4.11]]. Die Zeilen sind Linearkombinationen der oberen Matrix. Für diesen nicht systematischen Coder gilt mit $w_{\rm S} = 2$ und $w_{\rm Z} = 4$ für die Rate: &nbsp; $R \ge 1 - w_{\rm S}/w_{\rm Z} =  1/2$.
 
  
 
[[Datei:P ID3071 KC T 4 4 S2b v4.png|center|frame|Tanner–Graph eines regulären und eines irregelären Codes|class=fit]]
 
[[Datei:P ID3071 KC T 4 4 S2b v4.png|center|frame|Tanner–Graph eines regulären und eines irregelären Codes|class=fit]]
  
 
Die Grafik zeigt die zugehörigen Tanner&ndash;Graphen:
 
Die Grafik zeigt die zugehörigen Tanner&ndash;Graphen:
*Der linke Graph bezieht sich auf die obere (irreguläre) Matrix. Die acht <i>Variable Nodes</i> (abgekürzt VNs) $V_i$ sind mit den vier <i>Check Nodes</i> (abgekürzt CNs) $C_j$ verbunden, falls das Element in Zeile $j$ und Spalte $i &nbsp; &#8658; &nbsp; h_{j,\hspace{0.05cm}i}$ gleich $1$ ist. Andernfalls  (falls $h_{j,\hspace{0.05cm}i} = 0$) besteht keine Verbindung.<br>
+
*Der linke Graph bezieht sich auf die obere (irreguläre) Matrix. Die acht <i>Variable Nodes</i>&nbsp; (abgekürzt VNs)&nbsp; $V_i$&nbsp; sind mit den vier <i>Check Nodes</i>&nbsp; (abgekürzt CNs)&nbsp; $C_j$&nbsp; verbunden, falls das Element in Zeile&nbsp; $j$&nbsp; und Spalte&nbsp; $i \hspace{0.15cm} &#8658; \hspace{0.15cm} h_{j,\hspace{0.05cm}i}$&nbsp; gleich&nbsp; $1$&nbsp; ist. Andernfalls&nbsp; $($falls&nbsp; $h_{j,\hspace{0.05cm}i} = 0)$&nbsp; besteht keine Verbindung.<br>
  
*Dieser Graph ist für die [[Kanalcodierung/Grundlegendes_zu_den_Low%E2%80%93density_Parity%E2%80%93check_Codes#Iterative_Decodierung_von_LDPC.E2.80.93Codes| iterative symbolweise Decodierung]] nicht sonderlich gut geeignet. Die VNs $V_5, \ \text{...}\hspace{0.05cm} , \ V_8$ sind jeweils nur mit einem CN verbunden, was für die Decodierung keinerlei Information liefert.<br>
+
*Dieser Graph ist für die&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Low%E2%80%93density_Parity%E2%80%93check_Codes#Iterative_Decodierung_von_LDPC.E2.80.93Codes| iterative symbolweise Decodierung]]&nbsp; nicht sonderlich gut geeignet. Die VNs&nbsp; $V_5, \ \text{...}\hspace{0.05cm} , \ V_8$&nbsp; sind jeweils nur mit einem CN verbunden, was für die Decodierung keine Information liefert.<br>
  
*Im rechten Tanner&ndash;Graph für den regulären Code erkennt man, dass hier von jedem VN $V_i$ zwei Verbindungslinien (englisch: <i>Edges</i>) abgehen und von jedem CN $C_j$ deren vier. Damit ist bei der Decodierung  in jeder Iterationsschleife ein Informationsgewinn möglich.<br>
+
*Im rechten Tanner&ndash;Graph für den regulären Code erkennt man, dass hier von jedem <i>Variable Node</i>&nbsp; $V_i$&nbsp; zwei Verbindungslinien&nbsp; (englisch: <i>Edges</i>)&nbsp; abgehen und von jedem <i>Check Node</i>&nbsp; $C_j$&nbsp; deren vier. Damit ist bei der Decodierung  in jeder Iterationsschleife ein Informationsgewinn möglich.<br>
  
*Man erkennt zudem, dass hier beim Übergang vom irregulären zum äquivalenten regulären Code der Einsen&ndash;Anteil zunimmt, im Beispiel von $37.5\%$ auf $50\%$. Diese Aussage kann allerdings nicht verallgemeinert werden.}}<br>
+
*Man erkennt zudem, dass hier beim Übergang vom irregulären zum äquivalenten regulären Code der Einsen&ndash;Anteil zunimmt, im Beispiel von&nbsp; $37.5\%$&nbsp; auf $50\%$. Diese Aussage kann allerdings nicht verallgemeinert werden.}}<br>
  
 
== Iterative Decodierung von LDPC–Codes ==
 
== Iterative Decodierung von LDPC–Codes ==
 
<br>
 
<br>
Als Beispiel für die iterative LDPC&ndash;Decodierung wird nun der so genannte <i>Message&ndash;passing Algorithm</i> beschrieben. Wir verdeutlichen diesen anhand des rechten Tanner&ndash;Graphen im [[Kanalcodierung/Grundlegendes_zu_den_Low%E2%80%93density_Parity%E2%80%93check_Codes#Zweiteilige_LDPC.E2.80.93Graphenrepr.C3.A4sentation_.E2.80.93_Tanner|Beispiel 3]] auf der  vorherigen Seite und damit für die dort angegebene reguläre Prüfmatrix.<br>
+
Als Beispiel für die iterative LDPC&ndash;Decodierung wird nun der so genannte&nbsp; <i>Message&ndash;passing Algorithm</i>&nbsp; beschrieben. Wir verdeutlichen diesen anhand des rechten Tanner&ndash;Graphen im&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Low%E2%80%93density_Parity%E2%80%93check_Codes#Zweiteilige_LDPC.E2.80.93Graphenrepr.C3.A4sentation_.E2.80.93_Tanner|$\text{Beispiel 3}$]]&nbsp; auf der  vorherigen Seite und damit für die dort angegebene reguläre Prüfmatrix.<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Prinzip:}$&nbsp; Beim <b>Message&ndash;passing Algorithm</b>  erfolgt abwechselnd (oder iterativ) ein Informationsaustausch zwischen den <i>Variable Nodes </i> (VNs) $V_1, \ \text{...}\hspace{0.05cm} , \ V_n$ und den <i>Check Nodes </i> (CNs) $C_1 , \ \text{...}\hspace{0.05cm}  , \ C_m$.}}<br>
+
$\text{Prinzip:}$&nbsp; Beim&nbsp; <b>Message&ndash;passing Algorithm</b>&nbsp; erfolgt abwechselnd (oder iterativ) ein Informationsaustausch zwischen den <i>Variable Nodes </i>&nbsp; (VNs)&nbsp; $V_1, \ \text{...}\hspace{0.05cm} , \ V_n$&nbsp; und den <i>Check Nodes </i>&nbsp; (CNs)&nbsp; $C_1 , \ \text{...}\hspace{0.05cm}  , \ C_m$.}}<br>
  
 
[[Datei:P ID3075 KC T 4 4 S3a v1.png|center|frame|Iterative Decodierung von LDPC–Codes|class=fit]]
 
[[Datei:P ID3075 KC T 4 4 S3a v1.png|center|frame|Iterative Decodierung von LDPC–Codes|class=fit]]
  
 
Für das betrachtete Beispiel gilt:
 
Für das betrachtete Beispiel gilt:
*Es gibt $n = 8$ <i>Variable Nodes </i> und $m = 4$ <i>Check Nodes </i>. Da ein regulärer LDPC&ndash;Code vorliegt, gehen von jedem <i>Variable Node </i> $d_{\rm V} = 2$ Verbindungslinien zu einem <i>Check Node </i> und jeder <i>Check Node </i>  ist mit $d_{\rm C} = 4$ <i>Variable Nodes </i> verbunden.
+
*Es gibt&nbsp; $n = 8$&nbsp; <i>Variable Nodes </i> und&nbsp; $m = 4$&nbsp; <i>Check Nodes </i>. Da ein regulärer LDPC&ndash;Code vorliegt, gehen von jedem <i>Variable Node </i>&nbsp; $d_{\rm V} = 2$&nbsp; Verbindungslinien zu einem <i>Check Node </i>&nbsp; und jeder <i>Check Node </i>&nbsp; ist mit&nbsp; $d_{\rm C} = 4$&nbsp; <i>Variable Nodes </i> verbunden.
  
*Der <i>Variable Node Degree</i> $d_{\rm V}$ ist gleich dem Hamming&ndash;Gewicht einer jeden Spalte $(w_{\rm S})$ und für den <i>Check Node Degree</i> gilt: &nbsp; $d_{\rm C} = w_{\rm Z}$ (Hamming&ndash;Gewicht einer jeden Zeile).
+
*Der <i>Variable Node Degree</i>&nbsp; $d_{\rm V}$&nbsp; ist gleich dem Hamming&ndash;Gewicht einer jeden Spalte&nbsp; $(w_{\rm S})$&nbsp; und für den <i>Check Node Degree</i>&nbsp; gilt: &nbsp; $d_{\rm C} = w_{\rm Z}$ (Hamming&ndash;Gewicht einer jeden Zeile).
  
*In der folgenden Beschreibung verwenden wir auch die Begriffe <i>Nachbarn eines Variable Nodes</i> &nbsp;&#8658;&nbsp; $N(V_i)$ sowie <i>Nachbarn eines Check Nodes</i> &nbsp; &#8658;&nbsp; $N(C_j)$, wobei wir uns hier auf  implizite Definitionen beschränken:
+
*In der folgenden Beschreibung verwenden wir auch die Begriffe <i>Nachbarn eines Variable Nodes</i> &nbsp; &#8658; &nbsp; $N(V_i)$&nbsp; sowie <i>Nachbarn eines Check Nodes</i> &nbsp; &#8658; &nbsp; $N(C_j)$, wobei wir uns hier auf  implizite Definitionen beschränken:
  
::<math>N(V_1) \hspace{-0.15cm}  = \hspace{-0.15cm} \{ C_1, C_2\}\hspace{0.05cm}, \hspace{0.3cm}N(V_1) = \{ C_3, C_4\}\hspace{0.05cm}, \hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.15cm},\hspace{0.3cm}N(V_8) = \{ C_1, C_4\}\hspace{0.05cm},</math>
+
::<math>N(V_1) = \{ C_1, C_2\}\hspace{0.05cm}, \hspace{0.3cm}N(V_2) = \{ C_3, C_4\}\hspace{0.05cm}, \hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.15cm},\hspace{0.3cm}N(V_8) = \{ C_1, C_4\}\hspace{0.05cm},</math>
::<math>N(C_1) \hspace{-0.15cm}  = \hspace{-0.15cm} \{ V_1, V_4, V_5, V_8\}\hspace{0.05cm}, \hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.15cm}\hspace{0.05cm}, \hspace{0.3cm}N(C_4) = \{ V_2, V_3, V_6, V_8\}\hspace{0.05cm}.</math>
+
::<math>N(C_1) = \{ V_1, V_4, V_5, V_8\}\hspace{0.05cm}, \hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.15cm}\hspace{0.05cm}, \hspace{0.3cm}N(C_4) = \{ V_2, V_3, V_6, V_8\}\hspace{0.05cm}.</math>
  
[[Datei:P ID3085 KC T 4 4 S3c v2.png|right|frame|Informationsaustausch zwischen VNs und CNs]]
+
[[Datei:P ID3085 KC T 4 4 S3c v2.png|right|frame|Informationsaustausch zwischen <i>Variable Nodes</i>&nbsp; und <i>Check Nodes </i>]]
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 4:}$&nbsp; Die Skizze aus [Liv15]<ref name='Liv15'>Liva, G.: ''Channels Codes for Iterative Decoding.'' Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.</ref> zeigt den Austausch von Information zwischen dem <i>Variable Node</i> $V_i$ und dem <i>Check Node</i> $C_j$ &ndash; ausgedrückt durch [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Zuverl.C3.A4ssigkeitsinformation_.E2.80.93_Log_Likelihood_Ratio| Log&ndash;Likelihood Ratios]] (kurz: $L$&ndash;Werte). Der Informationsaustausch geschieht in zwei Richtungen:
+
$\text{Beispiel 4:}$&nbsp; Die Skizze aus&nbsp; [Liv15]<ref name='Liv15'>Liva, G.: ''Channels Codes for Iterative Decoding.'' Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.</ref>&nbsp; zeigt den Austausch von Information zwischen dem <i>Variable Node</i>&nbsp; $V_i$&nbsp; und dem <i>Check Node</i>&nbsp; $C_j$&nbsp; &ndash; ausgedrückt durch&nbsp; [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Zuverl.C3.A4ssigkeitsinformation_.E2.80.93_Log_Likelihood_Ratio| Log&ndash;Likelihood Ratios]]&nbsp; (kurz: $L$&ndash;Werte).  
*<b>$L(V_i &#8594; C_j)$</b>:&nbsp; Extrinsische Information aus $V_i$&ndash;Sicht, &nbsp;Apriori&ndash;Information aus $C_j$&ndash;Sicht.<br>
+
 
 +
Der Informationsaustausch geschieht in zwei Richtungen:
 +
*<b>$L(V_i &#8594; C_j)$</b>:&nbsp; Extrinsische Information aus&nbsp; $V_i$&ndash;Sicht, &nbsp;Apriori&ndash;Information aus&nbsp; $C_j$&ndash;Sicht.<br>
 +
 
 +
*<b>$L(C_j &#8594; V_i)$</b>:&nbsp; Extrinsische Information aus&nbsp; $C_j$&ndash;Sicht, &nbsp;Apriori&ndash;Information aus&nbsp; $V_i$&ndash;Sicht.}}
  
*<b>$L(C_j &#8594; V_i)$</b>: Extrinsische Information aus $C_j$&ndash;Sicht, &nbsp;Apriori&ndash;Information aus $V_i$&ndash;Sicht.}}<br>
 
  
 
Die Beschreibung des Decodieralgorithmus wird fortgesetzt:<br>
 
Die Beschreibung des Decodieralgorithmus wird fortgesetzt:<br>
  
<b>Initialisierung:</b> Zu Beginn der Decodierung erhalten die <i>Variable Nodes</i> (VNs) keine Apriori&ndash;Information von den <i>Check Nodes</i> (CNs), und es gilt für $1 &#8804; i &#8804; n \text{:} \, \, L(V_i &#8594; C_j) = L_{\rm K}(V_i)$. Wie aus der Grafik am Seitenbeginn ersichtlich, ergeben sich diese Kanal&ndash;$L$&ndash;Werte $L_{\rm K}(V_i)$ aus den Empfangswerten $y_i$.<br><br>
+
<b>Initialisierung:</b>&nbsp; Zu Beginn der Decodierung erhalten die <i>Variable Nodes</i>&nbsp; (VNs) keine Apriori&ndash;Information von den <i>Check Nodes</i>&nbsp; (CNs), und es gilt für&nbsp; $1 &#8804; i &#8804; n \text{:}$ &nbsp;
 +
:$$L(V_i &#8594; C_j) = L_{\rm K}(V_i).$$
 +
 
 +
Wie aus der Grafik am Seitenbeginn ersichtlich, ergeben sich diese Kanal&ndash;$L$&ndash;Werte&nbsp; $L_{\rm K}(V_i)$&nbsp; aus den Empfangswerten&nbsp; $y_i$.<br><br>
 +
 
 +
<b>Check Node Decoder</b>:&nbsp; Jeder Knoten&nbsp; $C_j$&nbsp; repräsentiert eine Prüfgleichung. So steht&nbsp; $C_1$&nbsp; für die Gleichung&nbsp; $V_1 + V_4 + V_5 + V_8 = 0$.  Man erkennt den Zusammenhang zur extrinsischen Information bei der symbolweisen Decodierung des <i>Single Parity&ndash;check Codes</i>.
  
<b>Check Node Decoder</b>: Jeder Knoten $C_j$ repräsentiert eine Prüfgleichung. So steht $C_1$ für die Gleichung $V_1 + V_4 + V_5 + V_8 = 0$.  Man erkennt den Zusammenhang zur extrinsischen Information bei der symbolweisen Decodierung des <i>Single Parity&ndash;check Codes</i>. In Analogie zur Seite  [[Kanalcodierung/Soft–in_Soft–out_Decoder#Zur_Berechnung_der_extrinsischen_L.E2.80.93Werte| Zur Berechnung der extrinsischen L&ndash;Werte]] und [[Aufgabe 4.4]] gilt somit für den extrinsischen $L$&ndash;Wert von $C_j$ und gleichzeitig für die Apriori&ndash;Information bezüglich $V_i$:
+
In Analogie zur Seite&nbsp; [[Kanalcodierung/Soft–in_Soft–out_Decoder#Zur_Berechnung_der_extrinsischen_L.E2.80.93Werte| Zur Berechnung der extrinsischen L&ndash;Werte]]&nbsp; und zur&nbsp; [[Aufgaben:Aufgabe_4.4:_Extrinsische_L–Werte_beim_SPC|Aufgabe 4.4]]&nbsp; gilt somit für den extrinsischen&nbsp; $L$&ndash;Wert von&nbsp; $C_j$&nbsp; und gleichzeitig für die Apriori&ndash;Information bezüglich&nbsp; $V_i$:
  
 
::<math>L(C_j \rightarrow V_i) = 2 \cdot  {\rm tanh}^{-1}\left  [ \prod\limits_{V \in N(C_j)\hspace{0.05cm},\hspace{0.1cm} V \ne V_i} \hspace{-0.35cm}{\rm tanh}\left [L(V \rightarrow C_j \right ] /2) \right ]
 
::<math>L(C_j \rightarrow V_i) = 2 \cdot  {\rm tanh}^{-1}\left  [ \prod\limits_{V \in N(C_j)\hspace{0.05cm},\hspace{0.1cm} V \ne V_i} \hspace{-0.35cm}{\rm tanh}\left [L(V \rightarrow C_j \right ] /2) \right ]
 
  \hspace{0.05cm}.</math>
 
  \hspace{0.05cm}.</math>
  
<b>Variable Node Decoder</b>: Im Gegensatz zum <i>Check Node Decoder</i> (CND) besteht beim <i>Variable Node Decoder</i> (VND) eine Verwandtschaft zur Decodierung eines <i>Repetition Codes</i>, weil alle mit $V_i$ verbundenen <i>Check Nodes</i> $C_j$ demselben Bit  entsprechen &nbsp;&#8658;&nbsp; dieses Bit wird quasi $d_{\rm V}$ mal wiederholt.<br>
 
  
In Analogie zu  zur Seite  [[Kanalcodierung/Soft–in_Soft–out_Decoder#Zur_Berechnung_der_extrinsischen_L.E2.80.93Werte| Zur Berechnung der extrinsischen L&ndash;Werte]]  gilt für den extrinsischen $L$&ndash;Wert von $V_i$ und gleichzeitig für die Apriori&ndash;Information bezüglich $C_j$:
+
<b>Variable Node Decoder</b>:&nbsp; Im Gegensatz zum <i>Check Node Decoder</i>&nbsp; (CND) besteht beim <i>Variable Node Decoder</i>&nbsp; (VND) eine Verwandtschaft zur Decodierung eines <i>Repetition Codes</i>, weil alle mit&nbsp; $V_i$&nbsp; verbundenen <i>Check Nodes</i>&nbsp; $C_j$&nbsp; demselben Bit  entsprechen &nbsp; &#8658; &nbsp; dieses Bit wird quasi&nbsp; $d_{\rm V}$&nbsp; mal wiederholt.<br>
 +
 
 +
In Analogie zu  zur Seite&nbsp; [[Kanalcodierung/Soft–in_Soft–out_Decoder#Zur_Berechnung_der_extrinsischen_L.E2.80.93Werte| Zur Berechnung der extrinsischen L&ndash;Werte]]&nbsp; gilt für den extrinsischen&nbsp; $L$&ndash;Wert von&nbsp; $V_i$&nbsp; und gleichzeitig für die Apriori&ndash;Information bezüglich&nbsp; $C_j$:
  
 
::<math>L(V_i  \rightarrow C_j) = L_{\rm K}(V_i) + \hspace{-0.55cm} \sum\limits_{C \hspace{0.05cm}\in\hspace{0.05cm} N(V_i)\hspace{0.05cm},\hspace{0.1cm} C \hspace{0.05cm}\ne\hspace{0.05cm} C_j} \hspace{-0.55cm}L(C \rightarrow V_i)  
 
::<math>L(V_i  \rightarrow C_j) = L_{\rm K}(V_i) + \hspace{-0.55cm} \sum\limits_{C \hspace{0.05cm}\in\hspace{0.05cm} N(V_i)\hspace{0.05cm},\hspace{0.1cm} C \hspace{0.05cm}\ne\hspace{0.05cm} C_j} \hspace{-0.55cm}L(C \rightarrow V_i)  
 
  \hspace{0.05cm}.</math>
 
  \hspace{0.05cm}.</math>
  
Das folgende Schaubild des beschriebenen Decodieralgorithmus' für LDPC&ndash;Codes zeigt Ähnlichkeiten mit der Vorgehensweise bei [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Seriell_verkettete_Turbocodes_.E2.80.93_SCCC| seriell verketteten Turbocodes]].
+
Das folgende Schaubild des beschriebenen Decodieralgorithmus' für LDPC&ndash;Codes zeigt Ähnlichkeiten mit der Vorgehensweise bei&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Seriell_verkettete_Turbocodes_.E2.80.93_SCCC| seriell verketteten Turbocodes]].
* Um eine vollständige Analogie zwischen der LDPC&ndash; und der Turbodecodierung herzustellen, ist auch hier zwischen dem <i>Variable Node Decoder</i> (VND) und dem <i>Check Node Decoder</i> (CND) ein <i>Interleaver</i> sowie ein <i>De&ndash;Interleaver</i> eingezeichnet.  
+
 
 +
[[Datei:P ID3078 KC T 4 4 S3b v3.png|center|frame|Zusammenhang zwischen LDPC–Decodierung und serieller Turbo–Decodierung|class=fit]]
 +
 
 +
* Um eine vollständige Analogie zwischen der LDPC&ndash; und der Turbodecodierung herzustellen, ist auch hier zwischen dem <i>Variable Node Decoder</i>&nbsp; (VND) und dem <i>Check Node Decoder</i>&nbsp; (CND) ein &bdquo;<i>Interleaver</i>&nbsp;&rdquo;&nbsp; sowie ein &bdquo;<i>De&ndash;Interleaver</i>&nbsp;&rdquo;&nbsp; eingezeichnet.  
 
*Da es sich hierbei nicht um reale Systemkomponenten handelt, sondern nur um Analogien, haben wir diese Begriffe in Hochkommata gesetzt.<br>
 
*Da es sich hierbei nicht um reale Systemkomponenten handelt, sondern nur um Analogien, haben wir diese Begriffe in Hochkommata gesetzt.<br>
  
[[Datei:P ID3078 KC T 4 4 S3b v3.png|center|frame|Zusammenhang zwischen  LDPC– und serieller Turbo–Decodierung|class=fit]]
 
  
 
== Leistungsfähigkeit regulärer LDPC–Codes ==
 
== Leistungsfähigkeit regulärer LDPC–Codes ==
 
<br>
 
<br>
 
[[Datei:P ID3079 KC T 4 4 S4a v5.png|right|frame|Bitfehlerrate von LDPC–Codes]]
 
[[Datei:P ID3079 KC T 4 4 S4a v5.png|right|frame|Bitfehlerrate von LDPC–Codes]]
Wir betrachten nun wie in [Str14]<ref name='Str14'>Strutz, T.: ''Low–density Parity–check Codes – Eine Einführung''. Vorlesungsmaterial.  Hochschule für Telekommunikation, Leipzig, 2014. PDF-Dokument [http://www1.hft-leipzig.de/strutz/Kanalcodierung/ldpc_tutorial.pdf PDF-Dokument].</ref> fünf reguläre LDPC&ndash;Codes. Die Grafik zeigt die Bitfehlerrate (BER) abhängig vom AWGN&ndash;Parameter $10 \cdot {\rm lg} \, E_{\rm B}/N_0$. Zum Vergleich ist die Kurve für uncodierte Übertragung  eingezeichnet.<br>
+
Wir betrachten nun wie in&nbsp; [Str14]<ref name='Str14'>Strutz, T.: ''Low–density Parity–check Codes – Eine Einführung''. Vorlesungsmaterial.  Hochschule für Telekommunikation, Leipzig, 2014. PDF-Dokument [http://www1.hft-leipzig.de/strutz/Kanalcodierung/ldpc_tutorial.pdf PDF-Dokument].</ref>&nbsp; fünf reguläre LDPC&ndash;Codes. Die Grafik zeigt die Bitfehlerrate&nbsp; $\rm (BER)$&nbsp; abhängig vom AWGN&ndash;Parameter&nbsp; $10 \cdot {\rm lg} \, E_{\rm B}/N_0$. Zum Vergleich ist auch die Kurve für uncodierte Übertragung  eingezeichnet.<br>
  
 
Diese LDPC&ndash;Codes  zeigen folgende Eigenschaften:
 
Diese LDPC&ndash;Codes  zeigen folgende Eigenschaften:
*Die Prüfmatrizen $\mathbf{H}$ weisen jeweils $n$ Spalten und $m = n/2$ linear voneinander unabhängige Zeilen auf. In jeder Zeile gibt es $w_{\rm Z} = 6$ Einsen und in jeder Spalte $w_{\rm S} = 3$ Einsen.<br>
+
*Die Prüfmatrizen&nbsp; $\mathbf{H}$&nbsp; weisen jeweils&nbsp; $n$&nbsp; Spalten und&nbsp; $m = n/2$&nbsp; linear voneinander unabhängige Zeilen auf. In jeder Zeile gibt es&nbsp; $w_{\rm Z} = 6$&nbsp; Einsen und in jeder Spalte&nbsp; $w_{\rm S} = 3$&nbsp; Einsen.<br>
  
*Der Einsen&ndash;Anteil beträgt $w_{\rm Z}/n = w_{\rm S}/m$, so dass bei großer Codewortlänge $n$ die Klassifizierung &bdquo;<i>Low&ndash;density</i>&rdquo; gerechtfertigt ist. Für die rote Kurve $(n = 2^{10})$ ist der Einsen&ndash;Anteil $0.6\%$.<br>
+
*Der Einsen&ndash;Anteil beträgt&nbsp; $w_{\rm Z}/n = w_{\rm S}/m$, so dass bei großer Codewortlänge&nbsp; $n$&nbsp; die Klassifizierung &bdquo;<i>Low&ndash;density</i>&rdquo; gerechtfertigt ist. Für die rote Kurve&nbsp; $(n = 2^{10})$&nbsp; beträgt der Einsen&ndash;Anteil&nbsp; $0.6\%$.<br>
  
*Die Rate aller Codes beträgt $R = 1 \, &ndash;w_{\rm S}/w_{\rm Z} = 1/2$. Wegen der linearen Unabhängigkeit der Matrixzeilen gilt aber auch $R = k/n$ mit der Informationswortlänge $k = n \, &ndash; m = n/2$.<br><br>
+
*Die Rate aller Codes beträgt&nbsp; $R = 1 - w_{\rm S}/w_{\rm Z} = 1/2$. Wegen der linearen Unabhängigkeit der Matrixzeilen gilt aber auch&nbsp; $R = k/n$&nbsp; mit der Informationswortlänge&nbsp; $k = n - m = n/2$.<br><br>
  
 
Aus der Grafik  erkennt man:
 
Aus der Grafik  erkennt man:
*Die Bitfehlerrate ist um so kleiner, je länger der  Code ist. Für $10 \cdot {\rm lg} \, E_{\rm B}/N_0 = 2 \ \rm dB$ und $n = 2^8 = 256$ ergibt sich ${\rm BER} \approx 10^{-2}$. Für $n = 2^{12} = 4096$ dagegen nur ${\rm BER} \approx 2 \cdot 10^{-7}$.<br>
+
*Die Bitfehlerrate ist um so kleiner, je länger der  Code ist:
 +
:*Für&nbsp; $10 \cdot {\rm lg} \, E_{\rm B}/N_0 = 2 \ \rm dB$&nbsp; und&nbsp; $n = 2^8 = 256$&nbsp; ergibt sich&nbsp; ${\rm BER} \approx 10^{-2}$.  
 +
:*Für&nbsp; $n = 2^{12} = 4096$&nbsp; dagegen nur&nbsp; ${\rm BER} \approx 2 \cdot 10^{-7}$.<br>
  
*Mit $n = 2^{15} = 32768$ (violette Kurve) benötigt man $10 \cdot {\rm lg} \, E_{\rm B}/N_0 \approx 1.35 \ \rm dB$ für ${\rm BER} = 10^{-5}$. Der Abstand von der  Shannon&ndash;Grenze ($0.18 \ \rm dB$ für $R = 1/2$ und BPSK) beträgt ca. $1.2 \ \rm dB$.
+
*Mit&nbsp; $n = 2^{15} = 32768$&nbsp; (violette Kurve) benötigt man&nbsp; $10 \cdot {\rm lg} \, E_{\rm B}/N_0 \approx 1.35 \ \rm dB$&nbsp; für&nbsp; ${\rm BER} = 10^{-5}$.  
 +
*Der Abstand von der  Shannon&ndash;Grenze &nbsp;$(0.18 \ \rm dB$&nbsp; für&nbsp; $R = 1/2$&nbsp; und BPSK$)$ beträgt ca.&nbsp; $1.2 \ \rm dB$.
 
<br clear=all>
 
<br clear=all>
Die Kurven für $n = 2^8$ bis $n = 2^{10}$ weisen zudem auf einen Effekt hin, den wir schon bei den [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Leistungsf.C3.A4higkeit_der_Turbocodes| Turbocodes]] festgestellt haben:  
+
[[Datei:P ID3080 KC T 4 4 S4b v4.png|right|frame| &bdquo;Waterfall Region & Error Floor&rdquo;]]
[[Datei:P ID3080 KC T 4 4 S4b v4.png|right|frame| „Waterfall Region” & „Error Floor”]]
+
Die Kurven für&nbsp; $n = 2^8$&nbsp; bis&nbsp; $n = 2^{10}$&nbsp; weisen zudem auf einen Effekt hin, den wir schon bei den&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Leistungsf.C3.A4higkeit_der_Turbocodes| Turbocodes]]&nbsp; festgestellt haben:
*Zuerst fällt die BER&ndash;Kurve steil ab &nbsp;&#8658;&nbsp; &bdquo;Waterfall Region&rdquo;.
 
*Danach folgt ein Knick und ein Verlauf mit deutlich geringerer Steigung  &nbsp;&#8658;&nbsp; &bdquo;Error Floor&rdquo;.
 
*Die qualitative Grafik rechts verdeutlicht den Effekt, der natürlich nicht abrupt einsetzt (Übergang nicht eingezeichnet).<br>
 
  
 +
*Zuerst fällt die BER&ndash;Kurve steil ab &nbsp; &#8658; &nbsp; &bdquo;Waterfall Region&rdquo;.
 +
*Danach folgt ein Knick und ein Verlauf mit deutlich geringerer Steigung  &nbsp; &#8658; &nbsp; &bdquo;Error Floor&rdquo;.
 +
*Die qualitative untere Grafik verdeutlicht den Effekt, der natürlich nicht abrupt einsetzt (Übergang nicht eingezeichnet).<br>
  
Ein (LDPC&ndash;)Code ist immer dann als gut zu bezeichnen, wenn
+
 
 +
Ein (LDPC&ndash;) Code ist immer dann als gut zu bezeichnen, wenn
 
* die BER&ndash;Kurve nahe der Shannon&ndash;Grenze steil abfällt,<br>
 
* die BER&ndash;Kurve nahe der Shannon&ndash;Grenze steil abfällt,<br>
  
* der &bdquo;Error Floor&rdquo;  bei sehr niedrigen BER&ndash;Werten liegt (Ursachen hierfür siehe nächste Seite, Beispiel 5),<br>
+
* der &bdquo;Error Floor&rdquo;  bei sehr niedrigen BER&ndash;Werten liegt (Ursachen hierfür siehe nächste Seite,&nbsp; $\text{Beispiel 5)}$,<br>
  
 
* die  Anzahl der erforderlichen Iterationen handhabbar ist, und<br>
 
* die  Anzahl der erforderlichen Iterationen handhabbar ist, und<br>
Zeile 192: Zeile 211:
 
<br>
 
<br>
 
[[Datei:P ID3087 KC T 4 4 S5a v3.png|right|frame|LDPC–Codes im Vergleich zur Shannon–Grenze]]  
 
[[Datei:P ID3087 KC T 4 4 S5a v3.png|right|frame|LDPC–Codes im Vergleich zur Shannon–Grenze]]  
In diesem Kapitel wurden vorwiegend reguläre LDPC&ndash;Codes behandelt, auch im BER&ndash;Diagramm auf der letzten Seite.<br>
+
In diesem Kapitel wurden vorwiegend reguläre LDPC&ndash;Codes behandelt, auch im&nbsp;  $\rm BER$&ndash;Diagramm auf der letzten Seite. Die Ignoranz der irregulären LDPC&ndash;Codes ist nur der Kürze dieses Kapitels geschuldet, nicht deren Leistungsfähigkeit. Im Gegenteil:
 
 
Die Ignoranz der irregulären LDPC&ndash;Codes ist nur der Kürze dieses Kapitels geschuldet, nicht deren Leistungsfähigkeit. Im Gegenteil:
 
 
* Irreguläre LDPC&ndash;Codes gehören zu den besten Kanalcodes überhaupt.  
 
* Irreguläre LDPC&ndash;Codes gehören zu den besten Kanalcodes überhaupt.  
*Das gelbe Kreuz in der Grafik liegt praktisch auf der informationstheoretischen Grenzkurve für binäre Eingangssignale (grüne Kurve, mit BPSK beschriftet).  
+
*Das gelbe Kreuz in der Grafik liegt praktisch auf der informationstheoretischen Grenzkurve für binäre Eingangssignale (grüne Kurve, mit&nbsp;  $\rm BPSK$ beschriftet).  
*Die Codewortlänge dieses irregulären Rate&ndash;1/2&ndash;Codes von [CFRU01]<ref>Chung S.Y; Forney Jr., G.D.; Richardson, T.J.; Urbanke, R.: ''On the Design of Low-Density Parity- Check Codes within 0.0045 dB of the Shannon Limit.'' – In: IEEE Communications Letters, vol. 5, no. 2 (2001), pp. 58–60.</ref> beträgt $2 \cdot 10^6$.  
+
*Die Codewortlänge dieses irregulären Rate&ndash;$1/2$&ndash;Codes von [CFRU01]<ref>Chung S.Y; Forney Jr., G.D.; Richardson, T.J.; Urbanke, R.: ''On the Design of Low-Density Parity- Check Codes within 0.0045 dB of the Shannon Limit.'' – In: IEEE Communications Letters, vol. 5, no. 2 (2001), pp. 58–60.</ref> beträgt&nbsp; $n = 2 \cdot 10^6$.  
*Daraus ist schon ersichtlich, dass dieser Code nicht für den praktischen Einsatz gedacht war, sondern für einen Rekordversuch getunt wurde.<br>
+
*Daraus ist schon ersichtlich, dass dieser Code nicht für den praktischen Einsatz gedacht war, sondern sogar für einen Rekordversuch getunt wurde.<br>
  
  
Bei der LDPC&ndash;Codekonstruktion geht man ja stets von der Prüfmatrix $\mathbf{H}$ aus. Für den gerade genannten Code hat diese die Dimension $1 \cdot 10^6 &times; 2 \cdot 10^6$, beinhaltet also $2 \cdot 10^{12}$ Matrixelemente.
+
Bei der LDPC&ndash;Codekonstruktion geht man ja stets von der Prüfmatrix&nbsp; $\mathbf{H}$&nbsp; aus. Für den gerade genannten Code hat diese die Dimension&nbsp; $1 \cdot 10^6 &times; 2 \cdot 10^6$, beinhaltet also&nbsp; $2 \cdot 10^{12}$&nbsp; Matrixelemente.
 
<br clear=all>
 
<br clear=all>
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Fazit:}$&nbsp; Füllt man die Matrix per Zufallsgenerator mit (wenigen) Einsen &nbsp;&#8658;&nbsp; &bdquo;<i>Low&ndash;density</i>&rdquo;. So spricht man von <b>unstrukturiertem Code&ndash;Design</b>. Dies kann zu langen Codes mit guter Performance führen, manchmal aber auch zu folgenden Problemen:
+
$\text{Fazit:}$&nbsp; Füllt man die Matrix per Zufallsgenerator mit (wenigen) Einsen &nbsp; &#8658; &nbsp; &bdquo;<i>Low&ndash;density</i>&rdquo;, so spricht man von&nbsp; <b>unstrukturiertem Code&ndash;Design</b>. Dies kann zu langen Codes mit guter Performance führen, manchmal aber auch zu folgenden Problemen:
*Die Komplexität des Coders kann zunehmen, da trotz Modifikation der Prüfmatrix $\mathbf{H}$ sichergestellt werden muss, dass die Generatormatrix $\mathbf{G}$ systematisch sein muss.<br>
+
*Die Komplexität des Coders kann zunehmen, da trotz Modifikation der Prüfmatrix&nbsp; $\mathbf{H}$&nbsp; sichergestellt werden muss, dass die Generatormatrix&nbsp; $\mathbf{G}$&nbsp; systematisch ist.<br>
  
*Aufwändige Hardware&ndash;Realisierung des iterativen Decoders.<br>
+
*Es erfordert eine aufwändige Hardware&ndash;Realisierung des iterativen Decoders.<br>
  
*&bdquo;Error Floor&rdquo; durch einzelne Einsen in einer Spalte (oder Zeile) sowie kurze Schleifen &nbsp; &rArr; &nbsp; siehe Beispiel 5..}}<br><br>
+
*Es kommt zu einem &bdquo;Error Floor&rdquo; durch einzelne Einsen in einer Spalte (oder Zeile) sowie durch kurze Schleifen &nbsp; &rArr; &nbsp; siehe nachfolgendes Beispiel.}}<br><br>
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 5:}$&nbsp; Im linken Teil der Grafik ist der Tanner&ndash;Graph für einen regulären LDPC&ndash;Code mit der Prüfmatrix $\mathbf{H}_1$ dargestellt. Grün eingezeichnet ist ein Beispiel für die minimale Schleifenlänge (englisch: <i>Girth</i>). Diese Kenngröße gibt an, wieviele Kanten man mindestens durchläuft, bis man von einem <i>Check Node</i> $C_j$ wieder bei diesem landet (oder von $V_i$ zu $V_i$). Im linken Beispiel ergibt sich die minimale Kantenlänge $6$, zum Beispiel der Weg $C_1 &#8594; V_1 &#8594; C_3 &#8594; V_5 &#8594; C_2 &#8594; V_2 &#8594; C_1$.<br>
+
$\text{Beispiel 5:}$&nbsp; Im linken Teil der Grafik ist der Tanner&ndash;Graph für einen regulären LDPC&ndash;Code mit der Prüfmatrix&nbsp; $\mathbf{H}_1$&nbsp; dargestellt. Grün eingezeichnet ist ein Beispiel für die minimale Schleifenlänge (englisch:&nbsp; <i>Girth</i>). Diese Kenngröße gibt an, wieviele Kanten man mindestens durchläuft, bis man von einem <i>Check Node</i>&nbsp; $C_j$&nbsp; wieder bei diesem landet $($oder von&nbsp; $V_i$&nbsp; zu&nbsp; $V_i)$. Im linken Beispiel ergibt sich die minimale Kantenlänge&nbsp; $6$, zum Beispiel der Weg&nbsp; $C_1 &#8594; V_1 &#8594; C_3 &#8594; V_5 &#8594; C_2 &#8594; V_2 &#8594; C_1$.<br>
  
 
[[Datei:P ID3088 KC T 4 4 S4c v3.png|center|frame|Zur Definition eines „Girth”|class=fit]]
 
[[Datei:P ID3088 KC T 4 4 S4c v3.png|center|frame|Zur Definition eines „Girth”|class=fit]]
  
Vertauscht man in der Prüfmatrix nur zwei Einsen &nbsp;&#8658;&nbsp; Matrix $\mathbf{H}_2$, so wird der  LDPC&ndash;Code irregulär:
+
Vertauscht man in der Prüfmatrix nur zwei Einsen &nbsp; &#8658; &nbsp; Matrix&nbsp; $\mathbf{H}_2$, so wird der  LDPC&ndash;Code irregulär:
*Die minimale Schleifenlänge ist nun $4$, von $C_1 &#8594; V_4 &#8594; C_4 &#8594; V_6 &#8594; C_1$.  
+
*Die minimale Schleifenlänge ist nun&nbsp; $4$, von&nbsp; $C_1 &#8594; V_4 &#8594; C_4 &#8594; V_6 &#8594; C_1$.  
*Ein kleiner <i>Girth</i> führt zu einem ausgeprägtrn &bdquo;Error Floor&rdquo; im BER&ndash;Verlauf.}}<br>
+
*Ein kleiner <i>Girth</i>&nbsp; führt zu einem ausgeprägten &bdquo;Error Floor&rdquo; im BER&ndash;Verlauf.}}<br>
  
 
== Einige Anwendungsgebiete für LDPC–Codes ==
 
== Einige Anwendungsgebiete für LDPC–Codes ==
Zeile 225: Zeile 242:
 
Im nebenstehenden Schaubild sind im Vergleich zur AWGN&ndash;Kanalkapazität zwei Kommunikations&ndash;Standards eingetragen, die auf strukturierten  (regulären) LDPC&ndash;Codes basieren.<br>
 
Im nebenstehenden Schaubild sind im Vergleich zur AWGN&ndash;Kanalkapazität zwei Kommunikations&ndash;Standards eingetragen, die auf strukturierten  (regulären) LDPC&ndash;Codes basieren.<br>
  
Anzumerken ist, dass für die eingezeichneten standardisierten Codes die Bitfehlerrate $10^{-5}$ zugrunde liegt, während die Kapazitätskurven (entsprechend der Informationstheorie) für die Fehlerwahrscheinlichkeit $0$ gelten.
+
Anzumerken ist, dass für die eingezeichneten standardisierten Codes die Bitfehlerrate ${\rm BER}=10^{-5}$ zugrunde liegt, während die Kapazitätskurven (entsprechend der Informationstheorie) für die Fehlerwahrscheinlichkeit &bdquo;Null&rdquo; gelten.
  
Rote Kreuze zeigen die '''LDPC&ndash;Codes nach CCSDS''' (<i>Consultative Comittee for Space Data Systems</i>), entwickelt für ferne Weltraummissionen:  
+
Rote Kreuze zeigen die&nbsp; '''LDPC&ndash;Codes nach CCSDS'''&nbsp; (<i>Consultative Comittee for Space Data Systems</i>), entwickelt für ferne Weltraummissionen:  
*Diese Klasse stellt Codes der Rate $1/3$, $1/2$, $2/3$ und $4/5$ bereit.  
+
*Diese Klasse stellt Codes der Rate&nbsp; $1/3$,&nbsp; $1/2$,&nbsp; $2/3$&nbsp; und&nbsp; $4/5$ bereit.  
*Alle Punkte liegen ca. $1 \ \rm dB$ rechts von der Kapazitätskurve für binären Eingang (grüne Kurve &bdquo;BPSK&rdquo;).<br>
+
*Alle Punkte liegen ca.&nbsp; $1 \ \rm dB$&nbsp; rechts von der Kapazitätskurve für binären Eingang (grüne Kurve &bdquo;BPSK&rdquo;).<br>
  
  
Die blauen Rechtecke markieren die '''LDPC&ndash;Codes für DVB&ndash;T2/S2'''. Die Abkürzungen stehen für  &bdquo;Digital Video Broadcasting &ndash; Terrestrial&rdquo; bzw. &bdquo;Digital Video Broadcasting &ndash; Satellite&rdquo;, und die &bdquo;$2$&rdquo; macht deutlich, dass es sich jeweils um die  zweite Generation (von 2005 bzw. 2009)  handelt.  
+
Die blauen Rechtecke markieren die&nbsp; '''LDPC&ndash;Codes für DVB&ndash;T2/S2'''. Die Abkürzungen stehen für  &bdquo;Digital Video Broadcasting &ndash; Terrestrial&rdquo; bzw. &bdquo;Digital Video Broadcasting &ndash; Satellite&rdquo;, und die Kennzeichnung  &bdquo;$2$&rdquo; macht deutlich, dass es sich jeweils um die  zweite Generation (von 2005 bzw. 2009)  handelt.  
*Der Standard ist durch 22 Prüfmatrizen definiert, die Raten von etwa $0.2$ bis zu $19/20$ zur Verfügung stellen.  
+
*Der Standard ist durch&nbsp; $22$&nbsp; Prüfmatrizen definiert, die Raten von etwa&nbsp; $0.2$&nbsp; bis zu&nbsp; $19/20$&nbsp; zur Verfügung stellen.  
*Je elf Varianten gelten für die  Codelänge $64800$ Bit (<i>Normal FECFRAME</i>) bzw. $16200$ Bit (<i>Short FECFRAME</i>).  
+
*Je elf Varianten gelten für die  Codelänge&nbsp; $64800$&nbsp; Bit (<i>Normal FECFRAME</i>) bzw.&nbsp; $16200$&nbsp; Bit (<i>Short FECFRAME</i>).  
*Kombiniert mit [[Modulationsverfahren/Quadratur%E2%80%93Amplitudenmodulation#Weitere_Signalraumkonstellationen| Modulationsverfahren hoher Ordnung]] (8PSK, 16&ndash;ASK/PSK, \text{...}\hspace{0.05cm}) zeichnen sich die Codes durch große spektrale Effizienz aus.<br>
+
*Kombiniert mit&nbsp; [[Modulationsverfahren/Quadratur%E2%80%93Amplitudenmodulation#Weitere_Signalraumkonstellationen| Modulationsverfahren hoher Ordnung]]&nbsp; (8PSK, 16&ndash;ASK/PSK, ...&nbsp;) zeichnen sich die Codes durch eine große spektrale Effizienz aus.<br>
  
  
Die DVB&ndash;Codes gehören zu den <i>Irregular Repeat Accumulate</i> (IRA) Codes die erstmals im Jahr 2000 in [JKE00]<ref name='JKE00'>Jin, H.; Khandekar, A.; McEliece, R.: ''Irregular Repeat–Accumulate Codes.'' Proc. of the 2nd Int. Symp. on Turbo Codes and Related Topics, Best, France, S. 1–8., Sept. 2000.</ref> vorgestellt wurden.  
+
Die DVB&ndash;Codes gehören zu den&nbsp; <i>Irregular Repeat Accumulate</i>&nbsp; $\rm (IRA)$ Codes, die erstmals im Jahr 2000 in&nbsp; [JKE00]<ref name='JKE00'>Jin, H.; Khandekar, A.; McEliece, R.: ''Irregular Repeat–Accumulate Codes.'' Proc. of the 2nd Int. Symp. on Turbo Codes and Related Topics, Best, France, S. 1–8., Sept. 2000.</ref>&nbsp; vorgestellt wurden.  
  
 
[[Datei:P ID3082 KC T 4 4 S6a v3.png|center|frame|IRA–Coder bei DVB–S2/T2|class=fit]]
 
[[Datei:P ID3082 KC T 4 4 S6a v3.png|center|frame|IRA–Coder bei DVB–S2/T2|class=fit]]
  
 
Die Grafik zeigt die Grundstruktur des Coders.  
 
Die Grafik zeigt die Grundstruktur des Coders.  
*Der grün hinterlegte Teil &ndash; mit Repetition Code (RC), Interleaver, Single Parity&ndash;Code (SPC) sowie Akkumulator &ndash; entspricht exakt einem seriell&ndash;verketteten Turbocode &nbsp;&#8658;&nbsp; siehe [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Einige_Anwendungsgebiete_f.C3.BCr_Turbocodes| RA&ndash;Coder]].  
+
*Der grün hinterlegte Teil &ndash; mit Repetition Code&nbsp; $\rm (RC)$, Interleaver, Single Parity&ndash;Code&nbsp; $\rm  (SPC)$&nbsp; sowie Akkumulator &ndash; entspricht exakt einem seriell&ndash;verketteten Turbocode &nbsp; &#8658; &nbsp; siehe&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Einige_Anwendungsgebiete_f.C3.BCr_Turbocodes| RA&ndash;Coder]].  
*Die Beschreibung des IRA&ndash;Codes basiert aber allein auf der Prüfmatrix $\mathbf{H}$, die sich durch den <i>irregulären Repetition Code</i> in eine für die Decodierung günstige Form bringen lässt.   
+
*Die Beschreibung des IRA&ndash;Codes basiert aber allein auf der Prüfmatrix&nbsp; $\mathbf{H}$, die sich durch den&nbsp; <i>irregulären Repetition Code</i>&nbsp; in eine für die Decodierung günstige Form bringen lässt.   
*Als äußerer Code wird zudem ein hochratiger BCH&ndash;Code (von '''B'''ose&ndash;'''C'''haudhuri&ndash;'''H'''ocquenghem) verwendet, der den <i>Error Floor</i> herabsetzen soll.<br>
+
*Als äußerer Code wird zudem ein hochratiger BCH&ndash;Code (von $\rm B$ose&ndash;$\rm C$haudhuri&ndash;$\rm H$ocquenghem) verwendet, der den&nbsp; <i>Error Floor</i>&nbsp; herabsetzen soll.<br>
  
  
  
 
In der Grafik am Seitenanfang nicht eingetragen sind  
 
In der Grafik am Seitenanfang nicht eingetragen sind  
*die LDPC&ndash;Codes für den Standard <i>DVB Return Channel Terrestrial</i> (RCS),  
+
*die LDPC&ndash;Codes für den Standard&nbsp; <i>DVB Return Channel Terrestrial</i> (RCS),  
*die LDPC&ndash;Codes für den WiMax&ndash;Standard (IEEE 802.16), sowie  
+
*die LDPC&ndash;Codes für den WiMax&ndash;Standard&nbsp; (IEEE 802.16), sowie  
*die LDPC&ndash;Codes für das 10GBASE&ndash;T&ndash;Ethernet,   
+
*die LDPC&ndash;Codes für das&nbsp; 10GBASE&ndash;T&ndash;Ethernet,   
 +
 
  
 
die gewisse Ähnlichkeiten mit den IRA&ndash;Codes aufweisen.<br>
 
die gewisse Ähnlichkeiten mit den IRA&ndash;Codes aufweisen.<br>
Zeile 262: Zeile 280:
 
[[Aufgaben:4.11Z_Coderate_aus_der_Pr%C3%BCfmatrix|Zusatzaufgabe 4.11Z: Coderate aus der Prüfmatrix]]
 
[[Aufgaben:4.11Z_Coderate_aus_der_Pr%C3%BCfmatrix|Zusatzaufgabe 4.11Z: Coderate aus der Prüfmatrix]]
  
[[Aufgaben:4.12 Regulärer/irregulärer Tanner–Graph|Aufgabe 4.12: Regulärer/irregulärer Tanner–Graph]]
+
[[Aufgaben:Aufgabe_4.12:_Regulärer_und_irregulärer_Tanner–Graph|Aufgabe 4.12: Regulärer/irregulärer Tanner–Graph]]
  
 
[[Aufgaben:4.13 Decodierung von LDPC–Codes|Aufgabe 4.13: Decodierung von LDPC–Codes]]
 
[[Aufgaben:4.13 Decodierung von LDPC–Codes|Aufgabe 4.13: Decodierung von LDPC–Codes]]

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



Einige Charakteristika der LDPC–Codes


Die  Low–density Parity–check Codes  – kurz  LDPC–Codes  – wurden bereits Anfang der 1960er Jahre erfunden und gehen auf die Dissertation  [Gal63][1] von  Robert G. Gallager  zurück.

Die Idee kam allerdings aufgrund der damaligen Prozessorentechnologie um einige Jahrzehnte zu früh. Schon drei Jahre nach Berrou's Erfindung der Turbocodes 1993 erkannten dann allerdings  David J. C. MacKay  und  Radford M. Neal  das riesige Potential der LDPC–Codes, wenn man diese ebenso wie die Turbocodes iterativ symbolweise decodiert. Sie erfanden die LDPC–Codes quasi neu.

Wie aus dem Namensbestandteil „Parity–check” bereits hervorgeht, handelt es sich bei diesen Codes um lineare Blockcodes entsprechend den Ausführungen im  ersten Hauptkapitel . Deshalb gilt auch hier:

  • Das Codewort ergibt sich aus dem Informationswort  $\underline{u}$  (dargestellt mit  $k$  Binärsymbolen) und der  Generatormatrix  $\mathbf{G}$  der Dimension  $k × n$  zu  $\underline{x} = \underline{u} \cdot \mathbf{G}$   ⇒   Codewortlänge  $n$.
  • Die Prüfgleichungen ergeben sich aus der Identität  $\underline{x} \cdot \mathbf{H}^{\rm T} ≡ 0$, wobei  $\mathbf{H}$  die Prüfmatrix bezeichnet. Diese besteht aus  $m$  Zeilen und  $n$  Spalten. Während im ersten Kapitel grundsätzlich  $m = n -k$  gegolten hat, fordern wir für die LPDC–Codes lediglich noch  $m ≥ n -k$.

Ein gravierender Unterschied zwischen einem LDPC–Code und einem herkömmlichen Blockcode nach der Beschreibung im ersten Kapitel ist, dass die Prüfmatrix  $\mathbf{H}$  nur spärlich mit Einsen besetzt ist  („Low–density”).

$\text{Beispiel 1:}$  Die Grafik zeigt beispielhaft die Prüfmatrizen  $\mathbf{H}$  für

  • den Hamming–Code mit Codelänge  $n = 15, \ m = 4$   ⇒   $k = 11$  Informationsbits,
  • den LDPC–Code aus  [Liv15][2]  der Länge  $n = 12$  und mit  $m = 9$  Prüfgleichungen   ⇒   $k ≥ 3$.

Prüfmatrizen eines Hamming–Codes und eines LDPC–Codes
  • In der linken Grafik beträgt der Anteil der Einsen  $32/60 \approx 53.3\%$, wohingegen in der rechten Grafik der Einsen–Anteil mit  $36/108 = 33.3\%$  geringer ist.
  • Bei den für die Praxis relevanten LDPC–Codes (großer Länge) ist der Einsen–Anteil noch deutlich niedriger.


Wir analysieren nun die beiden Prüfmatrizen anhand der Rate und des Hamming–Gewichts:

  • Die Rate des betrachteten Hamming–Codes (linke Grafik) ist  $R = k/n = 11/15 \approx 0.733$. Das Hamming–Gewicht einer jeden der vier Zeilen ist  $w_{\rm Z}= 8$, während die Hamming–Gewichte  $w_{\rm S}(i)$  der Spalten zwischen 1 und 4 variieren. Für die Spalten–Laufvariable gilt hier:   $1 ≤ i ≤ 15$.
  • Beim betrachteten LDPC–Code gibt es in allen Zeilen vier Einsen   ⇒   $w_{\rm Z} = 4$  und in allen Spalten drei Einsen   ⇒   $w_{\rm S} = 3$. Die Codebezeichnung  $(w_{\rm Z}, \ w_{\rm S})$  LDPC–Code verwendet genau diese Parameter. Beachten Sie die unterschiedliche Nomenklatur zum „$(n, \ k, \ m)$ Hamming–Code”.
  • Man spricht hier von einem  regulären LDPC–Code, da alle Zeilengewichte  $w_{\rm Z}(j)$  für  $1 ≤ j ≤ m$  konstant gleich  $w_{\rm Z}$ sind und auch alle Spaltengewichte $($mit den Indizes  $1 ≤ i ≤ n)$  gleich sind:   $w_{\rm S}(i) = w_{\rm S} = {\rm const.}$ Ist diese Bedingung nicht erfüllt, so liegt ein irregulärer LDPC–Code vor.


$\text{Merkmal der LDPC-Codes}$  Für die Coderate kann man allgemein  (wenn  $k$  nicht bekannt ist)  nur eine Schranke angeben:  

$$R ≥ 1 - w_{\rm S}/w_{\rm Z}.$$
  • Das Gleichheitszeichen gilt dann, wenn alle Zeilen von  $\mathbf{H}$  linear unabhängig sind   ⇒   $m = n \, – k$. Dann ergibt sich die herkömmliche Gleichung:
$$R = 1 - w_{\rm S}/w_{\rm Z} = 1 - m/n = k/n.$$
  • Dagegen gilt für die Coderate eines irregulären LDPC–Codes und auch für den links skizzierten  $(15, 11, 4)$ Hammingcode:
$$R \ge 1 - \frac{ {\rm E}[w_{\rm S}]}{ {\rm E}[w_{\rm Z}]} \hspace{0.5cm}{\rm mit}\hspace{0.5cm} {\rm E}[w_{\rm S}] =\frac{1}{n} \cdot \sum_{i = 1}^{n}w_{\rm S}(i) \hspace{0.5cm}{\rm und}\hspace{0.5cm} {\rm E}[w_{\rm Z}] =\frac{1}{m} \cdot \sum_{j = 1}^{ m}w_{\rm Z}(j) \hspace{0.05cm}.$$
Da beim Hamming–Code  die  $m = n - k$  Prüfgleichungen linear voneinander unabhängig sind, kann das  „$≥$”–Zeichen durch das Gleichheitszeichen ersetzt werden, was gleichzeitig  $R = k/n$  bedeutet.


Weitere Informationen zu diesem Thema finden Sie in  Aufgabe 4.11  und  Aufgabe 4.11Z.

Zweiteilige LDPC–Graphenrepräsentation – Tanner–Graph


Alle wesentlichen Merkmale eines LDPC–Codes sind in der Prüfmatrix  $\mathbf{H} = (h_{j,\hspace{0.05cm}i})$  enthalten und lassen sich durch einen so genannten  Tanner–Graphen  darstellen. Es handelt sich um eine  Bipartite Graph Representation, wobei die deutsche Übersetzung von „bipartite” in etwa „zweiteilig” lautet. Bevor wir beispielhafte Tanner–Graphen genauer betrachten und analysieren, müssen zuerst noch einige geeignete Beschreibungsgrößen definiert werden:

  • Die  $n$  Spalten der Prüfmatrix  $\mathbf{H}$  stehen jeweils für ein Codewortbit. Da jedes Codewortbit sowohl ein Informationsbit als auch ein Prüfbit sein kann, hat sich hierfür die neutrale Bezeichnung  Varibale Node  (VN) durchgesetzt. Das  $i$–te Codewortbit wird  $V_i$  genannt und die Menge aller  Variable Nodes  (VNs) ist $\{V_1, \ \text{...}\hspace{0.05cm} , \ V_i, \ \text{...}\hspace{0.05cm} , \ V_n\}$.
  • Die  $m$  Zeilen von  $\mathbf{H}$  beschreiben jeweils eine Prüfgleichung (englisch:  Parity–check Equation). Wir bezeichnen im folgenden eine solche Prüfgleichung als  Check Node  (CN). Die Menge aller  Check Nodes  (CNs) ist  $\{C_1, \ \text{...}\hspace{0.05cm} , \ C_j, \ \text{...}\hspace{0.05cm} , \ C_m\}$, wobei  $C_j$  die Prüfgleichung der  $j$–ten Zeile angibt.
  • Im Tanner–Graphen werden die  $n$  Variable Nodes  $V_i$  als Kreise und die  $m$  Check Nodes  $C_j$ als Quadrate dargestellt. Ist das Matrixelement in Zeile  $j$  und Spalte  $i \hspace{0.15cm} ⇒ \hspace{0.15cm} h_{j,\hspace{0.05cm}i} = 1$, so gibt es eine Verbindungslinie (englisch:  Edge) zwischen dem Variable Node  $V_i$  und dem Check Node  $C_j$.

Einfaches Beispiel für einen Tanner–Graphen

$\text{Beispiel 2:}$  Zur Verdeutlichung obiger Begriffe ist rechts ein beispielhafter Tannergraphen mit

  • den Variable Nodes  (kurz:  VNs)  $V_1$  bis  $V_4$, und
  • den Check Nodes  (kurz:  CNs)  $C_1$  bis  $C_3$

angegeben. Der zugehörige Code hat allerdings keinerlei praktische Bedeutung.

Man erkennt aus der Grafik:

  • Die Codelänge ist  $n = 4$  und es gibt  $m = 3$  Prüfgleichungen. Damit hat die Prüfmatrix  $\mathbf{H}$  die Dimension  $3×4$.
  • Es gibt insgesamt sechs Verbindungslinien (englisch:  Edges). Damit sind sechs der zwölf Elemente  $h_{j,\hspace{0.05cm}i}$  von  $\mathbf{H}$  Einsen.
  • Bei jedem Check Node  kommen zwei Linien an   ⇒   Die Hamming–Gewichte aller Zeilen gleich sind:   $w_{\rm S}(j) = 2 = w_{\rm S}$.
  • Von den Knoten  $V_1$  und  $V_4$  gibt es jeweils nur einen Übergang zu einem Check Node, von  $V_2$  und  $V_3$  dagegen zwei.
    Aus diesem Grund handelt es sich um einen irregulären Code.

Die Prüfmatrix lautet demnach:

\[{ \boldsymbol{\rm H} } = \begin{pmatrix} 1 &1 &0 &0\\ 0 &1 &1 &0\\ 0 &0 &1 &1 \end{pmatrix}\hspace{0.05cm}.\]


$\text{Beispiel 3:}$  Es folgt nun ein praxisrelevanteres Beispiel. In der  Aufgabe 4.11  wurden zwei Prüfmatrizen analysiert:

  • Der Coder entsprechend der Matrix  $\mathbf{H}_1$  ist systematisch. Die Codeparameter sind  $n = 8, \ k = 4$  und  $m = 4$   ⇒   Rate $1/2$. Der Code ist irregulär, da die Hamming–Gewichte nicht für alle Spalten gleich sind. In der Grafik ist diese „irreguläre  $\mathbf{H}$–Matrix” oben angegeben.
  • Unten angegeben ist die „reguläre  $\mathbf{H}$–Matrix” entsprechend der Matrix  $\mathbf{H}_3$  in Aufgabe 4.11. Die Zeilen sind Linearkombinationen der oberen Matrix. Für diesen nicht systematischen Coder gilt mit  $w_{\rm S} = 2$  und  $w_{\rm Z} = 4$  für die Rate:   $R \ge 1 - w_{\rm S}/w_{\rm Z} = 1/2$.


Tanner–Graph eines regulären und eines irregelären Codes

Die Grafik zeigt die zugehörigen Tanner–Graphen:

  • Der linke Graph bezieht sich auf die obere (irreguläre) Matrix. Die acht Variable Nodes  (abgekürzt VNs)  $V_i$  sind mit den vier Check Nodes  (abgekürzt CNs)  $C_j$  verbunden, falls das Element in Zeile  $j$  und Spalte  $i \hspace{0.15cm} ⇒ \hspace{0.15cm} h_{j,\hspace{0.05cm}i}$  gleich  $1$  ist. Andernfalls  $($falls  $h_{j,\hspace{0.05cm}i} = 0)$  besteht keine Verbindung.
  • Dieser Graph ist für die  iterative symbolweise Decodierung  nicht sonderlich gut geeignet. Die VNs  $V_5, \ \text{...}\hspace{0.05cm} , \ V_8$  sind jeweils nur mit einem CN verbunden, was für die Decodierung keine Information liefert.
  • Im rechten Tanner–Graph für den regulären Code erkennt man, dass hier von jedem Variable Node  $V_i$  zwei Verbindungslinien  (englisch: Edges)  abgehen und von jedem Check Node  $C_j$  deren vier. Damit ist bei der Decodierung in jeder Iterationsschleife ein Informationsgewinn möglich.
  • Man erkennt zudem, dass hier beim Übergang vom irregulären zum äquivalenten regulären Code der Einsen–Anteil zunimmt, im Beispiel von  $37.5\%$  auf $50\%$. Diese Aussage kann allerdings nicht verallgemeinert werden.


Iterative Decodierung von LDPC–Codes


Als Beispiel für die iterative LDPC–Decodierung wird nun der so genannte  Message–passing Algorithm  beschrieben. Wir verdeutlichen diesen anhand des rechten Tanner–Graphen im  $\text{Beispiel 3}$  auf der vorherigen Seite und damit für die dort angegebene reguläre Prüfmatrix.

$\text{Prinzip:}$  Beim  Message–passing Algorithm  erfolgt abwechselnd (oder iterativ) ein Informationsaustausch zwischen den Variable Nodes   (VNs)  $V_1, \ \text{...}\hspace{0.05cm} , \ V_n$  und den Check Nodes   (CNs)  $C_1 , \ \text{...}\hspace{0.05cm} , \ C_m$.


Iterative Decodierung von LDPC–Codes

Für das betrachtete Beispiel gilt:

  • Es gibt  $n = 8$  Variable Nodes und  $m = 4$  Check Nodes . Da ein regulärer LDPC–Code vorliegt, gehen von jedem Variable Node   $d_{\rm V} = 2$  Verbindungslinien zu einem Check Node   und jeder Check Node   ist mit  $d_{\rm C} = 4$  Variable Nodes verbunden.
  • Der Variable Node Degree  $d_{\rm V}$  ist gleich dem Hamming–Gewicht einer jeden Spalte  $(w_{\rm S})$  und für den Check Node Degree  gilt:   $d_{\rm C} = w_{\rm Z}$ (Hamming–Gewicht einer jeden Zeile).
  • In der folgenden Beschreibung verwenden wir auch die Begriffe Nachbarn eines Variable Nodes   ⇒   $N(V_i)$  sowie Nachbarn eines Check Nodes   ⇒   $N(C_j)$, wobei wir uns hier auf implizite Definitionen beschränken:
\[N(V_1) = \{ C_1, C_2\}\hspace{0.05cm}, \hspace{0.3cm}N(V_2) = \{ C_3, C_4\}\hspace{0.05cm}, \hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.15cm},\hspace{0.3cm}N(V_8) = \{ C_1, C_4\}\hspace{0.05cm},\]
\[N(C_1) = \{ V_1, V_4, V_5, V_8\}\hspace{0.05cm}, \hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.05cm}.\hspace{0.15cm}\hspace{0.05cm}, \hspace{0.3cm}N(C_4) = \{ V_2, V_3, V_6, V_8\}\hspace{0.05cm}.\]
Informationsaustausch zwischen Variable Nodes  und Check Nodes

$\text{Beispiel 4:}$  Die Skizze aus  [Liv15][2]  zeigt den Austausch von Information zwischen dem Variable Node  $V_i$  und dem Check Node  $C_j$  – ausgedrückt durch  Log–Likelihood Ratios  (kurz: $L$–Werte).

Der Informationsaustausch geschieht in zwei Richtungen:

  • $L(V_i → C_j)$:  Extrinsische Information aus  $V_i$–Sicht,  Apriori–Information aus  $C_j$–Sicht.
  • $L(C_j → V_i)$:  Extrinsische Information aus  $C_j$–Sicht,  Apriori–Information aus  $V_i$–Sicht.


Die Beschreibung des Decodieralgorithmus wird fortgesetzt:

Initialisierung:  Zu Beginn der Decodierung erhalten die Variable Nodes  (VNs) keine Apriori–Information von den Check Nodes  (CNs), und es gilt für  $1 ≤ i ≤ n \text{:}$  

$$L(V_i → C_j) = L_{\rm K}(V_i).$$

Wie aus der Grafik am Seitenbeginn ersichtlich, ergeben sich diese Kanal–$L$–Werte  $L_{\rm K}(V_i)$  aus den Empfangswerten  $y_i$.

Check Node Decoder:  Jeder Knoten  $C_j$  repräsentiert eine Prüfgleichung. So steht  $C_1$  für die Gleichung  $V_1 + V_4 + V_5 + V_8 = 0$. Man erkennt den Zusammenhang zur extrinsischen Information bei der symbolweisen Decodierung des Single Parity–check Codes.

In Analogie zur Seite  Zur Berechnung der extrinsischen L–Werte  und zur  Aufgabe 4.4  gilt somit für den extrinsischen  $L$–Wert von  $C_j$  und gleichzeitig für die Apriori–Information bezüglich  $V_i$:

\[L(C_j \rightarrow V_i) = 2 \cdot {\rm tanh}^{-1}\left [ \prod\limits_{V \in N(C_j)\hspace{0.05cm},\hspace{0.1cm} V \ne V_i} \hspace{-0.35cm}{\rm tanh}\left [L(V \rightarrow C_j \right ] /2) \right ] \hspace{0.05cm}.\]


Variable Node Decoder:  Im Gegensatz zum Check Node Decoder  (CND) besteht beim Variable Node Decoder  (VND) eine Verwandtschaft zur Decodierung eines Repetition Codes, weil alle mit  $V_i$  verbundenen Check Nodes  $C_j$  demselben Bit entsprechen   ⇒   dieses Bit wird quasi  $d_{\rm V}$  mal wiederholt.

In Analogie zu zur Seite  Zur Berechnung der extrinsischen L–Werte  gilt für den extrinsischen  $L$–Wert von  $V_i$  und gleichzeitig für die Apriori–Information bezüglich  $C_j$:

\[L(V_i \rightarrow C_j) = L_{\rm K}(V_i) + \hspace{-0.55cm} \sum\limits_{C \hspace{0.05cm}\in\hspace{0.05cm} N(V_i)\hspace{0.05cm},\hspace{0.1cm} C \hspace{0.05cm}\ne\hspace{0.05cm} C_j} \hspace{-0.55cm}L(C \rightarrow V_i) \hspace{0.05cm}.\]

Das folgende Schaubild des beschriebenen Decodieralgorithmus' für LDPC–Codes zeigt Ähnlichkeiten mit der Vorgehensweise bei  seriell verketteten Turbocodes.

Zusammenhang zwischen LDPC–Decodierung und serieller Turbo–Decodierung
  • Um eine vollständige Analogie zwischen der LDPC– und der Turbodecodierung herzustellen, ist auch hier zwischen dem Variable Node Decoder  (VND) und dem Check Node Decoder  (CND) ein „Interleaver ”  sowie ein „De–Interleaver ”  eingezeichnet.
  • Da es sich hierbei nicht um reale Systemkomponenten handelt, sondern nur um Analogien, haben wir diese Begriffe in Hochkommata gesetzt.


Leistungsfähigkeit regulärer LDPC–Codes


Bitfehlerrate von LDPC–Codes

Wir betrachten nun wie in  [Str14][3]  fünf reguläre LDPC–Codes. Die Grafik zeigt die Bitfehlerrate  $\rm (BER)$  abhängig vom AWGN–Parameter  $10 \cdot {\rm lg} \, E_{\rm B}/N_0$. Zum Vergleich ist auch die Kurve für uncodierte Übertragung eingezeichnet.

Diese LDPC–Codes zeigen folgende Eigenschaften:

  • Die Prüfmatrizen  $\mathbf{H}$  weisen jeweils  $n$  Spalten und  $m = n/2$  linear voneinander unabhängige Zeilen auf. In jeder Zeile gibt es  $w_{\rm Z} = 6$  Einsen und in jeder Spalte  $w_{\rm S} = 3$  Einsen.
  • Der Einsen–Anteil beträgt  $w_{\rm Z}/n = w_{\rm S}/m$, so dass bei großer Codewortlänge  $n$  die Klassifizierung „Low–density” gerechtfertigt ist. Für die rote Kurve  $(n = 2^{10})$  beträgt der Einsen–Anteil  $0.6\%$.
  • Die Rate aller Codes beträgt  $R = 1 - w_{\rm S}/w_{\rm Z} = 1/2$. Wegen der linearen Unabhängigkeit der Matrixzeilen gilt aber auch  $R = k/n$  mit der Informationswortlänge  $k = n - m = n/2$.

Aus der Grafik erkennt man:

  • Die Bitfehlerrate ist um so kleiner, je länger der Code ist:
  • Für  $10 \cdot {\rm lg} \, E_{\rm B}/N_0 = 2 \ \rm dB$  und  $n = 2^8 = 256$  ergibt sich  ${\rm BER} \approx 10^{-2}$.
  • Für  $n = 2^{12} = 4096$  dagegen nur  ${\rm BER} \approx 2 \cdot 10^{-7}$.
  • Mit  $n = 2^{15} = 32768$  (violette Kurve) benötigt man  $10 \cdot {\rm lg} \, E_{\rm B}/N_0 \approx 1.35 \ \rm dB$  für  ${\rm BER} = 10^{-5}$.
  • Der Abstand von der Shannon–Grenze  $(0.18 \ \rm dB$  für  $R = 1/2$  und BPSK$)$ beträgt ca.  $1.2 \ \rm dB$.


„Waterfall Region & Error Floor”

Die Kurven für  $n = 2^8$  bis  $n = 2^{10}$  weisen zudem auf einen Effekt hin, den wir schon bei den  Turbocodes  festgestellt haben:

  • Zuerst fällt die BER–Kurve steil ab   ⇒   „Waterfall Region”.
  • Danach folgt ein Knick und ein Verlauf mit deutlich geringerer Steigung   ⇒   „Error Floor”.
  • Die qualitative untere Grafik verdeutlicht den Effekt, der natürlich nicht abrupt einsetzt (Übergang nicht eingezeichnet).


Ein (LDPC–) Code ist immer dann als gut zu bezeichnen, wenn

  • die BER–Kurve nahe der Shannon–Grenze steil abfällt,
  • der „Error Floor” bei sehr niedrigen BER–Werten liegt (Ursachen hierfür siehe nächste Seite,  $\text{Beispiel 5)}$,
  • die Anzahl der erforderlichen Iterationen handhabbar ist, und
  • diese Eigenschaften nicht erst bei nicht mehr praktikablen Blocklängen erreicht werden.


Leistungsfähigkeit irregulärer LDPC–Codes


LDPC–Codes im Vergleich zur Shannon–Grenze

In diesem Kapitel wurden vorwiegend reguläre LDPC–Codes behandelt, auch im  $\rm BER$–Diagramm auf der letzten Seite. Die Ignoranz der irregulären LDPC–Codes ist nur der Kürze dieses Kapitels geschuldet, nicht deren Leistungsfähigkeit. Im Gegenteil:

  • Irreguläre LDPC–Codes gehören zu den besten Kanalcodes überhaupt.
  • Das gelbe Kreuz in der Grafik liegt praktisch auf der informationstheoretischen Grenzkurve für binäre Eingangssignale (grüne Kurve, mit  $\rm BPSK$ beschriftet).
  • Die Codewortlänge dieses irregulären Rate–$1/2$–Codes von [CFRU01][4] beträgt  $n = 2 \cdot 10^6$.
  • Daraus ist schon ersichtlich, dass dieser Code nicht für den praktischen Einsatz gedacht war, sondern sogar für einen Rekordversuch getunt wurde.


Bei der LDPC–Codekonstruktion geht man ja stets von der Prüfmatrix  $\mathbf{H}$  aus. Für den gerade genannten Code hat diese die Dimension  $1 \cdot 10^6 × 2 \cdot 10^6$, beinhaltet also  $2 \cdot 10^{12}$  Matrixelemente.

$\text{Fazit:}$  Füllt man die Matrix per Zufallsgenerator mit (wenigen) Einsen   ⇒   „Low–density”, so spricht man von  unstrukturiertem Code–Design. Dies kann zu langen Codes mit guter Performance führen, manchmal aber auch zu folgenden Problemen:

  • Die Komplexität des Coders kann zunehmen, da trotz Modifikation der Prüfmatrix  $\mathbf{H}$  sichergestellt werden muss, dass die Generatormatrix  $\mathbf{G}$  systematisch ist.
  • Es erfordert eine aufwändige Hardware–Realisierung des iterativen Decoders.
  • Es kommt zu einem „Error Floor” durch einzelne Einsen in einer Spalte (oder Zeile) sowie durch kurze Schleifen   ⇒   siehe nachfolgendes Beispiel.



$\text{Beispiel 5:}$  Im linken Teil der Grafik ist der Tanner–Graph für einen regulären LDPC–Code mit der Prüfmatrix  $\mathbf{H}_1$  dargestellt. Grün eingezeichnet ist ein Beispiel für die minimale Schleifenlänge (englisch:  Girth). Diese Kenngröße gibt an, wieviele Kanten man mindestens durchläuft, bis man von einem Check Node  $C_j$  wieder bei diesem landet $($oder von  $V_i$  zu  $V_i)$. Im linken Beispiel ergibt sich die minimale Kantenlänge  $6$, zum Beispiel der Weg  $C_1 → V_1 → C_3 → V_5 → C_2 → V_2 → C_1$.

Zur Definition eines „Girth”

Vertauscht man in der Prüfmatrix nur zwei Einsen   ⇒   Matrix  $\mathbf{H}_2$, so wird der LDPC–Code irregulär:

  • Die minimale Schleifenlänge ist nun  $4$, von  $C_1 → V_4 → C_4 → V_6 → C_1$.
  • Ein kleiner Girth  führt zu einem ausgeprägten „Error Floor” im BER–Verlauf.


Einige Anwendungsgebiete für LDPC–Codes


Einige standardisierte LDPC–Codes im Vergleich zur Shannon–Grenze

Im nebenstehenden Schaubild sind im Vergleich zur AWGN–Kanalkapazität zwei Kommunikations–Standards eingetragen, die auf strukturierten (regulären) LDPC–Codes basieren.

Anzumerken ist, dass für die eingezeichneten standardisierten Codes die Bitfehlerrate ${\rm BER}=10^{-5}$ zugrunde liegt, während die Kapazitätskurven (entsprechend der Informationstheorie) für die Fehlerwahrscheinlichkeit „Null” gelten.

Rote Kreuze zeigen die  LDPC–Codes nach CCSDS  (Consultative Comittee for Space Data Systems), entwickelt für ferne Weltraummissionen:

  • Diese Klasse stellt Codes der Rate  $1/3$,  $1/2$,  $2/3$  und  $4/5$ bereit.
  • Alle Punkte liegen ca.  $1 \ \rm dB$  rechts von der Kapazitätskurve für binären Eingang (grüne Kurve „BPSK”).


Die blauen Rechtecke markieren die  LDPC–Codes für DVB–T2/S2. Die Abkürzungen stehen für „Digital Video Broadcasting – Terrestrial” bzw. „Digital Video Broadcasting – Satellite”, und die Kennzeichnung „$2$” macht deutlich, dass es sich jeweils um die zweite Generation (von 2005 bzw. 2009) handelt.

  • Der Standard ist durch  $22$  Prüfmatrizen definiert, die Raten von etwa  $0.2$  bis zu  $19/20$  zur Verfügung stellen.
  • Je elf Varianten gelten für die Codelänge  $64800$  Bit (Normal FECFRAME) bzw.  $16200$  Bit (Short FECFRAME).
  • Kombiniert mit  Modulationsverfahren hoher Ordnung  (8PSK, 16–ASK/PSK, ... ) zeichnen sich die Codes durch eine große spektrale Effizienz aus.


Die DVB–Codes gehören zu den  Irregular Repeat Accumulate  $\rm (IRA)$ Codes, die erstmals im Jahr 2000 in  [JKE00][5]  vorgestellt wurden.

IRA–Coder bei DVB–S2/T2

Die Grafik zeigt die Grundstruktur des Coders.

  • Der grün hinterlegte Teil – mit Repetition Code  $\rm (RC)$, Interleaver, Single Parity–Code  $\rm (SPC)$  sowie Akkumulator – entspricht exakt einem seriell–verketteten Turbocode   ⇒   siehe  RA–Coder.
  • Die Beschreibung des IRA–Codes basiert aber allein auf der Prüfmatrix  $\mathbf{H}$, die sich durch den  irregulären Repetition Code  in eine für die Decodierung günstige Form bringen lässt.
  • Als äußerer Code wird zudem ein hochratiger BCH–Code (von $\rm B$ose–$\rm C$haudhuri–$\rm H$ocquenghem) verwendet, der den  Error Floor  herabsetzen soll.


In der Grafik am Seitenanfang nicht eingetragen sind

  • die LDPC–Codes für den Standard  DVB Return Channel Terrestrial (RCS),
  • die LDPC–Codes für den WiMax–Standard  (IEEE 802.16), sowie
  • die LDPC–Codes für das  10GBASE–T–Ethernet,


die gewisse Ähnlichkeiten mit den IRA–Codes aufweisen.

Aufgaben zum Kapitel


Aufgabe 4.11: Analyse von Prüfmatrizen

Zusatzaufgabe 4.11Z: Coderate aus der Prüfmatrix

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

Aufgabe 4.13: Decodierung von LDPC–Codes

Quellenverzeichnis

  1. Gallager, R. G.: Low–density Parity–check Codes. MIT Press, Cambridge, MA, 1963.
  2. 2,0 2,1 Liva, G.: Channels Codes for Iterative Decoding. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.
  3. Strutz, T.: Low–density Parity–check Codes – Eine Einführung. Vorlesungsmaterial. Hochschule für Telekommunikation, Leipzig, 2014. PDF-Dokument PDF-Dokument.
  4. Chung S.Y; Forney Jr., G.D.; Richardson, T.J.; Urbanke, R.: On the Design of Low-Density Parity- Check Codes within 0.0045 dB of the Shannon Limit. – In: IEEE Communications Letters, vol. 5, no. 2 (2001), pp. 58–60.
  5. Jin, H.; Khandekar, A.; McEliece, R.: Irregular Repeat–Accumulate Codes. Proc. of the 2nd Int. Symp. on Turbo Codes and Related Topics, Best, France, S. 1–8., Sept. 2000.