Quelltext der Seite Kanalcodierung/Decodierung linearer Blockcodes

 
{{Header
|Untermenü=Binäre Blockcodes zur Kanalcodierung
|Vorherige Seite=Allgemeine Beschreibung linearer Blockcodes
|Nächste Seite=Schranken für die Blockfehlerwahrscheinlichkeit
}}

== Blockschaltbild und Voraussetzungen ==
<br>
Wir gehen von dem bereits im Kapitel [[Kanalcodierung/Kanalmodelle_und Entscheiderstrukturen|Kanalmodelle und Entscheiderstrukturen]] gezeigten Blockschaltbild aus, wobei als Kanalmodell meist der <i>Binary Symmetric Channel</i> (BSC) verwendet wird. Zur Codewortschätzung verwenden wir den <i>Maximum&ndash;Likelihood&ndash;Entscheider</i> (ML), der für binäre Codes &nbsp; &#8658; &nbsp; $\underline{x}  \in {\rm GF}(2^n)$ das gleiche Ergebnis liefert wie der [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#MAP.E2.80.93_und_ML.E2.80.93Kriterium|MAP&ndash;Empfänger]].<br>

[[Datei:P ID2360 KC T 1 5 S1 v2.png|center|frame|Blockschaltbild zur Decodierung von Blockcodes|class=fit]]

Die Aufgabe des Kanaldecoders kann wie folgt beschrieben werden:
*Der Vektor <i><u>&upsilon;</u></i> nach der Decodierung (an der Sinke) soll möglichst gut mit dem Informationswort <i><u>u</u></i> übereinstimmen. Das heißt: Die Blockfehlerwahrscheinlichkeit soll möglichst klein sein:

::<math>{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{v} \ne \underline{u}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.</math>

*Aufgrund der deterministischen Zuweisungen <i><u>x</u></i> = enc(<i><u>u</u></i>) bzw. <i><u>&upsilon;</u></i>&nbsp;=&nbsp;enc<sup>&ndash;1</sup>(<i><u>z</u></i>) gilt aber auch:

::<math>{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{z} \ne \underline{x}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.</math> 

*Gesucht ist somit das zum gegebenen Empfangswort <i><u>y</u></i> = <i><u>x</u></i> + <i><u>e</u></i> am wahrscheinlichsten gesendete Codewort <i><u>x</u></i><sub><i>i</i></sub>, das als Ergebnis <i><u>z</u></i> weiter gegeben wird:

::<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm}|\hspace{0.05cm} \underline{y} ) \hspace{0.05cm}.</math>

*Beim BSC&ndash;Kanal gilt sowohl <i><u>x</u></i><sub><i>i</i></sub> &#8712; GF(2<sup><i>n</i></sup>) als auch <i><u>y</u></i> &#8712; GF(2<sup><i>n</i></sup>), so dass die ML&ndash;Regel auch mit der [http://www.lntwww.de/Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung Hamming&ndash;Distanz] <i>d</i><sub>H</sub>(<i><u>y</u></i>, <i><u>x</u></i><sub><i>i</i></sub>) geschrieben werden kann:

::<math>\underline{z} = {\rm arg} \min_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})\hspace{0.05cm}.</math>

== Prinzip der Syndromdecodierung ==
<br>
Vorausgesetzt wird hier ein (<i>n</i>, <i>k</i>)&ndash;Blockcode mit der Prüfmatrix <b>H</b> und den systematischen Codeworten

::<math>\underline{x}\hspace{0.05cm} = (x_1, x_2, ... \hspace{0.05cm}, x_i, ... \hspace{0.05cm}, x_n)
 = (u_1, u_2, ... \hspace{0.05cm}, u_k, p_1, ... \hspace{0.05cm}, p_{n-k})\hspace{0.05cm}. </math>

Mit dem Fehlervektor <i><u>e</u></i> gilt dann für das Empfangswort:

::<math>\underline{y} = \underline{x} + \underline{e} \hspace{0.05cm}, \hspace{0.4cm} \underline{y} \in \hspace{0.1cm} {\rm GF}(2^n) \hspace{0.05cm}, \hspace{0.1cm} \underline{x} \in \hspace{0.1cm} {\rm GF}(2^n) \hspace{0.05cm}, \hspace{0.1cm} \underline{e} \in \hspace{0.1cm} {\rm GF}(2^n)
\hspace{0.05cm}.</math>

Ein Bitfehler an der Position <i>i</i>, das heißt <i>y<sub>i</sub></i> &ne; <i>x<sub>i</sub></i>, wird ausgedrückt durch den Fehlerkoeffizienten <i>e<sub>i</sub></i> = 1.<br>

{{Definition}}''':''' Das Syndrom <i><u>s</u></i> = (<i>s</i><sub>0</sub>, <i>s</i><sub>1</sub>, ... , <i>s</i><sub><i>m</i>&ndash;1</sub>) berechnet sich (als Zeilen&ndash; bzw. Spaltenvektor) aus dem Empfangswort <i><u>y</u></i> und der Prüfmatrix <b>H</b> in folgender Weise:

:<math>\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T}\hspace{0.3cm}{\rm bzw.}\hspace{0.3cm} 
\underline{s}^{\rm T} = { \boldsymbol{\rm H}} \cdot \underline{y}^{\rm T}\hspace{0.05cm}.</math>

Die Vektorlänge von <u><i>s</i></u> ist gleich <i>m</i> = <i>n</i> &ndash; <i>k</i> (Zeilenzahl von <b>H</b>).{{end}}<br>

Das Syndrom <i><u>s</u></i> zeigt folgende Charakteristika:
*Wegen <i><u>x</u></i> &middot; <b>H</b><sup>T</sup> = <u>0</u> hängt <i><u>s</u></i> nicht vom Codewort <i><u>x</u></i> ab, sondern allein vom Fehlervektor <i><u>e</u></i>:

::<math>\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T}
= \hspace{0.05cm} \underline{x} \cdot { \boldsymbol{\rm H}}^{\rm T} + \hspace{0.05cm} \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T}
= \hspace{0.05cm} \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T}
\hspace{0.05cm}.</math>

*Bei hinreichend wenig Bitfehlern liefert <i><u>s</u></i> einen eindeutigen Hinweis auf die Fehlerpositionen und ermöglicht so eine vollständige Fehlerkorrektur.<br><br>

{{Beispiel}}''':''' Ausgehend vom systematischen [http://www.lntwww.de/Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Einige_Eigenschaften_des_.287.2C_4.2C_3.29.E2.80.93Hamming.E2.80.93Codes (7,&nbsp;4,&nbsp;3)&ndash;Hamming&ndash;Code] erhält man beispielsweise für den Empfangsvektor <u><i>y</i></u> = (0, 1, 1, 1, 0, 0, 1) das folgende Ergebnis:

:<math>{ \boldsymbol{\rm H}} \cdot \underline{y}^{\rm T}
=  \begin{pmatrix}
		1 &1 &1 &0 &1 &0 &0\\
		0 &1 &1 &1 &0 &1 &0\\
		1 &1 &0 &1 &0 &0 &1
	\end{pmatrix} \cdot \begin{pmatrix}
		0 \\
		1 \\
		1 \\
		1 \\
		0 \\
		0 \\
		1 
	\end{pmatrix} = \begin{pmatrix}
		0 \\
		1 \\
		1
	\end{pmatrix} = \underline{s}^{\rm T} \hspace{0.05cm}.</math>

Vergleicht man das Syndrom mit den [http://www.lntwww.de/Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Pr.C3.BCfmatrix Prüfgleichungen] des Hamming&ndash;Codes, so erkennt man, dass
*am wahrscheinlichsten das vierte Symbol (<i>x</i><sub>4</sub> = <i>u</i><sub>4</sub>) des Codewortes verfälscht wurde,<br>

*der Codewortschätzer somit das Ergebnis  <u><i>z</i></u> = (0, 1, 1, 0, 0, 0, 1) liefern wird.<br>

*die Entscheidung nur dann richtig ist, wenn bei der Übertragung nur ein Bit verfälscht wurde.<br><br>

Nachfolgend sind die erforderlichen Korrekturen für den (7,&nbsp;4,&nbsp;3)&ndash;Hamming&ndash;Code angegeben, die sich aus dem errechneten Syndrom <i><u>s</u></i> entsprechend den Spalten der Prüfmatrix ergeben:

:<math>\underline{s} \hspace{-0.15cm} =  \hspace{-0.15cm} (0, 0, 0) \hspace{0.10cm} \Rightarrow\hspace{0.10cm}{\rm keine\hspace{0.15cm} Korrektur}\hspace{0.05cm};\hspace{0.4cm}\underline{s} = (1, 0, 0)\hspace{0.10cm} \Rightarrow\hspace{0.10cm}p_1{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};</math>
:<math>\underline{s} \hspace{-0.15cm} =  \hspace{-0.15cm}(0, 0, 1)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} p_3{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};\hspace{0.82cm}\underline{s} = (1, 0, 1)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} u_1{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};</math>
:<math>\underline{s} \hspace{-0.15cm} =  \hspace{-0.15cm}(0, 1, 0)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} p_2{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};\hspace{0.82cm}\underline{s} = (1, 1, 0)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} u_3{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};</math>
:<math>\underline{s} \hspace{-0.15cm} =  \hspace{-0.15cm}(0, 1, 1)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} u_4{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm};\hspace{0.82cm}\underline{s} = (1, 1, 1)\hspace{0.10cm} \Rightarrow\hspace{0.10cm} u_2{\rm \hspace{0.15cm} invertieren}\hspace{0.05cm}. </math>{{end}}<br>

== Verallgemeinerung der Syndromdecodierung (1) ==
<br>
Wir fassen die Ergebnisse der letzten Seiten zusammen, wobei wir weiterhin vom BSC&ndash;Kanalmodell ausgehen. Das bedeutet: <i><u>y</u></i> und <i><u>e</u></i> sind Elemente von GF(2<sup><i>n</i></sup>), während die möglichen Codeworte <i><u>x</u><sub>i</sub></i> zum Code <i>C</i> gehören, der einen (<i>n</i> &ndash; <i>k</i>)&ndash;dimensionalen Untervektorraum von GF(2<sup><i>n</i></sup>) darstellt. Dann gilt:

*Die Syndromdecodierung ist eine Realisierungsmöglichkeit der Maximum&ndash;Likelihood&ndash;Detektion von Blockcodes. Man entscheidet sich für das Codewort mit der geringsten Hamming&ndash;Distanz zum Empfangswort:

::<math>\underline{z} = {\rm arg} \min_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})\hspace{0.05cm}.</math>

*Die Syndromdecodierung  ist aber auch die Suche nach dem wahrscheinlichsten Fehlervektor <i><u>e</u></i>, der die Bedingung <i><u>e</u></i> &middot; <b>H</b><sup>T</sup> = <i><u>s</u></i> erfüllt. Das <i>Syndrom</i> liegt dabei durch <i><u>s</u></i>&nbsp;=&nbsp;<i><u>y</u></i>&nbsp;&middot;&nbsp;<b>H</b><sup>T</sup> fest.

*Mit dem [http://www.lntwww.de/Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung Hamming&ndash;Gewicht] <i>w</i><sub>H</sub>(<i><u>e</u></i>) kann die zweite Interpretation auch wie folgt mathematisch formuliert werden:

::<math>\underline{z} = \underline{y} + {\rm arg} \min_{\underline{e}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} {\rm GF}(2^n)} \hspace{0.1cm}
w_{\rm H}(\underline{e}_{\hspace{0.03cm}i})\hspace{0.05cm}.</math>

Zu beachten ist, dass der Fehlervektor <i><u>e</u></i> ebenso wie der Empfangsvektor <i><u>y</u></i> ein Element von GF(2<sup><i>n</i></sup>) ist im Gegensatz zum Syndrom <i><u>s</u></i>&nbsp;&#8712;&nbsp;GF(2<sup><i>m</i></sup>)  mit der Anzahl <i>m</i>&nbsp;=&nbsp;<i>n</i>&nbsp;&ndash;&nbsp;<i>k</i> der Prüfgleichungen. Das bedeutet,
*dass die Zuordnung zwischen Syndrom <i><u>s</u></i> und Fehlervektor <i><u>e</u></i> nicht eindeutig ist, sondern<br>

*dass jeweils 2<sup><i>k</i></sup> Fehlervektoren zum gleichen Syndrom <i><u>s</u></i> führen, die man zu einer Nebenklasse (englisch: <i>Coset</i>) zusammenfasst.<br>
:[[Datei:P ID2361 KC T 1 5 S3 v2.png|Aufteilung der 2<sup><i>k</i></sup> Fehlervektoren in <i>Cosets</i>|class=fit]]<br>

Die Grafik verdeutlicht diesen Sachverhalt am Beispiel <i>n</i> = 5 und <i>k</i> = 2 &#8658; <i>m</i> = <i>n</i> &ndash; <i>k</i> = 3.
*Die insgesamt 2<sup><i>n</i></sup> = 32 möglichen Fehlervektoren <i><u>e</u></i> werden in 2<sup><i>m</i></sup> = 8 Nebenklassen <i>&Psi;</i><sub>0</sub>, ... , <i>&Psi;</i><sub>7</sub> aufgeteilt, auch &bdquo;<i>Cosets</i>&rdquo; genannt. Explizit gezeichnet sind hier nur die Cosets <i>&Psi;</i><sub>0</sub> und <i>&Psi;</i><sub>5</sub>.<br>

*Alle 2<sup><i>k</i></sup> = 4 Fehlervektoren des Cosets <i>&Psi;<sub>&mu;</sub></i> führen zum gleichen Syndrom <i><u>s</u></i><sub><i>&mu;</i></sub>. Zudem hat jede Nebenklasse einen Anführer <i><u>e</u></i><sub><i>&mu;</i></sub>, nämlich denjenigen mit dem minimalen Hamming&ndash;Gewicht.<br><br>

Die Vorgehensweise bei der Syndromdecodierung wird auf den nächsten Seiten nochmals ausführlich an einem Beispiel erläutert.<br>

== Verallgemeinerung der Syndromdecodierung (2) ==
<br>
Die Syndromdecodierung wird hier am Beispiel eines systematischen (5,&nbsp;2,&nbsp;3)&ndash;Codes beschrieben:

:<math>\mathcal{C} = \{ (0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.15cm}(0, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.15cm}(1, 0, 1, 1, 0)  \hspace{0.05cm},\hspace{0.15cm}(1, 1, 1, 0, 1) \}\hspace{0.05cm}.</math>

Generatormatrix und Prüfmatrix lauten:

:<math>{ \boldsymbol{\rm G}} 
=  \begin{pmatrix}
		1 &0 &1 &1 &0 \\
		0 &1 &0 &1 &1
	\end{pmatrix} \hspace{0.05cm}, \hspace{0.4cm} { \boldsymbol{\rm H}} 
=  \begin{pmatrix}
		1 &0 &1 &0 &0 \\
		1 &1 &0 &1 &0 \\
		0 &1 &0 &0 &1
	\end{pmatrix} \hspace{0.05cm}.</math>

Die Tabelle fasst das Endergebnis zusammen.<br>

[[Datei:P ID2362 KC T 1 5 S3b v2.png|center|frame|Beispielhafte (5, 2, 3)–Syndromtabelle  mit Nebenklassen|class=fit]]<br>

Zur Herleitung dieser Tabelle ist anzumerken:
*Die Zeile 1 bezieht sich auf das Syndrom <i><u>s</u></i><sub>0</sub> = (0, 0, 0) und die dazugehörige Nebenklasse <i>&Psi;</i><sub>0</sub>. Am wahrscheinlichsten ist hier die Fehlerfolge (0, 0, 0, 0, 0) &#8658; kein Bitfehler, die wir als Nebenklassenanführer <i><u>e</u></i><sub>0</sub> bezeichnen. Auch die weiteren Einträge in der ersten Zeile, nämlich (1, 0, 1, 1, 0 ),  (0, 1, 0, 1, 1) und (1, 1, 1, 0, 1 ), liefern jeweils das Syndrom <i><u>s</u></i><sub>0</sub> = (0, 0, 0), ergeben sich aber nur mit mindestens drei Bitfehlern und sind entsprechend unwahrscheinlich.<br>

*In den Zeilen 2 bis 6 beinhaltet der jeweilige Nebenklassenanführer <i><u>e</u></i><sub><i>&mu;</i></sub> genau eine einzige Eins. Dementsprechend ist <i><u>e</u></i><sub><i>&mu;</i></sub> stets das wahrscheinlichste Fehlermuster der Klasse <i>&Psi;<sub>&mu;</sub></i> (<i>&mu;</i> = 1, ... , 5). Die &bdquo;Mitläufer&rdquo; ergeben sich erst bei mindestens zwei Übertragungsfehlern.<br>

*Das Syndrom <i><u>s</u></i><sub>6</sub> = (1, 0, 1) ist mit nur einem Bitfehler nicht möglich. Bei der Erstellung obiger Tabelle wurden daraufhin alle &bdquo;5 über 2&rdquo; = 10 Fehlermuster <i><u>e</u></i> mit Gewicht <i>w</i><sub>H</sub>(<i><u>e</u></i>)  = 2 betrachtet. Die zuerst gefundene Folge mit  Syndrom <i><u>s</u></i><sub>6</sub> = (1, 0, 1) wurde als <i><u>e</u></i><sub>6</sub> = (1, 1, 0, 0, 0)   ausgewählt. Bei anderer Probierreihenfolge hätte sich auch die Folge (0, 0, 1, 0, 1) aus <i>&Psi;</i><sub>6</sub> ergeben können.<br>

*Ähnlich wurde bei der Bestimmung des Anführers <i><u>e</u></i><sub>7</sub> = (0, 1, 1, 0, 0) der Nebenklasse <i>&Psi;</i><sub>7</sub> vorgegangen, die durch das einheitliche Syndrom <i><u>s</u></i><sub>7</sub> = (1, 1, 1) gekennzeichnet ist. Auch in der Klasse <i>&Psi;</i><sub>7</sub> gibt es eine weitere Folge mit Hamming&ndash;Gewicht <i>w</i><sub>H</sub>(<i><u>e</u></i>)  = 2, nämlich (1, 0, 0, 0, 1).<br><br>

Die Beschreibung wird auf der nächsten Seite fortgesetzt.<br>

== Verallgemeinerung der Syndromdecodierung (3) ==
<br>
Das Beispiel der letzten Seite wird fortgesetzt. Beachten Sie bitte bei der Tabelle, dass der Index <i>&mu;</i> nicht identisch ist mit dem Binärwert von <i>s<sub>&mu;</sub></i>. Die Reihenfolge ergibt sich vielmehr durch die Anzahl der Einsen im Nebenklassenanführer <i>e<sub>&mu;</sub></i>. So ergibt sich beispielsweise das Syndrom <i>s</i><sub>5</sub> zu (1, 1, 0) und  das Syndrom <i>s</i><sub>6</sub> = (1, 0, 1).<br>

[[Datei:P ID2363 KC T 1 5 S3b v2.png|Beispielhafte (5, 2, 3)–Syndromtabelle  mit Nebenklassen|class=fit]]<br>

Die obige Tabelle muss nur einmal erstellt und kann beliebig oft genutzt werden. Lautet beispielsweise der Empfangsvektor  <i><u>y</u></i> = (0, 1, 0, 0, 1), so muss zunächst das Syndrom ermittelt werden:

:<math>\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} = \begin{pmatrix}
		0 &1 &0 &0 &1
	\end{pmatrix} \cdot 
	\begin{pmatrix}
		1 &1 &0 \\
		0 &1 &1 \\
		1 &0 &0 \\
		0 &1 &0 \\
		0 &0 &1 \\
	\end{pmatrix} = \begin{pmatrix}
		0 &1 &0 
	\end{pmatrix}= \underline{s}_2
\hspace{0.05cm}.</math>

Mit dem Nebenklassenanführer <i><u>e</u></i><sub>2</sub> = (0, 0, 0, 1, 0) aus obiger Tabelle (roter Eintrag für Index 2) gelangt man schließlich zum Decodierergebnis:

:<math>\underline{z} = \underline{y}  + \underline{e}_2  = (0,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 1) + (0,\hspace{0.05cm} 0,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 0) = (0,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm} 1,\hspace{0.05cm} 1)
\hspace{0.05cm}.</math>

Aus dieser Kurzzusammenfassung geht schon hervor, dass die Syndromdecodierung mit einem enormen Aufwand verbunden ist, wenn man nicht wie bei zyklischen Codes gewisse Eigenschaften nutzen kann. Bei großen Blockcodelängen versagt diese Methode vollständig. So müsste man zur Decodierung eines BCH&ndash;Codes &ndash; die Abkürzung steht für deren Erfinder Bose, Chaudhuri und  Hocquenghem &ndash; mit den Codeparametern <i>n</i> =  511, <i>k</i> = 259 und <i>d</i><sub>min</sub> = 61 genau 2<sup>511&ndash;259</sup>&nbsp;&asymp;&nbsp;10<sup>76</sup> Fehlermuster der Länge 511 auswerten und abspeichern. Für diese Codes und auch für andere Codes großer Blocklänge gibt es aber spezielle Decodieralgorithmen, die mit weniger Aufwand zum Erfolg führen.

== Codiergewinn – Bitfehlerrate bei AWGN ==
<br>
Wir betrachten nun die [http://www.lntwww.de/Digitalsignal%C3%BCbertragung/Fehlerwahrscheinlichkeit_bei_Basisband%C3%BCbertragung#Definition_der_Bitfehlerquote_.281.29 Bitfehlerrate] (englisch: <i>Bit Error Rate</i>, BER) für folgende Konstellationen:
*Hamming&ndash;Code (7, 4, 3),<br>

*AWGN&ndash;Kanal, gekennzeichnet durch den Quotienten <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> (in dB),<br>

*Maximum&ndash;Likelihood&ndash;Detektion (ML) mit <i>Hard Decision</i> bzw. <i>Soft Decision</i>.<br>

:[[Datei:P ID2364 KC T 1 5 S4 v2.png|center|frame|Bitfehlerrate bei (7, 4, 3)–Hamming–Codierung|class=fit]]

Zu dieser Grafik ist anzumerken:
*Die schwarze Vergleichskurve gilt beispielsweise für die binäre Phasenmodulation (BPSK) ohne Codierung. Hierfür benötigt man für die Bitfehlerrate 10<sup>&ndash;5</sup> etwa 10 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</Sub> &asymp; 9.6 dB.<br>

*Die roten Kreise gelten für den (7,&nbsp;4,&nbsp;3)&ndash;Code und harte Entscheidungen des ML&ndash;Decoders (ML&ndash;HD). Die Syndromdecodierung ist hierfür eine mögliche Realisierungsform.<br>

*Diese Systemkonfiguration bringt erst für 10 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> > 6 dB  eine Verbesserung gegenüber dem Vergleichssystem. Für BER = 10<sup>&ndash;5</sup> benötigt man nur noch 10&nbsp;&middot;&nbsp;lg&nbsp;<i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>&nbsp;&asymp;&nbsp;9.2&nbsp;dB.<br>

*Die grünen Kreuze für den Hamming&ndash;Code mit [http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#ML.E2.80.93Entscheidung_beim_AWGN.E2.80.93Kanal Soft&ndash;Decision] (ML&ndash;SD) liegen im gesamten Bereich unterhalb der Vergleichskurve. Für BER = 10<sup>&ndash;5</sup> ergibt sich 10 &middot; lg (<i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>) &asymp; 7.8 dB.<br><br>

{{Definition}}''':''' Als Codiergewinn einer Systemkonfiguration (gekennzeichnet durch seinen Code und die Art der Decodierung) bezeichnen wir das gegenüber dem Vergleichssystem (ohne Codierung) kleinere 10 &middot; lg (<i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>), das für eine vorgegebene Bitfehlerrate (BER) erforderlich ist:

:<math>G_{\rm Code} (\hspace{0.05cm}{\rm System}\hspace{0.05cm}|\hspace{0.05cm}{\rm BER}\hspace{0.05cm}) =</math>

:<math> = 10 \cdot {\rm lg}\hspace{0.1cm}{E}_{\rm B}/N_0
\hspace{0.15cm}(\hspace{0.05cm}{\rm ohne\hspace{0.1cm} Codierung}\hspace{0.05cm}|\hspace{0.05cm}{\rm BER}\hspace{0.05cm})-
10 \cdot {\rm lg}\hspace{0.1cm}{E}_{\rm B}/N_0
\hspace{0.15cm}(\hspace{0.05cm}{\rm System}\hspace{0.05cm}|\hspace{0.05cm}{\rm BER}\hspace{0.05cm})  
\hspace{0.05cm}. </math>{{end}}<br>

Angewendet auf obige Grafik erhält man:

:<math>G_{\rm Code} (\hspace{0.05cm}{\rm Hamming \hspace{0.1cm}(7,\hspace{0.02cm}4,\hspace{0.02cm}3), ML-HD}\hspace{0.05cm}|\hspace{0.05cm}{\rm BER} = 10^{-5}\hspace{0.05cm}) = 0.4\,{\rm dB}\hspace{0.05cm},</math>

:<math>G_{\rm Code} (\hspace{0.05cm}{\rm Hamming \hspace{0.1cm}(7,\hspace{0.02cm}4,\hspace{0.02cm}3), ML-SD}\hspace{0.05cm}|\hspace{0.05cm}{\rm BER} = 10^{-5}\hspace{0.05cm}) = 1.8\,{\rm dB}\hspace{0.05cm}.</math><br>

== Decodierung beim Binary Erasure Channel (1) ==
<br>
Abschließend soll noch gezeigt werden, in wie weit der Decoder zu modifizieren ist, wenn anstelle des [http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#Binary_Symmetric_Channel_.E2.80.93_BSC BSC&ndash;Modells] <i>(Binary Symmetrie Channel)</i> das [http://www.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#Binary_Erasure_Channel_.E2.80.93_BEC BEC&ndash;Kanalmodell] <i>(Binary Erasure Channel)</i> zum Einsatz kommt, der keine Fehler produziert, sondern  unsichere Bit als Auslöschungen markiert.<br>

{{Beispiel}}''':''' [[Datei:P ID2537 KC T 1 5 S5.png|Zur Fehlerkorrektur bei BSC und BEC|rechts|rahmenlos]] Nebenstehende Grafik zeigt das Systemmodell und gibt beispielhafte Werte für die einzelnen Vektoren wider. Der linke Bildteil (blau hinterlegt) gilt für das BSC&ndash;Modell (ein Bitfehler 0 &#8594; 1) und der rechte (grün hinterlegt) für das BEC&ndash;Modell (zwei <i>Erasures</i> 1 &#8594; E).

<br><br><br><br><br><br><br><br><br>Ohne Einschränkung der Allgemeingültigkeit betrachten wir wie im Beispiel auf Seite 3c dieses Kapitels wieder den systematischen (5, 2, 3)&ndash;Blockcode mit den vier Codeworten

:<math>\mathcal{C} = \{ (0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.15cm}(0, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.15cm}(1, 0, 1, 1, 0)  \hspace{0.05cm},\hspace{0.15cm}(1, 1, 1, 0, 1) \}\hspace{0.05cm}.</math>

Man erkennt:
*Bei BSC kann wegen <i>d</i><sub>min</sub> = 3 nur ein Bitfehler (<i>t</i> = 1) korrigiert werden (rot markiert).  Beschränkt man sich auf Fehlererkennung, so funktioniert diese bis zu <i>e</i> = <i>d</i><sub>min</sub> &ndash; 1 = 2 Bitfehler.<br>

*Bei BEC macht Fehlererkennung keinen Sinn, denn bereits der Kanal lokalisiert ein unsicheres Bit als <i>Erasure</i> E (Auslöschung). Die Nullen und Einsen im BEC&ndash;Empfangswort <u><i>y</i></u> sind sicher. Deshalb funktioniert hier die Fehlerkorrektur bis zu <i>e</i> = 2 Auslöschungen mit Sicherheit.<br>

*Auch <i>e</i> = 3 Auslöschungen sind manchmal noch korrigierbar. So kann <u><i>y</i></u> = (E, E, E, 1, 1) zu <u><i>z</i></u>&nbsp;=&nbsp;(0,&nbsp;1,&nbsp;0,&nbsp;1,&nbsp;1)  korrigiert werden, da kein zweites Codewort mit zwei Einsen endet. Dagegen ist <u><i>y</i></u>&nbsp;=&nbsp;(0,&nbsp;E,&nbsp;0,&nbsp;E,&nbsp;E) aufgrund des im Code erlaubten Nullwortes nicht korrigierbar.<br>

*Wird sichergestellt, dass in keinem Empfangswort mehr als zwei Auslöschungen vorkommen, so ist die BEC&ndash;Blockfehlerwahrscheinlichkeit Pr(<u><i>z</i></u> &ne; <u><i>x</i></u>) = Pr(<i>&upsilon;</i> &ne; <u><i>u</i></u>) identisch 0. Dagegen ist die entsprechende Blockfehlerwahrscheinlichkeit beim BSC&ndash;Modell stets größer als 0.{{end}}<br><br>

Da nach dem BEC ein jedes Empfangswort entweder richtig oder gar nicht decodiert wird, nennen wir hier den Block <i>y</i> &#8594; <i>z</i> zukünftig &bdquo;Codewortfinder&rdquo;. Eine &bdquo;Schätzung&rdquo; findet nur beim BSC&ndash;Modell statt.<br>

== Decodierung beim Binary Erasure Channel (2) ==
<br>
Wie funktioniert aber nun die Decodierung eines Empfangswortes <u><i>y</i></u> mit Auslöschungen algorithmisch? Ausgehend vom Empfangswort <u><i>y</i></u>&nbsp;=&nbsp;(0, E, 0, E, 1) des letzten Beispiels setzen wir den Ausgang des Codewortfinders formal zu <u><i>z</i></u>&nbsp;=&nbsp;(0,&nbsp;<i>z</i><sub>2</sub>,&nbsp;0,&nbsp;<i>z</i><sub>4</sub>,&nbsp;1), wobei die Symbole <i>z</i><sub>2</sub> und <i>z</i><sub>4</sub> (jeweils 0 oder 1) entsprechend der folgenden Gleichung zu bestimmen sind:

:<math>\underline{z} \cdot { \boldsymbol{\rm H}}^{\rm T}= \underline{0}
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
{ \boldsymbol{\rm H}} \cdot \underline{z}^{\rm T}= \underline{0}^{\rm T} \hspace{0.05cm}.</math>

Es geht nun darum, diese Bestimmungsgleichung möglichst effizient umzusetzen.<br>

{{Beispiel}}''':''' Wir betrachten wieder den auf der [http://www.lntwww.de/Kanalcodierung/Decodierung_linearer_Blockcodes#Decodierung_beim_Binary_Erasure_Channel_.281.29 letzten Seite] skizzierten Fall mit dem Empfangsvektor <u><i>y</i></u> = (0, E, 0, E, 1). Damit ergeben sich folgende Rechenschritte:
*Mit der Prüfmatrix <b>H</b> des (5, 2, 3)&ndash;Blockcodes und dem Vektor <u><i>z</i></u> = (0, <i>z</i><sub>2</sub>, 0, <i>z</i><sub>4</sub>, 1) lautet die obige Bestimmungsgleichung:

::<math>{ \boldsymbol{\rm H}} \cdot \underline{z}^{\rm T}
=  \begin{pmatrix}
		1 &0 &1 &0 &0\\
		1 &1 &0 &1 &0\\
		0 &1 &0 &0 &1
	\end{pmatrix} \cdot \begin{pmatrix}
		0 \\
		z_2 \\
		0 \\
		z_4 \\
		1 
	\end{pmatrix} = \begin{pmatrix}
		0 \\
		0 \\
		0
	\end{pmatrix}  
\hspace{0.05cm}.</math>

*Wir fassen die sicheren (korrekten) Bit zum Vektor <u><i>z</i></u><sub>K</sub> zusammen und die ausgelöschten Bit zum Vektor <u><i>z</i></u><sub>E</sub>. Dann teilen wir die Prüfmatrix <b>H</b> in die entsprechenden Teilmatrizen <b>H</b><sub>K</sub> und <b>H</b><sub>E</sub> auf:

::<math>\underline{z}_{\rm K} \hspace{-0.15cm}  =  \hspace{-0.15cm} (0, 0, 1)\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm H}}_{\rm K}=  
\begin{pmatrix}
		1 &1 &0\\
		1 &0 &0\\
		0 &0 &1
	\end{pmatrix}
\hspace{0.3cm}\Rightarrow\hspace{0.3cm}
{\rm Spalten\hspace{0.15cm} 1,\hspace{0.15cm}3 \hspace{0.15cm}und \hspace{0.15cm}5 \hspace{0.15cm}der \hspace{0.15cm}Pr\ddot{u}fmatrix} 
\hspace{0.05cm},</math>
::<math>\underline{z}_{\rm E} \hspace{-0.15cm}  =  \hspace{-0.15cm} (z_2, z_4)\hspace{0.05cm},\hspace{0.35cm} { \boldsymbol{\rm H}}_{\rm E}=  
\begin{pmatrix}
		0 &0\\
		1 &1\\
		1 &0
	\end{pmatrix}
 \hspace{0.9cm}\Rightarrow\hspace{0.3cm}
{\rm Spalten\hspace{0.15cm} 2 \hspace{0.15cm}und \hspace{0.15cm}4 \hspace{0.15cm}der \hspace{0.15cm}Pr\ddot{u}fmatrix}
\hspace{0.05cm}.</math>

*Unter Berücksichtigung der Tatsache, dass in GF(2) die Subtraktion gleich der Addition ist, lässt sich die obige Gleichung wie folgt darstellen:

::<math>{ \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T}
+ 
{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T}= \underline{0}^{\rm T} 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm}
{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T}=
{ \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T} </math>

::<math>\Rightarrow \hspace{0.3cm}
\begin{pmatrix}
		0 &0\\
		1 &1\\
		1 &0
	\end{pmatrix} \cdot  
\begin{pmatrix}
		z_2 \\
		z_4  
	\end{pmatrix} =
	\begin{pmatrix}
		1 &1 &0\\
		1 &0 &0\\
		0 &0 &1
	\end{pmatrix} \cdot 
	\begin{pmatrix}
		0 \\
		0 \\
		1  
	\end{pmatrix} = \begin{pmatrix}
		0 \\
		0 \\
		1  
	\end{pmatrix}
	\hspace{0.05cm}.</math>

*Dies führt zu einem linearen Gleichungssystem mit zwei Gleichungen für die beiden unbekannten <i>z</i><sub>2</sub> und <i>z</i><sub>4</sub> (jeweils 0 oder 1). Aus der letzten Zeile erhält man <i>z</i><sub>2</sub> = 1 und aus der zweiten Zeile folgt somit <i>z</i><sub>2</sub> + <i>z</i><sub>4</sub> = 0 &nbsp;&#8658;&nbsp; <i>z</i><sub>4</sub> = 1. Damit ergibt sich das zulässige Codewort <u><i>z</i></u>&nbsp;=&nbsp;(0,&nbsp;1,&nbsp;0,&nbsp;1,&nbsp;1).{{end}}<br>

== Aufgaben zum Kapitel ==
<br>
[[Aufgaben:1.11 Syndromdecodierung|A1.11 Syndromdecodierung]]

[[Zusatzaufgaben:1.11 Nochmals Syndromdecodierung]]

[[Aufgaben:1.12 Hard / Soft Decision|A1.12 Hard / Soft Decision]]

[[Zusatzaufgaben:1.12 Vergleich (7, 4, 3) und (8, 4, 4)]]

[[Aufgaben:1.13 BEC–Decodierung|A1.13 BEC–Decodierung]]

[[Zusatzaufgaben:1.13 Nochmals BEC–Decodierung]]

{{Display}}