Aufgaben:Aufgabe 1.13Z: Nochmals BEC–Decodierung: Unterschied zwischen den Versionen
Aus LNTwww
Wael (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „{{quiz-Header|Buchseite=Kanalcodierung/Decodierung linearer Blockcodes }} [[Datei:|right|]] ===Fragebogen=== <quiz display=simple> {Multiple-Choice Frage…“) |
|||
| (14 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). | |
| − | [[ | + | 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'' : | ||
| + | * 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 $\ d_{\rm min}$ des vorliegenden Codes? |
| − | |type=" | + | |type="{}"} |
| − | + | $\ d_{\rm min} \ = \ $ { 3 } | |
| − | |||
| + | {Ist der Code systematisch? | ||
| + | |type="()"} | ||
| + | + JA. | ||
| + | - NEIN. | ||
| − | { | + | {Bis zu wie vielen Auslöschungen („Erasures”; maximale Anzahl: $e_{\rm max})$ ist eine erfolgreiche Decodierung gewährleistet? |
|type="{}"} | |type="{}"} | ||
| − | $\ | + | $\ e_{\rm max} \ = \ $ { 2 } |
| + | {Wie lautet das gesendete Informationswort $\underline{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> | ||
| Zeile 26: | Zeile 52: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''1 | + | '''(1)''' Betrachtet wird hier der $(7, 4, 3)$–Hamming–Code. Dementsprechend ist die minimale Distanz $d_{\rm min} \ \underline{= 3}$. |
| − | '''2 | + | |
| − | '''3 | + | |
| − | '''4 | + | |
| − | '''5 | + | '''(2)''' Die ersten $k = 4$ Bit eines jeden Codewortes $\underline{x}$ stimmen mit dem Informationswort $\underline{u}$ überein. Richtig ist somit <u>JA</u>. |
| − | + | ||
| − | + | ||
| + | |||
| + | '''(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)$ ⇒ <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. | ||
| + | |||
| + | *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). | ||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Aktuelle Version vom 13. Mai 2019, 15: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 :
- Die Aufgabe bezieht sich auf das Kapitel Decodierung linearer Blockcodes.
- Im Gegensatz zur Aufgabe 1.13 soll hier die Lösung nicht formal, sondern intuitiv gefunden werden.
Fragebogen
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).
