Difference between revisions of "Aufgaben:Exercise 1.4: Maximum Likelihood Decision"

From LNTwww
Line 1: Line 1:
−
{{quiz-Header|Buchseite=Kanalcodierung/Kanalmodelle und Entscheiderstrukturen
+
{{quiz-Header|Buchseite=Channel Coding/Channel Models and Decision Structures
  
 
}}
 
}}
  
−
[[File:P_ID2384__KC_A_1_4.png|right|frame|Modell zur Maximum–Likelihood–Decodierung]]
+
[[File:P_ID2384__KC_A_1_4.png|right|frame|Maximum Likelihood Decoding Model]]
  
−
Wir betrachten das digitale Übertragungssystem entsprechend der Grafik. Berücksichtigt sind dabei:
+
We consider the digital transmission system according to the graph. Considered are:
−
*ein systematischer  $(5, 2)$–Blockcode  $\mathcal{C}$  mit den Codeworten
+
*a systematic  $(5, 2)$ block code  $\mathcal{C}$  with the code words
 
:$$\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  $\underline{x} \in {\rm GF} (2^{5})$  in den Vektor  $\underline{y} \in {\rm GF} (2^{5})$  verfälscht;
+
*a digital (binary) channel model that crosses the vector  $\underline{x} \in {\rm GF} (2^{5})$  over into the vector  $\underline{y} \in {\rm GF} (2^{5})$  (Noah)
−
*ein  [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Maximum-Likelihood.E2.80.93Entscheidung_beim_BSC.E2.80.93Kanal|Maximum–Likelihood–Decoder]]  (kurz:   ML–Decoder)  mit der Entscheidungsregel
+
*a  [[Channel_Coding/Channel_Models_and_Decision_Structures#Maximum_likelihood_decision_at_the_BSC_channel|Maximum Likelihood Decoder]]  (short:   ML–Decoder)  with the decision rule
 
:$$\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}).$$
  
−
Hier bezeichnet  $d_{\rm H} (\underline{y}, \ \underline{x_{i}})$  die  [[Channel_Coding/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming–Distanz]]  zwischen dem Empfangswort  $\underline{y}$  und dem (möglicherweise) gesendeten Codewort  $\underline{x_{i}}$.
+
Here,  $d_{\rm H} (\underline{y}, \ \underline{x_{i}})$  the  [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|Hamming distance]]  between the received word  $\underline{y}$  and the (possibly) sent codeword  $\underline{x_{i}}$.
  
  
Line 19: Line 19:
  
  
−
''Hinweis'':
+
Hints:
  
−
*Die Aufgabe gehört zum Kapitel  [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen|Kanalmodelle und  Entscheiderstrukturen]].  
+
*This exercise belongs to the chapter  [[Channel_Coding/Channel_Models_and_Decision_Structures|Channel Models and Decision Structures]].  
 
   
 
   
  
  
  
−
===Fragebogen===
+
===Questions===
  
 
<quiz display=simple>
 
<quiz display=simple>
−
{Es sei&nbsp; $\underline{y} = (1, 0, 0, 0, 1)$. Welche Entscheidungen erfüllen das Maximum–Likelihood–Kriterium?
+
{Let&nbsp; $\underline{y} = (1, 0, 0, 1)$. Which decisions satisfy the maximum likelihood criterion?
 
|type="[]"}
 
|type="[]"}
−
- $\underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0)$,
+
- $\underline{z} = \underline{x}_{0} = (0, 0, 0, 0)$,
 
- $\underline{z} = \underline{x}_{1} = (0, 1, 0, 1, 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}_{2} = (1, 0, 1, 0, 1)$,
−
- $\underline{z} = \underline{x}_{3} = (1, 1, 1, 1, 1)$.
+
- $\underline{z} = \underline{x}_{3} = (1, 1, 1, 1)$.
  
  
−
{Es sei&nbsp; $\underline{y} = (0, 0, 0, 1, 0)$. Welche Entscheidungen erfüllen das Maximum–Likelihood–Kriterium?
+
{Let&nbsp; $\underline{y} = (0, 0, 0, 1, 0)$. Which decisions satisfy the maximum likelihood criterion?
 
|type="[]"}
 
|type="[]"}
−
+ $\underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0)$,
+
+ $\underline{z} = \underline{x}_{0} = (0, 0, 0, 0)$,
 
+ $\underline{z} = \underline{x}_{1} = (0, 1, 0, 1, 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}_{2} = (1, 0, 1, 0, 1)$,
−
- $\underline{z} = \underline{x}_{3} = (1, 1, 1, 1, 1)$.
+
- $\underline{z} = \underline{x}_{3} = (1, 1, 1, 1)$.
  
−
{Welche Entscheidung trifft der ML–Decoder für&nbsp; $\underline{y} = (1, 0, 1, 1, 1)$, wenn ihm mitgeteilt wird, dass die beiden letzten Symbole unsicher sind?
+
{What decision does the ML decoder make for&nbsp; $\underline{y} = (1, 0, 1, 1, 1)$ when it is told that the last two symbols are uncertain?
 
|type="[]"}
 
|type="[]"}
−
- $\underline{z} = \underline{x}_{0} = (0, 0, 0, 0, 0)$,
+
- $\underline{z} = \underline{x}_{0} = (0, 0, 0, 0)$,
 
- $\underline{z} = \underline{x}_{1} = (0, 1, 0, 1, 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}_{2} = (1, 0, 1, 0, 1)$,
−
- $\underline{z} = \underline{x}_{3} = (1, 1, 1, 1, 1)$.
+
- $\underline{z} = \underline{x}_{3} = (1, 1, 1, 1)$.
  
  
  
−
{Zu welchem Informationswort&nbsp; $v = (v_{1}, v_{2})$&nbsp; führt die Entscheidung gemäß der letzten Teilaufgabe?
+
{What information word&nbsp; $v = (v_{1}, v_{2})$&nbsp; does the decision lead to according to the last subtask?
 
|type="{}"}
 
|type="{}"}
−
$v_{1} \ = \ $ { 1 }
+
$v_{1} \ = \ $ { 1 }
 
$v_{2} \ = \ $ { 0. }
 
$v_{2} \ = \ $ { 0. }
−
 
  
  
 
</quiz>
 
</quiz>
  
−
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
−
'''(1)'''&nbsp; Richtig ist die <u>Antwort 3</u>:
+
'''(1)'''&nbsp; Correct <u>answer 3</u>:
−
*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:
+
*The Hamming distances between the specific received word $\underline{y} = (1, 0, 0, 1)$ and the four possible codewords $\underline{x}_{i}$ are as follows:
 
:$$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 $d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_2) = 1$.
+
*A decision is made for the sequence with the smallest Hamming distance $d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_2) = 1$.
  
  
  
−
'''(2)'''&nbsp; Für $\underline{y} = (0, 0, 0, 1, 0)$ sind die <u>Antworten 1 und 2</u> richtig, wie die folgende Rechnung zeigt:
+
'''(2)'''&nbsp; For $\underline{y} = (0, 0, 0, 1, 0)$ the <u>answers 1 and 2</u> are correct, as the following calculation shows:
 
:$$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}.$$
 
:$$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 <u>Antwort 3</u>:
+
'''(3)'''&nbsp; Correct <u>answer 3</u>:
−
*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:
+
*According to the Hamming distance, a decision in favor of $x_{2}$ would be just as possible as for $x_{3}$ if the vector $\underline{y} = (1, 0, 1, 1, 1)$ is received:
 
:$$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}.$$
 
:$$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.
+
*But the received vector $\underline{y}$ is different from $x_{2}$ with respect to the fourth bit and from $x_{3}$ in the second bit.
−
* Da das vierte Bit unsicherer ist als das zweite, wird er sich für $x_{2}$ entscheiden .
+
* Since the fourth bit is more uncertain than the second, it will choose $x_{2}$ .
  
  
  
−
'''(4)'''&nbsp; 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
+
'''(4)'''&nbsp; Since this is a systematic code, the decision for $\underline{z} = (1, 0, 1, 0, 1)$ is equivalent to the decision
−
:$$v_{1}  \ \underline{ = 1}, \ v_{2} \ \underline{= 0}.$$
+
:$$v_{1}  \ \underline{ = 1}, \ v_{2} \ \underline{= 0}.$$
  
−
*Es ist nicht sicher, dass $\underline{u} = (1, 0)$ tatsächlich gesendet wurde.  
+
*It is not certain that $\underline{u} = (1, 0)$ was actually sent.  
−
*Aber die Wahrscheinlichkeit ist angesichts des Empfangsvektors $\underline{y} = (1, 0, 1, 1, 1)$ hierfür am größten.
+
*But the probability is highest for this given the received vector $\underline{y} = (1, 0, 1, 1)$.
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Revision as of 17:16, 29 May 2022

Maximum Likelihood Decoding Model

We consider the digital transmission system according to the graph. Considered are:

  • a systematic  $(5, 2)$ block code  $\mathcal{C}$  with the code words
$$\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};$$
  • a digital (binary) channel model that crosses the vector  $\underline{x} \in {\rm GF} (2^{5})$  over into the vector  $\underline{y} \in {\rm GF} (2^{5})$  (Noah)
  • a  Maximum Likelihood Decoder  (short:   ML–Decoder)  with the decision rule
$$\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}).$$

Here,  $d_{\rm H} (\underline{y}, \ \underline{x_{i}})$  the  Hamming distance  between the received word  $\underline{y}$  and the (possibly) sent codeword  $\underline{x_{i}}$.




Hints:



Questions

1

Let  $\underline{y} = (1, 0, 0, 1)$. Which decisions satisfy the maximum likelihood criterion?

$\underline{z} = \underline{x}_{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)$.

2

Let  $\underline{y} = (0, 0, 0, 1, 0)$. Which decisions satisfy the maximum likelihood criterion?

$\underline{z} = \underline{x}_{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)$.

3

What decision does the ML decoder make for  $\underline{y} = (1, 0, 1, 1, 1)$ when it is told that the last two symbols are uncertain?

$\underline{z} = \underline{x}_{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)$.

4

What information word  $v = (v_{1}, v_{2})$  does the decision lead to according to the last subtask?

$v_{1} \ = \ $

$v_{2} \ = \ $


Solution

Solution

(1)  Correct answer 3:

  • The Hamming distances between the specific received word $\underline{y} = (1, 0, 0, 1)$ and the four possible codewords $\underline{x}_{i}$ are as follows:
$$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}.$$
  • A decision is made for the sequence with the smallest Hamming distance $d_{\rm H}(\underline{y}, \hspace{0.05cm}\underline{x}_2) = 1$.


(2)  For $\underline{y} = (0, 0, 0, 1, 0)$ the answers 1 and 2 are correct, as the following calculation shows:

$$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)  Correct answer 3:

  • According to the Hamming distance, a decision in favor of $x_{2}$ would be just as possible as for $x_{3}$ if the vector $\underline{y} = (1, 0, 1, 1, 1)$ is received:
$$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}.$$
  • But the received vector $\underline{y}$ is different from $x_{2}$ with respect to the fourth bit and from $x_{3}$ in the second bit.
  • Since the fourth bit is more uncertain than the second, it will choose $x_{2}$ .


(4)  Since this is a systematic code, the decision for $\underline{z} = (1, 0, 1, 0, 1)$ is equivalent to the decision

$$v_{1} \ \underline{ = 1}, \ v_{2} \ \underline{= 0}.$$
  • It is not certain that $\underline{u} = (1, 0)$ was actually sent.
  • But the probability is highest for this given the received vector $\underline{y} = (1, 0, 1, 1)$.

Retrieved from "http://en.lntwww.de/index.php?title=Aufgaben:Exercise_1.4:_Maximum_Likelihood_Decision&oldid=47491"
  • Powered by MediaWiki