Kanalcodierung/Kanalmodelle und Entscheiderstrukturen: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(16 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 9: Zeile 9:
 
== AWGN–Kanal bei binärem Eingang ==
 
== AWGN–Kanal bei binärem Eingang ==
 
<br>
 
<br>
Wir betrachten das bekannte zeitdiskrete [[Modulationsverfahren/Qualit%C3%A4tskriterien#Einige_Anmerkungen_zum_AWGN.E2.80.93Kanalmodell| AWGN&ndash;Kanalmodell]] gemäß der unteren linken Grafik:
+
Wir betrachten das bekannte zeitdiskrete&nbsp; [[Modulationsverfahren/Qualit%C3%A4tskriterien#Einige_Anmerkungen_zum_AWGN.E2.80.93Kanalmodell| AWGN&ndash;Kanalmodell]]&nbsp; gemäß der unteren linken Grafik:
*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>
+
*Das binäre und zeitdiskrete Nachrichtensignal&nbsp; $x$&nbsp; nimmt mit gleicher Wahrscheinlichkeit die Werte&nbsp; $0$&nbsp; und&nbsp; $1$&nbsp; an:
 +
:$${\rm Pr}(x = 0) ={\rm Pr}(x = 1) =  1/2.$$
 +
*Wir transformieren nun die unipolare Variable&nbsp; $x \in \{0,\ 1 \}$&nbsp; in die für die Signalübertragung besser geeignete bipolare Variable&nbsp; $\tilde{x} \in \{+1, -1 \}$.&nbsp; Dann gilt:
 +
[[Datei:P ID2340 KC T 1 2 S1 v2.png|right|frame|Modell und Wahrscheinlichkeitsdichtefunktion (WDF) des AWGN–Kanals|class=fit]]
 +
:$${\rm Pr}(\tilde{x} =+1) ={\rm Pr}(\tilde{x} =-1) = 1/2.$$
 +
*Die Übertragung wird durch&nbsp; [[Digitalsignalübertragung/Systemkomponenten_eines_Basisbandübertragungssystems#.C3.9Cbertragungskanal_und_St.C3.B6rungen| additives weißes gaußverteiltes Rauschen]]&nbsp; (AWGN)&nbsp; $n$&nbsp; mit der (normierten) Rauschleistung&nbsp; $\sigma^2 = N_0/E_{\rm B}$&nbsp; beeinträchtigt. Die Streuung der Gauß&ndash;WDF ist&nbsp; $\sigma$.<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&nbsp; $y = \tilde{x} +n$&nbsp; alle reellen Werte im Bereich von&nbsp; $-\infty$&nbsp; bis&nbsp; $+\infty$&nbsp; annehmen. Der Signalwert&nbsp; $y$&nbsp; ist demzufolge zwar wie&nbsp; $x$&nbsp; &nbsp;$($bzw.  $\tilde{x})$&nbsp; zeitdiskret, im Gegensatz zu diesem aber wertkontinuierlich.<br>
 
+
<br clear=all>
*Aufgrund der Gaußschen WDF kann das Ausgangssignal $y = \tilde{x} +n$ alle reellen Werte im Bereich von $-\infty$ bis $+\infty$ annehmen. Der Signalwert $y$&nbsp; ist demzufolge zwar wie $x$ (bzw.  $\tilde{x})$ zeitdiskret, im Gegensatz zu diesem aber wertkontinuierlich.<br>
+
Die rechte Grafik zeigt&nbsp;  (in blau bzw. rot)&nbsp; die zwei bedingten Wahrscheinlichkeitsdichtefunktionen:
 
 
 
 
[[Datei: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}
 
::<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}
Zeile 26: Zeile 26:
 
\frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e}^{ -  (y+1)^2/(2\sigma^2) }\hspace{0.05cm}.</math>
 
\frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e}^{ -  (y+1)^2/(2\sigma^2) }\hspace{0.05cm}.</math>
  
Nicht dargestellt ist die gesamte (unbedingte) WDF, für die bei gleichwahrscheinlichen Symbolen gilt:
+
Nicht dargestellt ist die gesamte&nbsp; (unbedingte)&nbsp; WDF,&nbsp; 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 ) +   
 
::<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>
 
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ächeninhalte  (jeweils $\varepsilon$) markieren Entscheidungsfehler unter der Voraussetzung $x=0$ &nbsp; &#8658; &nbsp; $\tilde{x} = +1$ (blau) &nbsp; bzw. $x=1$ &nbsp; &#8658; &nbsp; $\tilde{x} = -1$ (rot), wenn harte Entscheidungen getroffen werden:
+
Die beiden schraffierten Flächeninhalte  &nbsp;$($jeweils &nbsp;$\varepsilon)$&nbsp; markieren Entscheidungsfehler unter der Voraussetzung&nbsp;
 +
*$x=0$ &nbsp; &#8658; &nbsp; $\tilde{x} = +1$&nbsp; (blau) &nbsp; bzw. &nbsp;
 +
*$x=1$ &nbsp; &#8658; &nbsp; $\tilde{x} = -1$&nbsp; (rot),&nbsp;
 +
 
 +
 
 +
wenn harte Entscheidungen getroffen werden:
  
 
::<math>z = \left\{ \begin{array}{c} 0\\
 
::<math>z = \left\{ \begin{array}{c} 0\\
Zeile 38: Zeile 43:
 
{\rm falls} \hspace{0.15cm}y < 0\hspace{0.05cm}.\\ \end{array}</math>
 
{\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:
+
Bei gleichwahrscheinlichen Eingangssymbolen ist dann die mittlere Bitfehlerwahrscheinlichkeit&nbsp; ${\rm Pr}(z \ne x)$&nbsp; ebenfalls gleich&nbsp; $\varepsilon$.&nbsp; Mit dem&nbsp; [[Stochastische_Signaltheorie/Gaußverteilte_Zufallsgrößen#.C3.9Cberschreitungswahrscheinlichkeit|komplementären Gaußschen Fehlerintergral]]&nbsp; ${\rm Q}(x)$ gilt dabei:
  
 
::<math>\varepsilon = {\rm Q}(1/\sigma) = {\rm Q}(\sqrt{\rho}) =  
 
::<math>\varepsilon = {\rm Q}(1/\sigma) = {\rm Q}(\sqrt{\rho}) =  
Zeile 44: Zeile 49:
 
\hspace{0.05cm}.</math>
 
\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:
+
Hierbei bezeichnet&nbsp; $\rho = 1/\sigma^2 =  2 \cdot E_{\rm S}/N_0$&nbsp; das Signal&ndash;zu&ndash;Rauschverhältnis&nbsp; $\rm (SNR)$&nbsp; vor dem Entscheider,&nbsp; wobei folgende Systemgrößen verwendet werden:
*$E_{\rm S}$ ist die Signalenergie pro Symbol (ohne Codierung gleich $E_{\rm B}$, also gleich der Signalenergie pro Bit),<br>
+
*$E_{\rm S}$&nbsp; ist die Signalenergie pro Symbol&nbsp; (ohne Codierung gleich &nbsp;$E_{\rm B}$,&nbsp; also gleich der Signalenergie pro Bit),<br>
  
*$N_0$ bezeichnet die konstante (einseitige) Rauschleistungsdichte des AWGN&ndash;Kanals.<br><br>
+
*$N_0$&nbsp; bezeichnet die konstante&nbsp; (einseitige)&nbsp; Rauschleistungsdichte des AWGN&ndash;Kanals.<br><br>
  
''Hinweis'':&nbsp; Der dargelegte Sachverhalt wird mit dem  interaktiven Applet [[Applets:Fehlerwahrscheinlichkeit|Symbolfehlerwahrscheinlichkeit von Digitalsystemen]] verdeutlicht.
+
Hinweis:&nbsp; Der dargelegte Sachverhalt wird mit dem  SWF&ndash;Applet&nbsp; [[Applets:Fehlerwahrscheinlichkeit|"Symbolfehlerwahrscheinlichkeit von Digitalsystemen"]]&nbsp; verdeutlicht.
  
 
== Binary Symmetric Channel – BSC ==
 
== Binary Symmetric Channel – BSC ==
 
<br>
 
<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>
+
Das AWGN&ndash;Kanalmodell ist kein digitales Kanalmodell,&nbsp;  wie wir es im Abscnitt&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Blockschaltbild_und_Voraussetzungen|"Blockschaltbild und Voraussetzungen"]]&nbsp; zur Einführung der Kanalcodierverfahren vorausgesetzt haben.&nbsp; Berücksichtigen wir aber eine harte Entscheidung,&nbsp; so kommen wir zum digitalen Modell&nbsp; "Binary Symmetric Channel"&nbsp; $\rm (BSC)$:<br>
 +
 
 +
[[Datei:P ID2341 KC T 1 2 S2 v2.png|right|frame|BSC–Modell und Zusammenhang mit dem AWGN–Modell<br> <u>Hinweis:</u>&nbsp; Beim AWGN&ndash;Modell haben wir die binäre Ausgangsgröße mit&nbsp; $z \in \{0, \hspace{0.05cm}1\}$&nbsp; bezeichnet.&nbsp; Bei den digitalen Kanalmodellen&nbsp; (BSC, BEC, BSEC)&nbsp; bezeichnen wir nun den wertdiskreten Ausgang wieder mit&nbsp; $y$.&nbsp; Um Verwechslungen zu vermeiden, nennen wir im Folgenden das Ausgangssignal des AWGN&ndash;Modells&nbsp; $y_{\rm A}$,&nbsp; und für das analoge Empfangssignal gilt dann&nbsp; $y_{\rm A} = \tilde{x} +n$.<br>|class=fit]]
  
[[Datei:P ID2341 KC T 1 2 S2 v2.png|center|frame|BSC–Modell und Zusammenhang mit dem AWGN–Modell|class=fit]]
+
*Wir wählen die beiden Verfälschungswahrscheinlichkeiten&nbsp; ${\rm Pr}(y = 1\hspace{0.05cm}|\hspace{0.05cm} x=0)$&nbsp;  bzw.&nbsp; ${\rm Pr}(y = 0\hspace{0.05cm}|\hspace{0.05cm} x=1)$&nbsp; jeweils zu
  
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>
  
::<math>\varepsilon = {\rm Q}(\sqrt{\rho})\hspace{0.05cm},</math>
+
*Damit ist der Zusammenhang zum&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang |AWGN&ndash;Kanalmodell]]&nbsp; hergestellt.&nbsp;
  
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>
+
*Die Entscheidungsgrenze liegt bei&nbsp; $G = 0$,&nbsp; wodurch auch die Eigenschaft &bdquo;symmetrisch&rdquo; begründet ist.<br>
  
<i>Hinweis:</i>&nbsp; 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>
+
Das BSC&ndash;Modell liefert eine statistisch unabhängige Fehlerfolge und eignet sich somit zur Modellierung gedächtnisloser rückkopplungsfreier Kanäle,&nbsp; 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
+
Zur Beschreibung gedächtnisbehafteter Kanäle müssen andere Modelle herangezogen werden,&nbsp; die im fünften Hauptkapitel  des Buches &bdquo;Digitalsignalübertragung&rdquo; behandelt werden,&nbsp; zum Beispiel die Bündelfehlerkanäle entsprechend
*dem [[Digitalsignalübertragung/Bündelfehlerkanäle#Kanalmodell_nach_Gilbert.E2.80.93Elliott| Gilbert&ndash;Elliott&ndash;Modell]],<br>
+
*dem&nbsp; [[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>
+
*dem&nbsp; [[Digitalsignalübertragung/Bündelfehlerkanäle#Kanalmodell_nach_McCullough| McCullough&ndash;Modell]].<br><br>
 +
 
 +
{{GraueBox|TEXT=
 +
[[Datei:P ID2342 KC T 1 2 S2b.png|right|frame|Statistisch unabhängige Fehler (links) und Bündelfehler (rechts) |class=fit]]
 +
$\text{Beispiel 1:}$&nbsp;  Die Abbildung zeigt
 +
*das Originalbild in der Mitte,
 +
 
 +
*statistisch unabhängige Fehler nach dem BSC&ndash;Modell&nbsp; (links),
 +
 
 +
*so genannte Bündelfehler gemäß Gilbert&ndash;Elliott&nbsp; (rechts).
  
[[Datei: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&nbsp; $10\%$.
  
Die Bitfehlerrate beträgt in beiden Fällen $10\%$. Aus der rechten Grafik ist zu erkennen, dass das Bild zeilenweise übertragen wird.}}<br>
+
Aus der rechten Grafik ist anhand der Bündelfehlerstruktur zu erkennen,&nbsp; dass das Bild zeilenweise übertragen wurde.}}<br>
  
 
== Binary Erasure Channel – BEC ==
 
== Binary Erasure Channel – BEC ==
 
<br>
 
<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>
+
Das BSC&ndash;Modell liefert nur die Aussagen &bdquo;richtig&rdquo; und &bdquo;falsch&rdquo;.&nbsp; Manche Empfänger &ndash; so zum Beispiel die so genannten&nbsp; [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Hard_Decision_vs._Soft_Decision|"Soft&ndash;in Soft&ndash;out Decoder"]]&nbsp; &ndash; können jedoch auch gewisse Informationen über die Sicherheit der Entscheidung liefern,&nbsp; wobei sie natürlich darüber informiert werden müssen,&nbsp; welche ihrer Eingangswerte sicher sind und welche eher unsicher.<br>
 +
 
 +
Der&nbsp; "Binary Erasure Channel"&nbsp; $\rm (BEC)$&nbsp; liefert eine solche Information.&nbsp; Anhand der Grafik erkennt man:
 +
[[Datei:P ID2343 KC T 1 2 S3 v2.png|right|frame|BEC und Zusammenhang mit dem AWGN–Modell|class=fit]]
 +
*Das Eingangsalphabet des BEC&ndash;Modells 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\}$.
  
[[Datei:P ID2343 KC T 1 2 S3 v2.png|center|frame|Binary Erasure Channel (BEC) und Zusammenhang mit dem AWGN–Modell|class=fit]]
+
*Ein&nbsp; "$\rm E$"&nbsp; kennzeichnet eine unsichere Entscheidung.&nbsp; Dieses neue &bdquo;Symbol&rdquo; steht für&nbsp; "Erasure",&nbsp; zu deutsch: &nbsp;Auslöschung.
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 $\rm E$ 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 $\rm (E)$ wird mit der Wahrscheinlichkeit $\lambda$ getroffen, während die Wahrscheinlichkeit für  eine richtige (und gleichzeitig sichere) Entscheidung $1-\lambda$ beträgt.
+
*Bitfehler werden durch das BEC&ndash;Modell per se ausgeschlossen.&nbsp; Eine unsichere Entscheidung&nbsp; $\rm (E)$&nbsp; wird mit Wahrscheinlichkeit&nbsp; $\lambda$&nbsp; getroffen,&nbsp; während die Wahrscheinlichkeit für  eine richtige&nbsp; (und gleichzeitig sichere)&nbsp; Entscheidung&nbsp; $1-\lambda$&nbsp; beträgt.
  
*Rechts oben ist der Zusammenhang zwischen BEC&ndash; und AWGN&ndash;Kanalmodell dargestellt, wobei das Erasure&ndash;Entscheidungsgebiet $\rm (E)$ grau hinterlegt ist. Im Gegensatz zum BSC&ndash;Modell gibt es nun zwei Entscheidungsgrenzen $G_0 = G$ &nbsp;und&nbsp; $G_1 = -G$ gibt. Es gilt:
+
*Rechts oben ist der Zusammenhang zwischen BEC&ndash; und AWGN&ndash;Modell dargestellt, wobei das Erasure&ndash;Entscheidungsgebiet&nbsp; $\rm (E)$&nbsp; grau hinterlegt ist.  
  
::<math>\lambda =  {\rm Q}[\sqrt{\rho} \cdot (1 - G)]\hspace{0.05cm}.</math>
+
*Im Gegensatz zum BSC gibt es nun zwei Entscheidungsgrenzen,&nbsp; nämlich&nbsp; $G_0 = G$ &nbsp;und symmetrisch dazu&nbsp; $G_1 = -G$.&nbsp; Es gilt:
 +
 
 +
::<math>\lambda =  {\rm Q}\big[\sqrt{\rho} \cdot (1 - G)\big]\hspace{0.05cm}.</math>
  
 
Wir weisen hier nochmals auf die folgenden Applets hin:  
 
Wir weisen hier nochmals auf die folgenden Applets hin:  
 
*[[Applets:Fehlerwahrscheinlichkeit|Symbolfehlerwahrscheinlichkeit von Digitalsystemen]],
 
*[[Applets:Fehlerwahrscheinlichkeit|Symbolfehlerwahrscheinlichkeit von Digitalsystemen]],
*[[Applets:Komplementäre_Gaußsche_Fehlerfunktionen_(Applet)|Komplementäre Gaußsche Fehlerfunktion]].
+
*[[Applets:Komplementäre_Gaußsche_Fehlerfunktionen|Komplementäre Gaußsche Fehlerfunktion]].
  
 
   
 
   
 
== Binary Symmetric Error & Erasure Channel – BSEC ==
 
== Binary Symmetric Error & Erasure Channel – BSEC ==
 
<br>
 
<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$.  
+
Das BEC&ndash;Modell &nbsp;$($Kennzeichen:&nbsp; Fehlerwahrscheinlichkeit $0)$&nbsp; ist eher unrealistisch und nur eine Näherung für ein extrem großes Signal&ndash;zu&ndash;Rausch&ndash;Leistungsverhältnis&nbsp; $\rho$.&nbsp; Stärkere Störungen&nbsp; $($das heißt,&nbsp; ein kleineres&nbsp; $\rho)$&nbsp; sollten besser durch den&nbsp; "Binary Symmetric Error & Erasure Channel"&nbsp; $\rm (BSEC)$&nbsp; mit den zwei Parametern
 
 
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 &nbsp; $\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>
 
*Verfälschungswahrscheinlichkeit &nbsp; $\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>
  
Zeile 110: Zeile 123:
  
  
modelliert werden. Wie beim BEC&ndash;Modell gilt auch hier $x &#8712; \{0, \hspace{0.05cm}1\}$ &nbsp;und&nbsp; $y &#8712; \{0, \hspace{0.05cm}1, \hspace{0.05cm}\rm E\}$.<br>
+
modelliert werden.&nbsp; Wie beim BEC&ndash;Modell gilt auch hier&nbsp; $x &#8712; \{0, \hspace{0.05cm}1\}$ &nbsp;und&nbsp; $y &#8712; \{0, \hspace{0.05cm}1, \hspace{0.05cm}\rm E\}$.<br>
  
[[Datei:KC_T_1_2_S4_version2.png|center|frame|Binary Symmetric Error & Erasure Channel (BSEC) & Zusammenhang mit dem AWGN–Modell|class=fit]]
+
{{GraueBox|TEXT= 
 +
$\text{Beispiel 2:}$&nbsp;  Wir betrachten das BSEC&ndash;Modell mit den beiden Entscheidungsgeraden&nbsp; (symmetrisch um den Nullpunkt)
 +
[[Datei:KC_T_1_2_S4_version2.png|right|frame|Binary Symmetric Error & Erasure Channel (BSEC) & Zusammenhang mit dem AWGN–Modell|class=fit]]
 +
*$G_0 = G = 0.5$,&nbsp;
 +
*$G_1 = -G = -0.5$.
  
{{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}\big[\sqrt{\rho} \cdot (1 + G)\big] = {\rm Q}(3) \approx 0.14\%\hspace{0.05cm},\hspace{0.6cm}
 
{\it \lambda} =  {\rm Q}\big[\sqrt{\rho} \cdot (1 - G)\big] -  \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$:
+
Dessen Modellparameter&nbsp; $\varepsilon$&nbsp; und&nbsp; $\lambda$&nbsp; werden durch das&nbsp;  $\rm SNR$&nbsp; $\rho=1/\sigma^2$&nbsp; des vergleichbaren AWGN&ndash;Kanals festgelegt.
 +
 
 +
*Für die rechts skizzierte WDF gilt&nbsp; $\sigma = 0.5$  &nbsp; &#8658; &nbsp; $\rho = 4$:
 +
:$$\varepsilon = {\rm Q}\big[\sqrt{\rho} \cdot (1 + G)\big] = {\rm Q}(3) \approx 0.14\%\hspace{0.05cm},$$
 +
:$${\it \lambda} =  {\rm Q}\big[\sqrt{\rho} \cdot (1 - G)\big] -  \varepsilon = {\rm Q}(1) - {\rm Q}(3) $$
 +
:$$\Rightarrow \hspace{0.3cm}{\it \lambda}  \approx 15.87\% -  0.14\% = 15.73\%\hspace{0.05cm},$$
 +
 
 +
*Für&nbsp; $\sigma = 0.25$  &nbsp; &#8658; &nbsp; $\rho = 16$&nbsp; ergeben sich folgende Parameter:
  
::<math>\varepsilon  = {\rm Q}(6) \approx 10^{-10}\hspace{0.05cm},\hspace{0.6cm}
+
:$$\varepsilon  = {\rm Q}(6) \approx 10^{-10}\hspace{0.05cm},$$
{\it \lambda} = {\rm Q}(2)  \approx 2.27\%\hspace{0.05cm}.</math>
+
:$${\it \lambda} = {\rm Q}(2)  \approx 2.27\%\hspace{0.05cm}.$$
  
Für die rechts dargestellte WDF wurde $\rho = 4$ vorausgesetzt. Für$\rho = 16$ könnte das BSEC&ndash;Modell durch die einfachere BEC&ndash;Variante ersetzt werden, ohne dass es zu gravierenden Unterschieden kommt.}}<br>
+
:Hier könnte das BSEC&ndash;Modell durch die einfachere BEC&ndash;Variante ersetzt werden,&nbsp; ohne dass es zu gravierenden Unterschieden kommt.}}<br>
  
 
== Maximum-a-posteriori– und Maximum-Likelihood–Kriterium ==
 
== Maximum-a-posteriori– und Maximum-Likelihood–Kriterium ==
 
<br>
 
<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>
+
Wir gehen nun von dem nachfolgend skizzierten Modell aus und wenden die bereits im Kapitel&nbsp; [[Digitalsignal%C3%BCbertragung/Struktur_des_optimalen_Empf%C3%A4ngers|"Struktur des optimalen Empfängers"]]&nbsp; des Buches &bdquo;Digitalsignalübertragung&rdquo; genannten Entscheidungskriterien auf den Decodiervorgang an.<br>
 
 
[[Datei: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=
 +
[[Datei:P ID2345 KC T 1 2 S5 v2.png|right|frame|Modell zur Beschreibung von MAP– und ML–Decodierung|class=fit]] 
 +
$\text{Aufgabe des Kanaldecoders}$&nbsp;
 +
ist es,&nbsp; den Vektor&nbsp; $\underline{v}$&nbsp; so zu bestimmen,&nbsp; dass dieser &bdquo;möglichst gut&rdquo; mit dem Informationswort&nbsp; $\underline{u}$&nbsp; übereinstimmt.  
  
{{BlaueBox|TEXT= 
+
Etwas genauer formuliert:  
$\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.  
+
*Minimierung der&nbsp; '''Blockfehlerwahrscheinlichkeit'''&nbsp; ${\rm Pr(Blockfehler)} = {\rm Pr}(\underline{v} \ne \underline{u}) $&nbsp; bezogen auf die Vektoren&nbsp; $\underline{u}$&nbsp; und&nbsp; $\underline{v}$,&nbsp; jeweils der Länge&nbsp; $k$.&nbsp; 
  
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:
+
*Wegen  der gleichen Zuordnung&nbsp; $\underline{x} = {\rm enc}(\underline{u})$&nbsp; des Kanalcoders und&nbsp; $\underline{v} = {\rm enc}^{-1}(\underline{z})$&nbsp; des Kanaldecoders gilt in gleicher Weise:
  
 
::<math>{\rm Pr(Blockfehler)} = {\rm Pr}(\underline{z} \ne \underline{x})\hspace{0.05cm}. </math>}}
 
::<math>{\rm Pr(Blockfehler)} = {\rm Pr}(\underline{z} \ne \underline{x})\hspace{0.05cm}. </math>}}
Zeile 144: Zeile 164:
  
 
Der Kanaldecoder in obigem Modell besteht aus zwei Teilen:
 
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>
+
*Der&nbsp; "Codewortschätzer"&nbsp; ermittelt aus dem Empfangsvektor&nbsp; $\underline{y}$&nbsp; einen Schätzwert&nbsp; $\underline{z} \in \mathcal{C}$&nbsp; 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>
+
*Aus dem (empfangenen) Codewort&nbsp; $\underline{z}$&nbsp; wird das Informationswort&nbsp; $\underline{v}$&nbsp; durch&nbsp; "einfaches Mapping"&nbsp; ermittelt.&nbsp; Dieses sollte mit&nbsp; $\underline{u}$&nbsp; übereinstimmen.<br><br>
  
 
Für den Codewortschätzer gibt es insgesamt vier unterschiedliche Varianten, nämlich
 
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 das gesamte Codewort&nbsp; $\underline{x}$,<br>
 
+
#den Maximum&ndash;a&ndash;posteriori&ndash;Empfänger für die einzelnen Codebits&nbsp; $x_i$,<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&nbsp; (ML&ndash;Empfänger)&nbsp; für das gesamte Codewort&nbsp; $\underline{x}$,<br>
 
+
#den Maximum&ndash;Likelihood&ndash;Empfänger  für die einzelnen Codebits&nbsp; $x_i$.<br><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:
+
Deren Definitionen folgen auf der nächsten Seite.&nbsp; Vorab aber gleich das wesentliche Unterscheidungsmerkmal zwischen&nbsp; $\rm MAP$&nbsp; und&nbsp; $\rm ML$:
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
 
$\text{Fazit:}$&nbsp;   
 
$\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>
+
*Ein&nbsp; '''MAP&ndash;Empfänger'''&nbsp; berücksichtigt 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>
+
*Sind alle  Codeworte&nbsp; $\underline{x}$&nbsp; und damit auch alle Bits&nbsp; $x_i$&nbsp; der Codeworte gleichwahrscheinlich,&nbsp; so ist der einfachere&nbsp; '''ML&ndash;Empfänger'''&nbsp; äquivalent zum MAP&ndash;Empfänger.}}<br><br>
  
 
== Definitionen der verschiedenen Optimalempfänger ==
 
== Definitionen der verschiedenen Optimalempfänger ==
 
<br>
 
<br>
 
{{BlaueBox|TEXT=   
 
{{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):
+
$\text{Definition:}$&nbsp; Der&nbsp; "Maximum&ndash;a&ndash;posteriori&ndash;Empfänger auf Blockebene"&nbsp; &ndash; kurz: &nbsp;<b>block&ndash;wise MAP</b> &ndash;  entscheidet sich unter den&nbsp; $2^k$&nbsp; Codeworten&nbsp; $\underline{x}_i \in \mathcal{C}$&nbsp; für das Codewort mit der größten Rückschlusswahrscheinlichkeit&nbsp; $($englisch: &nbsp; "a&ndash;posteriori probability",&nbsp; $\rm 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>
 
::<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>
+
*${\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm}\vert \hspace{0.05cm} \underline{y} )$&nbsp; ist die&nbsp; [[Stochastische_Signaltheorie/Statistische_Abh%C3%A4ngigkeit_und_Unabh%C3%A4ngigkeit#Bedingte_Wahrscheinlichkeit| '''bedingte Wahrscheinlichkeit''']], dass&nbsp; $\underline{x}_i$&nbsp; gesendet wurde,&nbsp; wenn&nbsp; $\underline{y}$&nbsp; 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:
+
Wir versuchen nun,&nbsp; diese Entscheidungsregel schrittweise zu vereinfachen.&nbsp; Die&nbsp; '''Rückschlusswahrscheinlichkeit'''&nbsp; kann  nach dem &bdquo;Satz von Bayes&rdquo; umgeformt werden:
  
 
::<math>{\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm}\vert \hspace{0.05cm} \underline{y} ) =  
 
::<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>
 
  \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>
+
*Die Wahrscheinlichkeit&nbsp; ${\rm Pr}( \underline{y}) $&nbsp; ist unabhängig von&nbsp; $\underline{x}_i$&nbsp; und muss bei der Maximierung nicht berücksichtigt werden.  
 +
*Sind zudem alle&nbsp; $2^k$&nbsp; Informationsworte&nbsp; $\underline{u}_i$&nbsp; gleichwahrscheinlich,&nbsp; so kann man bei der Maximierung auch auf den Beitrag&nbsp; ${\rm Pr}( \underline{x}_{\hspace{0.03cm}i}  ) = 2^{-k}$&nbsp; im Zähler verzichten.<br>
 +
 
  
 
{{BlaueBox|TEXT=   
 
{{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:
+
$\text{Definition:}$&nbsp;  Der&nbsp; "Maximum&ndash;Likelihood&ndash;Empfänger  auf Blockebene"&nbsp; &ndash; kurz: &nbsp;'''block&ndash;wise ML'''&nbsp; &ndash; entscheidet sich unter den&nbsp; $2^k$&nbsp; zulässigen Codeworten&nbsp; $\underline{x}_i \in \mathcal{C}$&nbsp; für das Codewort mit der größten&nbsp; '''Ü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>
 
::<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>
+
*Die bedingte Wahrscheinlichkeit&nbsp; ${\rm Pr}( \underline{y}  \hspace{0.05cm}\vert\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} )$&nbsp; ist nun in Vorwärtsrichtung zu verstehen,&nbsp; nämlich als die Wahrscheinlichkeit,&nbsp; dass der Vektor&nbsp; $\underline{y}$&nbsp; empfangen wird,&nbsp; wenn das Codewort&nbsp; $\underline{x}_i$&nbsp; 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>
+
*Im Folgenden verwenden wir auf Blockebene stets den Maximum&ndash;Likelihood&ndash;Empfänger.&nbsp; 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>
+
Anders sieht es jedoch auf Bitebene aus.&nbsp; Ziel einer iterativen Decodierung ist es gerade,&nbsp; für alle Codebits&nbsp; $x_i \in  \{0, 1\}$&nbsp; Wahrscheinlichkeiten zu schätzen und diese an die nächste Stufe weiterzugeben.&nbsp; Hierzu benötigt man einen MAP&ndash;Empfänger.<br>
  
 
{{BlaueBox|TEXT=   
 
{{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} )$:
+
$\text{Definition:}$&nbsp;  Der&nbsp; "Maximum&ndash;a&ndash;posteriori&ndash;Empfänger auf Bitebene"&nbsp; &ndash; kurz:&nbsp; '''bit&ndash;wise MAP''' &ndash; wählt für jedes einzelne Codebit&nbsp; $x_i$&nbsp; den Wert &nbsp;$(0$ oder $1)$&nbsp; mit der größten Rückschlusswahrscheinlichkeit&nbsp; ${\rm Pr}( {x}_{\hspace{0.03cm}i}\vert \hspace{0.05cm} \underline{y} )$&nbsp; aus:
  
:<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>
+
::<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 ==
 
== Maximum-Likelihood–Entscheidung beim BSC–Kanal ==
 
<br>
 
<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:
+
Wir wenden nun das Maximum&ndash;Likelihood&ndash;Kriterium auf den gedächtnislosen&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|BSC&ndash;Kanal]]&nbsp; an.&nbsp; Dann gilt:
 
::<math>{\rm Pr}( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} ) =
 
::<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}
+
\prod\limits_{l=1}^{n} {\rm Pr}( y_l  \hspace{0.05cm}|\hspace{0.05cm} x_l ) \hspace{0.4cm}{\rm mit}\hspace{0.4cm}
 
{\rm Pr}( y_l  \hspace{0.05cm}|\hspace{0.05cm} x_l ) =  
 
{\rm Pr}( y_l  \hspace{0.05cm}|\hspace{0.05cm} x_l ) =  
 
  \left\{ \begin{array}{c} 1 - \varepsilon\\
 
  \left\{ \begin{array}{c} 1 - \varepsilon\\
Zeile 214: Zeile 233:
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Beweis:}$&nbsp;  Dies lässt sich wie folgt begründen:
+
$\text{Beweis:}$&nbsp;  Dieses Ergebnis 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>
+
*Die&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming&ndash;Distanz]]&nbsp; $d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})$&nbsp; gibt die Anzahl der Bitpositionen an,&nbsp; in denen sich die Worte&nbsp; $\underline{y}$&nbsp; und&nbsp; $\underline{x}_{\hspace{0.03cm}i}$&nbsp; mit jeweils&nbsp; $n$&nbsp; binären Elementen unterscheiden. Beispiel: &nbsp; Die Hamming&ndash;Distanz zwischen&nbsp; $\underline{y}= (0, 1, 0, 1, 0, 1, 1)$ &nbsp; und &nbsp; $\underline{x}_{\hspace{0.03cm}i} = (0, 1, 0, 0, 1, 1, 1)$&nbsp; ist&nbsp; $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>
+
*In&nbsp; $n - d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})$&nbsp; Positionen unterscheiden sich demnach die beiden Vektoren&nbsp; $\underline{y}$&nbsp; und&nbsp; $\underline{x}_{\hspace{0.03cm}i}$&nbsp; nicht.&nbsp; Im obigen Beispiel sind fünf der&nbsp; $n = 7$&nbsp; Bit identisch.
 +
 +
*Zu obiger Gleichung kommt man schließlich durch Einsetzen der Verfälschungswahrscheinlichkeit&nbsp; $\varepsilon$&nbsp; bzw. deren Ergänzung&nbsp; $1-\varepsilon$.}}<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:
+
Die Vorgehensweise bei der Maximum&ndash;Likelihood&ndash;Detektion ist,&nbsp; dasjenige Codewort&nbsp; $\underline{x}_{\hspace{0.03cm}i}$&nbsp; zu finden,&nbsp; das die Übergangswahrscheinlichkeit&nbsp; ${\rm Pr}( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{x}_{\hspace{0.03cm}i} )$&nbsp; 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}  
 
::<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}  
Zeile 230: Zeile 251:
  
 
::<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
 
::<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 [  
+
L(\underline{x}_{\hspace{0.03cm}i})\hspace{0.5cm} {\rm mit}\hspace{0.5cm} L(\underline{x}_{\hspace{0.03cm}i})  = \ln \left [  
 
\varepsilon^{d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})} \cdot
 
\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})}
 
(1-\varepsilon)^{n-d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})}
 
\right ] </math>
 
\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  
 
::<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} \varepsilon + \big [n -d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})\big ] \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) = \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} (1- \varepsilon)
Zeile 241: Zeile 262:
  
 
Hierbei ist zu berücksichtigen:
 
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.  
+
*Der zweite Term dieser Gleichung ist unabhängig von&nbsp; $\underline{x}_{\hspace{0.03cm}i}$&nbsp; 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>
+
*Auch der Faktor vor der Hamming&ndash;Distanz ist für alle&nbsp; $\underline{x}_{\hspace{0.03cm}i}$&nbsp; gleich.
 +
 +
*Da&nbsp; $\ln \, {\varepsilon}/(1-\varepsilon)$&nbsp; negativ ist (zumindest für&nbsp; $\varepsilon <0.5$, was ohne große Einschränkung vorausgestzt werden kann),&nbsp; wird aus der Maximierung eine Minimierung,&nbsp; und man erhält folgendes Endergebnis:<br>
  
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{ML-Entscheidung beim BSC-Kanal:}$&nbsp;  
+
$\text{Maximum&ndash;Likelihood-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:
+
 
 +
Wähle von den&nbsp; $2^k$&nbsp; zulässigen Codeworten&nbsp; $\underline{x}_{\hspace{0.03cm}i}$&nbsp; dasjenige mit der&nbsp; '''geringsten Hamming&ndash;Distanz'''&nbsp; $d_{\rm H}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})$&nbsp; zum Empfangsvektor&nbsp; $\underline{y}$&nbsp; 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}
 
::<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}
 
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>}}
 
\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:
 
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>
+
*[[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Single_Parity.E2.80.93check_Codes|"Single Parity&ndash;check Code"]]&nbsp; $\rm (SPC)$<br>
  
*[[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|Wiederholungscode]] (englisch: <i>Repetition Code</i>, RC).<br>
+
*[[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|"Wiederholungscode"]]&nbsp; $($englisch: &nbsp; "Repetition Code",&nbsp; $\rm RC)$.<br>
  
 
== Maximum-Likelihood–Entscheidung beim AWGN–Kanal ==
 
== Maximum-Likelihood–Entscheidung beim AWGN–Kanal ==
 
<br>
 
<br>
Das AWGN&ndash;Modell für einen $(n, k)$&ndash;Blockcode unterscheidet sich vom [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang| Modell]] auf der ersten Seite dieses Kapitels dadurch, dass für $x$, $\tilde{x}$ und $y$ nun die entsprechenden Vektoren $\underline{x}$, $\underline{\tilde{x}}$ und $\underline{y}$ verwendet werden müssen, jeweils bestehend aus $n$ Elementen.  
+
Das AWGN&ndash;Modell für einen&nbsp; $(n, k)$&ndash;Blockcode unterscheidet sich vom&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang| Modell]]&nbsp; auf der ersten Kapitelseite dadurch,&nbsp; dass für&nbsp; $x$, &nbsp;$\tilde{x}$&nbsp; und &nbsp;$y$&nbsp; nun die entsprechenden Vektoren&nbsp; $\underline{x}$, &nbsp;$\underline{\tilde{x}}$&nbsp; und &nbsp;$\underline{y}$&nbsp; verwendet werden müssen,&nbsp; jeweils bestehend aus&nbsp; $n$&nbsp; Elementen.  
  
Die Schritte zur Herleitung des ML&ndash;Entscheiders bei AWGN werden nachfolgend nur stichpunktartig angegeben:
+
Die Schritte zur Herleitung des Maximum&ndash;Likelihood&ndash;Entscheiders bei AWGN werden nachfolgend nur stichpunktartig angegeben:
*Der AWGN&ndash;Kanal ist per se gedächtnislos (hierfür steht das &bdquo;White&rdquo; im Namen), so dass für die bedingte Wahrscheinlichkeitsdichtefunktion geschrieben werden kann:
+
*Der AWGN&ndash;Kanal ist per se gedächtnislos&nbsp; (hierfür steht das &bdquo;White&rdquo; im Namen).&nbsp; Für die bedingte Wahrscheinlichkeitsdichtefunktion kann somit geschrieben werden:
  
 
::<math>f( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{\tilde{x}} ) =
 
::<math>f( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{\tilde{x}} ) =
Zeile 270: Zeile 295:
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
*Die bedingte WDF ist für jedes einzelne Codeelement $(l = 1, \text{...} , n)$ ''gaußisch''. Damit genügt auch die gesamte WDF einer (eindimensionalen) Gaußverteilung:
+
*Die bedingte WDF ist für jedes einzelne Codeelement&nbsp; $(l = 1, \hspace{0.05cm}\text{...} \hspace{0.05cm}, n)$&nbsp; "gaußisch".&nbsp; Damit genügt auch die gesamte WDF einer&nbsp; (eindimensionalen)&nbsp; Gaußverteilung:
  
 
::<math>f({y_l \hspace{0.03cm}| \hspace{0.03cm}\tilde{x}_l }) =  
 
::<math>f({y_l \hspace{0.03cm}| \hspace{0.03cm}\tilde{x}_l }) =  
Zeile 279: Zeile 304:
 
  \right ] \hspace{0.05cm}.</math>
 
  \right ] \hspace{0.05cm}.</math>
  
*Da $\underline{y}$ 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:
+
*Da&nbsp; $\underline{y}$&nbsp; nun nicht mehr wie beim BSC&ndash;Modell wertdiskret ist,&nbsp; sondern wertkontinuierlich,&nbsp; müssen jetzt nach der ML&ndash;Entscheidungsregel&nbsp; Wahrscheinlichkeitsdichten&nbsp; untersucht werden und nicht mehr Wahrscheinlichkeiten.&nbsp; 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}
 
::<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
Zeile 285: Zeile 310:
 
\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>
 
\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 $\underline{y}$ und $\underline{\tilde{x}}$ im $n$&ndash;dimensionalen Raum als die [https://de.wikipedia.org/wiki/Euklidischer_Abstand Euklidische Distanz], benannt nach dem griechischen Mathematiker [https://de.wikipedia.org/wiki/Euklid Euklid], der im dritten Jahrhundert vor Christus lebte:
+
*In der Algebra bezeichnet man den Abstand zweier Punkte&nbsp; $\underline{y}$&nbsp; und&nbsp; $\underline{\tilde{x}}$&nbsp; im&nbsp; $n$&ndash;dimensionalen Raum als die&nbsp; [https://de.wikipedia.org/wiki/Euklidischer_Abstand Euklidische Distanz],&nbsp; benannt nach dem griechischen Mathematiker&nbsp; [https://de.wikipedia.org/wiki/Euklid Euklid],&nbsp; der im dritten Jahrhundert vor Christus lebte:
  
 
::<math>d_{\rm E}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{\tilde{x}}) =
 
::<math>d_{\rm E}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{\tilde{x}}) =
Zeile 292: Zeile 317:
 
\hspace{0.05cm}.</math>
 
\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 $f( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{\tilde{x}_i} )$ konstant ist:
+
*Damit lautet die ML&ndash;Entscheidungsregel beim AWGN&ndash;Kanal für einen jeden Blockcode unter Berücksichtigung der Tatsache,&nbsp; dass der erste Faktor der WDF&nbsp; $f( \underline{y}  \hspace{0.05cm}|\hspace{0.05cm} \underline{\tilde{x}_i} )$&nbsp; 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}
 
::<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm}
Zeile 302: Zeile 327:
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{ML-Entscheidung beim AWGN-Kanal:}$&nbsp;  
+
$\text{Maximum&ndash;Likelihood-Entscheidung beim AWGN-Kanal:}$&nbsp;
Wähle von den $2^k$ zulässigen Codeworten $\underline{x}_{\hspace{0.03cm}i}$ dasjenige mit der <i>kleinsten Euklidischen Distanz</i> $d_{\rm E}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})$ zum Empfangsvektor  $\underline{y}$ aus:
+
 +
Wähle von den&nbsp; $2^k$&nbsp; zulässigen Codeworten&nbsp; $\underline{x}_{\hspace{0.03cm}i}$&nbsp; dasjenige mit der&nbsp; '''kleinsten Euklidischen Distanz'''&nbsp; $d_{\rm E}(\underline{y}  \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})$&nbsp; zum Empfangsvektor  &nbsp;$\underline{y}$&nbsp; 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}
 
::<math>\underline{z} = {\rm arg} \min_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C} } \hspace{0.1cm}

Aktuelle Version vom 12. Juni 2022, 13:29 Uhr


AWGN–Kanal bei binärem Eingang


Wir betrachten das bekannte zeitdiskrete  AWGN–Kanalmodell  gemäß der unteren linken Grafik:

  • Das binäre und zeitdiskrete Nachrichtensignal  $x$  nimmt mit gleicher Wahrscheinlichkeit die Werte  $0$  und  $1$  an:
$${\rm Pr}(x = 0) ={\rm Pr}(x = 1) = 1/2.$$
  • Wir transformieren nun die unipolare Variable  $x \in \{0,\ 1 \}$  in die für die Signalübertragung besser geeignete bipolare Variable  $\tilde{x} \in \{+1, -1 \}$.  Dann gilt:
Modell und Wahrscheinlichkeitsdichtefunktion (WDF) des AWGN–Kanals
$${\rm Pr}(\tilde{x} =+1) ={\rm Pr}(\tilde{x} =-1) = 1/2.$$
  • Die Übertragung wird durch  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ß–WDF ist  $\sigma$.
  • Aufgrund der Gaußschen WDF kann das Ausgangssignal  $y = \tilde{x} +n$  alle reellen Werte im Bereich von  $-\infty$  bis  $+\infty$  annehmen. Der Signalwert  $y$  ist demzufolge zwar wie  $x$   $($bzw. $\tilde{x})$  zeitdiskret, im Gegensatz zu diesem aber wertkontinuierlich.


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

\[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 {\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}.\]

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

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

Die beiden schraffierten Flächeninhalte  $($jeweils  $\varepsilon)$  markieren Entscheidungsfehler unter der Voraussetzung 

  • $x=0$   ⇒   $\tilde{x} = +1$  (blau)   bzw.  
  • $x=1$   ⇒   $\tilde{x} = -1$  (rot), 


wenn harte Entscheidungen getroffen werden:

\[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}\]

Bei gleichwahrscheinlichen Eingangssymbolen ist dann die mittlere Bitfehlerwahrscheinlichkeit  ${\rm Pr}(z \ne x)$  ebenfalls gleich  $\varepsilon$.  Mit dem  komplementären Gaußschen Fehlerintergral  ${\rm Q}(x)$ gilt dabei:

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

Hierbei bezeichnet  $\rho = 1/\sigma^2 = 2 \cdot E_{\rm S}/N_0$  das Signal–zu–Rauschverhältnis  $\rm (SNR)$  vor dem Entscheider,  wobei folgende Systemgrößen verwendet werden:

  • $E_{\rm S}$  ist die Signalenergie pro Symbol  (ohne Codierung gleich  $E_{\rm B}$,  also gleich der Signalenergie pro Bit),
  • $N_0$  bezeichnet die konstante  (einseitige)  Rauschleistungsdichte des AWGN–Kanals.

Hinweis:  Der dargelegte Sachverhalt wird mit dem SWF–Applet  "Symbolfehlerwahrscheinlichkeit von Digitalsystemen"  verdeutlicht.

Binary Symmetric Channel – BSC


Das AWGN–Kanalmodell ist kein digitales Kanalmodell,  wie wir es im Abscnitt  "Blockschaltbild und Voraussetzungen"  zur Einführung der Kanalcodierverfahren vorausgesetzt haben.  Berücksichtigen wir aber eine harte Entscheidung,  so kommen wir zum digitalen Modell  "Binary Symmetric Channel"  $\rm (BSC)$:

BSC–Modell und Zusammenhang mit dem AWGN–Modell
Hinweis:  Beim AWGN–Modell haben wir die binäre Ausgangsgröße 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 im Folgenden das Ausgangssignal des AWGN–Modells  $y_{\rm A}$,  und für das analoge Empfangssignal gilt dann  $y_{\rm A} = \tilde{x} +n$.
  • Wir wählen die beiden 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
\[\varepsilon = {\rm Q}(\sqrt{\rho})\hspace{0.05cm}.\]
  • Die Entscheidungsgrenze liegt bei  $G = 0$,  wodurch auch die Eigenschaft „symmetrisch” begründet ist.


Das BSC–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.

Zur Beschreibung gedächtnisbehafteter Kanäle müssen andere Modelle herangezogen werden,  die im fünften Hauptkapitel des Buches „Digitalsignalübertragung” behandelt werden,  zum Beispiel die Bündelfehlerkanäle entsprechend

Statistisch unabhängige Fehler (links) und Bündelfehler (rechts)

$\text{Beispiel 1:}$  Die Abbildung zeigt

  • das Originalbild in der Mitte,
  • statistisch unabhängige Fehler nach dem BSC–Modell  (links),
  • so genannte Bündelfehler gemäß Gilbert–Elliott  (rechts).


Die Bitfehlerrate beträgt in beiden Fällen  $10\%$.

Aus der rechten Grafik ist anhand der Bündelfehlerstruktur zu erkennen,  dass das Bild zeilenweise übertragen wurde.


Binary Erasure Channel – BEC


Das BSC–Modell liefert nur die Aussagen „richtig” und „falsch”.  Manche Empfänger – so zum Beispiel die so genannten  "Soft–in Soft–out Decoder"  – 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.

Der  "Binary Erasure Channel"  $\rm (BEC)$  liefert eine solche Information.  Anhand der Grafik erkennt man:

BEC und Zusammenhang mit dem AWGN–Modell
  • Das Eingangsalphabet des BEC–Modells ist binär   ⇒   $x ∈ \{0, \hspace{0.05cm}1\}$ und das Ausgangsalphabet ternär   ⇒   $y ∈ \{0, \hspace{0.05cm}1, \hspace{0.05cm}\rm E\}$.
  • Ein  "$\rm E$"  kennzeichnet eine unsichere Entscheidung.  Dieses neue „Symbol” steht für  "Erasure",  zu deutsch:  Auslöschung.
  • Bitfehler werden durch das BEC–Modell per se ausgeschlossen.  Eine unsichere Entscheidung  $\rm (E)$  wird mit 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– und AWGN–Modell dargestellt, wobei das Erasure–Entscheidungsgebiet  $\rm (E)$  grau hinterlegt ist.
  • Im Gegensatz zum BSC gibt es nun zwei Entscheidungsgrenzen,  nämlich  $G_0 = G$  und symmetrisch dazu  $G_1 = -G$.  Es gilt:
\[\lambda = {\rm Q}\big[\sqrt{\rho} \cdot (1 - G)\big]\hspace{0.05cm}.\]

Wir weisen hier nochmals auf die folgenden Applets hin:


Binary Symmetric Error & Erasure Channel – BSEC


Das BEC–Modell  $($Kennzeichen:  Fehlerwahrscheinlichkeit $0)$  ist eher unrealistisch und nur eine Näherung für ein extrem großes Signal–zu–Rausch–Leistungsverhältnis  $\rho$.  Stärkere Störungen  $($das heißt,  ein kleineres  $\rho)$  sollten besser durch den  "Binary Symmetric Error & Erasure Channel"  $\rm (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)$,
  • Erasure–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–Modell gilt auch hier  $x ∈ \{0, \hspace{0.05cm}1\}$  und  $y ∈ \{0, \hspace{0.05cm}1, \hspace{0.05cm}\rm E\}$.

$\text{Beispiel 2:}$  Wir betrachten das BSEC–Modell mit den beiden Entscheidungsgeraden  (symmetrisch um den Nullpunkt)

Binary Symmetric Error & Erasure Channel (BSEC) & Zusammenhang mit dem AWGN–Modell
  • $G_0 = G = 0.5$, 
  • $G_1 = -G = -0.5$.


Dessen Modellparameter  $\varepsilon$  und  $\lambda$  werden durch das  $\rm SNR$  $\rho=1/\sigma^2$  des vergleichbaren AWGN–Kanals festgelegt.

  • Für die rechts skizzierte WDF gilt  $\sigma = 0.5$   ⇒   $\rho = 4$:
$$\varepsilon = {\rm Q}\big[\sqrt{\rho} \cdot (1 + G)\big] = {\rm Q}(3) \approx 0.14\%\hspace{0.05cm},$$
$${\it \lambda} = {\rm Q}\big[\sqrt{\rho} \cdot (1 - G)\big] - \varepsilon = {\rm Q}(1) - {\rm Q}(3) $$
$$\Rightarrow \hspace{0.3cm}{\it \lambda} \approx 15.87\% - 0.14\% = 15.73\%\hspace{0.05cm},$$
  • Für  $\sigma = 0.25$   ⇒   $\rho = 16$  ergeben sich folgende Parameter:
$$\varepsilon = {\rm Q}(6) \approx 10^{-10}\hspace{0.05cm},$$
$${\it \lambda} = {\rm Q}(2) \approx 2.27\%\hspace{0.05cm}.$$
Hier könnte das BSEC–Modell durch die einfachere BEC–Variante ersetzt werden,  ohne dass es zu gravierenden Unterschieden kommt.


Maximum-a-posteriori– und Maximum-Likelihood–Kriterium


Wir gehen nun von dem nachfolgend skizzierten Modell aus und wenden die bereits im Kapitel  "Struktur des optimalen Empfängers"  des Buches „Digitalsignalübertragung” genannten Entscheidungskriterien auf den Decodiervorgang an.

Modell zur Beschreibung von MAP– und ML–Decodierung

$\text{Aufgabe des Kanaldecoders}$  ist es,  den Vektor  $\underline{v}$  so zu bestimmen,  dass dieser „möglichst gut” mit dem Informationswort  $\underline{u}$  übereinstimmt.

Etwas genauer formuliert:

  • Minimierung der  Blockfehlerwahrscheinlichkeit  ${\rm Pr(Blockfehler)} = {\rm Pr}(\underline{v} \ne \underline{u}) $  bezogen auf die Vektoren  $\underline{u}$  und  $\underline{v}$,  jeweils der Länge  $k$. 
  • Wegen der gleichen Zuordnung  $\underline{x} = {\rm enc}(\underline{u})$  des Kanalcoders und  $\underline{v} = {\rm enc}^{-1}(\underline{z})$  des Kanaldecoders gilt in gleicher Weise:
\[{\rm Pr(Blockfehler)} = {\rm Pr}(\underline{z} \ne \underline{x})\hspace{0.05cm}. \]


Der Kanaldecoder in obigem Modell besteht aus zwei Teilen:

  • Der  "Codewortschätzer"  ermittelt aus dem Empfangsvektor  $\underline{y}$  einen Schätzwert  $\underline{z} \in \mathcal{C}$  gemäß einem vorgegebenen Kriterium.
  • Aus dem (empfangenen) Codewort  $\underline{z}$  wird das Informationswort  $\underline{v}$  durch  "einfaches Mapping"  ermittelt.  Dieses sollte mit  $\underline{u}$  übereinstimmen.

Für den Codewortschätzer gibt es insgesamt vier unterschiedliche Varianten, nämlich

  1. den Maximum–a–posteriori–Empfänger (MAP–Empfänger) für das gesamte Codewort  $\underline{x}$,
  2. den Maximum–a–posteriori–Empfänger für die einzelnen Codebits  $x_i$,
  3. den Maximum–Likelihood–Empfänger  (ML–Empfänger)  für das gesamte Codewort  $\underline{x}$,
  4. den Maximum–Likelihood–Empfänger für die einzelnen Codebits  $x_i$.

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

$\text{Fazit:}$ 

  • Ein  MAP–Empfänger  berücksichtigt auch unterschiedliche Auftrittswahrscheinlichkeiten für das gesamte Codewort bzw. für deren einzelne Bits.
  • Sind alle Codeworte  $\underline{x}$  und damit auch alle Bits  $x_i$  der Codeworte gleichwahrscheinlich,  so ist der einfachere  ML–Empfänger  äquivalent zum MAP–Empfänger.



Definitionen der verschiedenen Optimalempfänger


$\text{Definition:}$  Der  "Maximum–a–posteriori–Empfänger auf Blockebene"  – kurz:  block–wise MAP – entscheidet sich unter den  $2^k$  Codeworten  $\underline{x}_i \in \mathcal{C}$  für das Codewort mit der größten Rückschlusswahrscheinlichkeit  $($englisch:   "a–posteriori probability",  $\rm APP)$:

\[\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}.\]
  • ${\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm}\vert \hspace{0.05cm} \underline{y} )$  ist die  bedingte Wahrscheinlichkeit, dass  $\underline{x}_i$  gesendet wurde,  wenn  $\underline{y}$  empfangen wird.


Wir versuchen nun,  diese Entscheidungsregel schrittweise zu vereinfachen.  Die  Rückschlusswahrscheinlichkeit  kann nach dem „Satz von Bayes” umgeformt werden:

\[{\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}.\]
  • 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.


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

\[\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}.\]
  • 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.
  • Im Folgenden verwenden wir auf Blockebene stets den Maximum–Likelihood–Empfänger.  Aufgrund der vorausgesetzten gleichwahrscheinlichen Informationsworte liefert auch dieser stets die bestmögliche Entscheidung.


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–Empfänger.

$\text{Definition:}$  Der  "Maximum–a–posteriori–Empfänger auf Bitebene"  – kurz:  bit–wise MAP – wählt für jedes einzelne 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} )$  aus:

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


Maximum-Likelihood–Entscheidung beim BSC–Kanal


Wir wenden nun das Maximum–Likelihood–Kriterium auf den gedächtnislosen  BSC–Kanal  an.  Dann gilt:

\[{\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.4cm}{\rm mit}\hspace{0.4cm} {\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}.\]
\[\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}.\]

$\text{Beweis:}$  Dieses Ergebnis lässt sich wie folgt begründen:

  • Die  Hamming–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 Worte  $\underline{y}$  und  $\underline{x}_{\hspace{0.03cm}i}$  mit jeweils  $n$  binären Elementen unterscheiden. Beispiel:   Die Hamming–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)$  ist  $2$.
  • 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$.


Die Vorgehensweise bei der Maximum–Likelihood–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:

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

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

\[\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}) = \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 ] \]
\[ \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 + \big [n -d_{\rm H}(\underline{y} \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})\big ] \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}.\]

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–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:


$\text{Maximum–Likelihood-Entscheidung beim BSC-Kanal:}$ 

Wähle von den  $2^k$  zulässigen Codeworten  $\underline{x}_{\hspace{0.03cm}i}$  dasjenige mit der  geringsten Hamming–Distanz  $d_{\rm H}(\underline{y} \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})$  zum Empfangsvektor  $\underline{y}$  aus:

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


Anwendungen der ML/BSC–Entscheidung finden Sie auf den folgenden Seiten:

Maximum-Likelihood–Entscheidung beim AWGN–Kanal


Das AWGN–Modell für einen  $(n, k)$–Blockcode unterscheidet sich vom  Modell  auf der ersten Kapitelseite dadurch,  dass für  $x$,  $\tilde{x}$  und  $y$  nun die entsprechenden Vektoren  $\underline{x}$,  $\underline{\tilde{x}}$  und  $\underline{y}$  verwendet werden müssen,  jeweils bestehend aus  $n$  Elementen.

Die Schritte zur Herleitung des Maximum–Likelihood–Entscheiders bei AWGN werden nachfolgend nur stichpunktartig angegeben:

  • Der AWGN–Kanal ist per se gedächtnislos  (hierfür steht das „White” im Namen).  Für die bedingte Wahrscheinlichkeitsdichtefunktion kann somit geschrieben werden:
\[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}.\]
  • Die bedingte WDF ist für jedes einzelne Codeelement  $(l = 1, \hspace{0.05cm}\text{...} \hspace{0.05cm}, n)$  "gaußisch".  Damit genügt auch die gesamte WDF einer  (eindimensionalen)  Gaußverteilung:
\[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 ]\hspace{0.3cm} \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}.\]
  • Da  $\underline{y}$  nun nicht mehr wie beim BSC–Modell wertdiskret ist,  sondern wertkontinuierlich,  müssen jetzt nach der ML–Entscheidungsregel  Wahrscheinlichkeitsdichten  untersucht werden und nicht mehr Wahrscheinlichkeiten.  Das optimale Ergebnis lautet:
\[\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.5cm} \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}.\]
  • In der Algebra bezeichnet man den Abstand zweier Punkte  $\underline{y}$  und  $\underline{\tilde{x}}$  im  $n$–dimensionalen Raum als die  Euklidische Distanz,  benannt nach dem griechischen Mathematiker  Euklid,  der im dritten Jahrhundert vor Christus lebte:
\[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}.\]
  • Damit lautet die ML–Entscheidungsregel beim AWGN–Kanal für einen jeden Blockcode unter Berücksichtigung der Tatsache,  dass der erste Faktor der WDF  $f( \underline{y} \hspace{0.05cm}|\hspace{0.05cm} \underline{\tilde{x}_i} )$  konstant ist:
\[\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}.\]

Nach einigen weiteren Zwischenschritten kommt man zum Ergebnis:

$\text{Maximum–Likelihood-Entscheidung beim AWGN-Kanal:}$ 

Wähle von den  $2^k$  zulässigen Codeworten  $\underline{x}_{\hspace{0.03cm}i}$  dasjenige mit der  kleinsten Euklidischen Distanz  $d_{\rm E}(\underline{y} \hspace{0.05cm}, \hspace{0.1cm}\underline{x}_{\hspace{0.03cm}i})$  zum Empfangsvektor  $\underline{y}$  aus:

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

Aufgaben zum Kapitel


Aufgabe 1.3: Kanalmodelle BSC–BEC–BSEC–AWGN

Aufgabe 1.4: Maximum–Likelihood–Entscheidung