Aufgaben:Aufgabe 1.4: Maximum–Likelihood–Entscheidung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2384__KC_A_1_4.png|right|frame|Zur Maximum–Likelihood–Decodierung]]
+
[[Datei:P_ID2384__KC_A_1_4.png|right|frame|Modell zur Maximum–Likelihood–Decodierung]]
  
 
Wir betrachten das digitale Übertragungssystem entsprechend der Grafik. Berücksichtigt sind dabei:
 
Wir betrachten das digitale Übertragungssystem entsprechend der Grafik. Berücksichtigt sind dabei:
*ein systematischer (5, 2)–Blockcode ''C'' mit den Codeworten
+
*ein systematischer (5, 2)–Blockcode $\mathcal{C}$ mit den Codeworten
:$$\underline{x}_{0} \hspace{-0.1cm} \ =  \  \hspace{-0.1cm} (0, 0, 0, 0, 0) \hspace{0.05cm},$$ $$\underline{x}_{1} \hspace{-0.1cm} \  =  \  \hspace{-0.1cm} (0, 1, 0, 1, 0) \hspace{0.05cm},$$ $$\underline{x}_{2} \hspace{-0.1cm} \  =  \  \hspace{-0.1cm} (1, 0, 1, 0, 1) \hspace{0.05cm},$$ $$\underline{x}_{3} \hspace{-0.1cm} \  =  \  \hspace{-0.1cm} (1, 1, 1, 1, 1) \hspace{0.05cm},$$
+
:$$\underline{x}_{0} \hspace{-0.1cm} \ =  \  \hspace{-0.1cm} (0, 0, 0, 0, 0) \hspace{0.05cm},$$ $$\underline{x}_{1} \hspace{-0.1cm} \  =  \  \hspace{-0.1cm} (0, 1, 0, 1, 0) \hspace{0.05cm},$$ $$\underline{x}_{2} \hspace{-0.1cm} \  =  \  \hspace{-0.1cm} (1, 0, 1, 0, 1) \hspace{0.05cm},$$ $$\underline{x}_{3} \hspace{-0.1cm} \  =  \  \hspace{-0.1cm} (1, 1, 1, 1, 1) \hspace{0.05cm};$$
*ein digitales (binäres) Kanalmodell, das den Vektor <u>x</u> ∈ GF($2^{5}$) in den Vektor $\underline{y} \in {\rm GF} (2^{5}$) verfälscht,
+
*ein digitales (binäres) Kanalmodell, das den Vektor $\underline{x} \in {\rm GF} (2^{5})$ in den Vektor $\underline{y} \in {\rm GF} (2^{5})$ verfälscht;
 
*ein [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Maximum-Likelihood.E2.80.93Entscheidung_beim_BSC.E2.80.93Kanal|Maximum–Likelihood–Decoder]] mit der Entscheidungsregel
 
*ein [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Maximum-Likelihood.E2.80.93Entscheidung_beim_BSC.E2.80.93Kanal|Maximum–Likelihood–Decoder]] mit der Entscheidungsregel
 
:$$\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm}|\hspace{0.05cm} \underline{y} ) = {\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}).$$
 
:$$\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm}|\hspace{0.05cm} \underline{y} ) = {\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}).$$
  
In der Gleichung bezeichnet $d_{\rm H} (\underline{y},\underline{x_{i}})$ die [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming–Distanz]] zwischen Empfangswort $\underline{y}$ und dem (möglicherweise) gesendeten Codewort $\underline{x_{i}}$.
+
In der Gleichung bezeichnet $d_{\rm H} (\underline{y}, \ \underline{x_{i}})$ die [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming–Distanz]] zwischen Empfangswort $\underline{y}$ und dem (möglicherweise) gesendeten Codewort $\underline{x_{i}}$.
 +
 
 +
 
 +
''Hinweise'':
 +
 
 +
*Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen|Kanalmodelle und  Entscheiderstrukturen]].
 +
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
 +
 
  
''Hinweis'':
 
  
Die Aufgabe gehört zum [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen|Kanalmodelle und  Entscheiderstrukturen]]
 
 
===Fragebogen===
 
===Fragebogen===
  
Zeile 44: Zeile 49:
  
  
{Zu welchem Informationswort $\upsilon = (\upsilon_{1}, \upsilon_{2})$ führt diese Entscheidung?
+
{Zu welchem Informationswort $v = (v_{1}, v_{2})$ führt die Entscheidung gemäß der letzten Teilaufgabe?
 
|type="{}"}
 
|type="{}"}
$\upsilon_{1}$ = { 1 3% }
+
$v_{1}$ = { 1 }
$\upsilon_{2}$ = { 0 3% }
+
$v_{2}$ = { 0. }
  
  
Zeile 72: Zeile 77:
  
  
[[Category:Aufgaben zu  Kanalcodierung|^1.2 Kanalmodelle und Entscheiderstrukturen
+
[[Category:Aufgaben zu  Kanalcodierung|^1.2 Kanal und Entscheiderstrukturen
 
^]]
 
^]]

Version vom 11. Dezember 2017, 15:33 Uhr

Modell zur Maximum–Likelihood–Decodierung

Wir betrachten das digitale Übertragungssystem entsprechend der Grafik. Berücksichtigt sind dabei:

  • ein systematischer (5, 2)–Blockcode $\mathcal{C}$ mit den Codeworten
$$\underline{x}_{0} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (0, 0, 0, 0, 0) \hspace{0.05cm},$$ $$\underline{x}_{1} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (0, 1, 0, 1, 0) \hspace{0.05cm},$$ $$\underline{x}_{2} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (1, 0, 1, 0, 1) \hspace{0.05cm},$$ $$\underline{x}_{3} \hspace{-0.1cm} \ = \ \hspace{-0.1cm} (1, 1, 1, 1, 1) \hspace{0.05cm};$$
  • ein digitales (binäres) Kanalmodell, das den Vektor $\underline{x} \in {\rm GF} (2^{5})$ in den Vektor $\underline{y} \in {\rm GF} (2^{5})$ verfälscht;
  • ein Maximum–Likelihood–Decoder mit der Entscheidungsregel
$$\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm}|\hspace{0.05cm} \underline{y} ) = {\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}).$$

In der Gleichung bezeichnet $d_{\rm H} (\underline{y}, \ \underline{x_{i}})$ die Hamming–Distanz zwischen Empfangswort $\underline{y}$ und dem (möglicherweise) gesendeten Codewort $\underline{x_{i}}$.


Hinweise:


Fragebogen

1

Es sei $\underline{y} = (1, 0, 0, 0, 1)$. Welche Entscheidungen erfüllen das ML–Kriterium?

$\underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0)$,
$\underline{z} = \underline{x}_{1} = (0, 1, 0, 1, 0)$,
$\underline{z} = \underline{x}_{2} = (1, 0, 1, 0, 1)$,
$\underline{z} = \underline{x}_{3} = (1, 1, 1, 1, 1)$.

2

Es sei $\underline{y} = (0, 0, 0, 1, 0)$. Welche Entscheidungen erfüllen das ML–Kriterium?

$\underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0)$,
$\underline{z} = \underline{x}_{1} = (0, 1, 0, 1, 0)$,
$\underline{z} = \underline{x}_{2} = (1, 0, 1, 0, 1)$,
$\underline{z} = \underline{x}_{3} = (1, 1, 1, 1, 1)$.

3

Welche Entscheidung trifft der ML–Decoder für $\underline{y} = (1, 0, 1, 1, 1)$, wenn ihm mitgeteilt wird, dass die beiden letzten Symbole eher unsicher sind?

$\underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0)$,
$\underline{z} = \underline{x}_{1} = (0, 1, 0, 1, 0)$,
$\underline{z} = \underline{x}_{2} = (1, 0, 1, 0, 1)$,
$\underline{z} = \underline{x}_{3} = (1, 1, 1, 1, 1)$.

4

Zu welchem Informationswort $v = (v_{1}, v_{2})$ führt die Entscheidung gemäß der letzten Teilaufgabe?

$v_{1}$ =

$v_{2}$ =


Musterlösung

(1)  Die Hamming–Distanzen zwischen dem spezifischen Empfangswort $\underline{y} = (1, 0, 0, 0, 1)$ und den vier möglichen Codeworten $\underline{x}_{i}$ ergeben sich wie folgt:

$$d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_0) = 2\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_1) = 4\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_2) = 1\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_3) = 3\hspace{0.05cm}.$$

Entschieden wird sich für die Folge mit der geringsten Hamming–Distanz ⇒ Antwort 3.

(2)  Für $\underline{y} = (0, 0, 0, 1, 0)$ sind Antwort 1und Antwort 2 richtig, wie die folgende Rechnung zeigt:

$$d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_0) = 1\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_1) = 1\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_2) = 4\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_3) = 4\hspace{0.05cm}.$$

(3)  Entsprechend der Hamming–Distanz wäre eine Entscheidung zugunsten von $x_{2}$ genau so möglich wie für $x_{3}$, wenn der Vektor $\underline{y} = (1, 0, 1, 1, 1)$ empfangen wird:

$$d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_0) = 4\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_1) = 4\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_2) = 1\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_3) = 1\hspace{0.05cm}.$$

Der Empfangsvektor y unterscheidet sich von $x_{2}$ bezüglich des vierten Bits und von $x_{3}$ im zweiten Bit. Da das vierte Bit unsicherer ist als das zweite, wird er sich für $x_{2}$ entscheiden ⇒ Antwort 3.

(4)  Da es sich hier um einen systematischen Code handelt, ist die Entscheidung für $\underline{z} = (1, 0, 1, 0, 1)$ gleichbedeutend mit der Entscheidung $\upsilon_{1} \ \underline{ = 1}, \upsilon_{2} \ \underline{= 0}$. Es ist nicht sicher, dass u = (1, 0) tatsächlich gesendet wurde, aber die Wahrscheinlichkeit ist angesichts des Empfangsvektors $\underline{y} = (1, 0, 1, 1, 1)$ hierfür am größten.