Aufgaben:Aufgabe 1.13Z: Nochmals BEC–Decodierung: Unterschied zwischen den Versionen
Aus LNTwww
| (6 dazwischenliegende Versionen von 2 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 | + | [[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 des vorliegenden Codes? | + | Wie groß ist die minimale Distanz $\ d_{\rm min}$ des vorliegenden Codes? |
|type="{}"} | |type="{}"} | ||
| − | $\ d_{\rm min} \ = \ $ { 3 | + | $\ d_{\rm min} \ = \ $ { 3 } |
{Ist der Code systematisch? | {Ist der Code systematisch? | ||
| − | |type=" | + | |type="()"} |
+ JA. | + JA. | ||
- NEIN. | - NEIN. | ||
| − | {Bis zu wie vielen | + | {Bis zu wie vielen Auslöschungen („Erasures”; maximale Anzahl: $e_{\rm max})$ ist eine erfolgreiche Decodierung gewährleistet? |
|type="{}"} | |type="{}"} | ||
| − | $\ e_{\ max} \ = \ $ { 2 | + | $\ e_{\rm max} \ = \ $ { 2 } |
| − | {Wie lautet das gesendete Informationswort $\underline{u}$ für $\underline{y} = (1, 0, {\rm E}, {\rm E}, 0, 1, 0)$? | + | {Wie lautet das gesendete Informationswort $\underline{u}$ für $\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 49: | Zeile 52: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
| − | '''(1)''' Betrachtet wird der $(7, 4, 3)$–Hamming–Code. Dementsprechend ist die minimale Distanz $d_{\rm min} \ \underline{= 3}$. | + | '''(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 <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>. | '''(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 | + | * $\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)$ | + | *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 | + | *$\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). | *$\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). | ||
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).
