Aufgaben:Exercise 2.4Z: LZW Coding and Decoding again - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:57:54Z

Fix interlanguage link: resolve redirect chain

← Older revision		Revision as of 17:57, 16 March 2026
Line 40:		Line 40:
	*The exercise belongs to the chapter  [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch\|Compression according to Lempel, Ziv and Welch]].		*The exercise belongs to the chapter  [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch\|Compression according to Lempel, Ziv and Welch]].
	*In particular, reference is made to the pages		*In particular, reference is made to the pages
	:: [[Information_Theory/~~Komprimierung_nach_Lempel~~,~~_Ziv_und_Welch~~#LZ77_-_the_basic_form_of_the_Lempel-Ziv_algorithms\|LZ77 - the basic form of Lempel-Ziv algorithms]],		:: [[Information_Theory/Compression_According_to_Lempel,_Ziv_and_Welch#LZ77_-_the_basic_form_of_the_Lempel-Ziv_algorithms\|LZ77 - the basic form of Lempel-Ziv algorithms]],
	:: [[Information_Theory/~~Komprimierung_nach_Lempel~~,~~_Ziv_und_Welch~~#Lempel-Ziv_coding_with_variable_index_bit_length\|Lempel-Ziv coding with variable index bit length]],		:: [[Information_Theory/Compression_According_to_Lempel,_Ziv_and_Welch#Lempel-Ziv_coding_with_variable_index_bit_length\|Lempel-Ziv coding with variable index bit length]],
	:: [[Information_Theory/~~Komprimierung_nach_Lempel~~,~~_Ziv_und_Welch~~#Decoding_of_the_LZW_algorithm\|Decoding of the LZW algorithm]].		:: [[Information_Theory/Compression_According_to_Lempel,_Ziv_and_Welch#Decoding_of_the_LZW_algorithm\|Decoding of the LZW algorithm]].

	*Also, when solving this task, note that the LZW algorithm does not assume an empty dictionary.		*Also, when solving this task, note that the LZW algorithm does not assume an empty dictionary.
Line 133:		Line 133:

	[[Category:Information Theory: Exercises\|^2.2 Lempel-Ziv-Welch Compression^]]		[[Category:Information Theory: Exercises\|^2.2 Lempel-Ziv-Welch Compression^]]
	[[de:Aufgaben:2.~~04Z_LZW~~-Codierung-/-Decodierung]]		[[de:Aufgaben:Aufgabe 2.4Z: Nochmals LZW-Codierung und -Decodierung]]

Maintenance script: Join 1 split formula blocks

2026-03-16T14:16:15Z

Join 1 split formula blocks

← Older revision		Revision as of 16:16, 16 March 2026
Line 116:		Line 116:
	*For the sequence  <b>ABABABBAA</b>   ⇒   $I < i$ always applies according to subtask  '''(1)''' .		*For the sequence  <b>ABABABBAA</b>   ⇒   $I < i$ always applies according to subtask  '''(1)''' .
	*In contrast, the following indices would result for the sequence  <b>ABABABABA</b> :		*In contrast, the following indices would result for the sequence  <b>ABABABABA</b> :
	:$$i = 1\hspace{-0.15cm}: \hspace{0.15cm} I = 0\hspace{0.05cm},		:$$i = 1\hspace{-0.15cm}: \hspace{0.15cm} I = 0\hspace{0.05cm},\hspace{0.5cm}i = 2\hspace{-0.15cm}: \hspace{0.15cm}I = 1\hspace{0.05cm},\hspace{0.5cm}i = 3\hspace{-0.15cm}: \hspace{0.15cm}I = 2\hspace{0.05cm},\hspace{0.5cm}\underline{i = 4\hspace{-0.15cm}: \hspace{0.15cm}I = 4}\hspace{0.05cm},\hspace{0.5cm}i = 5\hspace{-0.15cm}: \hspace{0.15cm}I = 3\hspace{0.05cm}. $$
	\hspace{0.5cm}i = 2\hspace{-0.15cm}: \hspace{0.15cm}I = 1\hspace{0.05cm},
	\hspace{0.5cm}i = 3\hspace{-0.15cm}: \hspace{0.15cm}I = 2\hspace{0.05cm},
	\hspace{0.5cm}\underline{i = 4\hspace{-0.15cm}: \hspace{0.15cm}I = 4}\hspace{0.05cm},
	\hspace{0.5cm}i = 5\hspace{-0.15cm}: \hspace{0.15cm}I = 3\hspace{0.05cm}. $$

	Here is a summary of the entire decoding process of  <b>ABABABABA</b>:		Here is a summary of the entire decoding process of  <b>ABABABABA</b>:

Maintenance script: Add German interlanguage link

2026-03-16T12:30:44Z

Add German interlanguage link

← Older revision		Revision as of 14:30, 16 March 2026
Line 137:		Line 137:

	[[Category:Information Theory: Exercises\|^2.2 Lempel-Ziv-Welch Compression^]]		[[Category:Information Theory: Exercises\|^2.2 Lempel-Ziv-Welch Compression^]]
			[[de:Aufgaben:2.04Z_LZW-Codierung-/-Decodierung]]

Guenter at 09:34, 31 August 2021

2021-08-31T09:34:39Z

← Older revision		Revision as of 11:34, 31 August 2021
Line 3:		Line 3:
	}}		}}

	[[File:EN_Inf_Z2.4_vers2.png\|right\|frame\|Two snapshots of the LZW dictionary ~~  ⇒   "Wörterbuch"; <br> "Inhalt"   ⇒   "Content"~~]]		[[File:EN_Inf_Z2.4_vers2.png\|right\|frame\|Two snapshots of the LZW dictionary ]]
	The graph shows snapshots of the dictionary created during LZW coding of the input symbol sequence.		The graph shows snapshots of the dictionary created during LZW coding of the input symbol sequence.
	*The upper graph is for input symbol sequence  <b>ABABABBAA</b>.		*The upper graph is for input symbol sequence  <b>ABABABBAA</b>.

Guenter at 15:12, 30 August 2021

2021-08-30T15:12:37Z

← Older revision		Revision as of 17:12, 30 August 2021
Line 3:		Line 3:
	}}		}}

	[[File:~~EN_Inf_Z_2_4~~.png\|right\|frame\|Two snapshots of the LZW dictionary   ⇒   "Wörterbuch"; <br> "Inhalt"   ⇒   "Content"]]		[[File:EN_Inf_Z2.4_vers2.png\|right\|frame\|Two snapshots of the LZW dictionary   ⇒   "Wörterbuch"; <br> "Inhalt"   ⇒   "Content"]]
	The graph shows snapshots of the dictionary created during LZW coding of the input symbol sequence.		The graph shows snapshots of the dictionary created during LZW coding of the input symbol sequence.
	*The upper graph is for input symbol sequence  <b>ABABABBAA</b>.		*The upper graph is for input symbol sequence  <b>ABABABBAA</b>.

Guenter at 12:12, 10 August 2021

2021-08-10T12:12:01Z

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

	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Komprimierung nach Lempel~~, ~~Ziv und Welch~~		{{quiz-Header\|Buchseite=Information_Theory/Compression_According_to_Lempel,_Ziv_and_Welch
	}}		}}

Noah at 20:05, 6 August 2021

2021-08-06T20:05:49Z

← Older revision		Revision as of 22:05, 6 August 2021
Line 37:		Line 37:


	''Hints:''		Hints:
	*The exercise belongs to the chapter  [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch\|Compression according to Lempel, Ziv and Welch]].		*The exercise belongs to the chapter  [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch\|Compression according to Lempel, Ziv and Welch]].
	*In particular, reference is made to the pages		*In particular, reference is made to the pages

Guenter at 13:57, 17 July 2021

2021-07-17T13:57:27Z

Guenter at 12:44, 17 July 2021

2021-07-17T12:44:00Z

← Older revision		Revision as of 14:44, 17 July 2021
Line 50:		Line 50:

	<quiz display=simple>		<quiz display=simple>
	{~~Code~~ the input sequence  <b>ABABABBAA</b>  according to the <u>above diagram</u>.  Which indices  $I_i$  result for the steps  $i=1$, ... , $i=5$?		{Encode the input sequence  <b>ABABABBAA</b>  according to the <u>above diagram</u>.  Which indices  $I_i$  result for the steps  $i=1$, ... , $i=5$?
	\|type="{}"}		\|type="{}"}
	$I_1 \ = \ $ { 0. }		$I_1 \ = \ $ { 0. }
Line 60:		Line 60:


	{Now ~~code~~ the input sequence  <b>ABABABABA</b>  according to the <u>diagram below</u>.  Specify the indices  $I_i$  for the steps  $i=4$  and  $i=5$ .		{Now encode the input sequence  <b>ABABABABA</b>  according to the <u>diagram below</u>.  Specify the indices  $I_i$  for the steps  $i=4$  and  $i=5$ .
	\|type="{}"}		\|type="{}"}
	$I_4 \ = \ $ { 4 }		$I_4 \ = \ $ { 4 }
Line 66:		Line 66:


	{For which step  $i$  does the snapshot of the dictionary shown on the ~~input~~ page apply with respect to		{For which step  $i$  does the snapshot of the dictionary shown on the exercise description page apply with respect to
	\|type="{}"}		\|type="{}"}
	$\text{Encoding:} \ \ i \ = \ $ { 4 }		$\text{Encoding:} \ \ i \ = \ $ { 4 }

Guenter at 12:39, 17 July 2021

2021-07-17T12:39:28Z

← Older revision		Revision as of 14:39, 17 July 2021
Line 3:		Line 3:
	}}		}}

	[[File:EN_Inf_Z_2_4.png\|right\|frame\|Snapshots of the LZW dictionaries]]		[[File:EN_Inf_Z_2_4.png\|right\|frame\|Snapshots of the <br>LZW dictionaries]]
	The graph shows snapshots of the dictionary created during LZW coding of the input symbol sequence.		The graph shows snapshots of the dictionary created during LZW coding of the input symbol sequence.
	*The upper graph is for input symbol sequence  <b>ABABABBAA</b>.		*The upper graph is for input symbol sequence  <b>ABABABBAA</b>.
Line 14:		Line 14:


	In <u>LZW coding</u>, an index $I$ is selected for each coding step $i$ and transmitted (binary).  The character pair <b>AB</b> is represented by the index $I = 2$ in the two dictionaries.  Here we consider the index $I$ as a decimal number and leave the binary representation out of consideration for this task.		In <u>LZW coding</u>, an index  $I$  is selected for each coding step  $i$  and transmitted (binary).  The character pair  <b>AB</b>  is represented by the index  $I = 2$  in the two dictionaries.  Here we consider the index  $I$  as a decimal number and leave the binary representation out of consideration for this task.


	With <u>LZW decoding</u>, a character or character sequence is generated in the same way from each index  $I$  with the help of the dictionary, for example  $I = 1$  leads to the character  <b>B</b>  and  $I = 2$  to the character pair  <b>AB</b>.		With <u>LZW decoding</u>, a character or character sequence is generated in the same way from each index  $I$  with the help of the dictionary, for example  $I = 1$  leads to the character  <b>B</b>  and  $I = 2$  to the character pair  <b>AB</b>.

	If a dictionary entry with the desired index  $I$  is actually found, the decoding runs smoothly. However, this is not always the case:		If a dictionary entry with the desired index  $I$  is actually found, the decoding runs smoothly.  However, this is not always the case:
	* If a new index  $I$  is entered during encoding at step  $i$  and this  $I$  is at the same time the encoding result of the step, this index is not yet occupied in the dictionary at decoding step  $i$ .  The reason for this is that with the decoder the entries are made one step later than with the coder.		* If a new index  $I$  is entered during encoding at step  $i$  and this  $I$  is at the same time the encoding result of the step, this index is not yet occupied in the dictionary at decoding step  $i$ .  The reason for this is that with the decoder the entries are made one step later than with the coder.
	* In the case of a binary input sequence  $($all characters are  <b>A</b>  or  <b>B</b>$)$  , a special rule must always be applied in LZW decoding if the entry with index  $I = i$  was made in coding step  $i$ .		* In the case of a  "binary"  input sequence  $($all characters are  <b>A</b>  or  <b>B</b>$)$,  a special rule must always be applied in LZW decoding if the entry with index  $I = i$  was made in coding step  $i$ .

← Older revision		Revision as of 15:57, 17 July 2021
Line 3:		Line 3:
	}}		}}

	[[File:EN_Inf_Z_2_4.png\|right\|frame\|~~Snapshots~~ of the <br>~~LZW dictionaries~~]]		[[File:EN_Inf_Z_2_4.png\|right\|frame\|Two snapshots of the LZW dictionary   ⇒   "Wörterbuch"; <br> "Inhalt"   ⇒   "Content"]]
	The graph shows snapshots of the dictionary created during LZW coding of the input symbol sequence.		The graph shows snapshots of the dictionary created during LZW coding of the input symbol sequence.
	*The upper graph is for input symbol sequence  <b>ABABABBAA</b>.		*The upper graph is for input symbol sequence  <b>ABABABBAA</b>.
Line 84:		Line 84:
	===Solution===		===Solution===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  We use  $W(I)$  to denote a field (array), that describes the dictionary and whose elements contain characters or strings.		'''(1)'''  We use  $W(I)$  to denote a field (array),  that describes the dictionary and whose elements contain characters or strings.

	*The encoding of  <b>ABABABBAA</b>  ~~then~~ proceeds as follows:		*The encoding of  <b>ABABABBAA</b>  proceeds as follows:
	:: $i = 1$:     <b>A</b>    →   $\underline{I=0}$,   $W(I = 2) =$ <b>AB</b>,		:: $i = 1$:     <b>A</b>    →   $\underline{I=0}$,   $W(I = 2) =$ <b>AB</b>,
	:: $i = 2$:     <b>B</b>    →   $\underline{I=1}$,   $W(I = 3) =$ <b>BA</b>,		:: $i = 2$:     <b>B</b>    →   $\underline{I=1}$,   $W(I = 3) =$ <b>BA</b>,
Line 100:		Line 100:
	*Afterwards, the following applies:		*Afterwards, the following applies:
	:: $i = 4$:     <b>ABA</b> →   $\underline{I=4}$,   $W(I = 5) =$ <b>ABAB</b>,		:: $i = 4$:     <b>ABA</b> →   $\underline{I=4}$,   $W(I = 5) =$ <b>ABAB</b>,
	:: $i = 5$:     <b>BA</b> →   $\underline{I=3}$,   ~~coding~~ completed, no new dictionary entry possible.		:: $i = 5$:     <b>BA</b> →   $\underline{I=3}$,   encoding completed, no new dictionary entry possible.



	'''(3)'''  The comparison with above results shows:		'''(3)'''  The comparison with above results shows:
	*The dictionary of the <u>~~coder~~</u> has the entries shown exactly after  $\underline{i=4}$  ~~coding~~ steps.		*The dictionary of the  <u>encoder</u>  has the entries shown exactly after  $\underline{i=4}$  encoding steps.
	*With the <u>decoder</u>, on the other hand, there is a time delay of one step:   $\underline{i=5}$.		*With the  <u>decoder</u>, on the other hand, there is a time delay of one step:   $\underline{i=5}$.


Line 113:		Line 113:
	'''(4)'''  <u>Solution suggestion 2</u> is correct:		'''(4)'''  <u>Solution suggestion 2</u> is correct:
	*The special case regulation of the decoding is necessary  (in the present example)  if the index  $I =i$  is output in the coding step  $i$ .		*The special case regulation of the decoding is necessary  (in the present example)  if the index  $I =i$  is output in the coding step  $i$ .
	*During decoding, it then does not find the required assignment  "Index  →  String"  since the generated dictionary at time  $i$  only contains entries with ~~indices~~  $I < i$ .		*During decoding, it then does not find the required assignment  "Index  →  String"  since the generated dictionary at time  $i$  only contains entries with  $I < i$ .
	*For the sequence  <b>ABABABBAA</b>    $I < i$ always applies according to subtask  '''(1)''' .		*For the sequence  <b>ABABABBAA</b>   ⇒   $I < i$ always applies according to subtask  '''(1)''' .
	*In contrast, the following indices would result for the sequence  <b>ABABABABA</b> :		*In contrast, the following indices would result for the sequence  <b>ABABABABA</b> :
	:$$i = 1\hspace{-0.15cm}: \hspace{0.15cm} I = 0\hspace{0.05cm},		:$$i = 1\hspace{-0.15cm}: \hspace{0.15cm} I = 0\hspace{0.05cm},
Line 122:		Line 122:
	\hspace{0.5cm}i = 5\hspace{-0.15cm}: \hspace{0.15cm}I = 3\hspace{0.05cm}. $$		\hspace{0.5cm}i = 5\hspace{-0.15cm}: \hspace{0.15cm}I = 3\hspace{0.05cm}. $$

	Here is a summary of the entire decoding of  <b>ABABABABA</b>:		Here is a summary of the entire decoding process of  <b>ABABABABA</b>:

	*The pre-assignment of the dictionary includes  $(I=0$:  <b>A</b>$)$     and  $(I=1$:  <b>B</b>$)$.		*The pre-assignment of the dictionary includes  $(I=0$:  <b>A</b>$)$     and  $(I=1$:  <b>B</b>$)$.

	*Then with the dictionary array  $W(I)$:		*Then with the dictionary array  $W(I)$:
	:: $i = 1$:     ~~decoding~~   $I=0$   →   <b>A</b>,		:: $i = 1$:     Decoding   $I=0$   →   <b>A</b>,
	:: $i = 2$:     ~~decoding~~  $I=1$   →   <b>B</b>,       $W(I = 2) =$ <b>AB</b>,		:: $i = 2$:     Decoding  $I=1$   →   <b>B</b>,       $W(I = 2) =$ <b>AB</b>,
	:: $i = 3$:     ~~decoding~~  $I=2$   →   <b>AB</b>,     $W(I = 3) =$ <b>BA</b>,		:: $i = 3$:     Decoding  $I=2$   →   <b>AB</b>,     $W(I = 3) =$ <b>BA</b>,
	:: $i = 4$:     An entry with index  $I = 4$  is not present   ⇒   '''Special case rule''': <br>                  One takes the last decoding result  $($here  <b>AB</b>$)$ and adds the first character of this sequence at the end   ⇒   <b>ABA</b>. <br>                  Then  <b>ABA</b>  is stored in the dictionary under  index  $I = 4$ .		:: $i = 4$:     An entry with index  $I = 4$  is not present   ⇒   '''Special case rule''': <br>                  One takes the last decoding result  $($here  <b>AB</b>$)$ and adds the first character of this sequence at the end   ⇒   <b>ABA</b>. <br>                  Then  <b>ABA</b>  is stored in the dictionary under  index  $I = 4$ .
	:: $i = 5$:     Decoding   $I=3$   →   <b>BA</b>.             '''End of the decoder input sequence'''.		:: $i = 5$:     Decoding   $I=3$   →   <b>BA</b>.             '''End of the decoder input sequence'''.