Aufgaben:Exercise 2.9: Huffman Decoding after Errors - Revision history

Hwang at 15:29, 23 January 2023

2023-01-23T15:29:44Z

Javier: Text replacement - "code symbol sequence" to "encoded sequence"

2021-08-16T12:07:57Z

Text replacement - "code symbol sequence" to "encoded sequence"

Guenter at 13:46, 11 August 2021

2021-08-11T13:46:13Z

Guenter at 13:34, 11 August 2021

2021-08-11T13:34:46Z

Guenter at 12:17, 10 August 2021

2021-08-10T12:17:03Z

Noah at 19:59, 6 August 2021

2021-08-06T19:59:37Z

Noah at 20:29, 4 August 2021

2021-08-04T20:29:35Z

Show changes

Guenter at 13:00, 16 July 2021

2021-07-16T13:00:51Z

Guenter at 14:08, 8 July 2021

2021-07-08T14:08:56Z

Guenter: Guenter moved page Aufgaben:Aufgabe 2.9: Huffman-Decodierung nach Fehlern to Aufgaben:Exercise 2.9: Huffman Decoding after Errors

2021-07-03T15:23:11Z

Guenter moved page Aufgabe 2.9: Huffman-Decodierung nach Fehlern to Exercise 2.9: Huffman Decoding after Errors

@@ Line 37: / Line 37: @@
-{Which sequence&nbsp;  $\langle v_\nu \rangle$&nbsp; results after decoding if the first bit is corrupted&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$.
+{Which sequence&nbsp;  $\langle v_\nu \rangle$&nbsp; results after decoding if the first bit is falsified&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="()"}
 + $\langle v_\nu \rangle = \rm \langle \rm CCDAADBCA \rangle$,
@@ Line 53: / Line 53: @@
-{Which sequence&nbsp;  $\langle v_\nu \rangle$&nbsp; results after decoding if the sixth bit is corrupted&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$.
+{Which sequence&nbsp;  $\langle v_\nu \rangle$&nbsp; results after decoding if the sixth bit is falsified&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="()"}
 - $\langle v_\nu \rangle = \rm \langle \rm CCDAADBCA \rangle$,

@@ Line 9: / Line 9: @@
 Huffman coding is always&nbsp; <u>lossless</u>.&nbsp; This means:
-*If the code symbol sequence&nbsp; $\langle c_\nu \rangle$&nbsp; is immediately decoded again after the Huffman encoder, the decoding result&nbsp; $\langle v_\nu \rangle$&nbsp; is equal to the source symbol sequence&nbsp; $\langle q_\nu \rangle$.
+*If the encoded sequence&nbsp; $\langle c_\nu \rangle$&nbsp; is immediately decoded again after the Huffman encoder, the decoding result&nbsp; $\langle v_\nu \rangle$&nbsp; is equal to the source symbol sequence&nbsp; $\langle q_\nu \rangle$.
 *If, on the other hand, the  reception sequence&nbsp; $\langle r_\nu \rangle$&nbsp;&nbsp; does not match the generated code sequence&nbsp;  $\langle c_\nu \rangle$&nbsp; due to errors during transmission&nbsp; <br>$($<b>0</b> &nbsp;  &#8594; &nbsp; <b>1</b>, &nbsp;  &nbsp; <b>1</b> &nbsp;  &#8594; &nbsp; <b>0</b>$)$, error propagation may occur.
@@ Line 29: / Line 29: @@
 <quiz display=simple>
-{We consider the code symbol sequence&nbsp;  $\langle c_\nu \rangle = \rm \langle 10100100011000010011 \rangle$.&nbsp;  What is the corresponding source symbol sequence?
+{We consider the encoded sequence&nbsp;  $\langle c_\nu \rangle = \rm \langle 10100100011000010011 \rangle$.&nbsp;  What is the corresponding source symbol sequence?
 |type="()"}
 - $\langle q_\nu \rangle = \rm \langle \rm CCDAADBCA \rangle$,
@@ Line 67: / Line 67: @@
 {{ML-Kopf}}
 '''(1)'''&nbsp;<u>Solution suggestion 3</u> is correct:
-*Below you can see the code symbol sequence divided by inverted commas:
+*Below you can see the encoded sequence divided by inverted commas:
 :$$\langle c_\nu \rangle = \rm \langle 1'01'001'000'1'1'000'01'001'1 \rangle .$$
 *This belongs to the following source symbol sequence:

@@ Line 11: / Line 11: @@
 *If the code symbol sequence&nbsp; $\langle c_\nu \rangle$&nbsp; is immediately decoded again after the Huffman encoder, the decoding result&nbsp; $\langle v_\nu \rangle$&nbsp; is equal to the source symbol sequence&nbsp; $\langle q_\nu \rangle$.
-*If, on the other hand, the receive sequence&nbsp; $\langle r_\nu \rangle$&nbsp;&nbsp; does not match the generated code sequence&nbsp;  $\langle c_\nu \rangle$&nbsp; due to errors during transmission&nbsp; $($<b>0</b> &nbsp;  &#8594; &nbsp; <b>1</b>, &nbsp;  &nbsp; <b>1</b> &nbsp;  &#8594; &nbsp; <b>0</b>$)$, error propagation may occur.
+*If, on the other hand, the  reception sequence&nbsp; $\langle r_\nu \rangle$&nbsp;&nbsp; does not match the generated code sequence&nbsp;  $\langle c_\nu \rangle$&nbsp; due to errors during transmission&nbsp; <br>$($<b>0</b> &nbsp;  &#8594; &nbsp; <b>1</b>, &nbsp;  &nbsp; <b>1</b> &nbsp;  &#8594; &nbsp; <b>0</b>$)$, error propagation may occur.
 *A single bit error can then lead to (almost) all subsequent characters being decoded incorrectly.
@@ Line 66: / Line 66: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp;<u>Suggested solution 3</u> is correct:
+'''(1)'''&nbsp;<u>Solution suggestion 3</u> is correct:
 *Below you can see the code symbol sequence divided by inverted commas:
 :$$\langle c_\nu \rangle = \rm \langle 1'01'001'000'1'1'000'01'001'1 \rangle .$$
 *This belongs to the following source symbol sequence:
-:$$\langle c_\nu \rangle = \rm \langle ABCDAADBCA \rangle .$$
+:$$\langle q_\nu \rangle = \rm \langle ABCDAADBCA \rangle .$$
@@ Line 84: / Line 84: @@
 Interpretation:
 *$\rm AB$&nbsp; is replaced by&nbsp; $\rm C$&nbsp;, the further text&nbsp; $\rm CDAADBCA$&nbsp; is unchanged, but shifted by one position.
-*However, if you compare the first nine symbols of the original with the decoding <i>position by position</i>, as an automaton would do, you will recognise eight different symbols.
+*However, if you compare the first nine symbols of the original with the decoding result&nbsp; <u>position by position</u>, as an automaton would do, you will recognise eight different symbols.
@@ Line 90: / Line 90: @@
 '''(3)'''&nbsp; The correct <u>answers are 1 and 3</u>:
-* An additional bit error at position 2&nbsp;  $\rm (0 &nbsp; &#8594; &nbsp; 1)$&nbsp; falsifies&nbsp; $\rm AB$&nbsp; to&nbsp; $\rm BA$&nbsp;, but all further symbols are recognised correctly again.
+* An additional bit error at position 2&nbsp;  $\rm (0 &nbsp; &#8594; &nbsp; 1)$&nbsp; falsifies&nbsp; $\rm AB$&nbsp; to&nbsp; $\rm BA$,&nbsp; but all further symbols are recognised correctly again.
 * An additional bit error at position 15&nbsp;  $\rm (0 &nbsp; &#8594; &nbsp; 1)$&nbsp; leads to
 :$$\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 .$$
-::Due to the bit error at position 1&nbsp;  $\rm (1 &nbsp; &#8594; &nbsp; 0)$&nbsp;, &nbsp; $\rm AB$&nbsp; in&nbsp; $\rm C$&nbsp; is falsified, i.e. a character is "swallowed". The additional bit error at position 15&nbsp;  $\rm (0 &nbsp; &#8594; &nbsp; 1)$&nbsp; turns&nbsp; $\rm B$&nbsp; into the tuple&nbsp; $\rm AA$.&nbsp; After that, all symbols in the correct position are recognised correctly, starting with&nbsp; $\rm CA$.
+::Due to the bit error at position 1&nbsp;  $\rm (1 &nbsp; &#8594; &nbsp; 0)$&nbsp;, &nbsp; $\rm AB$&nbsp;  is falsified to&nbsp; $\rm C$&nbsp;, i.e. a character is&nbsp; "swallowed".&nbsp; The additional bit error at position 15&nbsp;  $\rm (0 &nbsp; &#8594; &nbsp; 1)$&nbsp; turns&nbsp; $\rm B$&nbsp; into the tuple&nbsp; $\rm AA$.&nbsp; After that, all symbols in the correct position are recognised correctly, starting with&nbsp; $\rm CA$.
 * An additional bit error at position 10&nbsp;  $\rm (1 &nbsp; &#8594; &nbsp; 0)$&nbsp; on the other hand, leads to
@@ Line 107: / Line 107: @@
 :$$\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 .$$
-*The first&nbsp; $\rm C$&nbsp; becomes a $\rm D$.&nbsp; All other symbols are decoded correctly.
+*The first&nbsp; $\rm C$&nbsp; becomes a&nbsp; $\rm D$.&nbsp; All other symbols are decoded correctly.

@@ Line 3: / Line 3: @@
 }}
-[[File:EN_Inf_A_2_9.png|right|frame|Observed system]]
+[[File:EN_Inf_A_2_9.png|right|frame|Overall system with "Huffman"]]
 We consider Huffman coding according to the following assignment:
 : &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>.
-Huffman coding is always&nbsp; <i>lossless</i>.&nbsp; This means:
+Huffman coding is always&nbsp; <u>lossless</u>.&nbsp; This means:
 *If the code symbol sequence&nbsp; $\langle c_\nu \rangle$&nbsp; is immediately decoded again after the Huffman encoder, the decoding result&nbsp; $\langle v_\nu \rangle$&nbsp; is equal to the source symbol sequence&nbsp; $\langle q_\nu \rangle$.
-*If, on the other hand, the receive sequence&nbsp; $\langle r_\nu \rangle$&nbsp;&nbsp; does not match the generated code sequence&nbsp;  $\langle c_\nu \rangle$&nbsp; due to errors during transmission&nbsp; $($<b>0</b> &nbsp;  &#8594; &nbsp; <b>1</b>, &nbsp;  &nbsp; <b>1</b> &nbsp;  &#8594; &nbsp; <b>0</b>$)$, error propagation may occur
+*If, on the other hand, the receive sequence&nbsp; $\langle r_\nu \rangle$&nbsp;&nbsp; does not match the generated code sequence&nbsp;  $\langle c_\nu \rangle$&nbsp; due to errors during transmission&nbsp; $($<b>0</b> &nbsp;  &#8594; &nbsp; <b>1</b>, &nbsp;  &nbsp; <b>1</b> &nbsp;  &#8594; &nbsp; <b>0</b>$)$, error propagation may occur.
 *A single bit error can then lead to (almost) all subsequent characters being decoded incorrectly.
@@ Line 19: / Line 19: @@
+<u>Hints:</u>
 *The exercise belongs to the chapter&nbsp;  [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy coding according to Huffman]].
 *In particular, reference is made to the page&nbsp;  [[Information_Theory/Entropiecodierung_nach_Huffman#Influence_of_transmission_errors_on_decoding|Influence of transmission errors on decoding]]&nbsp;.

← Older revision		Revision as of 12:17, 10 August 2021
Line 1:		Line 1:

−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Entropiecodierung nach Huffman~~	+	{{quiz-Header\|Buchseite=Information_Theory/Entropy_Coding_According_to_Huffman
	}}		}}

← Older revision		Revision as of 13:00, 16 July 2021
Line 117:		Line 117:


−	[[Category:Information Theory: Exercises\|^2.3 ~~Entropiecodierung nach~~ Huffman^]]	+	[[Category:Information Theory: Exercises\|^2.3 Entropy Coding according to Huffman^]]

@@ Line 3: / Line 3: @@
 }}
-[[File:P_ID2464__Inf_A_2_9.png|right|frame|Betrachtetes System]]
+[[File:EN_Inf_A_2_9.png|right|frame|Betrachtetes System]]
 Wir betrachten die Huffman&ndash;Codierung gemäß folgender Zuordnung: