Aufgaben:Aufgabe 2.9: Huffman-Decodierung nach Fehlern: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(13 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2464__Inf_A_2_9.png|right|]]
+
[[Datei:P_ID2464__Inf_A_2_9.png|right|frame|Gesamtsystem mit "Huffman"]]
 
Wir betrachten die Huffman–Codierung gemäß folgender Zuordnung:
 
Wir betrachten die Huffman–Codierung gemäß folgender Zuordnung:
  
:<b>A</b> &#8594; <b>1</b>, <b>B</b> &#8594; <b>01</b>, <b>C</b> &#8594; <b>001</b>, <b>D</b> &#8594; <b>000</b>.
+
: &nbsp; $\rm A$ &nbsp; &#8594; &nbsp; <b>1</b>, &nbsp; &nbsp; $\rm B$ &nbsp; &#8594; &nbsp;  <b>01</b>, &nbsp; &nbsp; $\rm C$ &nbsp; &#8594; &nbsp; <b>001</b>, &nbsp; &nbsp; $\rm D$ &nbsp; &#8594; &nbsp; <b>000</b>.
  
Die Codierung nach Huffman ist stets <i>verlustlos</i>. Das bedeutet: Decodiert man die Codesymbolfolge &#9001;<i>c<sub>&nu;</sub></i>&#9002; nach dem Huffman&ndash;Codierer sofort wieder, so ist das Decodierergebnis &#9001;<i>&upsilon;<sub>&nu;</sub></i>&#9002; gleich der Quellensymbolfolge &#9001;<i>q<sub>&nu;</sub></i>&#9002;.
+
Die Codierung nach Huffman ist stets&nbsp; <u>verlustlos</u>.&nbsp; Das bedeutet:  
 +
*Decodiert man die Codesymbolfolge&nbsp; $\langle c_\nu \rangle$&nbsp; nach dem Huffman&ndash;Codierer sofort wieder, so ist das Decodierergebnis&nbsp; $\langle v_\nu \rangle$&nbsp; gleich der Quellensymbolfolge&nbsp; $\langle q_\nu \rangle$.
  
Stimmt dagegen die Empfangsfolge &#9001;<i>r<sub>&nu;</sub></i>&#9002; aufgrund von Fehlern bei der Übertragung (<b>0</b> &#8594; <b>1</b>, <b>1</b> &#8594; <b>0</b>) mit der erzeugten Codefolge &#9001;<i>c<sub>&nu;</sub></i>&#9002; 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.
+
*Stimmt dagegen die Empfangsfolge&nbsp; $\langle r_\nu \rangle$&nbsp; aufgrund von Fehlern bei der Übertragung&nbsp; $($<b>0</b> &nbsp;  &#8594; &nbsp; <b>1</b>, &nbsp;  &nbsp; <b>1</b> &nbsp;  &#8594; &nbsp; <b>0</b>$)$&nbsp;  mit der erzeugten Codefolge&nbsp; $\langle c_\nu \rangle$&nbsp; 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.
 +
 
 +
 
 +
 
 +
 
 +
 
 +
<u>Hinweise:</u>
 +
*Die Aufgabe gehört zum  Kapitel&nbsp;  [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]].
 +
*Insbesondere wird auf die Seite&nbsp;  [[Informationstheorie/Entropiecodierung_nach_Huffman#Einfluss_von_.C3.9Cbertragungsfehlern_auf_die_Decodierung|Einfluss von Übertragungsfehlern auf die Decodierung]]&nbsp;  Bezug genommen.
 +
  
<b>Hinweis:</b> Die Aufgabe bezieht sich auf die Seite 5 von Kapitel 2.3.
 
  
  
Zeile 18: Zeile 28:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Wir betrachten die Codesymbolfolge <b>10100100011000010011</b>. Wie lautet die dazugehörige Quellensymbolfolge?
+
{Wir betrachten die Codesymbolfolge&nbsp;  $\langle c_\nu \rangle = \rm \langle 10100100011000010011 \rangle$.&nbsp;  Wie lautet die dazugehörige Quellensymbolfolge?
|type="[]"}
+
|type="()"}
- <b>CCDAADBCA</b>,
+
- $\langle q_\nu \rangle = \rm \langle \rm CCDAADBCA \rangle$,
- <b>ABDDAADBCA</b>,
+
- $\langle q_\nu \rangle = \rm \langle\rm ABDDAADBCA \rangle$,
+ <b>ABCDAADBCA</b>,
+
+ $\langle q_\nu \rangle = \rm \langle\rm ABCDAADBCA \rangle$,
- Anders als die drei genannten.
+
- Anders als die drei oben genannten.
  
  
{Welche Folge ergibt sich nach der Decodierung, wenn das erste Bit verfälscht wird (<b>1</b> &#8594; <b>0</b>)? &nbsp;&#8658;&nbsp; Anliegende Folge <b>00100100011000010011</b>.
+
{Welche Folge&nbsp;  $\langle v_\nu \rangle$&nbsp;  ergibt sich nach der Decodierung, wenn das erste Bit verfälscht wird&nbsp;  $\rm (1 &nbsp; &#8594; &nbsp; 0)$? <br> &nbsp;  &nbsp;  $\langle c_\nu \rangle = \rm \langle 10100100011000010011 \rangle$ &nbsp; &nbsp; &rArr; &nbsp; &nbsp; $\langle r_\nu \rangle = \rm \langle \underline{0}0100100011000010011 \rangle$.
|type="[]"}
+
|type="()"}
+ <b>CCDAADBCA</b>,
+
+ $\langle v_\nu \rangle = \rm \langle \rm CCDAADBCA \rangle$,
- <b>ABDDAADBCA</b>,
+
- $\langle v_\nu \rangle = \rm \langle\rm ABDDAADBCA \rangle$,
- <b>ABCDAADBCA</b>,
+
- $\langle v_\nu \rangle = \rm \langle\rm ABCDAADBCA \rangle$,
- Anders als die drei genannten.
+
- Eine andere, als die drei genannten.
  
  
{Ist es möglich, dass durch einen weiteren Bitfehler die späteren Symbole alle wieder richtig decodiert werden?
+
{Ist es möglich, dass durch einen weiteren Bitfehler die späteren Symbole alle wieder richtig decodiert werden?  
 
|type="[]"}
 
|type="[]"}
 
+ Ja, durch einen zweiten Bitfehler an Position 2.
 
+ Ja, durch einen zweiten Bitfehler an Position 2.
Zeile 42: Zeile 52:
  
  
{Welche Folge ergibt sich nach der Decodierung, wenn das sechste Bit verfälscht wird (<b>1</b> &#8594; <b>0</b>)?
+
{Welche Folge&nbsp;  $\langle v_\nu \rangle$&nbsp;  ergibt sich nach der Decodierung, wenn das sechste Bit verfälscht wird&nbsp;  $\rm (1 &nbsp; &#8594; &nbsp; 0)$? <br> &nbsp;  &nbsp; $\langle c_\nu \rangle = \rm \langle 10100100011000010011 \rangle$ &nbsp; &rArr; &nbsp; $\langle r_\nu \rangle = \rm \langle 10100\underline{0}00011000010011 \rangle$.
|type="[]"}
+
|type="()"}
- <b>CCDAADBCA</b>,
+
- $\langle v_\nu \rangle = \rm \langle \rm CCDAADBCA \rangle$,
+ <b>ABDDAADBCA</b>,
+
+ $\langle v_\nu \rangle = \rm \langle\rm ABDDAADBCA \rangle$,
- <b>ABCDAADBCA</b>,
+
- $\langle v_\nu \rangle = \rm \langle\rm ABCDAADBCA \rangle$,
- Anders als die drei genannten..
+
- Eine andere, als die drei genannten.
  
  
Zeile 55: Zeile 65:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
<b>1.</b>&nbsp;&nbsp;Richtig ist der <u>Vorschlag 3</u>. Nachfolgend sehen Sie die durch Hochkommata eingeteilte Codesymbolfolge <b>1&prime;01&prime;001&prime;000&prime;1&prime;1&prime;000&prime;01&prime;001&prime;1</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Quellensymbolfolge <b>ABCDAADBCA</b>.
+
'''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>:
 +
*Nachfolgend sehen Sie die durch Hochkommata eingeteilte Codesymbolfolge:
 +
:$$\langle c_\nu \rangle = \rm \langle 1'01'001'000'1'1'000'01'001'1 \rangle .$$
 +
*Diese gehört zur folgenden Quellensymbolfolge:
 +
:$$\langle q_\nu \rangle = \rm \langle ABCDAADBCA \rangle .$$
 +
 
 +
 
 +
 
 +
'''(2)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>:
 +
*Mit einem Bitfehler an der Position 1 erhält man für die Empfangsfolge:
 +
:$$\langle r_\nu \rangle = \rm \langle 00100100011000010011 \rangle .$$
 +
*Die Hochkommata verdeutlichen wieder die einzelnen Blöcke der Decodierung:
 +
:$$\langle r_\nu \rangle = \rm \langle 001'001'000'1'1'000'01'001'1 \rangle .$$
 +
*Dies führt zur folgenden Sinkensymbolfolge:
 +
:$$\langle v_\nu \rangle = \rm \langle CCDAADBCA \rangle .$$
 +
 
 +
Interpretation:
 +
*$\rm AB$&nbsp; wird durch&nbsp; $\rm C$&nbsp; ersetzt, der weitere Text&nbsp; $\rm CDAADBCA$&nbsp; ist unverändert, allerdings um eine Position verschoben.
 +
*Vergleicht man jedoch die ersten neun Symbole des Originals mit der Decodierung <u>Stelle für Stelle</u>, wie es ein Automat machen würde, so erkennt man acht unterschiedliche Symbole.
 +
 
 +
 
 +
 
 +
'''(3)'''&nbsp; Richtig sind die <u>Antworten 1 und 3</u>:
 +
 
 +
* Durch einen zusätzlichen Bitfehler an Position 2&nbsp; $\rm (0 &nbsp; &#8594; &nbsp; 1)$&nbsp; wird&nbsp; $\rm AB$&nbsp; zu&nbsp; $\rm BA$&nbsp; verfälscht, aber alle weiteren Symbole wieder richtig erkannt.
 +
* Ein zusätzlicher Bitfehler an Position 15&nbsp;  $\rm (0 &nbsp; &#8594; &nbsp; 1)$&nbsp; führt zu
 +
:$$\langle r_\nu \rangle = \rm {\langle \underline{0}01'001'000'1'1'000'\underline{1}'1'001'1 \rangle} \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\langle \it v_\nu \rangle = \rm \langle \underline{C}CDAAD\underline{AA}CA \rangle .$$
 +
 +
::Durch den Bitfehler an Position 1&nbsp;  $\rm (1 &nbsp; &#8594; &nbsp; 0)$&nbsp; wird &nbsp; $\rm AB$&nbsp; in&nbsp; $\rm C$&nbsp; verfälscht, also ein Zeichen &bdquo;verschluckt&rdquo;. Durch den zusätzlichen Bitfehler an Position 15&nbsp; $\rm (0 &nbsp; &#8594; &nbsp; 1)$&nbsp; wird aus&nbsp; $\rm B$&nbsp; das Tupel&nbsp; $\rm AA$.&nbsp; Danach werden alle Symbole an der richtigen Position richtig erkannt, beginnend mit&nbsp; $\rm CA$.
  
<b>2.</b>&nbsp;&nbsp;Mit einem Bitfehler an Position 1 erhält man das folgende Decodierergebnis:
+
* Ein zusätzlicher Bitfehler an Position 10&nbsp;  $\rm (1 &nbsp; &#8594; &nbsp; 0)$&nbsp; führt dagegen zu
 +
:$$\langle r_\nu \rangle = \rm \langle \underline{0}01'001'000'\underline{0}'1'000'0'1'001'1 \rangle \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\langle \it  v_\nu \rangle = \rm \langle \underline{C}CDAAD\underline{B}CA \rangle .$$ 
 +
::Der Bitfehler an Position 10 macht aus&nbsp; $\rm AA$&nbsp; ein&nbsp; $\rm B$.&nbsp; Insgesamt verschluckt so der Decoder zwei Zeichen.&nbsp; Alle nachfolgend decodierten Zeichen stehen dann nicht an der richtigen Position.
  
:<b><font color="#cc0000"><span style="font-weight: bold;">0</span></font>01&prime;001&prime;000&prime;1&prime;1&prime;000&prime;01&prime;001&prime;1</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>CCDAADBCA</b> &#8658; <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.
 
  
<b>3.</b>&nbsp;&nbsp;Richtig sind die <u>Antworten 1 und 3</u>:
+
'''(4)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
  
:* Durch einen zusätzlichen Bitfehler an Position 2 (<b>0</b> &#8594; <b>1</b>) wird <b>AB</b> zu <b>BA</b> verfälscht, aber alle weiteren Symbole wieder richtig erkannt.
+
*Der erste Bitfehler an der Position 6&nbsp;  $\rm (1 &nbsp; &#8594; &nbsp; 0)$&nbsp; liefert
 +
:$$\langle r_\nu \rangle = \rm \langle 101'00\underline{0}'000'1'000'0'1'001'1 \rangle \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\langle \it  v_\nu \rangle = \rm \langle AB\underline{D}DAADBCA \rangle .$$ 
  
:* Ein zusätzlicher Bitfehler an Position 15 (<b>0</b> &#8594; <b>1</b>) führt zu <b>001&prime;001&prime;000&prime;1&prime;1&prime;000&prime;<font color="#cc0000"><span style="font-weight: bold;">1</span></font>&prime; 1&prime; 001&prime; 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.
+
*Aus dem ersten&nbsp; $\rm C$&nbsp; wird ein $\rm D$.&nbsp; Alle anderen Symbole werden richtig decodiert.
  
:* Durch den ersten Bitfehler an Position 1 wird <b>AB</b> in <b>C</b> verfälscht, also ein Zeichen &bdquo;verschluckt&rdquo;. Ein weiterer Bitfehler an Position 10 macht aus <b>AA</b> ein <b>B</b>. Insgesamt verschluckt so der Decoder zwei Zeichen, und alle nachfolgend decodierten Zeichen stehen nicht an der richtigen Position.
 
  
<b>4.</b>&nbsp;&nbsp;Aus <b>001</b> wird <b>000</b>. Das bewirkt, dass insgesamt nur ein Fehler <b>C</b> &#8594; <b>D</b> entsteht:
 
  
<b><font color="#000000"><span style="font-weight: bold;">1</span></font>01&prime;00<b><font color="#cc0000"><span style="font-weight: bold;">0</span></font>&prime;000&prime;1&prime;1&prime;000&prime;01&prime;001&prime;1</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>AB<font color="#cc0000"><span style="font-weight: bold;">D</span></font>DAADBCA</b> &nbsp;&nbsp;&#8658;&nbsp;&nbsp;</b> <u>Lösungsvorschlag 2</u>.
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 11. August 2021, 15:04 Uhr

Gesamtsystem mit "Huffman"

Wir betrachten die Huffman–Codierung gemäß folgender Zuordnung:

  $\rm A$   →   1,     $\rm B$   →   01,     $\rm C$   →   001,     $\rm 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:



Fragebogen

1

Wir betrachten die Codesymbolfolge  $\langle c_\nu \rangle = \rm \langle 10100100011000010011 \rangle$.  Wie lautet die dazugehörige Quellensymbolfolge?

$\langle q_\nu \rangle = \rm \langle \rm CCDAADBCA \rangle$,
$\langle q_\nu \rangle = \rm \langle\rm ABDDAADBCA \rangle$,
$\langle q_\nu \rangle = \rm \langle\rm ABCDAADBCA \rangle$,
Anders als die drei oben genannten.

2

Welche Folge  $\langle v_\nu \rangle$  ergibt sich nach der Decodierung, wenn das erste Bit verfälscht wird  $\rm (1   →   0)$?
    $\langle c_\nu \rangle = \rm \langle 10100100011000010011 \rangle$     ⇒     $\langle r_\nu \rangle = \rm \langle \underline{0}0100100011000010011 \rangle$.

$\langle v_\nu \rangle = \rm \langle \rm CCDAADBCA \rangle$,
$\langle v_\nu \rangle = \rm \langle\rm ABDDAADBCA \rangle$,
$\langle v_\nu \rangle = \rm \langle\rm ABCDAADBCA \rangle$,
Eine andere, als die drei genannten.

3

Ist es möglich, dass durch einen weiteren Bitfehler die späteren Symbole alle wieder richtig decodiert werden?

Ja, durch einen zweiten Bitfehler an Position 2.
Ja, durch einen zweiten Bitfehler an Position 10.
Ja, durch einen zweiten Bitfehler an Position 15.
Nein.

4

Welche Folge  $\langle v_\nu \rangle$  ergibt sich nach der Decodierung, wenn das sechste Bit verfälscht wird  $\rm (1   →   0)$?
    $\langle c_\nu \rangle = \rm \langle 10100100011000010011 \rangle$   ⇒   $\langle r_\nu \rangle = \rm \langle 10100\underline{0}00011000010011 \rangle$.

$\langle v_\nu \rangle = \rm \langle \rm CCDAADBCA \rangle$,
$\langle v_\nu \rangle = \rm \langle\rm ABDDAADBCA \rangle$,
$\langle v_\nu \rangle = \rm \langle\rm ABCDAADBCA \rangle$,
Eine andere, als die drei genannten.


Musterlösung

(1)  Richtig ist der Lösungsvorschlag 3:

  • Nachfolgend sehen Sie die durch Hochkommata eingeteilte Codesymbolfolge:
$$\langle c_\nu \rangle = \rm \langle 1'01'001'000'1'1'000'01'001'1 \rangle .$$
  • Diese gehört zur folgenden Quellensymbolfolge:
$$\langle q_\nu \rangle = \rm \langle ABCDAADBCA \rangle .$$


(2)  Richtig ist der Lösungsvorschlag 1:

  • Mit einem Bitfehler an der Position 1 erhält man für die Empfangsfolge:
$$\langle r_\nu \rangle = \rm \langle 00100100011000010011 \rangle .$$
  • Die Hochkommata verdeutlichen wieder die einzelnen Blöcke der Decodierung:
$$\langle r_\nu \rangle = \rm \langle 001'001'000'1'1'000'01'001'1 \rangle .$$
  • Dies führt zur folgenden Sinkensymbolfolge:
$$\langle v_\nu \rangle = \rm \langle CCDAADBCA \rangle .$$

Interpretation:

  • $\rm AB$  wird durch  $\rm C$  ersetzt, der weitere Text  $\rm 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  $\rm (0   →   1)$  wird  $\rm AB$  zu  $\rm BA$  verfälscht, aber alle weiteren Symbole wieder richtig erkannt.
  • Ein zusätzlicher Bitfehler an Position 15  $\rm (0   →   1)$  führt zu
$$\langle r_\nu \rangle = \rm {\langle \underline{0}01'001'000'1'1'000'\underline{1}'1'001'1 \rangle} \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\langle \it v_\nu \rangle = \rm \langle \underline{C}CDAAD\underline{AA}CA \rangle .$$
Durch den Bitfehler an Position 1  $\rm (1   →   0)$  wird   $\rm AB$  in  $\rm C$  verfälscht, also ein Zeichen „verschluckt”. Durch den zusätzlichen Bitfehler an Position 15  $\rm (0   →   1)$  wird aus  $\rm B$  das Tupel  $\rm AA$.  Danach werden alle Symbole an der richtigen Position richtig erkannt, beginnend mit  $\rm CA$.
  • Ein zusätzlicher Bitfehler an Position 10  $\rm (1   →   0)$  führt dagegen zu
$$\langle r_\nu \rangle = \rm \langle \underline{0}01'001'000'\underline{0}'1'000'0'1'001'1 \rangle \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\langle \it v_\nu \rangle = \rm \langle \underline{C}CDAAD\underline{B}CA \rangle .$$
Der Bitfehler an Position 10 macht aus  $\rm AA$  ein  $\rm B$.  Insgesamt verschluckt so der Decoder zwei Zeichen.  Alle nachfolgend decodierten Zeichen stehen dann nicht an der richtigen Position.


(4)  Richtig ist der Lösungsvorschlag 2:

  • Der erste Bitfehler an der Position 6  $\rm (1   →   0)$  liefert
$$\langle r_\nu \rangle = \rm \langle 101'00\underline{0}'000'1'000'0'1'001'1 \rangle \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\langle \it v_\nu \rangle = \rm \langle AB\underline{D}DAADBCA \rangle .$$
  • Aus dem ersten  $\rm C$  wird ein $\rm D$.  Alle anderen Symbole werden richtig decodiert.