Aufgaben:Aufgabe 2.9: Huffman-Decodierung nach Fehlern: Unterschied zwischen den Versionen
Zeile 31: | Zeile 31: | ||
− | {Welche Folge ergibt sich nach der Decodierung, wenn das erste Bit verfälscht wird (<b>1</b> → <b>0</b>)? | + | {Welche Folge ergibt sich nach der Decodierung, wenn das erste Bit verfälscht wird (<b>1</b> → <b>0</b>)? <br> ⇒ Anliegende Empfangsfolge <b><font color="#cc0000"><span style="font-weight: bold;">0</span></font>0100100011000010011</b>. |
|type="[]"} | |type="[]"} | ||
+ <b>CCDAADBCA</b>, | + <b>CCDAADBCA</b>, | ||
Zeile 47: | Zeile 47: | ||
− | {Welche Folge ergibt sich nach der Decodierung, wenn das sechste Bit verfälscht wird (<b>1</b> → <b>0</b>)? | + | {Welche Folge ergibt sich nach der Decodierung, wenn das sechste Bit verfälscht wird (<b>1</b> → <b>0</b>)? <br>⇒ Anliegende Empfangsfolge <b>10100<font color="#cc0000"><span style="font-weight: bold;">0</span></font>00011000010011</b>. |
|type="[]"} | |type="[]"} | ||
- <b>CCDAADBCA</b>, | - <b>CCDAADBCA</b>, | ||
Zeile 60: | Zeile 60: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | + | '''(1)''' Richtig ist der <u>Vorschlag 3</u>. Nachfolgend sehen Sie die durch Hochkommata eingeteilte Codesymbolfolge <b>1′01′001′000′1′1′000′01′001′1</b> ⇒ Quellensymbolfolge <b>ABCDAADBCA</b>. | |
− | |||
− | :<b><font color="#cc0000"><span style="font-weight: bold;">0</span></font>01′001′000′1′1′000′01′001′1</b> ⇒ <b> | + | '''(2)''' Mit einem Bitfehler an Position 1 erhält man das folgende Decodierergebnis: |
+ | |||
+ | :<b><font color="#cc0000"><span style="font-weight: bold;">0</span></font>01′001′000′1′1′000′01′001′1</b> ⇒ <b><font color="#cc0000"><span style="font-weight: bold;">C</span></font>CDAADBCA</b> ⇒ <u>Lösungsvorschlag 1</u>. | ||
Das heißt: <b>AB</b> wird durch <b>C</b> ersetzt, der weitere Text <b>CDAADBCA</b> ist unverändert, allerdings um eine Position verschoben. Vergleicht man jedoch die ersten neun Symbole des Originals mit der Decodierung <i>Stelle für Stelle</i>, wie es ein Automat machen würde, so erkennt man acht unterschiedliche Symbole. | Das heißt: <b>AB</b> wird durch <b>C</b> ersetzt, der weitere Text <b>CDAADBCA</b> ist unverändert, allerdings um eine Position verschoben. Vergleicht man jedoch die ersten neun Symbole des Originals mit der Decodierung <i>Stelle für Stelle</i>, wie es ein Automat machen würde, so erkennt man acht unterschiedliche Symbole. | ||
− | |||
− | + | '''(3)''' Richtig sind die <u>Antworten 1 und 3</u>: | |
− | + | * Durch einen zusätzlichen Bitfehler an Position 2 (<b>0</b> → <b>1</b>) wird <b>AB</b> zu <b>BA</b> verfälscht, aber alle weiteren Symbole wieder richtig erkannt. | |
+ | * Ein zusätzlicher Bitfehler an Position 15 (<b>0</b> → <b>1</b>) führt zu <b>001′001′000′1′1′000′<font color="#cc0000"><span style="font-weight: bold;">1</span></font>′ 1′ 001′ 1</b> und damit zur Sinkensymbolfolge <b>CCDAADAA<font color="#008800"><span style="font-weight: bold;">CA</span></font></b>. Das neunte und das zehnte Symbol (beide grün markiert) und eventuell weitere Symbole werden richtig erkannt. | ||
+ | * Durch den ersten Bitfehler an Position 1 wird <b>AB</b> in <b>C</b> verfälscht, also ein Zeichen „verschluckt”. Ein weiterer Bitfehler an Position 10 macht aus <b>AA</b> ein <b>B</b>. Insgesamt verschluckt so der Decoder zwei Zeichen. Alle nachfolgend decodierten Zeichen stehen nicht an der richtigen Position. | ||
− | |||
− | + | '''(4)''' Aus <b>001</b> wird <b>000</b>. Das bewirkt, dass insgesamt nur ein Fehler <b>C</b> → <b>D</b> entsteht: | |
− | <b><font color="#000000"><span style="font-weight: bold;">1</span></font>01′00 | + | : <b><font color="#000000"><span style="font-weight: bold;">1</span></font>01′00<font color="#cc0000"><span style="font-weight: bold;">0</span></font>′000′1′1′000′01′001′1</b> ⇒ <b>AB<font color="#cc0000"><span style="font-weight: bold;">D</span></font>DAADBCA</b> ⇒ <u>Lösungsvorschlag 2</u>. |
{{ML-Fuß}} | {{ML-Fuß}} | ||
Version vom 24. Mai 2017, 15:21 Uhr
Wir betrachten die Huffman–Codierung gemäß folgender Zuordnung:
- A → 1, B → 01, C → 001, D → 000.
Die Codierung nach Huffman ist stets verlustlos. Das bedeutet: Decodiert man die Codesymbolfolge $\langle c_\nu \rangle$ nach dem Huffman–Codierer sofort wieder, so ist das Decodierergebnis $\langle v_\nu \rangle$ gleich der Quellensymbolfolge $\langle q_\nu \rangle$.
Stimmt dagegen die Empfangsfolge $\langle r_\nu \rangle$ aufgrund von Fehlern bei der Übertragung (0 → 1, 1 → 0) mit der erzeugten Codefolge $\langle c_\nu \rangle$ nicht überein, so kann es zu einer Fehlerfortpflanzung kommen. Ein einziger Bitfehler kann dann dazu führen, dass (nahezu) alle nachfolgenden Zeichen falsch decodiert werden.
Hinweise:
- Die Aufgabe gehört zum Kapitel Entropiecodierung nach Huffman.
- Insbesondere wird auf die Seite Einfluss von Übertragungsfehlern auf die Decodierung Bezug genommen.
- Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Fragebogen
Musterlösung
(2) Mit einem Bitfehler an Position 1 erhält man das folgende Decodierergebnis:
- 001′001′000′1′1′000′01′001′1 ⇒ CCDAADBCA ⇒ Lösungsvorschlag 1.
Das heißt: AB wird durch C ersetzt, der weitere Text CDAADBCA ist unverändert, allerdings um eine Position verschoben. Vergleicht man jedoch die ersten neun Symbole des Originals mit der Decodierung Stelle für Stelle, wie es ein Automat machen würde, so erkennt man acht unterschiedliche Symbole.
(3) Richtig sind die Antworten 1 und 3:
- Durch einen zusätzlichen Bitfehler an Position 2 (0 → 1) wird AB zu BA verfälscht, aber alle weiteren Symbole wieder richtig erkannt.
- Ein zusätzlicher Bitfehler an Position 15 (0 → 1) führt zu 001′001′000′1′1′000′1′ 1′ 001′ 1 und damit zur Sinkensymbolfolge CCDAADAACA. Das neunte und das zehnte Symbol (beide grün markiert) und eventuell weitere Symbole werden richtig erkannt.
- Durch den ersten Bitfehler an Position 1 wird AB in C verfälscht, also ein Zeichen „verschluckt”. Ein weiterer Bitfehler an Position 10 macht aus AA ein B. Insgesamt verschluckt so der Decoder zwei Zeichen. Alle nachfolgend decodierten Zeichen stehen nicht an der richtigen Position.
(4) Aus 001 wird 000. Das bewirkt, dass insgesamt nur ein Fehler C → D entsteht:
- 101′000′000′1′1′000′01′001′1 ⇒ ABDDAADBCA ⇒ Lösungsvorschlag 2.