Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(9 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
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
−
:x_0 = (0,0,0,0,0), x_1 = (0,1,0,1,0), x_2 = (1,0,1,0,1), $$\underline{x}_{3} \hspace{-0.1cm} \  =  \  \hspace{-0.1cm} (1, 1, 1, 1, 1) \hspace{0.05cm},$$
+
:x_0 = (0,0,0,0,0), x_1 = (0,1,0,1,0), x_2 = (1,0,1,0,1), $$\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 y_∈GF(25) verfälscht,
+
*ein digitales&nbsp; (binäres)&nbsp; Kanalmodell,&nbsp; das den Vektor&nbsp; $\underline{x} \in {\rm GF} (2^{5})$&nbsp; in den Vektor&nbsp; $\underline{y} \in {\rm GF} (2^{5})$&nbsp; verfälscht;
−
*ein [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Maximum-Likelihood.E2.80.93Entscheidung_beim_BSC.E2.80.93Kanal|Maximum–Likelihood–Decoder]] mit der Entscheidungsregel
+
 
 +
*ein&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Maximum-Likelihood.E2.80.93Entscheidung_beim_BSC.E2.80.93Kanal|Maximum–Likelihood–Decoder]]&nbsp; (kurz: &nbsp; "ML–Decoder") &nbsp;mit der Entscheidungsregel
 
:z_=argmax
 
:\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}}.
+
Hier bezeichnet&nbsp; $d_{\rm H} (\underline{y}, \ \underline{x_{i}})$&nbsp; die&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming–Distanz]]&nbsp; zwischen dem Empfangswort&nbsp; \underline{y}&nbsp; und dem&nbsp; (möglicherweise)&nbsp; gesendeten Codewort&nbsp; \underline{x_{i}}.
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
Hinweis:&nbsp; Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen|"Kanalmodelle und  Entscheiderstrukturen"]].
 +
 +
 
  
−
''Hinweis'':
 
  
−
Die Aufgabe gehört zum [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen|Kanalmodelle und  Entscheiderstrukturen]]
 
 
===Fragebogen===
 
===Fragebogen===
  
 
<quiz display=simple>
 
<quiz display=simple>
−
{Es sei \underline{y} = (1, 0, 0, 0, 1). Welche Entscheidungen erfüllen das ML–Kriterium?
+
{Es sei&nbsp; \underline{y} = (1, 0, 0, 0, 1).&nbsp; Welche Entscheidungen erfüllen das Maximum–Likelihood–Kriterium?
 
|type="[]"}
 
|type="[]"}
 
- \underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0),
 
- \underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0),
Zeile 28: Zeile 36:
  
  
−
{Es sei \underline{y} = (0, 0, 0, 1, 0). Welche Entscheidungen erfüllen das ML–Kriterium?
+
{Es sei&nbsp; \underline{y} = (0, 0, 0, 1, 0).&nbsp; Welche Entscheidungen erfüllen das Maximum–Likelihood–Kriterium?
 
|type="[]"}
 
|type="[]"}
 
+ \underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0),
 
+ \underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0),
Zeile 35: Zeile 43:
 
- \underline{z} = \underline{x}_{3} = (1, 1, 1, 1, 1).
 
- \underline{z} = \underline{x}_{3} = (1, 1, 1, 1, 1).
  
−
{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?
+
{Welche Entscheidung trifft der ML–Decoder für&nbsp; \underline{y} = (1, 0, 1, 1, 1),&nbsp; wenn ihm mitgeteilt wird,&nbsp; dass die beiden letzten Symbole unsicher sind?
 
|type="[]"}
 
|type="[]"}
 
- \underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0),
 
- \underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0),
Zeile 44: Zeile 52:
  
  
−
{Zu welchem Informationswort $\upsilon = (\upsilon_{1}, \upsilon_{2})$ führt diese Entscheidung?
+
{Zu welchem Informationswort&nbsp; $v = (v_{1}, v_{2})$&nbsp; 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 55: Zeile 63:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
−
'''(1)'''&nbsp; 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:
+
'''(1)'''&nbsp; Richtig ist die&nbsp; <u>Antwort 3</u> &nbsp; &rArr; &nbsp;  \underline{z} = \underline{x}_{2} = (1, 0, 1, 0, 1):
 +
*Die Hamming–Distanzen zwischen dem spezifischen Empfangswort&nbsp; \underline{y} = (1, 0, 0, 0, 1)&nbsp; und den vier möglichen Codeworten&nbsp; \underline{x}_{i}&nbsp; 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}.
 
: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 ⇒ <u>Antwort 3</u>.
+
*Entschieden wird sich für die Folge mit der geringsten Hamming–Distanz&nbsp; d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_2) = 1.
 +
 
 +
 
 +
 
 +
'''(2)'''&nbsp; Für&nbsp; \underline{y} = (0, 0, 0, 1, 0)&nbsp; sind die&nbsp; <u>Antworten 1 und 2</u>&nbsp; richtig,&nbsp; 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)'''&nbsp; Richtig ist die&nbsp; <u>Antwort 3</u>:
 +
*Entsprechend der Hamming–Distanz wäre eine Entscheidung zugunsten von&nbsp; x_{2}&nbsp; genau so möglich wie für&nbsp; x_{3},&nbsp; wenn \underline{y} = (1, 0, 1, 1, 1)&nbsp; 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&nbsp; \underline{y}&nbsp; unterscheidet sich aber von&nbsp; x_{2}&nbsp; bezüglich des vierten Bits und von&nbsp; x_{3}&nbsp; im zweiten Bit.
 +
* Da das vierte Bit unsicherer ist als das zweite,&nbsp; wird er sich für&nbsp; x_{2}&nbsp; entscheiden .
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; Da es sich hier um einen systematischen Code handelt,&nbsp; ist die Entscheidung für&nbsp; \underline{z} = (1, 0, 1, 0, 1)&nbsp; gleichbedeutend mit der Entscheidung
 +
:v_{1}  \ \underline{ = 1}, \ v_{2} \  \underline{= 0}.
 +
 
 +
*Es ist nicht sicher,&nbsp; dass&nbsp; \underline{u} = (1, 0)&nbsp;  tatsächlich gesendet wurde.
 +
 
 +
*Aber die Wahrscheinlichkeit ist angesichts des Empfangsvektors&nbsp; \underline{y} = (1, 0, 1, 1, 1)&nbsp; hierfür am größten.
  
−
'''2.'''
 
−
'''3.'''
 
−
'''4.'''
 
−
'''5.'''
 
−
'''6.'''
 
−
'''7.'''
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
−
[[Category:Aufgaben zu  Kanalcodierung|^1.2 Kanalmodelle und Entscheiderstrukturen
+
[[Category:Aufgaben zu  Kanalcodierung|^1.2 Kanal und Entscheiderstrukturen
 
^]]
 
^]]

Aktuelle Version vom 12. Juni 2022, 15:25 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;
\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}).

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




Hinweis:  Die Aufgabe gehört zum Kapitel  "Kanalmodelle und Entscheiderstrukturen".



Fragebogen

1

Es sei  \underline{y} = (1, 0, 0, 0, 1).  Welche Entscheidungen erfüllen das Maximum–Likelihood–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 Maximum–Likelihood–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 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

Musterlösung

(1)  Richtig ist die  Antwort 3   ⇒   \underline{z} = \underline{x}_{2} = (1, 0, 1, 0, 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  d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_2) = 1.


(2)  Für  \underline{y} = (0, 0, 0, 1, 0)  sind die  Antworten 1 und 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)  Richtig ist die  Antwort 3:

  • Entsprechend der Hamming–Distanz wäre eine Entscheidung zugunsten von  x_{2}  genau so möglich wie für  x_{3},  wenn \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  \underline{y}  unterscheidet sich aber 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 .


(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

v_{1} \ \underline{ = 1}, \ v_{2} \ \underline{= 0}.
  • Es ist nicht sicher,  dass  \underline{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.

Abgerufen von „http://www.lntwww.de/index.php?title=Aufgaben:Aufgabe_1.4:_Maximum–Likelihood–Entscheidung&oldid=33319“
  • Powered by MediaWiki