Kanalcodierung/Soft–in Soft–out Decoder: Unterschied zwischen den Versionen
Ayush (Diskussion | Beiträge) |
Ayush (Diskussion | Beiträge) |
||
Zeile 13: | Zeile 13: | ||
Nachfolgend werden alle Symbole in bipolarer Darstellung angegeben: „0” → „+1” und „1” → „–1”. | Nachfolgend werden alle Symbole in bipolarer Darstellung angegeben: „0” → „+1” und „1” → „–1”. | ||
− | *Die Symbolfolge <u><i>u</i></u> = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>) wird der Coderfolge <u><i>x</i></u> = (<i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, <i>x</i><sub>3</sub>) = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>, <i>p</i>) zugeordnet, wobei für das Paritybit <i>p</i> = <i>u</i><sub>1</sub> ⊕ <i>u</i><sub>2</sub> gilt ⇒ Single Parity–check Code ⇒ SPC (3, 2, 2).<br> | + | *Die Symbolfolge <u><i>u</i></u> = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>) wird der Coderfolge <u><i>x</i></u> = (<i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, <i>x</i><sub>3</sub>) = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>, <i>p</i>) zugeordnet, wobei für das Paritybit <i>p</i> = <i>u</i><sub>1</sub> ⊕ <i>u</i><sub>2</sub> gilt ⇒ [http://www.lntwww.de/Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Single_Parity.E2.80.93check_Codes_.281.29 Single Parity–check Code] ⇒ SPC (3, 2, 2).<br> |
− | *Der AWGN–Kanal verändert die Binärsymbole <i>x<sub>i</sub></i> ∈ {+1, –1} zu reellwertigen Ausgangswerten <i>y</i><sub><i>i</i></sub>, z.B. im Block 4 der unteren Tabelle: <i>x</i><sub>1</sub> = +1 ⇒ <i>y</i><sub>1</sub> = +0.9 und <i>x</i><sub>3</sub> = –1 ⇒ <i>y</i><sub>3</sub> = +0.1.<br> | + | *Der [http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang AWGN–Kanal] verändert die Binärsymbole <i>x<sub>i</sub></i> ∈ {+1, –1} zu reellwertigen Ausgangswerten <i>y</i><sub><i>i</i></sub>, z.B. im Block 4 der unteren Tabelle: <i>x</i><sub>1</sub> = +1 ⇒ <i>y</i><sub>1</sub> = +0.9 und <i>x</i><sub>3</sub> = –1 ⇒ <i>y</i><sub>3</sub> = +0.1.<br> |
− | *Die Decodierung geschieht gemäß dem Kriterium Maximum Likelihood (block–wise ML), wobei zwischen <i>Hard Decision</i> (ML–HD) und <i>Soft Decision</i> (ML–SD) zu unterscheiden ist.<br> | + | *Die Decodierung geschieht gemäß dem Kriterium [http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#MAP.E2.80.93_und_ML.E2.80.93Kriterium_.282.29 Maximum Likelihood (block–wise ML),] wobei zwischen <i>Hard Decision</i> (ML–HD) und <i>Soft Decision</i> (ML–SD) zu unterscheiden ist.<br> |
*Das obige Blockschaltbild in seiner Gesamtheit entspricht ML–HD. Hier werden zur Detektion nur die Vorzeichen der AWGN–Ausgangswerte entsprechend <i>y</i><sub>HD, <i>i</i></sub> = sign[<i>y</i><sub>SD, <i>i</i></sub>] ausgewertet.<br> | *Das obige Blockschaltbild in seiner Gesamtheit entspricht ML–HD. Hier werden zur Detektion nur die Vorzeichen der AWGN–Ausgangswerte entsprechend <i>y</i><sub>HD, <i>i</i></sub> = sign[<i>y</i><sub>SD, <i>i</i></sub>] ausgewertet.<br> | ||
Zeile 48: | Zeile 48: | ||
*Der Block 2 demonstriert geringe Signalverfälschungen. Wegen <u><i>y</i></u><sub>HD</sub> = <u><i>x</i></u> (das heißt, dass der Kanal die Vorzeichen nicht verfälscht) liefert auch ML–HD das richtige Ergebnis <u><i>υ</i></u><sub>HD</sub> = <u><i>u</i></u>.<br> | *Der Block 2 demonstriert geringe Signalverfälschungen. Wegen <u><i>y</i></u><sub>HD</sub> = <u><i>x</i></u> (das heißt, dass der Kanal die Vorzeichen nicht verfälscht) liefert auch ML–HD das richtige Ergebnis <u><i>υ</i></u><sub>HD</sub> = <u><i>u</i></u>.<br> | ||
− | *Dagegen gilt im dritten Block <u><i>y</i></u><sub>HD</sub> ≠ <u><i>x</i></u> und es gibt auch keine SPC (3, 2)–Zuordnung <u><i>u</i></u> ⇒ <u><i>y</i></u><sub>HD</sub>. Der ML–Decoder kann hier nur durch die Ausgabe <u><i>υ</i></u><sub>HD</sub> = (E, E) vermelden, dass er bei der Decodierung dieses Blocks gescheitert ist. „E” steht hierbei für Erasure (deutsch: <i>Auslöschung</i>).<br> | + | *Dagegen gilt im dritten Block <u><i>y</i></u><sub>HD</sub> ≠ <u><i>x</i></u> und es gibt auch keine SPC (3, 2)–Zuordnung <u><i>u</i></u> ⇒ <u><i>y</i></u><sub>HD</sub>. Der ML–Decoder kann hier nur durch die Ausgabe <u><i>υ</i></u><sub>HD</sub> = (E, E) vermelden, dass er bei der Decodierung dieses Blocks gescheitert ist. „E” steht hierbei für [http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#Binary_Erasure_Channel_.E2.80.93_BEC Erasure] (deutsch: <i>Auslöschung</i>).<br> |
*Auch der <i>Soft Decision</i> Decoder erkennt, dass eine Decodierung anhand der Vorzeichen nicht funktioniert. Anhand der <u><i>y</i></u><sub>SD</sub>–Werte erkennt er aber, dass mit großer Wahrscheinlichkeit das zweite Bit verfälscht wurde und entscheidet sich für die richtige Symbolfolge <u><i>υ</i></u><sub>SD</sub> = (+1, –1) = <u><i>u</i></u>.<br> | *Auch der <i>Soft Decision</i> Decoder erkennt, dass eine Decodierung anhand der Vorzeichen nicht funktioniert. Anhand der <u><i>y</i></u><sub>SD</sub>–Werte erkennt er aber, dass mit großer Wahrscheinlichkeit das zweite Bit verfälscht wurde und entscheidet sich für die richtige Symbolfolge <u><i>υ</i></u><sub>SD</sub> = (+1, –1) = <u><i>u</i></u>.<br> | ||
Zeile 83: | Zeile 83: | ||
{{Beispiel}}''':''' | {{Beispiel}}''':''' | ||
− | [[Datei:P ID2976 KC T 4 1 S2b v2.png|rahmenlos|rechts|BSC–Modell]] Wir betrachten das skizzierte BSC–Modell mit bipolarer Darstellung. Hier gilt mit der Verfälschungswahrscheinlichkeit <i>ε</i> = 0.1 sowie den beiden Zufallsgrößen <i>x</i> ∈ {+1, –1} und <i>y</i> ∈ {+1, –1} am Eingang und Ausgang des Kanals: | + | [[Datei:P ID2976 KC T 4 1 S2b v2.png|rahmenlos|rechts|BSC–Modell]] Wir betrachten das skizzierte [http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#Binary_Symmetric_Channel_.E2.80.93_BSC BSC–Modell] mit bipolarer Darstellung. Hier gilt mit der Verfälschungswahrscheinlichkeit <i>ε</i> = 0.1 sowie den beiden Zufallsgrößen <i>x</i> ∈ {+1, –1} und <i>y</i> ∈ {+1, –1} am Eingang und Ausgang des Kanals: |
:<math>L(y\hspace{0.05cm}|\hspace{0.05cm}x) \hspace{-0.15cm} = \hspace{-0.15cm} | :<math>L(y\hspace{0.05cm}|\hspace{0.05cm}x) \hspace{-0.15cm} = \hspace{-0.15cm} | ||
Zeile 147: | Zeile 147: | ||
== Symbolweise Soft–in Soft–out Decodierung == | == Symbolweise Soft–in Soft–out Decodierung == | ||
<br> | <br> | ||
− | Wir gehen nun von einem (<i>n</i>, <i>k</i>)–Blockcode aus, wobei das Codewort <u><i>x</i></u> = (<i>x</i><sub>1</sub>, ... , <i>x<sub>n</sub></i>) durch den Kanal in das Empfangswort <u><i>y</i></u> = (<i>y</i><sub>1</sub>, ... , <i>y<sub>n</sub></i>) verfälscht wird. Bei langen Codes ist eine <i>Maximum–a–posteriori–Entscheidung auf Blockebene</i> – kurz: <b>block–wise MAP</b> – sehr aufwändig. Man müsste unter den 2<sup><i>k</i></sup> zulässigen Codeworten <i><u>x</u></i><sub><i>j</i></sub> ∈ <i>C</i> dasjenige mit der größten Rückschlusswahrscheinlichkeit (englisch: <i>A Posteriori Probability</i>, APP) finden. Das auszugebende Codewort <i><u>z</u></i> wäre in diesem Fall | + | Wir gehen nun von einem (<i>n</i>, <i>k</i>)–Blockcode aus, wobei das Codewort <u><i>x</i></u> = (<i>x</i><sub>1</sub>, ... , <i>x<sub>n</sub></i>) durch den Kanal in das Empfangswort <u><i>y</i></u> = (<i>y</i><sub>1</sub>, ... , <i>y<sub>n</sub></i>) verfälscht wird. Bei langen Codes ist eine <i>Maximum–a–posteriori–Entscheidung auf Blockebene</i> – kurz: <b>[http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#MAP.E2.80.93_und_ML.E2.80.93Kriterium_.282.29 block–wise MAP]</b> – sehr aufwändig. Man müsste unter den 2<sup><i>k</i></sup> zulässigen Codeworten <i><u>x</u></i><sub><i>j</i></sub> ∈ <i>C</i> dasjenige mit der größten Rückschlusswahrscheinlichkeit (englisch: <i>A Posteriori Probability</i>, APP) finden. Das auszugebende Codewort <i><u>z</u></i> wäre in diesem Fall |
:<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}j} \hspace{0.03cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}j} |\hspace{0.05cm} \underline{y} ) \hspace{0.05cm}.</math> | :<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}j} \hspace{0.03cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}j} |\hspace{0.05cm} \underline{y} ) \hspace{0.05cm}.</math> | ||
Zeile 170: | Zeile 170: | ||
*Die Iterationen werden fortgesetzt, bis alle |<i>L</i><sub>APP</sub>(<i>i</i>)| größer sind als ein vorzugebender Wert. Das wahrscheinlichste Codewort <i><u>z</u></i> ergibt sich dann aus den Vorzeichen aller <i>L</i><sub>APP</sub>(<i>i</i>), mit <i>i</i> = 1, ... , <i>n</i>.<br> | *Die Iterationen werden fortgesetzt, bis alle |<i>L</i><sub>APP</sub>(<i>i</i>)| größer sind als ein vorzugebender Wert. Das wahrscheinlichste Codewort <i><u>z</u></i> ergibt sich dann aus den Vorzeichen aller <i>L</i><sub>APP</sub>(<i>i</i>), mit <i>i</i> = 1, ... , <i>n</i>.<br> | ||
− | *Bei einem systematischen Code geben die ersten <i>k</i> Bit von <u><i>z</i></u> das gesuchte Informationswort an, das mit großer Wahrscheinlichkeit mit der gesendeten Nachricht <u><i>u</i></u> übereinstimmen wird.<br><br> | + | *Bei einem [http://www.lntwww.de/Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes_.282.29 systematischen Code] geben die ersten <i>k</i> Bit von <u><i>z</i></u> das gesuchte Informationswort an, das mit großer Wahrscheinlichkeit mit der gesendeten Nachricht <u><i>u</i></u> übereinstimmen wird.<br><br> |
− | Diese Beschreibung des SISO–Decodierers nach [Bos98]<ref>Bossert, M.: ''Kanalcodierung.'' Stuttgart: B. G. Teubner, 1998.</ref> soll in erster Linie die unterschiedlichen <i>L</i>–Werte verdeutlichen. Das große Potential der symbolweisen Decodierung erkennt man allerdings erst im Zusammenhang mit verketteten Codiersystemen.<br> | + | Diese Beschreibung des SISO–Decodierers nach [Bos98]<ref>Bossert, M.: ''Kanalcodierung.'' Stuttgart: B. G. Teubner, 1998.</ref> soll in erster Linie die unterschiedlichen <i>L</i>–Werte verdeutlichen. Das große Potential der symbolweisen Decodierung erkennt man allerdings erst im Zusammenhang mit [http://www.lntwww.de/Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Grundstruktur_von_verketteten_Codiersystemen verketteten Codiersystemen.]<br> |
== Zur Berechnung der extrinsischen L–Werte (1) == | == Zur Berechnung der extrinsischen L–Werte (1) == | ||
Zeile 214: | Zeile 214: | ||
</b><br> | </b><br> | ||
− | Bei jedem <i>Single Parity–check Code</i> ist die Anzahl der Einsen in jedem Codewort geradzahlig. Oder anders ausgedrückt: Für jedes Codewort <u><i>x</i></u> ist das Hamming–Gewicht <i>w</i><sub>H</sub>(<u><i>x</i></u>) geradzahlig.<br> | + | Bei jedem <i>Single Parity–check Code</i> ist die Anzahl der Einsen in jedem Codewort geradzahlig. Oder anders ausgedrückt: Für jedes Codewort <u><i>x</i></u> ist das [http://www.lntwww.de/Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung Hamming–Gewicht] <i>w</i><sub>H</sub>(<u><i>x</i></u>) geradzahlig.<br> |
Das Codewort <u><i>x</i></u><sup>(–<i>i</i>)</sup> beinhalte alle Symbole mit Ausnahme von <i>x<sub>i</sub></i> ⇒ Vektor der Länge <i>n</i> – 1. Damit lautet der extrinsische <i>L</i>–Wert bezüglich dieses <i>i</i>–ten Symbols, wenn <u><i>x</i></u> empfangen wurde: | Das Codewort <u><i>x</i></u><sup>(–<i>i</i>)</sup> beinhalte alle Symbole mit Ausnahme von <i>x<sub>i</sub></i> ⇒ Vektor der Länge <i>n</i> – 1. Damit lautet der extrinsische <i>L</i>–Wert bezüglich dieses <i>i</i>–ten Symbols, wenn <u><i>x</i></u> empfangen wurde: | ||
Zeile 261: | Zeile 261: | ||
<br> | <br> | ||
Ein Beispiel für die iterative Decodierung von Faltungscodes ist der <i>BCJR–Algorithmus</i>, benannt nach dessen Erfindern L. R. Bahl, J. Cocke, F. Jelinek und J. Raviv ⇒ [BCJR74]<ref>Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.: ''Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate.'' In: IEEE Transactions on Information Theory, Vol. IT-20, S. 284-287, 1974.</ref>. Der Algorithmus weist viele Parallelen zur sieben Jahren älteren Viterbi–Decodierung auf, doch auch signifikante Unterschiede: | Ein Beispiel für die iterative Decodierung von Faltungscodes ist der <i>BCJR–Algorithmus</i>, benannt nach dessen Erfindern L. R. Bahl, J. Cocke, F. Jelinek und J. Raviv ⇒ [BCJR74]<ref>Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.: ''Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate.'' In: IEEE Transactions on Information Theory, Vol. IT-20, S. 284-287, 1974.</ref>. Der Algorithmus weist viele Parallelen zur sieben Jahren älteren Viterbi–Decodierung auf, doch auch signifikante Unterschiede: | ||
− | *Während Viterbi die Gesamtsequenz schätzt ⇒ block–wise Maximum Likelihood, minimiert der BCJR–Algorithmus die Bitfehlerwahrscheinlichkeit ⇒ bit–wise MAP.<br> | + | *Während Viterbi die Gesamtsequenz schätzt ⇒ [http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#MAP.E2.80.93_und_ML.E2.80.93Kriterium_.282.29 block–wise Maximum Likelihood,] minimiert der BCJR–Algorithmus die Bitfehlerwahrscheinlichkeit ⇒ [http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#MAP.E2.80.93_und_ML.E2.80.93Kriterium_.282.29 bit–wise MAP.]<br> |
*Der Viterbi–Algorithmus kann (in seiner ursprünglichen Form) keine Softinformation verarbeiten. Dagegen gibt der BCJR–Algorithmus bei jeder Iteration für jedes einzelne Symbol (Bit) einen Zuverlässigkeitswert an, der bei späteren Iterationen berücksichtigt wird.<br> | *Der Viterbi–Algorithmus kann (in seiner ursprünglichen Form) keine Softinformation verarbeiten. Dagegen gibt der BCJR–Algorithmus bei jeder Iteration für jedes einzelne Symbol (Bit) einen Zuverlässigkeitswert an, der bei späteren Iterationen berücksichtigt wird.<br> | ||
Zeile 284: | Zeile 284: | ||
*Bei GSM (<i>Global System for Mobile Communications</i>, zweite Mobilfunkgeneration) wird zunächst die Datenbitrate von 9.6 kbit/s auf 12 kbit/s erhöht, um auch in leitungsvermittelten Netzen eine Fehlererkennung zu ermöglichen. Anschließend folgt ein punktierter Faltungscode mit der Ausgangsbitrate 22.8 kbit/s. Die Gesamtcoderate beträgt somit etwa 42.1%. | *Bei GSM (<i>Global System for Mobile Communications</i>, zweite Mobilfunkgeneration) wird zunächst die Datenbitrate von 9.6 kbit/s auf 12 kbit/s erhöht, um auch in leitungsvermittelten Netzen eine Fehlererkennung zu ermöglichen. Anschließend folgt ein punktierter Faltungscode mit der Ausgangsbitrate 22.8 kbit/s. Die Gesamtcoderate beträgt somit etwa 42.1%. | ||
− | *Beim 3G–Mobilfunksystem UMTS (<i>Universal Mobile Telecommunications System</i>) verwendet man je nach den Randbedingungen (guter/schlechter Kanal, wenige/viele Teilnehmer in der Zelle) einen Faltungscode oder einen Turbocode (darunter versteht man per se die Verkettung zweier Faltungscodierer). Beim 4G–Mobilfunksystem LTE (<i>Long Term Evolution</i>) verwendet man für kurze Kontrollsignale einen Faltungscode und für die längeren Payload-Daten einen Turbocode.<br> | + | *Beim 3G–Mobilfunksystem UMTS (<i>Universal Mobile Telecommunications System</i>) verwendet man je nach den Randbedingungen (guter/schlechter Kanal, wenige/viele Teilnehmer in der Zelle) einen Faltungscode oder einen [http://www.lntwww.de/Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Grundstruktur_eines_Turbocodes_.281.29 Turbocode] (darunter versteht man per se die Verkettung zweier Faltungscodierer). Beim 4G–Mobilfunksystem LTE (<i>Long Term Evolution</i>) verwendet man für kurze Kontrollsignale einen Faltungscode und für die längeren Payload-Daten einen Turbocode.<br> |
[[Datei:P ID2998 KC T 4 1 S6 v1.png|Parallel verkettetes Codiersystem|class=fit]]<br> | [[Datei:P ID2998 KC T 4 1 S6 v1.png|Parallel verkettetes Codiersystem|class=fit]]<br> | ||
− | Die Grafik zeigt die Grundstruktur eines parallel verketteten Codiersystems. Alle Vektoren bestehen aus <i>n</i> Elementen: <u><i>L</i></u> = (<i>L</i>(1), ... , <i>L</i>(<i>n</i>)). Die Berechnung aller <i>L</i>–Werte geschieht also auf Symbolebene. Nicht dargestellt ist hier der Interleaver, der zum Beispiel bei den Turbocodes obligatorisch ist. | + | Die Grafik zeigt die Grundstruktur eines parallel verketteten Codiersystems. Alle Vektoren bestehen aus <i>n</i> Elementen: <u><i>L</i></u> = (<i>L</i>(1), ... , <i>L</i>(<i>n</i>)). Die Berechnung aller <i>L</i>–Werte geschieht also auf Symbolebene. Nicht dargestellt ist hier der [http://www.lntwww.de/Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Zweite_Voraussetzung_f.C3.BCr_Turbocodes:_Interleaving Interleaver,] der zum Beispiel bei den Turbocodes obligatorisch ist. |
*Die Codesequenzen <u><i>x</i></u><sub>1</sub> und <u><i>x</i></u><sub>2</sub> werden zur gemeinsamen Übertragung über den Kanal durch einen Multiplexer zum Vektor <u><i>x</i></u> zusammengefügt. Am Empfänger wird die Sequenz <u><i>y</i></u> wieder in die Einzelteile <u><i>y</i></u><sub>1</sub> und <u><i>y</i></u><sub>2</sub> zerlegt. Daraus werden die Kanal–<i>L</i>–Werte <u><i>L</i></u><sub>K,1</sub> und <u><i>L</i></u><sub>K,2</sub> gebildet.<br> | *Die Codesequenzen <u><i>x</i></u><sub>1</sub> und <u><i>x</i></u><sub>2</sub> werden zur gemeinsamen Übertragung über den Kanal durch einen Multiplexer zum Vektor <u><i>x</i></u> zusammengefügt. Am Empfänger wird die Sequenz <u><i>y</i></u> wieder in die Einzelteile <u><i>y</i></u><sub>1</sub> und <u><i>y</i></u><sub>2</sub> zerlegt. Daraus werden die Kanal–<i>L</i>–Werte <u><i>L</i></u><sub>K,1</sub> und <u><i>L</i></u><sub>K,2</sub> gebildet.<br> | ||
− | *Der symbolweise Decoder ermittelt entsprechend der vorne beschriebenen Vorgehensweise die extrinsischen <i>L</i>–Werte <u><i>L</i></u><sub>E,1</sub> und <u><i>L</i></u><sub>E,2</sub>, die gleichzeitig die Apriori–Informationen <u><i>L</i></u><sub>A,2</sub> und <u><i>L</i></u><sub>A,1</sub> für den jeweils anderen Decoder darstellen. <br> | + | *Der symbolweise Decoder ermittelt entsprechend der vorne beschriebenen [http://www.lntwww.de/Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Zur_Berechnung_der_extrinsischen_L.E2.80.93Werte_.281.29 Vorgehensweise] die extrinsischen <i>L</i>–Werte <u><i>L</i></u><sub>E,1</sub> und <u><i>L</i></u><sub>E,2</sub>, die gleichzeitig die Apriori–Informationen <u><i>L</i></u><sub>A,2</sub> und <u><i>L</i></u><sub>A,1</sub> für den jeweils anderen Decoder darstellen. <br> |
*Nach ausreichend vielen Iterationen (also dann, wenn ein Abbruchkriterium erfüllt ist) liegt am Decoderausgang der Vektor der Aposteriori–Werte ⇒ <u><i>L</i></u><sub>APP</sub> an. Im Beispiel wird willkürlich der Wert im oberen Zweig genommen. Möglich wäre aber auch der untere <i>L</i>–Wert.<br><br> | *Nach ausreichend vielen Iterationen (also dann, wenn ein Abbruchkriterium erfüllt ist) liegt am Decoderausgang der Vektor der Aposteriori–Werte ⇒ <u><i>L</i></u><sub>APP</sub> an. Im Beispiel wird willkürlich der Wert im oberen Zweig genommen. Möglich wäre aber auch der untere <i>L</i>–Wert.<br><br> | ||
− | Das obige Modell gilt insbesondere auch für die Decodierung der Turbo–Codes gemäß Kapitel 4.3.<br> | + | Das obige Modell gilt insbesondere auch für die Decodierung der Turbo–Codes gemäß [http://www.lntwww.de/Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Grundstruktur_eines_Turbocodes_.281.29 Kapitel 4.3.]<br> |
== Aufgaben == | == Aufgaben == |
Version vom 24. Januar 2017, 22:36 Uhr
Inhaltsverzeichnis
- 1 Hard Decision vs. Soft Decision (1)
- 2 Hard Decision vs. Soft Decision (2)
- 3 Zuverlässigkeitsinformation – Log Likelihood Ratio (1)
- 4 Zuverlässigkeitsinformation – Log Likelihood Ratio (2)
- 5 Symbolweise Soft–in Soft–out Decodierung
- 6 Zur Berechnung der extrinsischen L–Werte (1)
- 7 Zur Berechnung der extrinsischen L–Werte (2)
- 8 BCJR–Decodierung: Vorwärts–Rückwärts–Algorithmus
- 9 Grundstruktur von verketteten Codiersystemen
- 10 Aufgaben
- 11 Quellenverzeichnis
Hard Decision vs. Soft Decision (1)
Zur Hinleitung auf die Thematik dieses vierten und letzten Kapitels und zur Motivation betrachten wir das folgende Nachrichtenübertragungssystem mit Codierung.
Nachfolgend werden alle Symbole in bipolarer Darstellung angegeben: „0” → „+1” und „1” → „–1”.
- Die Symbolfolge u = (u1, u2) wird der Coderfolge x = (x1, x2, x3) = (u1, u2, p) zugeordnet, wobei für das Paritybit p = u1 ⊕ u2 gilt ⇒ Single Parity–check Code ⇒ SPC (3, 2, 2).
- Der AWGN–Kanal verändert die Binärsymbole xi ∈ {+1, –1} zu reellwertigen Ausgangswerten yi, z.B. im Block 4 der unteren Tabelle: x1 = +1 ⇒ y1 = +0.9 und x3 = –1 ⇒ y3 = +0.1.
- Die Decodierung geschieht gemäß dem Kriterium Maximum Likelihood (block–wise ML), wobei zwischen Hard Decision (ML–HD) und Soft Decision (ML–SD) zu unterscheiden ist.
- Das obige Blockschaltbild in seiner Gesamtheit entspricht ML–HD. Hier werden zur Detektion nur die Vorzeichen der AWGN–Ausgangswerte entsprechend yHD, i = sign[ySD, i] ausgewertet.
- Bei Soft Decision (ML–SD) verzichtet man auf den schraffierten Block in obigem Blockschaltbild und wertet direkt die wertkontinuierlichen Eingangsgrößen ySD, i aus.
Aus der Beispieltabelle erkennt man:
- Hard Decision ⇒ die Symbolfolge υHD ergibt sich aus den hart entschiedenen Kanalwerten yHD (blaue Hinterlegung): Es werden nur die beiden ersten Blöcke fehlerfrei decodiert.
- Soft Decision ⇒ die Symbolfolge υSD ergibt sich aus den „weichen” Kanalausgangswerten ySD (grüne Hinterlegung): Nun wird in diesem Beispiel auch der dritte Block richtig entschieden.
Die Bildbeschreibung wird auf der nächsten Seite fortgesetzt.
Hard Decision vs. Soft Decision (2)
Für alle Spalten der folgenden Tabelle wird vorausgesetzt:
- der Nachrichtenblock u = (0, 1), bipolar darstellbar als (+1, –1),
- der SPC (3, 2)–codierte Block x = (0, 1, 1) bzw. in Bipolardarstellung (+1, –1, –1).
Die vier Blöcke unterscheiden sich also nur durch unterschiedliche AWGN–Realisierungen.
Die Tabelle ist wie folgt zu interpretieren:
- Bei idealem Kanal entsprechend Block 1 ⇒ x = ySD = yHD gibt es keinen Unterschied zwischen der (blauen) herkömmlichen ML–HD –Variante und der (grünen) ML–SD –Variante.
- Der Block 2 demonstriert geringe Signalverfälschungen. Wegen yHD = x (das heißt, dass der Kanal die Vorzeichen nicht verfälscht) liefert auch ML–HD das richtige Ergebnis υHD = u.
- Dagegen gilt im dritten Block yHD ≠ x und es gibt auch keine SPC (3, 2)–Zuordnung u ⇒ yHD. Der ML–Decoder kann hier nur durch die Ausgabe υHD = (E, E) vermelden, dass er bei der Decodierung dieses Blocks gescheitert ist. „E” steht hierbei für Erasure (deutsch: Auslöschung).
- Auch der Soft Decision Decoder erkennt, dass eine Decodierung anhand der Vorzeichen nicht funktioniert. Anhand der ySD–Werte erkennt er aber, dass mit großer Wahrscheinlichkeit das zweite Bit verfälscht wurde und entscheidet sich für die richtige Symbolfolge υSD = (+1, –1) = u.
- Im vierten Block werden durch den AWGN–Kanal sowohl die Vorzeichen von Bit 2 als auch von Bit 3 verändert, was zum Ergebnis υHD = (+1, +1) ≠ u (+1, –1) führt ⇒ ein Blockfehler und gleichzeitig ein Bitfehler. Auch der Soft Decision Decoder liefert hier das gleiche falsche Ergebnis.
Die Decodiervariante ML–SD bietet gegenüber ML–HD zudem den Vorteil, dass man relativ einfach jedes Decodierergebnis mit einem Zuverlässigkeitswert versehen kann (in obiger Tabelle ist dieser allerdings nicht angegeben). Dieser Zuverlässigkeitswert
- hätte bei Block 1 seinen Maximalwert,
- wäre bei Block 2 deutlich kleiner,
- läge bei Block 3 und 4 nahe bei 0.
Zuverlässigkeitsinformation – Log Likelihood Ratio (1)
Es sei x ∈ {+1, –1} eine binäre Zufallsvariable mit den Wahrscheinlichkeiten Pr(x = +1) und Pr(x = –1). Für die Codierungstheorie erweist es sich als zweckmäßig hinsichtlich der Rechenzeiten, wenn man anstelle der Wahrscheinlichkeiten Pr(x = ±1) den natürlichen Logarithmus des Quotienten heranzieht.
\[L(x)={\rm ln} \hspace{0.15cm} \frac{{\rm Pr}(x = +1)}{{\rm Pr}(x = -1)}\hspace{0.05cm}.\]
Bei unipolarer/symbolhafter Darstellung (+1 → 0 und –1 → 1) gilt entsprechend mit ξ ∈ {0, 1}:
\[L(\xi)={\rm ln} \hspace{0.15cm} \frac{{\rm Pr}(\xi = 0)}{{\rm Pr}(\xi = 1)}\hspace{0.05cm}.\]
Nachfolgend ist der nichtlineare Zusammenhang zwischen Pr(x = ±1) und L(x) angegeben. Ersetzt man Pr(x = +1) durch Pr(ξ = 0), so gibt die mittlere Zeile den L–Wert der unipolaren Zufallsgröße ξ an.
Man erkennt:
- Der wahrscheinlichere Zufallswert von x ∈ {+1, –1} ist durch sign L(x) ⇒ Vorzeichen gegeben.
- Dagegen gibt der Betrag |L(x)| die Zuverlässigkeit für das Ergebnis sign(L(x)) an.
\[L(y\hspace{0.05cm}|\hspace{0.05cm}x) \hspace{-0.15cm} = \hspace{-0.15cm} {\rm ln} \hspace{0.15cm} \frac{{\rm Pr}(y\hspace{0.05cm}|\hspace{0.05cm}x = +1)}{{\rm Pr}(y\hspace{0.05cm}|\hspace{0.05cm}x = -1)} = \] \[\hspace{-0.15cm} = \hspace{-0.15cm} \left\{ \begin{array}{c} {\rm ln} \hspace{0.15cm} [(1 - \varepsilon)/\varepsilon]\\ {\rm ln} \hspace{0.15cm} [\varepsilon/(1 - \varepsilon)] \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r} \hspace{0.15cm} y = +1, \\ {\rm f\ddot{u}r} \hspace{0.15cm} y = -1. \\ \end{array}\]
Beispielsweise ergeben sich für ε = 0.1 folgende Zahlenwerte (vergleiche obere Tabelle):
\[L(y = +1\hspace{0.05cm}|\hspace{0.05cm}x) = {\rm ln} \hspace{0.15cm} \frac{0.9}{0.1} = +2.197\hspace{0.05cm}, \hspace{0.2cm} L(y = -1\hspace{0.05cm}|\hspace{0.05cm}x) = -2.197\hspace{0.05cm}.\]
Dieses Beispiel zeigt, dass man die sog. L–Wert–Algebra auch auf bedingte Wahrscheinlichkeiten anwenden kann. In Aufgabe Z4.1 wird das BEC–Modell in ähnlicher Weise beschrieben.
Zuverlässigkeitsinformation – Log Likelihood Ratio (2)
Wir betrachten nun den AWGN–Kanal mit den beiden bedingten Wahrscheinlichkeitsdichtefunktionen
\[f_{y \hspace{0.03cm}| \hspace{0.03cm}x=+1 } \hspace{0.05cm} (y \hspace{0.05cm}| \hspace{0.05cm}x=+1 )\hspace{-0.1cm} = \hspace{-0.1cm} \frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ - {(y-1)^2}/(2\sigma^2) } \hspace{0.05cm},\] \[f_{y \hspace{0.03cm}| \hspace{0.03cm}x=-1 } \hspace{0.05cm} (y \hspace{0.05cm}| \hspace{0.05cm}x=-1 )\hspace{-0.1cm} = \hspace{-0.1cm} \frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ - {(y+1)^2}/(2\sigma^2) } \hspace{0.05cm}.\]
In der Grafik sind zwei beispielhafte Gaußfunktionen als blaue bzw. rote Kurve dargestellt.
Die gesamte WDF des Ausgangssignals y ergibt sich aus der (gleich) gewichteten Summe:
\[f_{y } \hspace{0.05cm} (y ) = 1/2 \cdot \big [ f_{y \hspace{0.03cm}| \hspace{0.03cm}x=+1 } \hspace{0.05cm} (y \hspace{0.05cm}| \hspace{0.05cm}x=+1 ) \hspace{0.1cm} + \hspace{0.1cm} f_{y \hspace{0.03cm}| \hspace{0.03cm}x=-1 } \hspace{0.05cm} (y \hspace{0.05cm}| \hspace{0.05cm}x=-1 ) \big ] \hspace{0.05cm}.\]
Berechnen wir nun die Wahrscheinlichkeit, dass der Empfangswert y in einem (sehr) schmalen Intervall der Breite Δ um y0 = 0.25 liegt, so erhält man näherungsweise
\[{\rm Pr} (|y - y_0| \le{\it \Delta}/2 \hspace{0.05cm} \Big | \hspace{0.05cm}x=+1 )\hspace{-0.1cm} \approx \hspace{-0.1cm} \frac {\it \Delta}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ - {(y_0-1)^2}/(2\sigma^2) } \hspace{0.05cm},\] \[{\rm Pr} (|y - y_0| \le {\it \Delta}/2 \hspace{0.05cm} \Big | \hspace{0.05cm}x=-1 )\hspace{-0.1cm} \approx \hspace{-0.1cm} \frac {\it \Delta}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ - {(y_0+1)^2}/(2\sigma^2) } \hspace{0.05cm}.\]
Die etwas größeren senkrechten Striche bezeichnen die Bedingungen, die kleineren die Betragsbildung.
Der L–Wert der bedingten Wahrscheinlichkeit in Vorwärtsrichtung (das bedeutet: Ausgang y für einen gegebenen Eingang x) ergibt sich somit als der Logarithmus des Quotienten beider Ausdrücke:
\[L(y = y_0\hspace{0.05cm}|\hspace{0.05cm}x) \hspace{-0.1cm} = \hspace{-0.1cm} {\rm ln} \hspace{0.15cm} \left [ \frac{{\rm e} ^{ - {(y_0-1)^2}/(2\sigma^2)}}{{\rm e} ^{ - {(y_0+1)^2}/(2\sigma^2)}} \right ] = {\rm ln} \left [ {\rm e} ^{ - [ {(y_0-1)^2}+{(y_0+1)^2}]/(2\sigma^2)} \right ]\hspace{0.15cm} = \] \[\hspace{2.4cm} = \hspace{-0.1cm} \frac{(y_0+1)^2-(y_0-1)^2}{2\cdot \sigma^2} = \frac{2 \cdot y_0}{\sigma^2}\hspace{0.05cm}. \]
Ersetzen wir nun die Hilfsgröße y0 durch die (allgemeine) Zufallsgröße y am AWGN–Ausgang, so lautet das Endergebnis:
\[L(y \hspace{0.05cm}|\hspace{0.05cm}x) = {2 \cdot y}/{\sigma^2} =K_{\rm L} \cdot y\hspace{0.05cm}. \]
Hierbei ist KL = 2/σ2 eine Konstante, die allein von der Streuung der Gaußschen Störung abhängt.
Symbolweise Soft–in Soft–out Decodierung
Wir gehen nun von einem (n, k)–Blockcode aus, wobei das Codewort x = (x1, ... , xn) durch den Kanal in das Empfangswort y = (y1, ... , yn) verfälscht wird. Bei langen Codes ist eine Maximum–a–posteriori–Entscheidung auf Blockebene – kurz: block–wise MAP – sehr aufwändig. Man müsste unter den 2k zulässigen Codeworten xj ∈ C dasjenige mit der größten Rückschlusswahrscheinlichkeit (englisch: A Posteriori Probability, APP) finden. Das auszugebende Codewort z wäre in diesem Fall
\[\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}j} \hspace{0.03cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}j} |\hspace{0.05cm} \underline{y} ) \hspace{0.05cm}.\]
Eine zweite Möglichkeit ist die Decodierung auf Bitebene. Der dargestellte symbolweise (oder bitweise) Soft–in Soft–out Decoder hat die Aufgabe, alle Codewortbits xi ∈ {0, 1} entsprechend maximaler Rückschlusswahrscheinlichkeit Pr(xi | y) zu decodieren. Mit der Laufvariablen i = 1, ... , n gilt dabei:
- Der entsprechende L–Wert (englisch: Log Likelihood Ratio, LLR) für das i–te Codebit lautet:
- \[L_{\rm APP} (i) = L(x_i\hspace{0.05cm}|\hspace{0.05cm}\underline{y}) = {\rm ln} \hspace{0.15cm} \frac{{\rm Pr}(x_i = 0\hspace{0.05cm}|\hspace{0.05cm}\underline{y})}{{\rm Pr}(x_i = 1\hspace{0.05cm}|\hspace{0.05cm}\underline{y})}\hspace{0.05cm} . \]
- Der Decoder arbeitet iterativ. Bei der Initialisierung (gekennzeichnet durch den Parameter I = 0) ist LAPP(i) = LK(i), wobei das Kanal–LLR LK(i) durch den Empfangswert yi gegeben ist.
- Berechnet wird zudem der extrinsische L–Wert LE(i), der die gesamte Information quantifiziert, die alle anderen Bits (j ≠ i) aufgrund der Code–Eigenschaften über das betrachtete i–te Bit liefern.
- Bei der nächsten Iteration (ab I = 1) wird LE(i) bei der Berechnung von LAPP(i) als Apriori–Information LA(i) berücksichtigt. Für das neue Aposteriori–LLR in der Iteration I + 1 gilt somit:
- \[L_{\hspace{0.1cm}\rm APP}^{(I+1)} (i) = L_{\hspace{0.1cm}\rm APP}^{(I)} (i) + L_{\hspace{0.1cm}\rm A}^{(I+1)} (i) = L_{\hspace{0.1cm}\rm APP}^{(I)} (i) + L_{\hspace{0.1cm}\rm E}^{(I)} (i)\hspace{0.05cm} . \]
- Die Iterationen werden fortgesetzt, bis alle |LAPP(i)| größer sind als ein vorzugebender Wert. Das wahrscheinlichste Codewort z ergibt sich dann aus den Vorzeichen aller LAPP(i), mit i = 1, ... , n.
- Bei einem systematischen Code geben die ersten k Bit von z das gesuchte Informationswort an, das mit großer Wahrscheinlichkeit mit der gesendeten Nachricht u übereinstimmen wird.
Diese Beschreibung des SISO–Decodierers nach [Bos98][1] soll in erster Linie die unterschiedlichen L–Werte verdeutlichen. Das große Potential der symbolweisen Decodierung erkennt man allerdings erst im Zusammenhang mit verketteten Codiersystemen.
Zur Berechnung der extrinsischen L–Werte (1)
Die Schwierigkeit bei der symbolweisen iterativen Decodierung ist im allgemeinen die Bereitstellung der extrinsischen L–Werte LE(i). Bei einem Code der Länge n gilt hierbei für die Laufvariable: i = 1, ... , n.
Wir berechnen nun die extrinsischen L–Werte LE(i) für zwei beispielhafte Codes.
Repetition Code ⇒ RC (n, 1, n)
Ein Wiederholungscode zeichnet sich dadurch aus, dass alle n Codesymbole xi ∈ {0, 1} identisch sind. Der extrinsische L–Wert für das i–ten Symbol ist hier sehr einfach anzugeben und lautet:
\[L_{\rm E}(i) = \hspace{0.05cm}\sum_{j \ne i} \hspace{0.1cm} L_j \hspace{0.3cm}{\rm mit}\hspace{0.3cm}L_j = L_{\rm APP}(j) \hspace{0.05cm}.\]
Ist die Summe über alle Lj≠i positiv, so bedeutet dies aus Sicht der anderen L–Werte eine Präferenz für „xi = 0”. Bei negativer Summe ist „xi = 1” wahrscheinlicher. LE(i) = 0 erlaubt keine Vorhersage.
- L = (+1, –1, +3, –1) ⇒ LE = (+1, +3, –1, +3): LE(1) ist positiv, obwohl zwei der anderen
L–Werte (Mehrheit) negativ sind ⇒ Präferenz für „x1 = 0”. Alle Aposteriori–L–Werte sind
nach einer Iteration positiv ⇒ Informationsbit ist u = 0. Weitere Iterationen bringen nichts.
- L = (+1, +1, –4, +1) ⇒ LE = (–2, –2, +3, –2): Alle Aposteriori–L–Werte sind
nach zwei Iterationen negativ ⇒ Informationsbit ist u = 1 ⇒ zu Beginn waren drei Vorzeichen falsch.
- L = (+1, +1, –3, +1) ⇒ LE = (–1, –1, +3, –1): Alle Aposteriori–L–Werte sind
nach einer Iteration 0 ⇒ Informationsbit kann nicht decodiert werden. Weitere Iterationen bringen nichts.
Zur Berechnung der extrinsischen L–Werte (2)
Single Parity–check Code ⇒ SPC (n, n –1, 2)
Bei jedem Single Parity–check Code ist die Anzahl der Einsen in jedem Codewort geradzahlig. Oder anders ausgedrückt: Für jedes Codewort x ist das Hamming–Gewicht wH(x) geradzahlig.
Das Codewort x(–i) beinhalte alle Symbole mit Ausnahme von xi ⇒ Vektor der Länge n – 1. Damit lautet der extrinsische L–Wert bezüglich dieses i–ten Symbols, wenn x empfangen wurde:
\[L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} ungerade} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]} \hspace{0.05cm}.\]
Wie in der Aufgabe A4.4 gezeigt werden soll, kann hierfür auch geschrieben werden:
\[L_{\rm E}(i) = 2 \cdot {\rm tanh}^{-1} \hspace{0.1cm} \left [ \prod\limits_{j \ne i}^{n} \hspace{0.15cm}{\rm tanh}(L_j/2) \right ] \hspace{0.3cm}{\rm mit}\hspace{0.3cm}L_j = L_{\rm APP}(j) \hspace{0.05cm}.\]
\[ \underline{x}_0 \hspace{-0.05cm}=\hspace{-0.05cm} (+1\hspace{-0.03cm},\hspace{-0.05cm}+1\hspace{-0.03cm},\hspace{-0.05cm}+1)\hspace{-0.05cm}, \hspace{0.3cm} \underline{x}_1 \hspace{-0.05cm}=\hspace{-0.05cm} (+1\hspace{-0.03cm},\hspace{-0.05cm} -1\hspace{-0.03cm},\hspace{-0.05cm} -1)\hspace{-0.05cm}, \hspace{0.3cm} \underline{x}_2 \hspace{-0.05cm}=\hspace{-0.05cm} (-1\hspace{-0.03cm},\hspace{-0.05cm} +1\hspace{-0.03cm},\hspace{-0.05cm} -1)\hspace{-0.05cm}, \hspace{0.3cm} \underline{x}_3 \hspace{-0.05cm}=\hspace{-0.05cm} (-1\hspace{-0.03cm},\hspace{-0.05cm} -1\hspace{-0.03cm},\hspace{-0.05cm} +1)\hspace{-0.05cm}. \]
Bei diesem Code ist also das Produkt x1 · x2 · x3 stets positiv.
Die Tabelle zeigt den Decodiervorgang für LAPP = (+2.0, +0.4, –1.6). Die harte Entscheidung nach den Vorzeichen von LAPP(i) ergäbe hier (+1, +1, –1), also kein gültiges Codewort des SP(3, 2, 2).
Rechts sind in der Tabelle die dazugehörigen extrinsischen L–Werte eingetragen:
\[L_{\rm E}(1) \hspace{-0.15cm} = \hspace{-0.15cm} 2 \cdot {\rm tanh}^{-1} \hspace{0.05cm} \left [ {\rm tanh} (0.2) \cdot {\rm tanh} (-0.8)\hspace{0.05cm}\right ] = -0.131\hspace{0.05cm}, \] \[L_{\rm E}(2) \hspace{-0.15cm} = \hspace{-0.15cm}2 \cdot {\rm tanh}^{-1} \hspace{0.05cm} \left [ {\rm tanh} (1.0) \cdot {\rm tanh} (-0.8)\hspace{0.05cm}\right ] = -0.518\hspace{0.05cm}, \] \[L_{\rm E}(3) \hspace{-0.15cm} = \hspace{-0.15cm}2 \cdot {\rm tanh}^{-1} \hspace{0.05cm} \left [ {\rm tanh} (1.0) \cdot {\rm tanh} (0.2)\hspace{0.05cm}\right ] = +0.151\hspace{0.05cm}.\]
Die zweite Gleichung lässt sich wie folgt interpretieren:
- LAPP(1) = +2.0 und LAPP(3) = –1.6 sagen aus, dass Bit 1 eher „+1” als „–1” ist und Bit 3 eher „–1” als „+1”. Die Zuverlässigkeit (Betrag) ist beim ersten Bit etwas größer als beim dritten.
- Die extrinsische Information LE(2) = –0.518 berücksichtigt nur die Informationen von Bit 1 und Bit 3 über Bit 2. Aus deren Sicht ist das zweite Bit eine „–1” mit der Zuverlässigkeit 0.518.
- Der vom Empfangswert y2 abgeleitete L–Wert ⇒ LAPP(2) = +0.4 hat für das zweite Bit eine „+1” vermuten lassen. Die Diskrepanz wird hier bereits in der Iteration I = 1 aufgelöst.
- Entschieden wird hier für das Codewort x1. Bei 0.518 < LAPP(2) < 1.6 würde das Ergebnis x1 erst nach mehreren Iterationen vorliegen. Für LAPP(2) > 1.6 liefert der Decoder dagegen x0.
BCJR–Decodierung: Vorwärts–Rückwärts–Algorithmus
Ein Beispiel für die iterative Decodierung von Faltungscodes ist der BCJR–Algorithmus, benannt nach dessen Erfindern L. R. Bahl, J. Cocke, F. Jelinek und J. Raviv ⇒ [BCJR74][2]. Der Algorithmus weist viele Parallelen zur sieben Jahren älteren Viterbi–Decodierung auf, doch auch signifikante Unterschiede:
- Während Viterbi die Gesamtsequenz schätzt ⇒ block–wise Maximum Likelihood, minimiert der BCJR–Algorithmus die Bitfehlerwahrscheinlichkeit ⇒ bit–wise MAP.
- Der Viterbi–Algorithmus kann (in seiner ursprünglichen Form) keine Softinformation verarbeiten. Dagegen gibt der BCJR–Algorithmus bei jeder Iteration für jedes einzelne Symbol (Bit) einen Zuverlässigkeitswert an, der bei späteren Iterationen berücksichtigt wird.
Die Abbildung soll – fast unzulässig vereinfacht – die unterschiedliche Vorgehensweise von Viterbi–Algorithmus (links) und BCJR–Algorithmus (rechts) verdeutlichen. Zugrunde liegt ein Faltungscode mit dem Gedächtnis m = 1 und der Länge L = 4 ⇒ Gesamtlänge L' = 5 (mit Terminierung).
- Der Viterbi–Algorithmus sucht und findet den wahrscheinlichsten Pfad von Γ0(S0) nach Γ5(S0), nämlich S0 → S1 → S0 → S0 → S1. Wir verweisen auf die Musterlösung zur Aufgabe Z3.9.
Die Skizze für den BCJR–Algorithmus verdeutlicht die Gewinnung des extrinsischen L–Wertes für das dritte Symbol ⇒ LE(3). Der relevante Bereich im Trellis ist schraffiert:
- Bei der Abarbeitung des Trellisdiagramms in Vorwärtsrichtung gewinnt man – in gleicher Weise wie bei Viterbi – die Metriken α1, α2, ... α5. Zur Berechnung von LE(3) benötigt man hiervon α2.
- Anschließend durchläuft man das Trellisdiagramm rückwärts (also von rechts nach links) und erhält damit die Metriken β4, β3, .... , β0 entsprechend der unteren Skizze.
- Der gesuchte extrinsische L–Wert LE(3) ergibt sich aus den Metriken α2 (in Vorwärtsrichtung) und β3 (in Rückwärtsrichtung) sowie der Apriori–Information γ3 über das Symbol i = 3.
Grundstruktur von verketteten Codiersystemen
Die wichtigsten Kommunikationssysteme der letzten Jahre verwenden zwei unterschiedliche Kanalcodes. Man spricht dann von verketteten Codiersystemen (englisch: Concatenated Codes). Auch bei relativ kurzen Komponentencodes C1 und C2 ergibt sich für den verketteten Code C eine hinreichend große Codewortlänge n, die ja bekanntlich erforderlich ist, um sich der Kanalkapazität anzunähern.
Zunächst seien einige Beispiele aus dem Mobilfunk genannt:
- Bei GSM (Global System for Mobile Communications, zweite Mobilfunkgeneration) wird zunächst die Datenbitrate von 9.6 kbit/s auf 12 kbit/s erhöht, um auch in leitungsvermittelten Netzen eine Fehlererkennung zu ermöglichen. Anschließend folgt ein punktierter Faltungscode mit der Ausgangsbitrate 22.8 kbit/s. Die Gesamtcoderate beträgt somit etwa 42.1%.
- Beim 3G–Mobilfunksystem UMTS (Universal Mobile Telecommunications System) verwendet man je nach den Randbedingungen (guter/schlechter Kanal, wenige/viele Teilnehmer in der Zelle) einen Faltungscode oder einen Turbocode (darunter versteht man per se die Verkettung zweier Faltungscodierer). Beim 4G–Mobilfunksystem LTE (Long Term Evolution) verwendet man für kurze Kontrollsignale einen Faltungscode und für die längeren Payload-Daten einen Turbocode.
Die Grafik zeigt die Grundstruktur eines parallel verketteten Codiersystems. Alle Vektoren bestehen aus n Elementen: L = (L(1), ... , L(n)). Die Berechnung aller L–Werte geschieht also auf Symbolebene. Nicht dargestellt ist hier der Interleaver, der zum Beispiel bei den Turbocodes obligatorisch ist.
- Die Codesequenzen x1 und x2 werden zur gemeinsamen Übertragung über den Kanal durch einen Multiplexer zum Vektor x zusammengefügt. Am Empfänger wird die Sequenz y wieder in die Einzelteile y1 und y2 zerlegt. Daraus werden die Kanal–L–Werte LK,1 und LK,2 gebildet.
- Der symbolweise Decoder ermittelt entsprechend der vorne beschriebenen Vorgehensweise die extrinsischen L–Werte LE,1 und LE,2, die gleichzeitig die Apriori–Informationen LA,2 und LA,1 für den jeweils anderen Decoder darstellen.
- Nach ausreichend vielen Iterationen (also dann, wenn ein Abbruchkriterium erfüllt ist) liegt am Decoderausgang der Vektor der Aposteriori–Werte ⇒ LAPP an. Im Beispiel wird willkürlich der Wert im oberen Zweig genommen. Möglich wäre aber auch der untere L–Wert.
Das obige Modell gilt insbesondere auch für die Decodierung der Turbo–Codes gemäß Kapitel 4.3.
Aufgaben
A4.1 Zum „Log Likelihood Ratio”
Zusatzaufgaben:4.1 L–Werte des BEC–Modells
A4.3 Iterative Decodierung beim BSC
Zusatzaufgaben:4.3 Umrechnung von L–Wert und S–Wert
A4.4 Extrinsische L–Werte beim SPC
Zusatzaufgaben:4.4 Ergänzung zur Aufgabe A4.4
Quellenverzeichnis