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

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 13: Zeile 13:
  
 
Wie aus dem Namensbestandteil „Parity–check” bereits hervorgeht, handelt es sich bei diesen Codes um lineare Blockcodes entsprechend den Ausführungen in Kapitel 1. Deshalb gilt auch hier:
 
Wie aus dem Namensbestandteil „Parity–check” bereits hervorgeht, handelt es sich bei diesen Codes um lineare Blockcodes entsprechend den Ausführungen in Kapitel 1. Deshalb gilt auch hier:
*Das Codewort ergibt sich aus dem Informationswort <u><i>u</i></u> (dargestellt mit <i>k</i> Binärsymbolen) und der Generatormatrix <b>G</b> der Dimension <i>k</i>&times;<i>n</i> zu <u><i>x</i></u> = <u><i>u</i></u> &middot; <b>G</b> &nbsp;&#8658;&nbsp; Codewortlänge <i>n</i>.<br>
+
*Das Codewort ergibt sich aus dem Informationswort <u><i>u</i></u> (dargestellt mit <i>k</i> Binärsymbolen) und der [http://www.lntwww.de/Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix Generatormatrix] <b>G</b> der Dimension <i>k</i>&times;<i>n</i> zu <u><i>x</i></u> = <u><i>u</i></u> &middot; <b>G</b> &nbsp;&#8658;&nbsp; Codewortlänge <i>n</i>.<br>
  
 
*Die Prüfgleichungen ergeben sich aus der Identität <u><i>x</i></u> &middot; <b>H</b><sup>T</sup> &equiv; 0, wobei <b>H</b> die Prüfmatrix bezeichnet. Diese besteht aus <i>m</i> Zeilen und <i>n</i> Spalten. Während im ersten Kapitel grundsätzlich <i>m</i> = <i>n</i> &ndash; <i>k</i> gegolten hat, fordern wir für die LPDC&ndash;Codes lediglich noch <i>m</i> &#8805; <i>n</i> &ndash; <i>k</i>.<br><br>
 
*Die Prüfgleichungen ergeben sich aus der Identität <u><i>x</i></u> &middot; <b>H</b><sup>T</sup> &equiv; 0, wobei <b>H</b> die Prüfmatrix bezeichnet. Diese besteht aus <i>m</i> Zeilen und <i>n</i> Spalten. Während im ersten Kapitel grundsätzlich <i>m</i> = <i>n</i> &ndash; <i>k</i> gegolten hat, fordern wir für die LPDC&ndash;Codes lediglich noch <i>m</i> &#8805; <i>n</i> &ndash; <i>k</i>.<br><br>
Zeile 108: Zeile 108:
 
*Der linke Graph bezieht sich auf die irreguläre Matrix. Die acht <i>Variable Nodes</i> (abgekürzt VNs) <i>V<sub>i</sub></i> sind mit den vier <i>Check Nodes</i> (abgekürzt CNs) <i>C<sub>j</sub></i> verbunden, falls das Element in Zeile <i>j</i> und Spalte <i>i</i> &nbsp;&#8658;&nbsp; <i>h<sub>j,i</sub></i> gleich 1 ist. Andernfalls  (falls <i>h<sub>j,i</sub></i> = 0) besteht keine Verbindung.<br>
 
*Der linke Graph bezieht sich auf die irreguläre Matrix. Die acht <i>Variable Nodes</i> (abgekürzt VNs) <i>V<sub>i</sub></i> sind mit den vier <i>Check Nodes</i> (abgekürzt CNs) <i>C<sub>j</sub></i> verbunden, falls das Element in Zeile <i>j</i> und Spalte <i>i</i> &nbsp;&#8658;&nbsp; <i>h<sub>j,i</sub></i> gleich 1 ist. Andernfalls  (falls <i>h<sub>j,i</sub></i> = 0) besteht keine Verbindung.<br>
  
*Der links dargestellte  Graph ist für die iterative symbolweise Decodierung nicht sonderlich gut geeignet. Die VNs <i>V</i><sub>5</sub>, ...., <i>V</i><sub>8</sub> sind jeweils nur mit einem CN verbunden, was für die Decodierung keinerlei Information liefert.<br>
+
*Der links dargestellte  Graph ist für die [http://www.lntwww.de/Kanalcodierung/Grundlegendes_zu_den_Low%E2%80%93density_Parity%E2%80%93check_Codes#Iterative_Decodierung_von_LDPC.E2.80.93Codes_.281.29 iterative symbolweise Decodierung] nicht sonderlich gut geeignet. Die VNs <i>V</i><sub>5</sub>, ...., <i>V</i><sub>8</sub> sind jeweils nur mit einem CN verbunden, was für die Decodierung keinerlei Information liefert.<br>
  
 
*Im rechten Tanner&ndash;Graph für den regulären Code erkennt man, dass hier von jedem VN <i>V<sub>i</sub></i> zwei Verbindungslinien (englisch: <i>Edges</i>) abgehen und von jedem CN <i>C<sub>j</sub></i> 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 VN <i>V<sub>i</sub></i> zwei Verbindungslinien (englisch: <i>Edges</i>) abgehen und von jedem CN <i>C<sub>j</sub></i> deren vier. Damit ist bei der Decodierung  in jeder Iterationsschleife ein Informationsgewinn möglich.<br>
Zeile 116: Zeile 116:
 
== Iterative Decodierung von LDPC–Codes (1) ==
 
== Iterative Decodierung von LDPC–Codes (1) ==
 
<br>
 
<br>
Als Beispiel für die iterative LDPC&ndash;Decodierung wird nun der sog. <b>Message&ndash;passing Algorithm</b> beschrieben. Wir verdeutlichen diesen anhand des rechten Tanner&ndash;Graphen 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 sog. <b>Message&ndash;passing Algorithm</b> beschrieben. Wir verdeutlichen diesen anhand des rechten Tanner&ndash;Graphen auf der [http://www.lntwww.de/Kanalcodierung/Grundlegendes_zu_den_Low%E2%80%93density_Parity%E2%80%93check_Codes#Zweiteilige_LDPC.E2.80.93Graphenrepr.C3.A4sentation_.E2.80.93_Tanner.E2.80.93Graph_.282.29 vorherigen Seite] und damit für die dort angegebene reguläre Prüfmatrix.<br>
  
 
Bei diesem Decodieralgorithmus  erfolgt abwechselnd (oder iterativ) ein Informationsaustausch zwischen den <i>Variable Nodes </i> (VNs) <i>V</i><sub>1</sub>, ... , <i>V<sub>n</sub></i> und den <i>Check Nodes </i> (CNs) <i>C</i><sub>1</sub>, ... , <i>C<sub>m</sub></i>.<br>
 
Bei diesem Decodieralgorithmus  erfolgt abwechselnd (oder iterativ) ein Informationsaustausch zwischen den <i>Variable Nodes </i> (VNs) <i>V</i><sub>1</sub>, ... , <i>V<sub>n</sub></i> und den <i>Check Nodes </i> (CNs) <i>C</i><sub>1</sub>, ... , <i>C<sub>m</sub></i>.<br>
Zeile 134: Zeile 134:
 
[[Datei:P ID3085 KC T 4 4 S3c v2.png|rahmenlos|rechts|Informationsaustausch zwischen VNs und CNs]]
 
[[Datei:P ID3085 KC T 4 4 S3c v2.png|rahmenlos|rechts|Informationsaustausch zwischen VNs und CNs]]
  
Die Skizze aus [Liv15]<ref>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> <i>V<sub>i</sub></i> und dem <i>Check Node</i>  <i>C<sub>j</sub></i> &ndash; ausgedrückt durch Log&ndash;Likelihood Ratios (kurz: <i>L</i>&ndash;Werte). Der Informationsaustausch geschieht in zwei Richtungen:
+
Die Skizze aus [Liv15]<ref>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> <i>V<sub>i</sub></i> und dem <i>Check Node</i>  <i>C<sub>j</sub></i> &ndash; ausgedrückt durch [http://www.lntwww.de/Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Zuverl.C3.A4ssigkeitsinformation_.E2.80.93_Log_Likelihood_Ratio_.281.29 Log&ndash;Likelihood Ratios] (kurz: <i>L</i>&ndash;Werte). Der Informationsaustausch geschieht in zwei Richtungen:
 
*<b><i>L</i>(<i>V<sub>i</sub></i> &#8594; <i>C<sub>j</sub></i>)</b>: Extrinsische Information aus Sicht von <i>V<sub>i</sub></i>, Apriori&ndash;Information  aus Sicht von <i>C<sub>j</sub></i>.<br>
 
*<b><i>L</i>(<i>V<sub>i</sub></i> &#8594; <i>C<sub>j</sub></i>)</b>: Extrinsische Information aus Sicht von <i>V<sub>i</sub></i>, Apriori&ndash;Information  aus Sicht von <i>C<sub>j</sub></i>.<br>
  
Zeile 143: Zeile 143:
 
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>i</i> &#8804; <i>n</i>: <i>L</i>(<i>V<sub>i</sub></i> &#8594; <i>C<sub>j</sub></i>) =  <i>L</i><sub>K</sub>(<i>V<sub>i</sub></i>). Wie aus der letzten Grafik ersichtlich, ergeben sich diese Kanal&ndash;<i>L</i>&ndash;Werte <i>L</i><sub>K</sub>(<i>V<sub>i</sub></i>) aus den Empfangswerten <i>y<sub>i</sub></i>.<br><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>i</i> &#8804; <i>n</i>: <i>L</i>(<i>V<sub>i</sub></i> &#8594; <i>C<sub>j</sub></i>) =  <i>L</i><sub>K</sub>(<i>V<sub>i</sub></i>). Wie aus der letzten [http://www.lntwww.de/Kanalcodierung/Grundlegendes_zu_den_Low%E2%80%93density_Parity%E2%80%93check_Codes#Iterative_Decodierung_von_LDPC.E2.80.93Codes_.281.29 Grafik] ersichtlich, ergeben sich diese Kanal&ndash;<i>L</i>&ndash;Werte <i>L</i><sub>K</sub>(<i>V<sub>i</sub></i>) aus den Empfangswerten <i>y<sub>i</sub></i>.<br><br>
  
<b>Check Node Decoder</b>: Jeder Knoten <i>C<sub>j</sub></i> repräsentiert eine Prüfgleichung. So steht <i>C</i><sub>1</sub> für &bdquo;<i>V</i><sub>1</sub> + <i>V</i><sub>4</sub> + <i>V</i><sub>5</sub> + <i>V</i><sub>8</sub> = 0&rdquo;.  Man erkennt den Zusammenhang zur extrinsischen Information bei der symbolweisen Decodierung des <i>Single Parity&ndash;check Codes</i>. In Analogie zu Kapitel 4.1 und Aufgabe A4.4 gilt somit  für den extrinsischen <i>L</i>&ndash;Wert von <i>C<sub>j</sub></i> und gleichzeitig für die Apriori&ndash;Information bezüglich <i>V<sub>i</sub></i>:
+
<b>Check Node Decoder</b>: Jeder Knoten <i>C<sub>j</sub></i> repräsentiert eine Prüfgleichung. So steht <i>C</i><sub>1</sub> für &bdquo;<i>V</i><sub>1</sub> + <i>V</i><sub>4</sub> + <i>V</i><sub>5</sub> + <i>V</i><sub>8</sub> = 0&rdquo;.  Man erkennt den Zusammenhang zur extrinsischen Information bei der symbolweisen Decodierung des <i>Single Parity&ndash;check Codes</i>. In Analogie zu [http://www.lntwww.de/Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Zur_Berechnung_der_extrinsischen_L.E2.80.93Werte_.282.29 Kapitel 4.1] und Aufgabe A4.4 gilt somit  für den extrinsischen <i>L</i>&ndash;Wert von <i>C<sub>j</sub></i> und gleichzeitig für die Apriori&ndash;Information bezüglich <i>V<sub>i</sub></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 ]
Zeile 152: Zeile 152:
 
<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 <i>V<sub>i</sub></i> verbundenen <i>Check Nodes</i> <i>C<sub>j</sub></i> demselben Bit  entsprechen &nbsp;&#8658;&nbsp; dieses Bit wird quasi  <i>d</i><sub>V</sub> mal wiederholt.<br>
 
<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 <i>V<sub>i</sub></i> verbundenen <i>Check Nodes</i> <i>C<sub>j</sub></i> demselben Bit  entsprechen &nbsp;&#8658;&nbsp; dieses Bit wird quasi  <i>d</i><sub>V</sub> mal wiederholt.<br>
  
In Analogie zu Kapitel 4.1 gilt für den extrinsischen <i>L</i>&ndash;Wert von  <i>V<sub>i</sub></i> und gleichzeitig für die Apriori&ndash;Information bezüglich <i>C<sub>j</sub></i>:
+
In Analogie zu [http://www.lntwww.de/Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Zur_Berechnung_der_extrinsischen_L.E2.80.93Werte_.281.29 Kapitel 4.1] gilt für den extrinsischen <i>L</i>&ndash;Wert von  <i>V<sub>i</sub></i> und gleichzeitig für die Apriori&ndash;Information bezüglich <i>C<sub>j</sub></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)  
 
:<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 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. Da es sich hierbei nicht um reale Systemkomponenten handelt, sondern nur um Analogien, haben wir diese Begriffe in Hochkommata gesetzt.<br>
+
Das folgende Schaubild des beschriebenen Decodieralgorithmus' für LDPC&ndash;Codes zeigt Ähnlichkeiten mit der Vorgehensweise bei [http://www.lntwww.de/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. 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|Zusammenhang zwischen  LDPC– und serieller Turbo–Decodierung|class=fit]]<br>
 
[[Datei:P ID3078 KC T 4 4 S3b v3.png|Zusammenhang zwischen  LDPC– und serieller Turbo–Decodierung|class=fit]]<br>
Zeile 182: Zeile 182:
  
 
<br><br><br><br><br>
 
<br><br><br><br><br>
Die Kurven für <i>n</i> = 2<sup>8</sup> bis <i>n</i> = 2<sup>10</sup> weisen zudem auf einen Effekt hin, den wir schon bei den Turbocodes 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 links verdeutlicht den Effekt, der natürlich nicht abrupt einsetzt (Übergang nicht eingezeichnet).<br>
+
Die Kurven für <i>n</i> = 2<sup>8</sup> bis <i>n</i> = 2<sup>10</sup> weisen zudem auf einen Effekt hin, den wir schon bei den [http://www.lntwww.de/Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Leistungsf.C3.A4higkeit_der_Turbocodes_.281.29 Turbocodes] 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 links 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
Zeile 224: Zeile 224:
  
 
*Die blauen Rechtecke markieren die LDPC&ndash;Codes für DVB&ndash;T2/S2. Die  
 
*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; Satellite&rdquo; bzw. &bdquo;Digital Video Broadcasting &ndash; Terrestrial&rdquo;, und die &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. Je elf Varianten gelten für die  Codelänge 64800 Bit (<i>Normal FECFRAME</i>) bzw. 16200 Bit (<i>Short FECFRAME</i>). Kombiniert mit Modulationsverfahren hoher Ordnung (8PSK, 16&ndash;ASK/PSK, ...) zeichnen sich die Codes durch große spektrale Effizienz aus.<br>
+
Abkürzungen stehen für  &bdquo;Digital Video Broadcasting &ndash; Satellite&rdquo; bzw. &bdquo;Digital Video Broadcasting &ndash; Terrestrial&rdquo;, und die &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. Je elf Varianten gelten für die  Codelänge 64800 Bit (<i>Normal FECFRAME</i>) bzw. 16200 Bit (<i>Short FECFRAME</i>). Kombiniert mit [http://www.lntwww.de/Modulationsverfahren/Quadratur%E2%80%93Amplitudenmodulation#Weitere_Signalraumkonstellationen Modulationsverfahren hoher Ordnung] (8PSK, 16&ndash;ASK/PSK, ...) zeichnen sich die Codes durch große spektrale Effizienz aus.<br>
  
 
[[Datei:P ID3082 KC T 4 4 S6a v3.png|IRA–Coder bei DVB–S2/T2|class=fit]]<br>
 
[[Datei:P ID3082 KC T 4 4 S6a v3.png|IRA–Coder bei DVB–S2/T2|class=fit]]<br>
  
DVB&ndash;Codes gehören zu den <i>Irregular Repeat Accumulate</i> (IRA) Codes die erstmals im Jahr 2000 in [JKE00]<ref>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 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 RA&ndash;Coder. Die Beschreibung des IRA&ndash;Codes basiert aber allein auf der Prüfmatrix <b>H</b>, die sich durch den <i>irregulären Repetition Code</i> in eine für die Decodierung günstige Form bringen lässt.  Als äußerer Code wird zudem ein hochratiger BCH&ndash;Code (von <i>Bose&ndash;Chaudhuri&ndash;Hocquenghem</i>) verwendet, der den <i>Error Floor</i> herabsetzen soll.<br>
+
DVB&ndash;Codes gehören zu den <i>Irregular Repeat Accumulate</i> (IRA) Codes die erstmals im Jahr 2000 in [JKE00]<ref>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 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 [http://www.lntwww.de/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 <b>H</b>, die sich durch den <i>irregulären Repetition Code</i> in eine für die Decodierung günstige Form bringen lässt.  Als äußerer Code wird zudem ein hochratiger BCH&ndash;Code (von <i>Bose&ndash;Chaudhuri&ndash;Hocquenghem</i>) verwendet, der den <i>Error Floor</i> herabsetzen soll.<br>
  
 
In der oberen Grafik nicht eingetragen sind die LDPC&ndash;Codes für den Standard <i>DVB Return Channel Terrestrial</i> (RCS), für den WiMax&ndash;Standard (IEEE 802.16) sowie für das 10GBASE&ndash;T&ndash;Ethernet,  die gewisse Ähnlichkeiten mit den IRA&ndash;Codes aufweisen.<br>
 
In der oberen Grafik nicht eingetragen sind die LDPC&ndash;Codes für den Standard <i>DVB Return Channel Terrestrial</i> (RCS), für den WiMax&ndash;Standard (IEEE 802.16) sowie für das 10GBASE&ndash;T&ndash;Ethernet,  die gewisse Ähnlichkeiten mit den IRA&ndash;Codes aufweisen.<br>

Version vom 24. Januar 2017, 23:27 Uhr



Einige Charakteristika der LDPC–Codes (1)


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 in Kapitel 1. Deshalb gilt auch hier:

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

Ein gravierender Unterschied zwischen einem LDPC–Code und einem herkömmlichen Blockcode nach der Beschreibung im ersten Kapitel ist, dass die Prüfmatrix H nur spärlich mit Einsen besetzt ist.

: Die Grafik zeigt beispielhaft die Prüfmatrizen 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 ≈ 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.

Hinweis: Auf der nächsten Seite wird auf diese Grafik noch mehrmals Bezug genommen.


Einige Charakteristika der LDPC–Codes (2)


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

Prüfmatrizen eines Hamming–Codes und eines LDPC–Codes

  • Die Rate des betrachteten Hamming–Codes (linke Grafik) ist R = k/n = 11/15 ≈ 0.733. Das Hamming–Gewicht einer jeden der vier Zeilen ist wZ = 8, während die Hamming–Gewichte wS(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  ⇒  wZ = 4 und in allen Spalten drei Einsen ⇒ wS = 3. Die Codebezeichnung (wZ, wS) 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 wZ(j) für 1 ≤ jm konstant gleich wZ sind und auch alle Spaltengewichte (mit den Indizes 1 ≤ in) gleich sind: wS(i) = wS = const. Ist diese Bedingung nicht erfüllt, so liegt ein irregulärer LDPC–Code vor.
  • Für die Coderate kann man allgemein (also, wenn k nicht bekannt ist) nur eine Schranke angeben: R ≥ 1 – wS/wZ. Das Gleichheitszeichen gilt dann, wenn alle Zeilen von H linear unabhängig sind  ⇒  m = nk. Dann ergibt sich die herkömmliche Gleichung: R = 1 – wS/wZ = 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 = nk 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 A4.11 und in Aufgabe Z4.11

Zweiteilige LDPC–Graphenrepräsentation – Tanner–Graph (1)


Alle wesentlichen Merkmale eines LDPC–Codes sind in der Prüfmatrix H = (hj,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 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 Vi genannt und die Menge aller Variable Nodes (VNs) ist {V1, ..., Vi, ..., Vn}.
  • Die m Zeilen von 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 {C1, ..., Cj, ..., Cm}, wobei Cj die Prüfgleichung der j–ten Zeile angibt.
  • Im Tanner–Graphen werden die n Variable Nodes Vi als Kreise und die m Check Nodes Cj als Quadrate dargestellt. Ist das Matrixelement in Zeile j und Spalte ihj,i = 1, so gibt es eine Verbindungslinie (englisch: Edge) zwischen dem Variable Node Vi und dem Check Node Cj.

:
Einfaches Beispiel für einen Tanner–Graphen
Sie sehen rechts einen beispielhaften Tannergraphen zur Verdeutlichung obiger Begriffe mit
  • den Variable Nodes (kurz: VNs) V1 bis V4, und
  • den Check Nodes (kurz: CNs) C1 bis C3.

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 H die Dimension 3×4.
  • Es gibt insgesamt sechs Verbindungslinien (englisch: Edges). Damit sind sechs der zwölf Elemente hj,i von H Einsen.
  • Bei jedem Check Node kommen zwei Linien an. Das bedeutet, dass die Hamming–Gewichte aller Zeilen gleich sind: wS(j) = 2 = wS.
  • Von den Knoten V1 und V4 gibt es jeweils nur einen Übergang zu einem Check Node, von V2 und V3 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}.\]


Auf der nächsten Seite folgt ein praxisrelevanteres Beispiel.

Zweiteilige LDPC–Graphenrepräsentation – Tanner–Graph (2)


: In Aufgabe A4.11 wurden zwei Prüfmatrizen analysiert:
  • Der Coder entsprechend der Matrix H1 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 folgenden Grafik ist diese „irreguläre H–Matrix” oben angegeben.
  • Unten angegeben ist die „reguläre H–Matrix” entsprechend der Matrix H3 in Aufgabe A4.11. Die Zeilen sind Linearkombinationen der oberen Matrix. Für diesen nicht systematischen Coder gilt mit wS = 2 und wZ = 4 ebenfalls:
\[R \ge 1 - \frac{w_{\rm S}}{w_{\rm Z}} = 1 - \frac{2}{4} = 1/2 \hspace{0.05cm}.\]

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 irreguläre Matrix. Die acht Variable Nodes (abgekürzt VNs) Vi sind mit den vier Check Nodes (abgekürzt CNs) Cj verbunden, falls das Element in Zeile j und Spalte i  ⇒  hj,i gleich 1 ist. Andernfalls (falls hj,i = 0) besteht keine Verbindung.
  • Der links dargestellte Graph ist für die iterative symbolweise Decodierung nicht sonderlich gut geeignet. Die VNs V5, ...., V8 sind jeweils nur mit einem CN verbunden, was für die Decodierung keinerlei Information liefert.
  • Im rechten Tanner–Graph für den regulären Code erkennt man, dass hier von jedem VN Vi zwei Verbindungslinien (englisch: Edges) abgehen und von jedem CN Cj 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 (1)


Als Beispiel für die iterative LDPC–Decodierung wird nun der sog. Message–passing Algorithm beschrieben. Wir verdeutlichen diesen anhand des rechten Tanner–Graphen auf der vorherigen Seite und damit für die dort angegebene reguläre Prüfmatrix.

Bei diesem Decodieralgorithmus erfolgt abwechselnd (oder iterativ) ein Informationsaustausch zwischen den Variable Nodes (VNs) V1, ... , Vn und den Check Nodes (CNs) C1, ... , Cm.

Iterative Decodierung von LDPC–Codes

Für das betrachtete Beispiel gilt:

  • Es gibt n = 8 VNs und m = 4 CNs. Da ein regulärer LDPC–Code vorliegt, gehen von jedem VN dV = 2 Verbindungslinien zu einem CN und jeder CN ist mit dC = 4 VNs verbunden.
  • Der Variable Node Degree dV ist gleich dem Hamming–Gewicht einer jeden Spalte (wS) und für den Check Node Degree gilt: dC = wZ (Hamming–Gewicht einer jeden Zeile).
  • In der folgenden Beschreibung verwenden wir auch die Begriffe Nachbarn eines VN  ⇒  N(Vi) sowie Nachbarn eines CN  ⇒  N(Cj), wobei wir uns hier auf implizite Definitionen beschränken:
\[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},\]
\[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}.\]
Informationsaustausch zwischen VNs und CNs

Die Skizze aus [Liv15][3] zeigt den Austausch von Information zwischen dem Variable Node Vi und dem Check Node Cj – ausgedrückt durch Log–Likelihood Ratios (kurz: L–Werte). Der Informationsaustausch geschieht in zwei Richtungen:

  • L(ViCj): Extrinsische Information aus Sicht von Vi, Apriori–Information aus Sicht von Cj.
  • L(CjVi): Extrinsische Information aus Sicht von Cj, Apriori–Information aus Sicht von Vi.

Iterative Decodierung von LDPC–Codes (2)


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 ≤ in: L(ViCj) = LK(Vi). Wie aus der letzten Grafik ersichtlich, ergeben sich diese Kanal–L–Werte LK(Vi) aus den Empfangswerten yi.

Check Node Decoder: Jeder Knoten Cj repräsentiert eine Prüfgleichung. So steht C1 für „V1 + V4 + V5 + V8 = 0”. Man erkennt den Zusammenhang zur extrinsischen Information bei der symbolweisen Decodierung des Single Parity–check Codes. In Analogie zu Kapitel 4.1 und Aufgabe A4.4 gilt somit für den extrinsischen L–Wert von Cj und gleichzeitig für die Apriori–Information bezüglich Vi:

\[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 Vi verbundenen Check Nodes Cj demselben Bit entsprechen  ⇒  dieses Bit wird quasi dV mal wiederholt.

In Analogie zu Kapitel 4.1 gilt für den extrinsischen L–Wert von Vi und gleichzeitig für die Apriori–Information bezüglich Cj:

\[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. 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.

Zusammenhang zwischen LDPC– und serieller Turbo–Decodierung

Leistungsfähigkeit der LDPC–Codes (1)


Wir betrachten nun wie in [Str14] fünf reguläre LDPC–Codes mit den folgenden Eigenschaften:

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

Bitfehlerrate von LDPC–Codes

Die Grafik zeigt die Bitfehlerrate (BER) abhängig vom AWGN–Parameter 10 · lg EB/N0. Zum Vergleich ist die Kurve für uncodierte Übertragung eingezeichnet.

Man erkennt:

  • Die Bitfehlerrate ist um so kleiner, je länger der Code ist. Für 10 · lg EB/N0 = 2 dB und n = 28 = 256 ergibt sich BER ≈ 10–2. Für n = 212 = 4096 dagegen nur BER ≈ 2 · 10–7.
  • Mit n = 215 = 32768 (violette Kurve) benötigt man 10 · lg EB/N0 ≈ 1.35 dB für BER = 10–5. Der Abstand von der Shannon–Grenze (0.18 dB für R = 1/2 und BPSK) beträgt ca. 1.2 dB.

„Waterfall Region” und „Error Floor”






Die Kurven für n = 28 bis n = 210 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 Grafik links 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” (Ursachen hierfür siehe nächste Seite) bei sehr niedrigen BER–Werten liegt,
  • die Anzahl der erforderlichen Iterationen handhabbar ist, und
  • diese Eigenschaften nicht erst bei nicht mehr praktikablen Blocklängen erreicht werden.

Leistungsfähigkeit der LDPC–Codes (2)


LDPC–Codes im Vergleich zur Shannon–Grenze

In diesem Kapitel wurden vorwiegend reguläre LDPC–Codes behandelt, auch im 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 BPSK beschriftet). Die Codewortlänge dieses irregulären Rate–1/2–Codes von [CFRU01][4] beträgt 2 · 106. Daraus ist schon ersichtlich, dass dieser Code nicht für den praktischen Einsatz gedacht war, sondern für einen Rekordversuch getunt wurde.

Bei der LDPC–Codekonstruktion geht man ja stets von der Prüfmatrix H aus. Für den gerade genannten Code hat diese die Dimension 1000000×2000000, beinhaltet also 2 · 1012 Matrixelemente.

Füllt man die Matrix per Zufallsgenerator mit (wenigen) Einsen  ⇒  „Low–density”. So spricht man von unstrukturiertem Code–Design. Dies kann bei langen Codes zu folgenden Problemen führen:

  • Die Komplexität des Coders kann zunehmen, da trotz Modifikation der Prüfmatrix H sichergestellt werden muss, dass die Generatormatrix G systematisch sein muss.
  • Aufwändige Hardware–Realisierung des iterativen Decoders.
  • „Error Floor” durch einzelne Einsen in einer Spalte (oder Zeile) sowie kurze Schleifen.

: Im linken Teil der Grafik ist der Tanner–Graph für einen regulären LDPC–Code mit der Prüfmatrix H1 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 Cj wieder bei diesem landet (oder von Vi zu Vi). Im linken Beispiel ergibt sich die minimale Kantenlänge 6, zum Beispiel der Weg C1V1C3V5C2V2C1.

Zur Definition eines „Girth”

Vertauscht man in der Prüfmatrix nur zwei Einsen  ⇒  Matrix H2, so ist die minimale Schleifenlänge 4, von C1V4C4V6C1. Ein kleiner Girth führt zu einem „Error Floor” im BER–Verlauf.


Einige Anwendungsgebiete für LDPC–Codes


Einige standardisierte LDPC–Codes im Vergleich zur Shannon–Grenze

In dem Schaubild sind zwei Kommunikations–Standards, die auf strukturierten LDPC–Codes basieren, im Vergleich zur AWGN–Kanalkapazität eingetragen.

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.

  • 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 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 – Satellite” bzw. „Digital Video Broadcasting – Terrestrial”, und die „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 große spektrale Effizienz aus.

IRA–Coder bei DVB–S2/T2

DVB–Codes gehören zu den Irregular Repeat Accumulate (IRA) Codes die erstmals im Jahr 2000 in [JKE00][5] vorgestellt wurden. Die Grafik zeigt die Grundstruktur des Coders. Der grün hinterlegte Teil – mit Repetition Code (RC), Interleaver, Single Parity–Code (SPC) sowie Akkumulator – entspricht exakt einem seriell–verketteten Turbocode  ⇒  siehe RA–Coder. Die Beschreibung des IRA–Codes basiert aber allein auf der Prüfmatrix 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 Bose–Chaudhuri–Hocquenghem) verwendet, der den Error Floor herabsetzen soll.

In der oberen Grafik nicht eingetragen sind die LDPC–Codes für den Standard DVB Return Channel Terrestrial (RCS), für den WiMax–Standard (IEEE 802.16) sowie für das 10GBASE–T–Ethernet, die gewisse Ähnlichkeiten mit den IRA–Codes aufweisen.

Aufgaben


A4.11 Analyse von Prüfmatrizen

Zusatzaufgaben:4.11 Coderate aus der Prüfmatrix

A4.12 Regulärer/irregulärer Tanner–Graph

A4.13 Decodierung von LDPC–Codes

Quellenverzeichnis

  1. Gallager, R. G.: Low–density Parity–check Codes. MIT Press, Cambridge, MA, 1963.
  2. Liva, G.: Channels Codes for Iterative Decoding. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.
  3. Liva, G.: Channels Codes for Iterative Decoding. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.
  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.