Aufgaben:Aufgabe 1.13: Decodierung beim binären Auslöschungskanal (BEC): Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(7 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
 
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung linearer Blockcodes}}
 
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung linearer Blockcodes}}
  
[[Datei:P_ID2539__KC_A_1_13.png|right|frame|Zur BEC–Decodierung]]
+
[[Datei:KC_A_1_13_neu.png|right|frame|Zur Decodierung beim BEC]]
  
Wir gehen hier vom Modell im Abschnitt [[Kanalcodierung/Decodierung_linearer_Blockcodes#Decodierung_beim_Binary_Erasure_Channel|Decodierung beim ''Binary Erasure Channel'']]  aus (grün hinterlegte BEC–Konfiguration):
+
Wir gehen hier vom Modell im Abschnitt  [[Kanalcodierung/Decodierung_linearer_Blockcodes#Decodierung_beim_Binary_Erasure_Channel|"Decodierung beim Binary Erasure Channel"]]  aus  (grün hinterlegte BEC–Konfiguration):
  
*Jedes Informationswort $\underline{u}$ wird blockweise codiert und liefert das Codewort $\underline{x}$. Der Blockcode sei linear und durch seine Prüfmatrix $\boldsymbol{\rm H}$ vollständig gegeben.
+
*Jedes Informationswort  $\underline{u}$  wird blockweise codiert und liefert das Codewort  $\underline{x}$.  Der Blockcode sei linear und durch seine Prüfmatrix  $\boldsymbol{\rm H}$  vollständig gegeben.
  
*Bei der Übertragung werden $n_{\rm E}$ Bit des Codewortes ausgelöscht ⇒ [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|Binary Erasure Channel]] (BEC). Aus dem Codewort $\underline{x}$ wird somit das Empfangswort $\underline{y}$.
+
*Bei der Übertragung werden  $n_{\rm E}$  Bit des Codewortes ausgelöscht    [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|"Binary Erasure Channel"]]  $\rm (BEC)$.  Aus dem Codewort  $\underline{x}$  wird somit das Empfangswort  $\underline{y}$.
  
*Ist die Anzahl $n_{\rm E}$ der Auslöschungen kleiner als die [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|minimale Distanz]] $d_{\rm min}$ des Codes, so gelingt es, aus $\underline{y}$ das Codewort $\underline{z} = \underline{x}$ ohne Fehler zu rekonstruieren, und man erhält so auch das richtige Informationswort $\underline{v} = \underline{u}$.
+
*Ist die Anzahl  $n_{\rm E}$  der Auslöschungen kleiner als die  [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|"minimale Distanz"]]  $d_{\rm min}$  des Codes,  so gelingt es,  aus  $\underline{y}$   das Codewort  $\underline{z} = \underline{x}$  ohne Fehler zu rekonstruieren,  und man erhält so auch das richtige Informationswort  $\underline{v} = \underline{u}$.
  
  
Zur Aufgabenbeschreibung betrachten wir nun beispielhaft das Hamming–Codewort $\underline{x} = (0, 1, 0, 1, 1, 0, 0)$ und das Empfangswort $\underline{y} = (0, 1, {\rm E} , {\rm E}, 1, 0, 0).$
+
Zur Aufgabenbeschreibung betrachten wir nun beispielhaft das Hamming–Codewort   $\underline{x} = (0, 1, 0, 1, 1, 0, 0)$   und das Empfangswort   $\underline{y} = (0, 1, {\rm E} , {\rm E}, 1, 0, 0).$
  
*Ausgelöscht wurden somit durch den Kanal das dritte und vierte Bit.  
+
*Ausgelöscht wurden somit durch den Kanal das dritte und vierte Bit.  Der Codewortfinder hat somit die Aufgabe,  den Vektor  $z_{\rm E} = (z_{3}, z_{4})$  mit  $z_{3}, \ z_{4} \in \{0, 1\}$  zu bestimmen.  Dies geschieht entsprechend der Gleichung
*Der Codewortfinder hat somit die Aufgabe, den Vektor $z_{\rm E} = (z_{3}, z_{4})$ mit $z_{3}, \ z_{4} \in \{0, 1\}$ zu bestimmen. Dies geschieht entsprechend der Gleichung
 
  
 
:$${ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T}= { \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T}\hspace{0.05cm}.$$
 
:$${ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T}= { \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T}\hspace{0.05cm}.$$
Zeile 23: Zeile 22:
 
:$$\underline{z}_{\rm K} = (0, 1, 1, 0, 0)\hspace{0.05cm},\hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm K} = \begin{pmatrix} 1 &1 &1 &0 &0\\ 0 &1 &0 &1 &0\\ 1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} 1 &0\\ 1 &1\\ 0 &1 \end{pmatrix} \hspace{0.05cm}.$$
 
:$$\underline{z}_{\rm K} = (0, 1, 1, 0, 0)\hspace{0.05cm},\hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm K} = \begin{pmatrix} 1 &1 &1 &0 &0\\ 0 &1 &0 &1 &0\\ 1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} 1 &0\\ 1 &1\\ 0 &1 \end{pmatrix} \hspace{0.05cm}.$$
  
*Diese Gleichung liefert zwei Bestimmungsgleichungen für die zu bestimmenden Bits, deren Lösung zum Ergebnis $z_{3} = 0$ und $z_{4} = 1$ führt.
+
*Wir haben nun zwei Gleichungen für die zu bestimmenden Bits,  deren Lösung zum Ergebnis  $z_{3} = 0$  und  $z_{4} = 1$  führt.
  
  
  
  
''Hinweise: ''
+
Hinweise:
* Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes|Decodierung linearer Blockcodes]].
+
* Die Aufgabe gehört zum Kapitel  [[Kanalcodierung/Decodierung_linearer_Blockcodes|"Decodierung linearer Blockcodes"]].
* Der Algorithmus zur Zuordnung des Empfangswortes $\underline{y}$ zum richtigen Codewort $\underline{z} = \underline{x}$  ist im [[Aufgaben:1.1_ISDN–Versorgungsleitungen|Theorieteil]] ausführlich beschrieben.  
+
 
* Wir möchten nochmals daran erinnern, dass wir bei der BEC–Decodierung den ersten Decoderblock $\underline{y} → \underline{z}$  als ''Codewortfinder'' bezeichnen, da hier Fehlentscheidungen ausgeschlossen sind. Jedes Empfangswort wird richtig decodiert, oder es kann gar nicht decodiert werden.  
+
* Der Algorithmus zur Zuordnung des Empfangswortes  $\underline{y}$  zum richtigen Codewort  $\underline{z} = \underline{x}$  ist im  [[Kanalcodierung/Decodierung_linearer_Blockcodes#Decodierung_beim_Binary_Erasure_Channel|"Theorieteil"]]  ausführlich beschrieben.
*Beim BSC–Modell lassen sich dagegen Decodierfehler nicht vermeiden. Dementsprechend heißt der entsprechende Block dort ''Codewortschätzer''.
+
 +
* Wir möchten nochmals daran erinnern, dass wir bei der BEC–Decodierung den ersten Decoderblock  $\underline{y} → \underline{z}$  als  "Codewortfinder"  bezeichnen,  da hier Fehlentscheidungen ausgeschlossen sind.  Jedes Empfangswort wird richtig decodiert,  oder es kann gar nicht decodiert werden.
 +
 +
*Beim BSC–Modell lassen sich dagegen Decodierfehler nicht vermeiden.  Dementsprechend bezeichnen wir den entsprechenden Block dort als  "Codewortschätzer".
  
  
Zeile 39: Zeile 41:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
{Empfangen wurde $\underline{y} = (1, {\rm E}, 0, 1, 0, 0, {\rm E})$. Für welche Sequenz entscheidet sich der Codewortfinder?
+
{Empfangen wurde&nbsp; $\underline{y} = (1, {\rm E}, 0, 1, 0, 0, {\rm E})$.&nbsp; Für welche Sequenz entscheidet sich der Codewortfinder?
 
|type="()"}
 
|type="()"}
 
- $\underline{z} = (1, 0, 0, 1, 0, 0, 0),$
 
- $\underline{z} = (1, 0, 0, 1, 0, 0, 0),$
Zeile 45: Zeile 47:
 
- $\underline{z} = (1, 0, 0, 1, 0, 0, 1).$
 
- $\underline{z} = (1, 0, 0, 1, 0, 0, 1).$
  
{Welche Konsequenzen ergeben sich aus den roten Eintragungen für $\boldsymbol{\rm H}_{\rm K}$ und $z_{\rm K}$ (siehe Grafik auf der Angabenseite)?
+
{Welche Konsequenzen ergeben sich aus den roten Eintragungen für&nbsp; $\boldsymbol{\rm H}_{\rm K}$&nbsp; und&nbsp; $z_{\rm K}$&nbsp; (siehe Grafik auf der Angabenseite)?
 
|type="[]"}
 
|type="[]"}
+ Der Erasure–Vektor lautet $\underline{z}_{\rm E} = (z_{5}, z_{6}, z_{7}).$
+
+ Der Erasure–Vektor lautet&nbsp; $\underline{z}_{\rm E} = (z_{5}, z_{6}, z_{7}).$
+ Das Empfangswort lautet $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E}).$
+
+ Das Empfangswort lautet&nbsp; $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E}).$
- $\boldsymbol{\rm H}_{\rm E}$ ist eine $2 \times 3$–Matrix.
+
- $\boldsymbol{\rm H}_{\rm E}$&nbsp; ist eine&nbsp; $2 \times 3$–Matrix.
+ $\boldsymbol{\rm H}_{\rm E}$ ist eine $3 \times 3$–Matrix.
+
+ $\boldsymbol{\rm H}_{\rm E}$&nbsp; ist eine&nbsp; $3 \times 3$–Matrix.
  
{Nun gelte $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E}).$ Welches Codewort wird ausgewählt?
+
{Nun gelte&nbsp; $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E}).$&nbsp; Welches Codewort wird ausgewählt?
 
|type="()"}
 
|type="()"}
 
- $\underline{z} = (1, 1, 0, 1, 1, 1, 0),$
 
- $\underline{z} = (1, 1, 0, 1, 1, 1, 0),$
 
+ $\underline{z} = (1, 1, 0, 1, 0, 0, 1),$
 
+ $\underline{z} = (1, 1, 0, 1, 0, 0, 1),$
 
- $\underline{z} = (1, 1, 0, 0, 0, 1, 0).$
 
- $\underline{z} = (1, 1, 0, 0, 0, 1, 0).$
- Für das vorliegende $\underline{y}$ ist keine eindeutige Decodierung möglich.
+
- Für das vorliegende&nbsp; $\underline{y}$&nbsp; ist keine eindeutige Decodierung möglich.
  
{Welche Konsequenzen ergeben sich aus den grünen Eintragungen für $\boldsymbol{\rm H}_{\rm K}$ und  $z_{\rm K}$ (siehe Grafik auf der Angabenseite)?
+
{Welche Konsequenzen ergeben sich aus den grünen Eintragungen für&nbsp; $\boldsymbol{\rm H}_{\rm K}$&nbsp; und&nbsp; $z_{\rm K}$&nbsp; (siehe Grafik auf der Angabenseite)?
 
|type="[]"}
 
|type="[]"}
+ Das Empfangswort lautet $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E}).$
+
+ Das Empfangswort lautet&nbsp; $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E}).$
- $\boldsymbol{\rm H}_{\rm K}$  unterscheidet sich gegenüber Teilfrage (2) in der letzten Zeile.
+
- $\boldsymbol{\rm H}_{\rm K}$&nbsp; unterscheidet sich gegenüber Teilfrage&nbsp; '''(2)'''&nbsp; in der letzten Zeile.
+ $\boldsymbol{\rm H}_{\rm K}$ unterscheidet sich gegenüber Teilfrage (2) in der letzten Spalte.
+
+ $\boldsymbol{\rm H}_{\rm K}$&nbsp; unterscheidet sich gegenüber Teilfrage&nbsp; '''(2)'''&nbsp; in der letzten Spalte.
  
{Nun gelte $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E}).$ Welches Codewort wird ausgewählt?
+
{Nun gelte&nbsp; $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E}).$&nbsp; Welches Codewort wird ausgewählt?
 
|type="()"}
 
|type="()"}
 
- $\underline{z} = (1, 1, 0, 1, 1, 1, 0),$
 
- $\underline{z} = (1, 1, 0, 1, 1, 1, 0),$
 
- $\underline{z} = (1, 1, 0, 1, 0, 0, 1),$
 
- $\underline{z} = (1, 1, 0, 1, 0, 0, 1),$
 
- $\underline{z} = (1, 1, 0, 0, 0, 1, 0).$
 
- $\underline{z} = (1, 1, 0, 0, 0, 1, 0).$
+ Für das vorliegende $\underline{y}$ ist keine eindeutige Decodierung möglich.
+
+ Für das vorliegende&nbsp; $\underline{y}$&nbsp; ist keine eindeutige Decodierung möglich.
  
{Welche Aussagen ergeben sich für die Korrekturfähigkeit beim BEC? $n_{\rm E}$ gibt dabei die Anzahl der Auslöschungen (''Erasures'') an.
+
{Welche Aussagen ergeben sich für die Korrekturfähigkeit beim BEC?&nbsp; $n_{\rm E}$&nbsp; gibt im Folgenden die Anzahl der Auslöschungen&nbsp; ("Erasures")&nbsp; an.
 
|type="[]"}
 
|type="[]"}
+ Für $n_{\rm E} < d_{\rm min}$ ist stets eine eindeutige Decodierung möglich.
+
+ Für&nbsp; $n_{\rm E} < d_{\rm min}$&nbsp; ist stets eine eindeutige Decodierung möglich.
- Für $n_{\rm E} = d_{\rm min}$ ist stets eine eindeutige Decodierung möglich.
+
- Für&nbsp; $n_{\rm E} = d_{\rm min}$&nbsp; ist stets eine eindeutige Decodierung möglich.
+ Für $n_{\rm E} = d_{\rm min}$ ist manchmal eine eindeutige Decodierung möglich.
+
+ Für&nbsp; $n_{\rm E} = d_{\rm min}$&nbsp; ist manchmal eine eindeutige Decodierung möglich.
+ Für $n_{\rm E} > d_{\rm min}$ ist eine eindeutige Decodierung nie möglich.
+
+ Für&nbsp; $n_{\rm E} > d_{\rm min}$&nbsp; ist eine eindeutige Decodierung nie möglich.
 
</quiz>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp;  Der Empfangsvektor lautet $\underline{y} = (1, {\rm E}, 0, 1, 0, 0, {\rm E})$. Ausgelöscht wurden also die Codesymbole an den Positionen 2 und 7. Ausgehend von der vorgegebenen Prüfmatrix
+
'''(1)'''&nbsp;  Der Empfangsvektor lautet&nbsp; $\underline{y} = (1, {\rm E}, 0, 1, 0, 0, {\rm E})$.&nbsp; Ausgelöscht wurden also die Codesymbole an den Positionen 2 und 7.  
 +
 
 +
Ausgehend von der vorgegebenen Prüfmatrix
  
 
:$${ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &0 &1 &0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &1 &0 &1 &0 &0 &1 \end{pmatrix}$$
 
:$${ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &0 &1 &0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &1 &0 &1 &0 &0 &1 \end{pmatrix}$$
  
des Hammingcodes erhält man für Vektor und Matrix hinsichtlich
+
des Hammingcodes erhält man für Vektor und Matrix
  
*aller <b><span style="color: rgb(204, 0, 0);">korrekt übertragenen Codesymbole</span></b> (Index $\rm K$), die dem Codewortfinder bekannt sind:
+
* hinsichtlich aller&nbsp; "korrekt übertragenen Codesymbole"&nbsp; $($Index&nbsp; $\rm K)$,&nbsp; die dem Codewortfinder bekannt sind:
  
 
:$$\underline{z}_{\rm K} = (1, 0, 1, 0, 0)\hspace{0.05cm},\hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm K} = \begin{pmatrix} 1 &1 &0 &1 &0\\ 0 &1 &1 &0 &1\\ 1 &0 &1 &0 &0 \end{pmatrix} \hspace{0.05cm},$$
 
:$$\underline{z}_{\rm K} = (1, 0, 1, 0, 0)\hspace{0.05cm},\hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm K} = \begin{pmatrix} 1 &1 &0 &1 &0\\ 0 &1 &1 &0 &1\\ 1 &0 &1 &0 &0 \end{pmatrix} \hspace{0.05cm},$$
  
*hinsichtlich der beiden <b><span style="color: rgb(204, 0, 0);">ausgelöschten Codesymbole</span></b> $z_{2}$ und $z_{7}$ (Index $\rm E$), die zu ermitteln sind:
+
*hinsichtlich der beiden&nbsp; "ausgelöschten Codesymbole"&nbsp; $z_{2}$&nbsp; und&nbsp; $z_{7}$&nbsp; $($Index&nbsp; $\rm E)$,&nbsp; die zu ermitteln sind:
  
 
:$$\underline{z}_{\rm E} = (z_2, z_7)\hspace{0.05cm},\hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} 1 &0\\ 1 &0\\ 1 &1 \end{pmatrix} \hspace{0.05cm}.$$
 
:$$\underline{z}_{\rm E} = (z_2, z_7)\hspace{0.05cm},\hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} 1 &0\\ 1 &0\\ 1 &1 \end{pmatrix} \hspace{0.05cm}.$$
Zeile 98: Zeile 102:
 
Die Bestimmungsgleichung lautet somit:
 
Die Bestimmungsgleichung lautet somit:
  
:$${ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T}= { \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T}$$
+
:$${ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T}= { \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T}\hspace{0.3cm}
 +
\Rightarrow \hspace{0.3cm} \begin{pmatrix} 1 &0\\ 1 &0\\ 1 &1 \end{pmatrix} \cdot \begin{pmatrix} z_2 \\ z_7 \end{pmatrix} = \begin{pmatrix} 1 &1 &0 &1 &0\\ 0 &1 &1 &0 &1\\ 1 &0 &1 &0 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} \hspace{0.05cm}.$$
  
:$$\Rightarrow \hspace{0.3cm} \begin{pmatrix} 1 &0\\ 1 &0\\ 1 &1 \end{pmatrix} \cdot \begin{pmatrix} z_2 \\ z_7 \end{pmatrix} = \begin{pmatrix} 1 &1 &0 &1 &0\\ 0 &1 &1 &0 &1\\ 1 &0 &1 &0 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} \hspace{0.05cm}.$$
+
Daraus ergeben sich drei Gleichungen für die beiden Unbekannten $z_{2}$ und $z_{7}$:
  
Daraus ergeben sich drei Gleichungen für die beiden Unbekannten $z_{2}$ und $z_{7}$:
+
:$${\rm (a)}\ z_{2} = 1,$$
 +
:$${\rm (b)}\ z_{2} = 1,$$
 +
:$${\rm (c)}\ z_{2} + z_{7} = 0 \ \Rightarrow \ z_{7}= 1.$$  
  
# (a) $z_{2} = 1$,
 
# (b) $z_{2} = 1$,
 
# (c) $z_{2} + z_{7} = 0 \ \Rightarrow \ z_{7}= 1$.
 
  
 +
Somit liefert der Codewortfinder $\underline{z} = (1, 1, 0, 1, 0, 0, 1)$ &nbsp; ⇒ &nbsp; <u>Lösungsvorschlag 2</u>.
  
Somit liefert der Codewortfinder $\underline{z} = (1, 1, 0, 1, 0, 0, 1)$ &nbsp;⇒&nbsp; <u>Lösungsvorschlag 2</u>.
 
  
  
'''(2)'''&nbsp;  Betrachtet man die vorgegebene Matrix $\boldsymbol{\rm H}_{\rm K}$, so erkennt man, dass diese mit den ersten vier Spalten der Prüfmatrix $\boldsymbol{\rm H}$ übereinstimmt. Die Auslöschungen betreffen also die letzten 3 Bit des Empfangswortes &nbsp;⇒&nbsp; $\underline{z}_{\rm E} = (z_{5}, z_{6}, z_{7})    ⇒    \underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E})$ und die Erasure–Matrix lautet:
+
'''(2)'''&nbsp;  Betrachtet man die vorgegebene Matrix&nbsp; $\boldsymbol{\rm H}_{\rm K}$,&nbsp; so erkennt man,&nbsp; dass diese mit den ersten vier Spalten der Prüfmatrix&nbsp; $\boldsymbol{\rm H}$&nbsp; übereinstimmt.  
 +
*Die Auslöschungen betreffen also die letzten drei Bit des Empfangswortes &nbsp; ⇒ &nbsp; $\underline{z}_{\rm E} = (z_{5}, z_{6}, z_{7})$   &nbsp; &nbsp;   $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E})$.
 +
*Die Erasure–Matrix lautet:
 
   
 
   
 
:$${ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
 
:$${ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
  
Richtig sind demzufolge die <u>Aussagen 1, 2 und 4</u>.
+
Richtig sind demzufolge die&nbsp; <u>Aussagen 1, 2 und 4</u>.
 +
 
  
  
 
'''(3)'''&nbsp; Man erhält nach einigen Matrizenmultiplikationen:  
 
'''(3)'''&nbsp; Man erhält nach einigen Matrizenmultiplikationen:  
:$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T} = \begin{pmatrix} 1 &1 &1 &0\\ 0 &1 &1 &1\\ 1 &1 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \hspace{0.05cm},$$
+
:$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T} = \begin{pmatrix} 1 &1 &1 &0\\ 0 &1 &1 &1\\ 1 &1 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \hspace{0.05cm},\hspace{1cm}
 +
{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T} = \begin{pmatrix} 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} z_5 \\ z_6 \\ z_7 \end{pmatrix} = \begin{pmatrix} z_5 \\ z_6 \\ z_7 \end{pmatrix} \hspace{0.05cm}.$$
 +
 +
Durch Gleichsetzen folgt&nbsp; $z_{5} = 0, \ z_{6} = 0, \ z_{7} = 1$ &nbsp; ⇒ &nbsp; <u>Lösungsvorschlag 2</u>.
 +
 
 +
 
  
:$${ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T} = \begin{pmatrix} 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} z_5 \\ z_6 \\ z_7 \end{pmatrix} = \begin{pmatrix} z_5 \\ z_6 \\ z_7 \end{pmatrix} \hspace{0.05cm}.$$
+
'''(4)'''&nbsp; Der Matrizenvergleich zeigt,&nbsp; dass die ersten drei Spalten von&nbsp; $\boldsymbol{\rm H}$&nbsp; und&nbsp; $\boldsymbol{\rm H}_{\rm K}$&nbsp; identisch sind.
+
* Die vierte Spalte von&nbsp; $\boldsymbol{\rm H}_{\rm K}$&nbsp; ist gleich der fünften Spalte der Prüfmatrix.  
Durch Gleichsetzen folgt $z_{5} = 0, \ z_{6} = 0, \ z_{7} = 1$ &nbsp;⇒&nbsp; <u>Lösungsvorschlag 2</u>.
 
  
 +
*Daraus folgt für den Vektor&nbsp; $z_{\rm E} = (z_{4}, z_{6}, z_{7})$&nbsp; und weiter für den Empfangsvektor&nbsp; $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E})$ &nbsp; ⇒ &nbsp; <u>Lösungsvorschlag 1 und 3</u>.
  
'''(4)'''&nbsp; Der Matrizenvergleich zeigt, dass die ersten drei Spalten von $\boldsymbol{\rm H}$ und $\boldsymbol{\rm H}_{\rm K}$ identisch sind. Die vierte Spalte von $\boldsymbol{\rm H}_{\rm K}$ ist gleich der fünften Spalte der Prüfmatrix. Daraus folgt für den Vektor $z_{\rm E} = (z_{4}, z_{6}, z_{7})$ und weiter für den Empfangsvektor $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E})$ ⇒ <u>Lösungsvorschlag 1 und 3</u>.
 
  
  
'''(5)'''&nbsp;  Analog zur Teilaufgabe (3) erhält man nun:
+
'''(5)'''&nbsp;  Analog zur Teilaufgabe&nbsp; '''(3)'''&nbsp; erhält man nun:
 
   
 
   
:$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T} = \begin{pmatrix} 1 &1 &1 &1\\ 0 &1 &1 &0\\ 1 &1 &0 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \hspace{0.05cm},$$
+
:$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T} = \begin{pmatrix} 1 &1 &1 &1\\ 0 &1 &1 &0\\ 1 &1 &0 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \hspace{0.05cm},\hspace{1cm}
 +
{ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T} = \begin{pmatrix} 0 &0 &0\\ 1 &1 &0\\ 1 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} z_4 \\ z_6 \\ z_7 \end{pmatrix} = \begin{pmatrix} 0 \\ z_4 + z_6 \\ z_4 + z_7 \end{pmatrix} \hspace{0.05cm}.$$
 +
 +
* Setzt man nun die beiden Spaltenvektoren gleich,&nbsp; so erhält man nur mehr zwei Gleichungen für die drei Unbekannten &nbsp; ⇒ &nbsp; <u>Lösungsvorschlag 4</u>.&nbsp; Oder anders ausgedrückt: &nbsp;
 +
*Ist die Anzahl der Auslöschungen des BEC–Kanals größer als der Rang der MatrixOder anders ausgedrückt: &nbsp;  $\boldsymbol{\rm H}_{\rm E}$,Oder anders ausgedrückt: &nbsp;  so ergibt sich keine eindeutige Lösung des resultierenden Gleichungssystems.
  
:$${ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T} = \begin{pmatrix} 0 &0 &0\\ 1 &1 &0\\ 1 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} z_4 \\ z_6 \\ z_7 \end{pmatrix} = \begin{pmatrix} 0 \\ z_4 + z_6 \\ z_4 + z_7 \end{pmatrix} \hspace{0.05cm}.$$
 
 
Setzt man nun die beiden Spaltenvektoren gleich, so erhält man nur mehr zwei Gleichungen für die drei Unbekannten &nbsp;⇒&nbsp; <u>Lösungsvorschlag 4</u>.
 
Oder anders ausgedrückt: Ist die Anzahl der Auslöschungen des BEC–Kanals größer als der Rang der Matrix $\boldsymbol{\rm H}_{\rm E}$, so ergibt sich keine eindeutige Lösung des resultierenden Gleichungssystems.
 
  
  
'''(6)'''&nbsp; Zur Lösung dieser Aufgabe beziehen wir uns wieder auf den systematischen Hamming–Code $(7, 4, 3)$ entsprechend der angegebenen Prüfgleichung und der nachfolgenden Codetabelle. Die Informationsbit sind schwarz dargestellt und die Prüfbit rot. Die minimale Distanz dieses Codes beträgt $d_{\rm min} = 3$.
+
'''(6)'''&nbsp; Zur Lösung dieser Aufgabe beziehen wir uns wieder auf den systematischen Hamming–Code $(7, 4, 3)$ entsprechend der angegebenen Prüfgleichung und der angegebenen Codetabelle.
 +
[[Datei:P_ID2540__KC_A_1_13f.png|right|frame|Codetabelle des systematischenOder anders ausgedrückt: &nbsp;  $(7, 4, 3)$–Hamming–Codes<br><br><br>]]
 +
*Die Informationsbit sind schwarz dargestellt und die Prüfbit rot.&nbsp; Die minimale Distanz dieses Codes beträgt&nbsp; $d_{\rm min} = 3$.
  
[[Datei:P_ID2540__KC_A_1_13f.png|center|frame|Codetabelle des systematischen $(7, 4, 3)$–Hamming–Codes]]
+
*Weiter nehmen wir an,&nbsp; dass stets das gelb hinterlegte Codewort&nbsp; $\underline{x} = (1, 1, 0, 1, 0, 0, 1)$&nbsp; gesendet wurde.&nbsp; Dann gilt:
  
Weiter nehmen wir an, dass stets das gelb hinterlegte Codewort $\underline{x} = (1, 1, 0, 1, 0, 0, 1)$ gesendet wurde:
+
*Ist die Anzahl&nbsp; $n_{\rm E}$&nbsp; der Auslöschungen kleiner als&nbsp; $d_{\rm min} = 3$,&nbsp; so ist eine Decodierung nach der  beschriebenen Methode immer möglich &nbsp; ⇒ &nbsp; siehe  Aufgabe&nbsp; '''(1)'''&nbsp; mit&nbsp; $n_{\rm E}= 2$.
  
*Ist die Anzahl $n_{\rm E}$ der Auslöschungen kleiner als $d_{\rm min} = 3$, so ist eine Decodierung nach der hier beschriebenen Methode immer möglich &nbsp;&nbsp; siehe beispielsweise Teilaufgabe (1) mit $n_{E }= 2$.
+
*Für&nbsp; $n_{\rm E} = d_{\rm min} = 3$&nbsp; ist manchmal eine Decodierung möglich,&nbsp; siehe Aufgabe&nbsp; '''(3)'''.&nbsp;  Es gibt nur ein Codewort,&nbsp; das zum Empfangsvektor&nbsp; $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E})$&nbsp; passen könnte,&nbsp; nämlich das  gelb hinterlegte Codewort&nbsp; $\underline{x} = (1, 1, 0, 1, 0, 0, 1)$.
  
*Auch für $n_{\rm E} = d_{\rm min} = 3$ ist manchmal eine Decodierung möglich, wie in Aufgabe (3) gezeigt. In der Codetabelle gibt es nur ein einziges Codewort, das zum Empfangsvektor $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E})$ passen könnte, nämlich das gelb hinterlegte Codewort $\underline{x} = (1, 1, 0, 1, 0, 0, 1)$.
+
*Dagegen ist&nbsp; $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E})$&nbsp; gemäß Aufgabe&nbsp; '''(4)'''&nbsp; nicht decodierbar.&nbsp; In der Codetabelle erkennt man neben&nbsp; $(1, 1, 0, 1, 0, 0, 1)$&nbsp; mit&nbsp; $(1, 1, 0, 0, 0, 1, 0)$&nbsp; ein weiteres Codewort&nbsp; (grün hinterlegt),&nbsp; das durch die&nbsp; $n_{\rm E} = 3$&nbsp;  Auslöschungen bezüglich Bit 4, 6 und 7 zum Empfangswort&nbsp; $\underline{y}$&nbsp; wird.
  
*Dagegen konnte $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E})$ entsprechend Teilaufgabe (4) nicht decodiert werden. In der Codetabelle erkennt man neben $(1, 1, 0, 1, 0, 0, 1)$ mit $(1, 1, 0, 0, 0, 1, 0)$ ein weiteres Codewort (grün hinterlegt), das durch die $n_{\rm E} = 3$ gegebenen Auslöschungen zum Empfangswort $\underline{y}$ wird. Dieser Fall, wenn die $n_{\rm E} = d_{\rm min}$ Auslöschungen genau die $d_{\rm min}$ unterschiedlichen Bit zweier Codeworte betreffen, führt zu einer Matrix $\mathbf{H}_{\rm E}$ mit einem Rang kleiner als $d_{\rm min}$.
+
*Dieser Fall, wenn die&nbsp; $n_{\rm E} = d_{\rm min}$&nbsp; Auslöschungen die&nbsp; $d_{\rm min}$&nbsp; unterschiedlichen Bit zweier Codeworte betreffen, führt zu einer Matrix&nbsp; $\mathbf{H}_{\rm E}$&nbsp; mit Rang kleiner&nbsp; $d_{\rm min}$.
  
*Ist $\boldsymbol{\rm H}_{\rm E}  > d_{\rm min}$, so ist die Anzahl $n n_{\rm E}$ der nicht ausgelöschten Bit kleiner als die Anzahl $k$ der Informationsbit. In diesem Fall kann das Codewort natürlich nicht decodiert werden.
+
*Ist&nbsp; $n_{\rm E}  > d_{\rm min}$,&nbsp; so ist die Anzahl&nbsp; $n - n_{\rm E}$&nbsp; der nicht ausgelöschten Bit kleiner als die Anzahl&nbsp; $k$&nbsp; der Informationsbit.&nbsp; In diesem Fall kann das Codewort natürlich nicht decodiert werden.
  
  
Das heißt: Zutreffend sind die <u>Aussagen 1, 3 und 4</u>.
+
Das heißt: &nbsp; Zutreffend sind die&nbsp; <u>Aussagen 1, 3 und 4</u>.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 21. Juli 2022, 16:46 Uhr

Zur Decodierung beim BEC

Wir gehen hier vom Modell im Abschnitt  "Decodierung beim Binary Erasure Channel"  aus  (grün hinterlegte BEC–Konfiguration):

  • Jedes Informationswort  $\underline{u}$  wird blockweise codiert und liefert das Codewort  $\underline{x}$.  Der Blockcode sei linear und durch seine Prüfmatrix  $\boldsymbol{\rm H}$  vollständig gegeben.
  • Bei der Übertragung werden  $n_{\rm E}$  Bit des Codewortes ausgelöscht   ⇒  "Binary Erasure Channel"  $\rm (BEC)$.  Aus dem Codewort  $\underline{x}$  wird somit das Empfangswort  $\underline{y}$.
  • Ist die Anzahl  $n_{\rm E}$  der Auslöschungen kleiner als die  "minimale Distanz"  $d_{\rm min}$  des Codes,  so gelingt es,  aus  $\underline{y}$   das Codewort  $\underline{z} = \underline{x}$  ohne Fehler zu rekonstruieren,  und man erhält so auch das richtige Informationswort  $\underline{v} = \underline{u}$.


Zur Aufgabenbeschreibung betrachten wir nun beispielhaft das Hamming–Codewort   $\underline{x} = (0, 1, 0, 1, 1, 0, 0)$   und das Empfangswort   $\underline{y} = (0, 1, {\rm E} , {\rm E}, 1, 0, 0).$

  • Ausgelöscht wurden somit durch den Kanal das dritte und vierte Bit.  Der Codewortfinder hat somit die Aufgabe,  den Vektor  $z_{\rm E} = (z_{3}, z_{4})$  mit  $z_{3}, \ z_{4} \in \{0, 1\}$  zu bestimmen.  Dies geschieht entsprechend der Gleichung
$${ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T}= { \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T}\hspace{0.05cm}.$$
  • Im vorliegenden Beispiel gilt:
$$\underline{z}_{\rm K} = (0, 1, 1, 0, 0)\hspace{0.05cm},\hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm K} = \begin{pmatrix} 1 &1 &1 &0 &0\\ 0 &1 &0 &1 &0\\ 1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}, \hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} 1 &0\\ 1 &1\\ 0 &1 \end{pmatrix} \hspace{0.05cm}.$$
  • Wir haben nun zwei Gleichungen für die zu bestimmenden Bits,  deren Lösung zum Ergebnis  $z_{3} = 0$  und  $z_{4} = 1$  führt.



Hinweise:

  • Der Algorithmus zur Zuordnung des Empfangswortes  $\underline{y}$  zum richtigen Codewort  $\underline{z} = \underline{x}$  ist im  "Theorieteil"  ausführlich beschrieben.
  • Wir möchten nochmals daran erinnern, dass wir bei der BEC–Decodierung den ersten Decoderblock  $\underline{y} → \underline{z}$  als  "Codewortfinder"  bezeichnen,  da hier Fehlentscheidungen ausgeschlossen sind.  Jedes Empfangswort wird richtig decodiert,  oder es kann gar nicht decodiert werden.
  • Beim BSC–Modell lassen sich dagegen Decodierfehler nicht vermeiden.  Dementsprechend bezeichnen wir den entsprechenden Block dort als  "Codewortschätzer".



Fragebogen

1

Empfangen wurde  $\underline{y} = (1, {\rm E}, 0, 1, 0, 0, {\rm E})$.  Für welche Sequenz entscheidet sich der Codewortfinder?

$\underline{z} = (1, 0, 0, 1, 0, 0, 0),$
$\underline{z} = (1, 1, 0, 1, 0, 0, 1),$
$\underline{z} = (1, 0, 0, 1, 0, 0, 1).$

2

Welche Konsequenzen ergeben sich aus den roten Eintragungen für  $\boldsymbol{\rm H}_{\rm K}$  und  $z_{\rm K}$  (siehe Grafik auf der Angabenseite)?

Der Erasure–Vektor lautet  $\underline{z}_{\rm E} = (z_{5}, z_{6}, z_{7}).$
Das Empfangswort lautet  $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E}).$
$\boldsymbol{\rm H}_{\rm E}$  ist eine  $2 \times 3$–Matrix.
$\boldsymbol{\rm H}_{\rm E}$  ist eine  $3 \times 3$–Matrix.

3

Nun gelte  $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E}).$  Welches Codewort wird ausgewählt?

$\underline{z} = (1, 1, 0, 1, 1, 1, 0),$
$\underline{z} = (1, 1, 0, 1, 0, 0, 1),$
$\underline{z} = (1, 1, 0, 0, 0, 1, 0).$
Für das vorliegende  $\underline{y}$  ist keine eindeutige Decodierung möglich.

4

Welche Konsequenzen ergeben sich aus den grünen Eintragungen für  $\boldsymbol{\rm H}_{\rm K}$  und  $z_{\rm K}$  (siehe Grafik auf der Angabenseite)?

Das Empfangswort lautet  $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E}).$
$\boldsymbol{\rm H}_{\rm K}$  unterscheidet sich gegenüber Teilfrage  (2)  in der letzten Zeile.
$\boldsymbol{\rm H}_{\rm K}$  unterscheidet sich gegenüber Teilfrage  (2)  in der letzten Spalte.

5

Nun gelte  $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E}).$  Welches Codewort wird ausgewählt?

$\underline{z} = (1, 1, 0, 1, 1, 1, 0),$
$\underline{z} = (1, 1, 0, 1, 0, 0, 1),$
$\underline{z} = (1, 1, 0, 0, 0, 1, 0).$
Für das vorliegende  $\underline{y}$  ist keine eindeutige Decodierung möglich.

6

Welche Aussagen ergeben sich für die Korrekturfähigkeit beim BEC?  $n_{\rm E}$  gibt im Folgenden die Anzahl der Auslöschungen  ("Erasures")  an.

Für  $n_{\rm E} < d_{\rm min}$  ist stets eine eindeutige Decodierung möglich.
Für  $n_{\rm E} = d_{\rm min}$  ist stets eine eindeutige Decodierung möglich.
Für  $n_{\rm E} = d_{\rm min}$  ist manchmal eine eindeutige Decodierung möglich.
Für  $n_{\rm E} > d_{\rm min}$  ist eine eindeutige Decodierung nie möglich.


Musterlösung

(1)  Der Empfangsvektor lautet  $\underline{y} = (1, {\rm E}, 0, 1, 0, 0, {\rm E})$.  Ausgelöscht wurden also die Codesymbole an den Positionen 2 und 7.

Ausgehend von der vorgegebenen Prüfmatrix

$${ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &0 &1 &0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &1 &0 &1 &0 &0 &1 \end{pmatrix}$$

des Hammingcodes erhält man für Vektor und Matrix

  • hinsichtlich aller  "korrekt übertragenen Codesymbole"  $($Index  $\rm K)$,  die dem Codewortfinder bekannt sind:
$$\underline{z}_{\rm K} = (1, 0, 1, 0, 0)\hspace{0.05cm},\hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm K} = \begin{pmatrix} 1 &1 &0 &1 &0\\ 0 &1 &1 &0 &1\\ 1 &0 &1 &0 &0 \end{pmatrix} \hspace{0.05cm},$$
  • hinsichtlich der beiden  "ausgelöschten Codesymbole"  $z_{2}$  und  $z_{7}$  $($Index  $\rm E)$,  die zu ermitteln sind:
$$\underline{z}_{\rm E} = (z_2, z_7)\hspace{0.05cm},\hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} 1 &0\\ 1 &0\\ 1 &1 \end{pmatrix} \hspace{0.05cm}.$$

Die Bestimmungsgleichung lautet somit:

$${ \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T}= { \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} \begin{pmatrix} 1 &0\\ 1 &0\\ 1 &1 \end{pmatrix} \cdot \begin{pmatrix} z_2 \\ z_7 \end{pmatrix} = \begin{pmatrix} 1 &1 &0 &1 &0\\ 0 &1 &1 &0 &1\\ 1 &0 &1 &0 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} \hspace{0.05cm}.$$

Daraus ergeben sich drei Gleichungen für die beiden Unbekannten $z_{2}$ und $z_{7}$:

$${\rm (a)}\ z_{2} = 1,$$
$${\rm (b)}\ z_{2} = 1,$$
$${\rm (c)}\ z_{2} + z_{7} = 0 \ \Rightarrow \ z_{7}= 1.$$


Somit liefert der Codewortfinder $\underline{z} = (1, 1, 0, 1, 0, 0, 1)$   ⇒   Lösungsvorschlag 2.


(2)  Betrachtet man die vorgegebene Matrix  $\boldsymbol{\rm H}_{\rm K}$,  so erkennt man,  dass diese mit den ersten vier Spalten der Prüfmatrix  $\boldsymbol{\rm H}$  übereinstimmt.

  • Die Auslöschungen betreffen also die letzten drei Bit des Empfangswortes   ⇒   $\underline{z}_{\rm E} = (z_{5}, z_{6}, z_{7})$   ⇒   $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E})$.
  • Die Erasure–Matrix lautet:
$${ \boldsymbol{\rm H}}_{\rm E} = \begin{pmatrix} 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$

Richtig sind demzufolge die  Aussagen 1, 2 und 4.


(3)  Man erhält nach einigen Matrizenmultiplikationen:

$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T} = \begin{pmatrix} 1 &1 &1 &0\\ 0 &1 &1 &1\\ 1 &1 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \hspace{0.05cm},\hspace{1cm} { \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T} = \begin{pmatrix} 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} z_5 \\ z_6 \\ z_7 \end{pmatrix} = \begin{pmatrix} z_5 \\ z_6 \\ z_7 \end{pmatrix} \hspace{0.05cm}.$$

Durch Gleichsetzen folgt  $z_{5} = 0, \ z_{6} = 0, \ z_{7} = 1$   ⇒   Lösungsvorschlag 2.


(4)  Der Matrizenvergleich zeigt,  dass die ersten drei Spalten von  $\boldsymbol{\rm H}$  und  $\boldsymbol{\rm H}_{\rm K}$  identisch sind.

  • Die vierte Spalte von  $\boldsymbol{\rm H}_{\rm K}$  ist gleich der fünften Spalte der Prüfmatrix.
  • Daraus folgt für den Vektor  $z_{\rm E} = (z_{4}, z_{6}, z_{7})$  und weiter für den Empfangsvektor  $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E})$   ⇒   Lösungsvorschlag 1 und 3.


(5)  Analog zur Teilaufgabe  (3)  erhält man nun:

$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline{z}_{\rm K}^{\rm T} = \begin{pmatrix} 1 &1 &1 &1\\ 0 &1 &1 &0\\ 1 &1 &0 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \hspace{0.05cm},\hspace{1cm} { \boldsymbol{\rm H}}_{\rm E} \cdot \underline{z}_{\rm E}^{\rm T} = \begin{pmatrix} 0 &0 &0\\ 1 &1 &0\\ 1 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} z_4 \\ z_6 \\ z_7 \end{pmatrix} = \begin{pmatrix} 0 \\ z_4 + z_6 \\ z_4 + z_7 \end{pmatrix} \hspace{0.05cm}.$$
  • Setzt man nun die beiden Spaltenvektoren gleich,  so erhält man nur mehr zwei Gleichungen für die drei Unbekannten   ⇒   Lösungsvorschlag 4.  Oder anders ausgedrückt:  
  • Ist die Anzahl der Auslöschungen des BEC–Kanals größer als der Rang der MatrixOder anders ausgedrückt:   $\boldsymbol{\rm H}_{\rm E}$,Oder anders ausgedrückt:   so ergibt sich keine eindeutige Lösung des resultierenden Gleichungssystems.


(6)  Zur Lösung dieser Aufgabe beziehen wir uns wieder auf den systematischen Hamming–Code $(7, 4, 3)$ entsprechend der angegebenen Prüfgleichung und der angegebenen Codetabelle.

Codetabelle des systematischenOder anders ausgedrückt:   $(7, 4, 3)$–Hamming–Codes


  • Die Informationsbit sind schwarz dargestellt und die Prüfbit rot.  Die minimale Distanz dieses Codes beträgt  $d_{\rm min} = 3$.
  • Weiter nehmen wir an,  dass stets das gelb hinterlegte Codewort  $\underline{x} = (1, 1, 0, 1, 0, 0, 1)$  gesendet wurde.  Dann gilt:
  • Ist die Anzahl  $n_{\rm E}$  der Auslöschungen kleiner als  $d_{\rm min} = 3$,  so ist eine Decodierung nach der beschriebenen Methode immer möglich   ⇒   siehe Aufgabe  (1)  mit  $n_{\rm E}= 2$.
  • Für  $n_{\rm E} = d_{\rm min} = 3$  ist manchmal eine Decodierung möglich,  siehe Aufgabe  (3).  Es gibt nur ein Codewort,  das zum Empfangsvektor  $\underline{y} = (1, 1, 0, 1, {\rm E}, {\rm E}, {\rm E})$  passen könnte,  nämlich das gelb hinterlegte Codewort  $\underline{x} = (1, 1, 0, 1, 0, 0, 1)$.
  • Dagegen ist  $\underline{y} = (1, 1, 0, {\rm E}, 0, {\rm E}, {\rm E})$  gemäß Aufgabe  (4)  nicht decodierbar.  In der Codetabelle erkennt man neben  $(1, 1, 0, 1, 0, 0, 1)$  mit  $(1, 1, 0, 0, 0, 1, 0)$  ein weiteres Codewort  (grün hinterlegt),  das durch die  $n_{\rm E} = 3$  Auslöschungen bezüglich Bit 4, 6 und 7 zum Empfangswort  $\underline{y}$  wird.
  • Dieser Fall, wenn die  $n_{\rm E} = d_{\rm min}$  Auslöschungen die  $d_{\rm min}$  unterschiedlichen Bit zweier Codeworte betreffen, führt zu einer Matrix  $\mathbf{H}_{\rm E}$  mit Rang kleiner  $d_{\rm min}$.
  • Ist  $n_{\rm E} > d_{\rm min}$,  so ist die Anzahl  $n - n_{\rm E}$  der nicht ausgelöschten Bit kleiner als die Anzahl  $k$  der Informationsbit.  In diesem Fall kann das Codewort natürlich nicht decodiert werden.


Das heißt:   Zutreffend sind die  Aussagen 1, 3 und 4.