View source for Channel Coding/Channel Models and Decision Structures

 
 
{{Header
|Untermenü=Binäre Blockcodes zur Kanalcodierung
|Vorherige Seite=Zielsetzung der Kanalcodierung
|Nächste Seite=Beispiele binärer Blockcodes
}}

== AWGN–Kanal bei binärem Eingang ==
<br>
Wir betrachten das bekannte zeitdiskrete [[Modulationsverfahren/Qualit%C3%A4tskriterien#Einige_Anmerkungen_zum_AWGN.E2.80.93Kanalmodell| AWGN&ndash;Kanalmodell]] gemäß der unteren Grafik (links):
*Das binäre und zeitdiskrete Nachrichtensignal $x$ nimmt mit gleicher Wahrscheinlichkeit die Werte $0$ und $1$ an, das heißt, es ist  ${\rm Pr}(x = 0) = {\rm Pr}(\tilde{x} =+1) = 1/2$ sowie ${\rm Pr}(x = 1) = {\rm Pr}(\tilde{x} =-1) = 1/2$.<br>

*Die Übertragung wird durch [[Digitalsignalübertragung/Systemkomponenten_eines_Basisbandübertragungssystems#.C3.9Cbertragungskanal_und_St.C3.B6rungen| additives weißes gaußverteiltes Rauschen]] (AWGN) $n$ mit der (normierten) Rauschleistung $\sigma^2 = N_0/E_{\rm B}$ beeinträchtigt. Die Streuung der Gauß&ndash;WDF ist $\sigma$.<br>

*Aufgrund der Gaußschen WDF kann das Ausgangssignal $y + \tilde{x} +n$ alle reellen Werte annehmen. Der Signalwert $y$ ist zwar wie $x$ (bzw.  $\tilde{x})$ zeitdiskret, im Gegensatz zu diesem aber wertkontinuierlich.<br>

[[File:P ID2340 KC T 1 2 S1 v2.png|center|frame|Modell und WDF des AWGN–Kanals|class=fit]]

Die rechte Grafik zeigt die bedingten Wahrscheinlichkeitsdichtefunktionen (in blau bzw. rot):

::<math>f_{y \hspace{0.03cm}| \hspace{0.03cm}x=0 } \hspace{0.05cm} (y \hspace{0.05cm}| \hspace{0.05cm}x=0 )\hspace{-0.1cm} =  \hspace{-0.1cm}
\frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot \exp \left [ -  \frac {(y-1)^2}{2\sigma^2} \right ]\hspace{0.05cm},</math>
::<math>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 \exp \left [ -  \frac {(y+1)^2}{2\sigma^2} \right ]\hspace{0.05cm}.</math>

Nicht dargestellt ist die gesamte (unbedingte) WDF, für die bei gleichwahrscheinlichen Symbolen gilt:

::<math>f_y(y) = {1}/{2} \cdot  \left [ f_{y \hspace{0.03cm}| \hspace{0.03cm}x=0 } \hspace{0.05cm} (y \hspace{0.05cm}| \hspace{0.05cm}x=0 ) +  
f_{y \hspace{0.03cm}| \hspace{0.03cm}x=1 } \hspace{0.05cm} (y \hspace{0.05cm}| \hspace{0.05cm}x=1 )\right ]\hspace{0.05cm}.</math>

Die beiden schraffierten Flächen (jeweils $\varepsilon$) markieren Entscheidungsfehler unter der Voraussetzung $x=0$ &nbsp; &#8658; &nbsp; $\tilde{x} = +1$ (blau) &nbsp; bzw. $x=0$ &nbsp; &#8658; &nbsp; $\tilde{x} = -1$ (rot), wenn harte Entscheidungen getroffen werden:

:<math>z = \left\{ \begin{array}{c} 0\\
 1   \end{array} \right.\quad
\begin{array}{*{1}c} {\rm falls} \hspace{0.15cm} y > 0\hspace{0.05cm},\\
{\rm falls} \hspace{0.15cm}y < 0\hspace{0.05cm}.\\ \end{array}</math>

Bei gleichwahrscheinlichen Eingangssymbolen ist dann die mittlere Bitfehlerwahrscheinlichkeit ${\rm Pr}(z \ne x)$ ebenfalls gleich $\varepsilon$. Mit dem [[Stochastische_Signaltheorie/Gaußverteilte_Zufallsgrößen#.C3.9Cberschreitungswahrscheinlichkeit|komplementären Gaußschen Fehlerintergral]] ${\rm Q}(x)$ gilt dabei:

::<math>\varepsilon = {\rm Q}(1/\sigma) = {\rm Q}(\sqrt{\rho}) = 
\frac {1}{\sqrt{2\pi} } \cdot \int_{\sqrt{\rho}}^{\infty}{\rm e}^{- \alpha^2/2} \hspace{0.1cm}{\rm d}\alpha
\hspace{0.05cm}.</math>

Hierbei bezeichnet $\rho = 1/\sigma^2 =  2 \cdot E_{\rm S}/N_0$ das Signal&ndash;zu&ndash;Rauschverhältnis (SNR) vor dem Entscheider, wobei folgende Systemgrößen verwendet werden:
*$E_{\rm S}$ ist die Signalenergie pro Symbol (ohne Codierung gleich <i>E</i><sub>B</sub>, also der Signalenergie pro Bit),<br>

*$N_0$ bezeichnet die konstante (einseitige) Rauschleistungsdichte des AWGN&ndash;Kanals.<br><br>

''Hinweis'':&nbsp; Der hier dargelegte Sachverhalt wird mit dem  Applet [[Fehlerwahrscheinlichkeit von Digitalsystemen]] verdeutlicht.

== Binary Symmetric Channel – BSC ==
<br>
Das AWGN&ndash;Kanalmodell ist kein digitales Kanalmodell, wie wir es im Abscnitt [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Blockschaltbild_und_Voraussetzungen|Blockschaltbild und Voraussetzungen]] zur einführenden Beschreibung der Kanalcodierverfahren vorausgesetzt haben. Berücksichtigen wir aber eine harte Entscheidung, so kommen wir zum digitalen Modell <i>Binary Symmetric Channel</i> (BSC):<br>

[[File:P ID2341 KC T 1 2 S2 v2.png|center|frame|BSC–Modell und Zusammenhang mit dem AWGN–Modell|class=fit]]

Wählt man die Verfälschungswahrscheinlichkeiten ${\rm Pr}(y = 1\hspace{0.05cm}|\hspace{0.05cm} x=0)$  bzw. ${\rm Pr}(y = 0\hspace{0.05cm}|\hspace{0.05cm} x=1)$ jeweils zu

::<math>\varepsilon =  {\rm Q}(\sqrt{\rho})\hspace{0.05cm},</math>

so ist der Zusammenhang zum [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang |AWGN&ndash;Kanalmodell]] hergestellt. Die Entscheidungsgrenze liegt dabei bei $G = 0$, wodurch auch die Eigenschaft &bdquo;symmetrisch&rdquo; begründet ist.<br>

<i>Hinweis:</i> Beim AWGN&ndash;Modell haben wir die binäre Ausgangsgröße (nach Schwellenwertentscheidung) mit $z \in \{0, \hspace{0.05cm}1\}$ bezeichnet. Bei den digitalen Kanalmodellen (BSC, BEC, BSEC) bezeichnen wir nun den wertdiskreten Ausgang wieder mit $y$. Um Verwechslungen zu vermeiden, nennen wir das Ausgangssignal des AWGN &ndash;Modells nun $y_{\rm A}$. Für das analoge Empfangssignal gilt $y_{\rm A} + \tilde{x} +n$.<br>

Das BSC&ndash;Modell liefert eine statistisch unabhängige Fehlerfolge und eignet sich somit zur Modellierung gedächtnisloser rückkopplungsfreier Kanäle, die in diesem Buch ausnahmslos betrachtet werden.<br>

Zur Beschreibung gedächtnisbehafteter Kanäle müssen andere Modelle herangezogen werden, die im fünften Hauptkapitel  des Buches &bdquo;Digitalsignalübertragung&rdquo; behandelt werden, zum Beispiel Bündelfehlerkanäle nach 
*dem [[Digitalsignalübertragung/Bündelfehlerkanäle#Kanalmodell_nach_Gilbert.E2.80.93Elliott| Gilbert&ndash;Elliott&ndash;Modell]],<br>

*dem [[Digitalsignalübertragung/Bündelfehlerkanäle#Kanalmodell_nach_McCullough| McCullough&ndash;Modell]].<br><br>

[[File:P ID2342 KC T 1 2 S2b.png|rightr|frame|Statistisch unabhängige Fehler (links) und Bündelfehler (rechts) |class=fit]]
{{GraueBox|TEXT=  
$\text{Beispiel 1:}$&nbsp;  Die Abbildung zeigt 
*statistisch unabhängige Fehler nach dem BSC&ndash;Modell (links), und 
*so genannte Bündelfehler gemäß Gilbert&ndash;Elliott (rechts).


Die Bitfehlerrate beträgt in beiden Fällen $10\%$. Aus der rechten Grafik ist zu erkennen, dass das Bild zeilenweise übertragen wird.}}<br>

== Binary Erasure Channel – BEC ==
<br>
Das BSC&ndash;Modell liefert nur die Aussagen &bdquo;richtig&rdquo; und &bdquo;falsch&rdquo;. Manche Empfänger &ndash; so zum Beispiel die so genannten [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Hard_Decision_vs._Soft_Decision|Soft&ndash;in Soft&ndash;out Decoder]] &ndash; können jedoch auch gewisse Informationen über die Sicherheit der Entscheidung liefern, wobei sie natürlich darüber informiert werden müssen, welche ihrer Eingangswerte sicher sind und welche eher unsicher.<br>

[[File:P ID2343 KC T 1 2 S3 v2.png|center|frame|Binary Erasure Channel (BEC) und Zusammenhang mit dem AWGN–Modell|class=fit]]
Der <i>Binary Erasure Channel</i> (BEC) liefert eine solche Information. Anhand der Grafik erkennt man:
*Das Eingangsalphabet des BEC&ndash;Kanalmodells ist binär &nbsp; &#8658; &nbsp;  $x &#8712; \{0, \hspace{0.05cm}1\}$ und das Ausgangsalphabet ternär &nbsp; &#8658; &nbsp;  $y &#8712; \{0, \hspace{0.05cm}1, \hspace{0.05cm}\rm E\}$. Ein &bdquo;E&rdquo; kennzeichnet eine unsichere Entscheidung. Dieses neue &bdquo;Symbol&rdquo; steht für <i>Erasure</i>, zu deutsch: Auslöschung.

*Bitfehler werden durch das BEC&ndash;Modell per se ausgeschlossen. Eine unsichere Entscheidung (E) wird mit der Wahrscheinlichkeit $\lambda$ getroffen, während die Wahrscheinlichkeit für  eine richtige (und gleichzeitig sichere) Entscheidung $1-\lambda$ beträgt.

*Rechts oben ist der Zusammenhang zwischen BEC&ndash; und AWGN&ndash;Kanalmodell dargestellt, wobei das Erasure&ndash;Entscheidungsgebiet (&bdquo;E&rdquo;) grau hinterlegt ist. Man erkennt, dass es im Gegensatz zum BSC&ndash;Modell $(G = 0)$ nun zwei Entscheidungsgrenzen $G_0 = G$ und $G_1 = -G$ gibt. Es gilt:

::<math>\lambda =  {\rm Q}[\sqrt{\rho} \cdot (1 - G)]\hspace{0.05cm}.</math>

Wir weisen hier nochmals auf die Applets [[Fehlerwahrscheinlichkeit von Digitalsystemen ]] &nbsp; und &nbsp; [[Komplementäre Gaußsche Fehlerfunktion]] hin.

 
== Binary Symmetric Error & Erasure Channel – BSEC ==
<br>
Das BEC&ndash;Modell ist aufgrund der Fehlerwahrscheinlichkeit $0$ eher unrealistisch und nur eine Näherung für ein extrem großes Signal&ndash;zu&ndash;Rausch&ndash;Leistungsverhältnis (kurz SNR) $\rho$. Stärkere Störungen &nbsp; &#8658; &nbsp; ein kleineres $\rho$ sollten besser durch den <i>Binary Symmetric Error & Erasure Channel</i> (BSEC) mit den zwei Parametern
*Verfälschungswahrscheinlichkeit $\varepsilon = {\rm Pr}(y = 1\hspace{0.05cm}|\hspace{0.05cm} x=0)= {\rm Pr}(y = 0\hspace{0.05cm}|\hspace{0.05cm} x=1)$,<br>

*Erasure&ndash;Wahrscheinlichkeit $\lambda = {\rm Pr}(y = {\rm E}\hspace{0.05cm}|\hspace{0.05cm} x=0)= {\rm Pr}(y = {\rm E}\hspace{0.05cm}|\hspace{0.05cm} x=1)$


modelliert werden. Wie beim BEC&ndash;Modell gilt auch hier $x &#8712; \{0, \hspace{0.05cm}1\}$ und $y &#8712; \{0, \hspace{0.05cm}1, \hspace{0.05cm}\rm E\}$.<br>

[[File:P ID2344 KC T 1 2 S4 v2.png|center|frame|Binary Symmetric Error & Erasure Channel (BSEC) und Zusammenhang mit dem AWGN–Modell|class=fit]]

{{GraueBox|TEXT=  
$\text{Beispiel 2:}$&nbsp;  Wir betrachten das BSEC&ndash;Modell mit den beiden Entscheidungsgeraden $G_0 = G = 0.5$ und $G_1 = -G = -0.5$ , dessen Parameter $\varepsilon$ und $\lambda$ durch das SNR $\rho=1/\sigma^2$ des vergleichbaren AWGN&ndash;Kanals festgelegt sind. Dann gilt 
*für $\sigma = 0.5$  &nbsp; &#8658; &nbsp; $\rho = 4$:
::<math>\varepsilon = {\rm Q}[\sqrt{\rho} \cdot (1 + G)] = {\rm Q}(3) \approx 0.14\%\hspace{0.05cm},\hspace{1cm}
{\it \lambda} =  {\rm Q}[\sqrt{\rho} \cdot (1 - G)] -  \varepsilon = {\rm Q}(1) - {\rm Q}(3) \approx 15.87\% -  0.14\% = 15.73\%\hspace{0.05cm},</math>

*für $\sigma = 0.25$  &nbsp; &#8658; &nbsp; $\rho = 16$:

::<math>\varepsilon  = {\rm Q}(6) \approx 10^{-10}\hspace{0.05cm},\hspace{1cm} 
{\it \lambda} = {\rm Q}(2)  \approx 2.27\%\hspace{0.05cm}.</math>

Für die rechts dargestellte WDF wurde $\rho = 4$ vorausgesetzt. Für$\rho = 16$ könnte das BSEC&ndash;Modell durch die BEC&ndash;Variante ersetzt werden, ohne dass es zu einer gravierenden Unterschieden kommt.}}<br>

== Maximum-a-posteriori– und Maximum-Likelihood–Kriterium ==
<br>
Wir gehen nun von dem nachfolgend skizzierten Modell aus und wenden die bereits im Kapitel [[Digitalsignal%C3%BCbertragung/Struktur_des_optimalen_Empf%C3%A4ngers#Blockschaltbild_und_Voraussetzungen| Struktur des optimalen Empfängers]] des Buches &bdquo;Digitalsignalübertragung&rdquo; genannten Entscheidungskriterien auf den Decodiervorgang an.<br>

[[File:P ID2345 KC T 1 2 S5 v2.png|center|frame|Modell zur Beschreibung von MAP– und ML–Decodierung|class=fit]]

Aufgabe des Kanaldecoders ist es, den Ausgabevektor $\underline{v}$ so zu bestimmen, dass er &bdquo;möglichst gut&rdquo; mit dem Informationswort $\underline{u}$ übereinstimmt. 

{{BlaueBox|TEXT=  
$\text{Etwas genauer formuliert:}$&nbsp;  Es soll die '''Blockfehlerwahrscheinlichkeit''' ${\rm Pr(Blockfehler)} = {\rm Pr}(\underline{v} \ne \underline{u}) $ bezogen auf die Vektoren $\underline{u}$ und $\underline{v}$ der Länge $k$ möglichst gering sein. 

Aufgrund der eindeutigen Zuordnung $\underline{x} = {\rm enc}(\underline{u})$ durch den Kanalcoder bzw. empfängerseitig $\underline{v} = {\rm enc}^{-1}(\underline{z})$ gilt in gleicher Weise:

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


Der Kanaldecoder in obigem Modell besteht aus zwei Teilen:
*Der <i>Codewortschätzer</i> ermittelt aus dem Empfangsvektor $\underline{y}$ einen Schätzwert $\underline{z} \in \mathcal{C}$ gemäß einem vorgegebenen Kriterium.<br>

*Anschließend wird aus dem (empfangenen) Codewort $\underline{z}$ das (empfangene) Informationswort  $\underline{v}$ durch <i>einfaches Mapping</i> ermittelt, das möglichst mit $\underline{u}$ übereinstimmen sollte.<br><br>

Für den Codewortschätzer gibt es insgesamt vier unterschiedliche Varianten, nämlich
*den Maximum&ndash;a&ndash;posteriori&ndash;Empfänger (MAP&ndash;Empfänger) für das gesamte Codewort $\underline{x}$,<br>

*den Maximum&ndash;a&ndash;posteriori&ndash;Empfänger (MAP&ndash;Empfänger) für die einzelnen Codebits $x_i$,<br>

*den Maximum&ndash;Likelihood&ndash;Empfänger (ML&ndash;Empfänger)  für das gesamte Codewort $\underline{x}$,<br>

*den Maximum&ndash;Likelihood&ndash;Empfänger (ML&ndash;Empfänger)  für die einzelnen Codebits $x_i$.<br><br>

Deren Definitionen folgen auf der nächsten Seite. Vorab aber gleich das Unterscheidungsmerkmal zwischen MAP und ML:

{{BlaueBox|TEXT=  
$\text{Fazit:}$&nbsp;  
*Ein MAP&ndash;Empfängerberücksichtigt im Gegensatz zum ML&ndash;Empfänger auch unterschiedliche Auftrittswahrscheinlichkeiten für das gesamte Codewort bzw. für deren einzelne Bits.<br>

*Sind alle  Codeworte $\underline{x}$ und damit auch alle Codebits $x_i$ der Codeworte gleichwahrscheinlich, so ist der einfachere ML&ndash;Empfänger  äquivalent zum entsprechenden MAP&ndash;Empfänger.}}<br><br>

== Definitionen der verschiedenen Optimalempfänger ==
<br>
{{BlaueBox|TEXT=  
$\text{Definition:}$&nbsp; Der '''Maximum&ndash;a&ndash;posteriori&ndash;Empfänger auf Blockebene''' &ndash; kurz: <b>block&ndash;wise MAP</b> &ndash;  entscheidet sich unter den $2^k$ zulässigen Codeworten $\underline{x}_i \in \mathcal{C}$ für das Codewort mit der größten Rückschlusswahrscheinlichkeit (englisch: <i>a&ndash;posteriori probability</i>, APP):

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

P${\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm}\vert \hspace{0.05cm} \underline{y} )$ ist die [[Stochastische_Signaltheorie/Statistische_Abh%C3%A4ngigkeit_und_Unabh%C3%A4ngigkeit#Bedingte_Wahrscheinlichkeit| bedingte Wahrscheinlichkeit]], dass $\underline{x}_i$ gesendet wurde, wenn $\underline{y}$ empfangen wird.}}<br>

Wir versuchen nun, diese Entscheidungsregel schrittweise zu vereinfachen: Nach dem &bdquo;Satz von Bayes&rdquo; kann die Rückschlusswahrscheinlichkeit wie folgt umgeformt werden:

::<math>{\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm}\vert \hspace{0.05cm} \underline{y} ) = 
 \frac{{\rm Pr}( \underline{y} \hspace{0.08cm} |\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} ) \cdot {\rm Pr}( \underline{x}_{\hspace{0.03cm}i}  )}{{\rm Pr}( \underline{y}  )} \hspace{0.05cm}.</math>

Die Wahrscheinlichkeit ${\rm Pr}( \underline{y}) $  ist unabhängig von $\underline{x}_i$ und muss bei der Maximierung nicht berücksichtigt werden. Sind zudem alle $2^k$ Informationsworte $\underline{u}_i$ gleichwahrscheinlich, so kann man bei der Maximierung auch auf den Beitrag ${\rm Pr}( \underline{x}_{\hspace{0.03cm}i}  ) = 2^{-k}$ im Zähler verzichten.<br>

{{BlaueBox|TEXT=  
$\text{Definition:}$&nbsp;  Der '''Maximum&ndash;Likelihood&ndash;Empfänger  auf Blockebene''' &ndash; kurz: '''block&ndash;wise ML''' &ndash; entscheidet sich unter den $2^k$ zulässigen Codeworten $\underline{x}_i \in \mathcal{C}$ für das Codewort mit der größten  Übergangswahrscheinlichkeit:

::<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{y}  \hspace{0.05cm}\vert\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} ) \hspace{0.05cm}.</math>

Die bedingte Wahrscheinlichkeit ${\rm Pr}( \underline{y}  \hspace{0.05cm}\vert\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} )$ ist nun in Vorwärtsrichtung zu verstehen, nämlich als die Wahrscheinlichkeit, dass der Vektor $\underline{y}$ empfangen wird, wenn das Codewort $\underline{x}_i$ gesendet wurde.<br>

Im Folgenden verwenden wir auf Blockebene stets den Maximum&ndash;Likelihood&ndash;Empfänger . Aufgrund der vorausgesetzten gleichwahrscheinlichen Informationsworte liefert auch dieser stets die bestmögliche Entscheidung.}}<br>

Anders sieht es jedoch auf Bitebene aus. Ziel einer iterativen Decodierung ist es gerade, für alle Codebits $x_i \in  \{0, 1\}$ Wahrscheinlichkeiten zu schätzen und diese an die nächste Stufe weiterzugeben. Hierzu benötigt man einen MAP&ndash;Empfänger.<br>

{{BlaueBox|TEXT=  
$\text{Definition:}$&nbsp;  Der '''Maximum&ndash;a&ndash;posteriori&ndash;Empfänger auf Bitebene''' (kurz: '''bit&ndash;wise MAP''') wählt für jedes Codebit $x_i$ den Wert ($0$ oder $1$) mit der größten Rückschlusswahrscheinlichkeit ${\rm Pr}( {x}_{\hspace{0.03cm}i}\vert \hspace{0.05cm} \underline{y} )$:

:<math>\underline{z} = {\rm arg}\hspace{-0.1cm}{ \max_{ {x}_{\hspace{0.03cm}i} \hspace{0.03cm} \in \hspace{0.05cm} \{0, 1\} } \hspace{0.03cm} {\rm Pr}( {x}_{\hspace{0.03cm}i}\vert \hspace{0.05cm} \underline{y} ) \hspace{0.05cm} }.</math>}}<br>

== Maximum-Likelihood–Entscheidung beim BSC–Kanal ==
<br>
Wenden wir nun das ML&ndash;Kriterium auf den gedächtnislosen [[Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|BSC&ndash;Kanal]] an. Dann gilt:
::<math>{\rm Pr}( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} ) =
\prod\limits_{l=1}^{n} {\rm Pr}( y_l  \hspace{0.05cm}|\hspace{0.05cm} x_l ) \hspace{0.2cm}{\rm mit}\hspace{0.2cm}
{\rm Pr}( y_l  \hspace{0.05cm}|\hspace{0.05cm} x_l ) = 
 \left\{ \begin{array}{c} 1 - \varepsilon\\
  \varepsilon  \end{array} \right.\quad
\begin{array}{*{1}c} {\rm falls} \hspace{0.15cm} y_l = x_l \hspace{0.05cm},\\
{\rm falls} \hspace{0.15cm}y_l \ne x_l\hspace{0.05cm}.\\ \end{array}
\hspace{0.05cm}.</math>
::<math>\Rightarrow \hspace{0.3cm} {\rm Pr}( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} ) =
\varepsilon^{d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})} \cdot
(1-\varepsilon)^{n-d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})} 
\hspace{0.05cm}.</math>

{{BlaueBox|TEXT=  
$\text{Beweis:}$&nbsp;  Dies lässt sich wie folgt begründen:
*Die [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming&ndash;Distanz]] $d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})$ gibt die Anzahl der Bitpositionen an, in denen sich die beiden Worte $\underline{y}$ und $\underline{x}_{\hspace{0.03cm}i}$ mit jeweils $n$ binären Elementen unterscheiden. Beispielsweise ist die Hamming&ndash;Distanz zwischen $\underline{y}= (0, 1, 0, 1, 0, 1, 1)$ und $\underline{x}_{\hspace{0.03cm}i} = (0, 1, 0, 0, 1, 1, 1)$ gleich 2.<br>

*In $n - d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})$ Positionen unterscheiden sich demnach die beiden Vektoren  $\underline{y}$ und $\underline{x}_{\hspace{0.03cm}i}$ nicht. Im obigen Beispiel sind fünf der $n = 7$ Bit identisch. Zu obiger Gleichung kommt man schließlich durch Einsetzen der Verfälschungswahrscheinlichkeit $\varepsilon$ bzw. deren Ergänzung $1-\varepsilon$.}}<br><br>

Die Vorgehensweise bei der Maximum&ndash;Likelihood&ndash;Detektion ist, dasjenige Codewort $\underline{x}_{\hspace{0.03cm}i}$ zu finden, das die Übergangswahrscheinlichkeit ${\rm Pr}( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} )$ maximiert:

:<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} 
\left [ 
\varepsilon^{d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})} \cdot
(1-\varepsilon)^{n-d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})}
\right ] \hspace{0.05cm}.</math>

Da der Logarithmus eine monoton steigende Funktion ist, erhält man das gleiche Ergebnis nach folgender Maximierung:

::<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
L(\underline{x}_{\hspace{0.03cm}i})\hspace{0.5cm} {\rm mit}\hspace{0.5cm} L(\underline{x}_{\hspace{0.03cm}i})  \hspace{-0.1cm} = \hspace{-0.1cm} \ln \left [ 
\varepsilon^{d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})} \cdot
(1-\varepsilon)^{n-d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})}
\right ] </math>
::<math> \Rightarrow \hspace{0.3cm} L(\underline{x}_{\hspace{0.03cm}i}) = d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i}) \cdot \ln 
\hspace{0.05cm} \varepsilon + [n -d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})] \cdot \ln 
\hspace{0.05cm} (1- \varepsilon) = \ln \frac{\varepsilon}{1-\varepsilon} \cdot d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i}) + n \cdot \ln 
\hspace{0.05cm} (1- \varepsilon)
\hspace{0.05cm}.</math>

Hierbei ist zu berücksichtigen:
*Der zweite Term dieser Gleichung ist unabhängig von $\underline{x}_{\hspace{0.03cm}i}$ und muss für die Maximierung nicht weiter betrachtet werden. 
*Auch der Faktor vor der Hamming&ndash;Distanz ist für alle  $\underline{x}_{\hspace{0.03cm}i}$ gleich. 
*Da $\ln \, {\varepsilon}/(1-\varepsilon)$ negativ ist (zumindest für $\varepsilon <0.5$, was ohne große Einschränkung vorausgestzt werden kann), wird aus der Maximierung eine Minimierung, und man erhält folgendes Endergebnis:<br>


{{BlaueBox|TEXT=  
$\text{ML-Entscheidung beim BSC-Kanal:}$&nbsp; 
Wähle von den $2^k$ zulässigen Codeworten $\underline{x}_{\hspace{0.03cm}i}$ dasjenige mit der <i>geringsten Hamming&ndash;Distanz</i> $d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})$ zum Empfangsvektor $\underline{y}$ aus:

::<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}, \hspace{0.2cm}
\underline{y} \in {\rm GF}(2^n) \hspace{0.05cm}, \hspace{0.2cm}\underline{x}_{\hspace{0.03cm}i}\in {\rm GF}(2^n) \hspace{0.05cm}.</math>}}

Anwendungen der ML/BSC&ndash;Entscheidung finden Sie auf den folgenden Seiten:
*[[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Single_Parity.E2.80.93check_Codes|Single Parity&ndash;check Code]] (SPC)<br>

*[[Beispiele_bin%C3%A4rer_Blockcodes#Wiederholungscodes| Wiederholungscode]] (englisch: <i>Repetition Code</i>, RC).<br>

== Maximum-Likelihood–Entscheidung beim AWGN–Kanal ==
<br>
Das AWGN&ndash;Modell für einen (<i>n</i>, <i>k</i>)&ndash;Blockcode unterscheidet sich vom [http://en.lntwww.de/Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang Modell] auf der ersten Seite dieses Kapitels dadurch, dass für <i>x</i>, <i>x</i>&#x0303; und <i>y</i> nun die entsprechenden Vektoren <i><u>x</u></i>, <u><i>x</i></u>&#x0303; und <i><u>y</u></i> verwendet werden müssen, jeweils bestehend aus <i>n</i> Elementen. Die Schritte zur Herleitung des ML&ndash;Entscheiders bei AWGN werden nachfolgend nur stichpunktartig angegeben:
*Der AWGN&ndash;Kanal ist per se gedächtnislos (hierfür steht das <i>White</i> im Namen), so dass für die bedingte Wahrscheinlichkeitsdichtefunktion geschrieben werden kann:

::<math>f( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{\tilde{x}} ) =
\prod\limits_{l=1}^{n} f( y_l  \hspace{0.05cm}|\hspace{0.05cm} \tilde{x}_l ) 
\hspace{0.05cm}.</math>

*Die bedingte WDF ist für jedes einzelne Codeelement (<i>l</i> = 1, ... , <i>n</i>) gaußisch. Damit genügt auch die gesamte WDF einer (eindimensionalen) Gaußverteilung:

::<math>f({y_l \hspace{0.03cm}| \hspace{0.03cm}\tilde{x}_l }) = 
\frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot \exp \left [ -  \frac {(y_l - \tilde{x}_l)^2}{2\sigma^2} \right ]</math>

::<math>\Rightarrow \hspace{0.3cm}  f( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{\tilde{x}} ) =
\frac {1}{(2\pi)^{n/2} \cdot \sigma^n } \cdot \exp \left [ -  \frac {1}{2\sigma^2} \cdot 
\sum_{l=1}^{n} \hspace{0.2cm}(y_l - \tilde{x}_l)^2
 \right ] \hspace{0.05cm}.</math>


*Da <u><i>y</i></u> nun nicht mehr wie beim BSC&ndash;Modell wertdiskret ist, sondern wertkontinuierlich, müssen jetzt entsprechend der ML&ndash;Entscheidungsregel <i>Wahrscheinlichkeitsdichten</i> untersucht werden und nicht mehr Wahrscheinlichkeiten. Das optimale Ergebnis lautet:

::<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
f( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{\tilde{x}}_i )\hspace{0.05cm}, \hspace{0.8cm}
\underline{y} \in R^n\hspace{0.05cm}, \hspace{0.2cm}\underline{x}_{\hspace{0.03cm}i}\in {\rm GF}(2^n) \hspace{0.05cm}.</math>

*In der Algebra bezeichnet man den Abstand zweier Punkte <u><i>y</i></u> und <i>x</i>&#x0303; im <i>n</i>&ndash;dimensionalen Raum als die Euklidische Distanz, benannt nach dem griechischen Mathematiker Euklid, der im dritten Jahrhundert vor Christus lebte:

::<math>d_{\rm E}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{\tilde{x}}) =
\sqrt{\sum_{l=1}^{n} \hspace{0.2cm}(y_l - \tilde{x}_l)^2}\hspace{0.05cm},\hspace{0.8cm}
\underline{y} \in R^n\hspace{0.05cm}, \hspace{0.2cm}\underline{x}_{\hspace{0.03cm}i}\in \mathcal{C}
\hspace{0.05cm}.</math>

*Damit lautet die ML&ndash;Entscheidungsregel beim AWGN&ndash;Kanal für einen jeden Blockcode unter Berücksichtigung der Tatsache, dass der erste Faktor der WDF <i>f</i>(<u><i>y</i></u> | <u><i>x</i></u>&#x0303;<sub><i>i</i></sub>) konstant ist:

::<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
\exp \left [ -  \frac {d_{\rm E}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{\tilde{x}}_i)}{2\sigma^2} 
 \right ]\hspace{0.05cm}, \hspace{0.8cm}
\underline{y} \in R^n\hspace{0.05cm}, \hspace{0.2cm}\underline{x}_{\hspace{0.03cm}i}\in {\rm GF}(2^n) \hspace{0.05cm}.</math>

Nach einigen weiteren Zwischenschritten kommt man zum Ergebnis:<br>

ML&ndash;Entscheidung beim AWGN&ndash;Kanal: Wähle von den 2<sup><i>k</i></sup> zulässigen Codeworten <i>x<sub>i</sub></i> dasjenige mit der <i>kleinsten Euklidischen Distanz</i> zum Empfangsvektor <u><i>y</i></u> aus:

:<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 E}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})\hspace{0.05cm}, \hspace{0.8cm}
\underline{y} \in R^n\hspace{0.05cm}, \hspace{0.2cm}\underline{x}_{\hspace{0.03cm}i}\in {\rm GF}(2^n) \hspace{0.05cm}.</math>

==Aufgaben zum Kapitel==
<br>
[[Aufgaben:1.3 BSC–BEC–BSEC–AWGN|A1.3 BSC–BEC–BSEC–AWGN]]

[[Aufgaben:1.4 Maximum–Likelihood–Entscheidung|A1.4 Maximum–Likelihood–Entscheidung]]

{{Display}}