Aufgaben:Aufgabe 1.13Z: Nochmals BEC–Decodierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(11 dazwischenliegende Versionen von 4 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung linearer Blockcodes
+
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung linearer Blockcodes}}
  
 +
[[Datei:P_ID2541__KC_Z_1_13.png|right|frame|Codetabelle des  $\rm HC \ (7, 4, 3)$]]
  
}}
+
Wir betrachten wieder wie in der  [[Aufgaben:Aufgabe_1.13:_Decodierung_beim_binären_Auslöschungskanal_(BEC)|Aufgabe 1.13]]  die Decodierung eines  [[Kanalcodierung/Beispiele_binärer_Blockcodes#Hamming.E2.80.93Codes|Hamming–Codes]]  nach der Übertragung über einen Auslöschungskanal   ⇒   [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|Binary Erasure Channel]]  (abgekürzt BEC).
  
[[Datei:P_ID2541__KC_Z_1_13.png|right|frame|Codetabelle des vorgegebenen Hamming–Codes]]
+
Der  $(7, 4, 3)$–Hamming–Code wird durch die nebenstehende Codetabelle  $\underline{u}_{i} → \underline{x}_{i}$  vollständig beschrieben, anhand derer alle Lösungen gefunden werden können.
  
Wir betrachten wieder wie in der vorherigen Aufgabe die Decodierung eines [[Kanalcodierung/Beispiele_binärer_Blockcodes#Hamming.E2.80.93Codes|Hamming–Codes]] nach der Übertragung über einen Auslöschungskanal ⇒ [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|Binary Erasure Channel]] (abgekürzt BEC).
 
Der (7, 4, 3)–Hamming–Code wird durch die nebenstehende Codetabelle $\underline{u}_{i} → \underline{x}_{i}$ vollständig beschrieben, anhand derer alle Lösungen gefunden werden können.
 
  
  
  
  
''Hinweis'' :
 
  
  
Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes|Decodierung linearer Blockcodes]]. Im Gegensatz zur [[Aufgaben:1.13_BEC–Decodierung|Aufgabe 1.13]] soll hier die Lösung nicht streng formal, sondern eher intuitiv gefunden werden.
+
''Hinweise'' :
 +
* Die Aufgabe bezieht sich auf das Kapitel  [[Kanalcodierung/Decodierung_linearer_Blockcodes|Decodierung linearer Blockcodes]].
 +
* Im Gegensatz zur   [[Aufgaben:Aufgabe_1.13:_Decodierung_beim_binären_Auslöschungskanal_(BEC)|Aufgabe 1.13]]  soll hier die Lösung nicht formal, sondern intuitiv gefunden werden.
 +
 +
 
  
 
===Fragebogen===
 
===Fragebogen===
 
 
<quiz display=simple>
 
<quiz display=simple>
 
+
Wie groß ist die minimale Distanz&nbsp; $\ d_{\rm min}$&nbsp; des vorliegenden Codes?
 
 
 
 
Wie groß ist die minimale Distanz des vorliegenden Codes?
 
 
|type="{}"}
 
|type="{}"}
$\ d_{\rm min}$ = { 3 3% }
+
$\ d_{\rm min} \ = \ $ { 3 }
  
 
{Ist der Code systematisch?
 
{Ist der Code systematisch?
|type="[]"}
+
|type="()"}
 
+ JA.
 
+ JA.
 
- NEIN.
 
- NEIN.
  
 
+
{Bis zu wie vielen Auslöschungen (&bdquo;Erasures&rdquo;; &nbsp; maximale Anzahl:&nbsp; $e_{\rm max})$&nbsp; ist eine erfolgreiche Decodierung gewährleistet?
{Bis zu wie vielen ''Erasures'' ist die erfolgreiche Decodierung gewährleistet?
 
 
|type="{}"}
 
|type="{}"}
$\ e_{\ max}$ = { 2 3% }
+
$\ e_{\rm max} \ = \ $ { 2 }
  
{Wie lautet das gesendete Informationswort <u>''u''</u> für $\underline{y} = (1, 0, {\rm E}, {\rm E}, 0, 1, 0)$?
+
{Wie lautet das gesendete Informationswort&nbsp; $\underline{u}$&nbsp; für&nbsp; $\underline{y} = (1, 0, {\rm E}, {\rm E}, 0, 1, 0)$?
|type="[]"}
+
|type="()"}
 
- $\underline{u} = (1, 0, 0, 0),$
 
- $\underline{u} = (1, 0, 0, 0),$
 
+ $\underline{u}= (1, 0, 0, 1),$
 
+ $\underline{u}= (1, 0, 0, 1),$
Zeile 55: Zeile 52:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Betrachtet wird der (7, 4, 3)–Hamming–Code. Dementsprechend ist die minimale Distanz $d_{\rm min} \underline{= 3}$.
+
'''(1)'''&nbsp; Betrachtet wird hier der $(7, 4, 3)$–Hamming–Code. Dementsprechend ist die minimale Distanz $d_{\rm min} \ \underline{= 3}$.
  
  
'''(2)'''&nbsp; Die ersten $k = 4$ Bit eines jeden Codewortes <u>''x''</u> stimmen mit dem Informationswort u überein. Richtig ist somit <u>JA</u>.
 
  
 +
'''(2)'''&nbsp; Die ersten $k = 4$ Bit eines jeden Codewortes $\underline{x}$ stimmen mit dem Informationswort $\underline{u}$ überein. Richtig ist somit <u>JA</u>.
  
  
  
'''(3)'''&nbsp;  Es können bis zu $e_{\rm max} = d_{\rm min} – 1 \underline{ = 2}$ Bit ausgelöscht sein, damit eine Decodierung mit Sicherheit möglich ist. Jedes Codewort unterscheidet sich von jedem anderen in mindestens drei Bitpositionen. Bei nur zwei Auslöschungen kann deshalb das Codewort in jedem Fall rekonstruiert werden.
+
'''(3)'''&nbsp;  Werden nicht mehr als $e_{\rm max} = d_{\rm min} – 1 \underline{ = 2}$ Bit ausgelöscht,so ist eine Decodierung mit Sicherheit möglich.  
 +
*Jedes Codewort unterscheidet sich von jedem anderen in mindestens drei Bitpositionen.  
 +
*Bei nur zwei Auslöschungen kann deshalb das Codewort in jedem Fall rekonstruiert werden.
  
  
  
'''(4)'''&nbsp;  In der Tabelle auf der Angabenseite findet man ein einziges Codewort, das mit „10” beginnt und mit „010” endet, nämlich $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$. Da es sich um einen systematischen Code handelt, beschreiben die ersten $k = 4$ Bit das Informationswort $\underline{u} = (1, 0, 0, 1)$ ⇒ <u>Antwort 2</u>.
+
 
 +
'''(4)'''&nbsp;  In der Codetabelle findet man ein einziges Codewort, das mit „$10$” beginnt und mit „$010$” endet, nämlich $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$.  
 +
Da es sich um einen systematischen Code handelt, beschreiben die ersten $k = 4$ Bit das Informationswort $\underline{u} = (1, 0, 0, 1)$ &nbsp; &nbsp;  <u>Antwort 2</u>.
 +
 
  
  
 
'''(5)'''&nbsp;  Richtig sind die <u>Lösungsvorschläge 1 und 2</u>.
 
'''(5)'''&nbsp;  Richtig sind die <u>Lösungsvorschläge 1 und 2</u>.
  
* $\underline{y}_{\rm D} = (1, 0, {\rm E},  {\rm E},  {\rm E},  {\rm E}, 0)$ kann nicht decodiert werden, da weniger als $k = 4$ Bit (Anzahl der Informationsbit) ankommen.
+
* $\underline{y}_{\rm D} = (1, 0, {\rm E},  {\rm E},  {\rm E},  {\rm E}, 0)$&nbsp; kann nicht decodiert werden, da weniger als&nbsp; $k = 4$&nbsp; Bit (Anzahl der Informationsbit) ankommen.
  
*$\underline{y}_{\rm C} = ( {\rm E},  {\rm E},  {\rm E}, 1, 0, 1, 0)$ ist ebenfalls nicht decodierbar, da sowohl $\underline{x} = (0, 1, 1, 1, 0, 1, 0)$ als auch $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$ als mögliches Ergebnis in Frage kommen.
+
*Auch &nbsp;$\underline{y}_{\rm C} = ( {\rm E},  {\rm E},  {\rm E}, 1, 0, 1, 0)$&nbsp; kann nicht decodierbar, da&nbsp;  $\underline{x} = (0, 1, 1, 1, 0, 1, 0)$&nbsp; und &nbsp; $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$&nbsp; als mögliches Ergebnis in Frage kommen.
  
*$\underline{y}_{\rm B} = ( {\rm E},  {\rm E}, 0,  {\rm E}, 0, 1, 0)$ ist dagegen decodierbar, da von allen 16 möglichen Codeworten nur $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$ mit $\underline{y}_{\rm B}$ in den (richtigen) Bitpositionen 3, 5, 6 und 7 übereinstimmt.
+
*$\underline{y}_{\rm B} = ( {\rm E},  {\rm E}, 0,  {\rm E}, 0, 1, 0)$&nbsp; ist decodierbar, da von den 16 möglichen Codeworten nur&nbsp; $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$&nbsp; mit&nbsp; $\underline{y}_{\rm B}$&nbsp; in den Positionen 3, 5, 6, 7 übereinstimmt.
  
 
*$\underline{y}_{\rm A} = (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E})$ ist decodierbar. Es fehlen nur die $m = 3$ Prüfbit. Damit liegt das Informationswort $\underline{u} = (1, 0, 0, 1)$ ebenfalls fest (systematischer Code).
 
*$\underline{y}_{\rm A} = (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E})$ ist decodierbar. Es fehlen nur die $m = 3$ Prüfbit. Damit liegt das Informationswort $\underline{u} = (1, 0, 0, 1)$ ebenfalls fest (systematischer Code).
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 13. Mai 2019, 14:20 Uhr

Codetabelle des  $\rm HC \ (7, 4, 3)$

Wir betrachten wieder wie in der  Aufgabe 1.13  die Decodierung eines  Hamming–Codes  nach der Übertragung über einen Auslöschungskanal   ⇒   Binary Erasure Channel  (abgekürzt BEC).

Der  $(7, 4, 3)$–Hamming–Code wird durch die nebenstehende Codetabelle  $\underline{u}_{i} → \underline{x}_{i}$  vollständig beschrieben, anhand derer alle Lösungen gefunden werden können.




Hinweise :


Fragebogen

1

Wie groß ist die minimale Distanz  $\ d_{\rm min}$  des vorliegenden Codes?

$\ d_{\rm min} \ = \ $

2

Ist der Code systematisch?

JA.
NEIN.

3

Bis zu wie vielen Auslöschungen („Erasures”;   maximale Anzahl:  $e_{\rm max})$  ist eine erfolgreiche Decodierung gewährleistet?

$\ e_{\rm max} \ = \ $

4

Wie lautet das gesendete Informationswort  $\underline{u}$  für  $\underline{y} = (1, 0, {\rm E}, {\rm E}, 0, 1, 0)$?

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

5

Welche der nachfolgenden Empfangsworte können decodiert werden?

$\underline{y}_{\rm A }= (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E}),$
$\underline{y}_{\rm B} = ({\rm E}, {\rm E }, 0, {\rm E}, 0, 1, 0),$
$\underline{y}_{\rm C} = ({\rm E}, {\rm E}, {\rm E}, 1, 0, 1, 0),$
$\underline{y}_{\rm D} = (1, 0, {\rm E}, {\rm E}, {\rm E}, {\rm E}, 0).$


Musterlösung

(1)  Betrachtet wird hier der $(7, 4, 3)$–Hamming–Code. Dementsprechend ist die minimale Distanz $d_{\rm min} \ \underline{= 3}$.


(2)  Die ersten $k = 4$ Bit eines jeden Codewortes $\underline{x}$ stimmen mit dem Informationswort $\underline{u}$ überein. Richtig ist somit JA.


(3)  Werden nicht mehr als $e_{\rm max} = d_{\rm min} – 1 \underline{ = 2}$ Bit ausgelöscht,so ist eine Decodierung mit Sicherheit möglich.

  • Jedes Codewort unterscheidet sich von jedem anderen in mindestens drei Bitpositionen.
  • Bei nur zwei Auslöschungen kann deshalb das Codewort in jedem Fall rekonstruiert werden.



(4)  In der Codetabelle findet man ein einziges Codewort, das mit „$10$” beginnt und mit „$010$” endet, nämlich $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$. Da es sich um einen systematischen Code handelt, beschreiben die ersten $k = 4$ Bit das Informationswort $\underline{u} = (1, 0, 0, 1)$   ⇒  Antwort 2.


(5)  Richtig sind die Lösungsvorschläge 1 und 2.

  • $\underline{y}_{\rm D} = (1, 0, {\rm E}, {\rm E}, {\rm E}, {\rm E}, 0)$  kann nicht decodiert werden, da weniger als  $k = 4$  Bit (Anzahl der Informationsbit) ankommen.
  • Auch  $\underline{y}_{\rm C} = ( {\rm E}, {\rm E}, {\rm E}, 1, 0, 1, 0)$  kann nicht decodierbar, da  $\underline{x} = (0, 1, 1, 1, 0, 1, 0)$  und   $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$  als mögliches Ergebnis in Frage kommen.
  • $\underline{y}_{\rm B} = ( {\rm E}, {\rm E}, 0, {\rm E}, 0, 1, 0)$  ist decodierbar, da von den 16 möglichen Codeworten nur  $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$  mit  $\underline{y}_{\rm B}$  in den Positionen 3, 5, 6, 7 übereinstimmt.
  • $\underline{y}_{\rm A} = (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E})$ ist decodierbar. Es fehlen nur die $m = 3$ Prüfbit. Damit liegt das Informationswort $\underline{u} = (1, 0, 0, 1)$ ebenfalls fest (systematischer Code).