Difference between revisions of "Aufgaben:Exercise 1.13Z: Binary Erasure Channel Decoding again"
| Line 20: | Line 20: | ||
<quiz display=simple> | <quiz display=simple> | ||
| − | { | + | |
| + | |||
| + | |||
| + | Wie groß ist die minimale Distanz des vorliegenden Codes? | ||
| + | |type="{}"} | ||
| + | $\ d_{\rm min}$ = { 3 3% } | ||
| + | |||
| + | {Ist der Code systematisch? | ||
|type="[]"} | |type="[]"} | ||
| − | - | + | + JA. |
| − | + | - NEIN. | |
| − | { | + | {Bis zu wie vielen ''Erasures'' ist die erfolgreiche Decodierung gewährleistet? |
|type="{}"} | |type="{}"} | ||
| − | $\ | + | $\ e_{\ max}$ = { 2 3% } |
| + | {Wie lautet das gesendete Informationswort <u>''u''</u> für $\underline{y} = (1, 0, {\rm E}, {\rm E}, 0, 1, 0)$? | ||
| + | |type="[]"} | ||
| + | - $\underline{u} = (1, 0, 0, 0),$ | ||
| + | + $\underline{u}= (1, 0, 0, 1),$ | ||
| + | - $\underline{u} = (1, 0, 1, 0),$ | ||
| + | - $\underline{u} = (1, 0, 1, 1).$ | ||
| + | {Welche der nachfolgenden Empfangsworte können decodiert werden? | ||
| + | |type="[]"} | ||
| + | + $\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).$ | ||
</quiz> | </quiz> | ||
| Line 36: | Line 55: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''1 | + | '''(1)''' Betrachtet wird der (7, 4, 3)–Hamming–Code. Dementsprechend ist die minimale Distanz $d_{\rm min} \underline{= 3}$. |
| − | '''2 | + | |
| − | '''3 | + | |
| − | '''4 | + | '''(2)''' Die ersten $k = 4$ Bit eines jeden Codewortes <u>''x''</u> stimmen mit dem Informationswort u überein. Richtig ist somit <u>JA</u>. |
| − | '''5 | + | |
| − | + | ||
| − | + | ||
| + | |||
| + | '''(3)''' 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. | ||
| + | |||
| + | |||
| + | |||
| + | '''(4)''' 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>. | ||
| + | |||
| + | |||
| + | '''(5)''' 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 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. | ||
| + | |||
| + | *$\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 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ß}} | ||
Revision as of 17:09, 11 December 2017
Wir betrachten wieder wie in der vorherigen Aufgabe 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.
Hinweis :
Die Aufgabe bezieht sich auf das Kapitel Decodierung linearer Blockcodes. Im Gegensatz zur Aufgabe 1.13 soll hier die Lösung nicht streng formal, sondern eher intuitiv gefunden werden.
Fragebogen
Musterlösung
(2) Die ersten $k = 4$ Bit eines jeden Codewortes x stimmen mit dem Informationswort u überein. Richtig ist somit JA.
(3) 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.
(4) 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)$ ⇒ 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.
- $\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.
- $\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 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).
