Information Theory/Further Source Coding Methods - Revision history

Maintenance script: Join split $$ formula lines for correct rendering

2026-03-16T13:46:59Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:46, 16 March 2026
Line 11:		Line 11:
	The Huffman coding from 1952 is a special case of  "entropy coding".  It attempts to represent the source symbol  $q_μ$  by a code symbol  $c_μ$  of length  $L_μ$,  aiming for the following construction rule:		The Huffman coding from 1952 is a special case of  "entropy coding".  It attempts to represent the source symbol  $q_μ$  by a code symbol  $c_μ$  of length  $L_μ$,  aiming for the following construction rule:

	:$$L_{\mu} \approx -{\rm log}_2\hspace{0.15cm}(p_{\mu})		:$$L_{\mu} \approx -{\rm log}_2\hspace{0.15cm}(p_{\mu})\hspace{0.05cm}.$$
	\hspace{0.05cm}.$$

	Since  $-{\rm log}_2\hspace{0.15cm}(p_{\mu})$  is in contrast to  $L_μ$  not always an integer, this does not succeed in any case.		Since  $-{\rm log}_2\hspace{0.15cm}(p_{\mu})$  is in contrast to  $L_μ$  not always an integer, this does not succeed in any case.
Line 23:		Line 22:

	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Example 1:}$  As in the  [[Information_Theory/~~Entropiecodierung_nach_Huffman~~#The_Huffman_algorithm\|"introductory example for the Huffman algorithm"]]  in the last chapter, we assume  $M = 6$  symbols and the following probabilities:		$\text{Example 1:}$  As in the  [[Information_Theory/Entropy_Coding_According_to_Huffman#The_Huffman_algorithm\|"introductory example for the Huffman algorithm"]]  in the last chapter, we assume  $M = 6$  symbols and the following probabilities:

	:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}		:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04\hspace{0.05cm}.$$
	p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04
	\hspace{0.05cm}.$$

	Then the Shannon-Fano algorithm is:		Then the Shannon-Fano algorithm is:
Line 38:		Line 35:
	''Notes'':		''Notes'':
	*An "x" again indicates that bits must still be added in subsequent coding steps.		*An "x" again indicates that bits must still be added in subsequent coding steps.
	*This results in a different assignment than with  [[Information_Theory/~~Entropiecodierung_nach_Huffman~~#The_Huffman_algorithm\|$\text{Huffman coding}$]], but exactly the same average code word length:		*This results in a different assignment than with  [[Information_Theory/Entropy_Coding_According_to_Huffman#The_Huffman_algorithm\|$\text{Huffman coding}$]], but exactly the same average code word length:

	:$$L_{\rm M} = (0.30\hspace{-0.05cm}+\hspace{-0.05cm} 0.24\hspace{-0.05cm}+ \hspace{-0.05cm}0.20) \hspace{-0.05cm}\cdot\hspace{-0.05cm} 2 + 0.12\hspace{-0.05cm} \cdot \hspace{-0.05cm} 3 + (0.10\hspace{-0.05cm}+\hspace{-0.05cm}0.04) \hspace{-0.05cm}\cdot \hspace{-0.05cm}4 = 2.4\,{\rm bit/source\hspace{0.15cm} symbol}\hspace{0.05cm}.$$}}		:$$L_{\rm M} = (0.30\hspace{-0.05cm}+\hspace{-0.05cm} 0.24\hspace{-0.05cm}+ \hspace{-0.05cm}0.20) \hspace{-0.05cm}\cdot\hspace{-0.05cm} 2 + 0.12\hspace{-0.05cm} \cdot \hspace{-0.05cm} 3 + (0.10\hspace{-0.05cm}+\hspace{-0.05cm}0.04) \hspace{-0.05cm}\cdot \hspace{-0.05cm}4 = 2.4\,{\rm bit/source\hspace{0.15cm} symbol}\hspace{0.05cm}.$$}}
Line 49:		Line 46:
	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Example 2:}$  We consider  $M = 5$  symbols with the following probabilities:		$\text{Example 2:}$  We consider  $M = 5$  symbols with the following probabilities:
	:$$p_{\rm A} = 0.38 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.18 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.16 \hspace{0.05cm},\hspace{0.2cm}		:$$p_{\rm A} = 0.38 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.18 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.16 \hspace{0.05cm},\hspace{0.2cm}p_{\rm D}= 0.15 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm E}= 0.13 \hspace{0.3cm}\Rightarrow\hspace{0.3cm} H = 2.19\,{\rm bit/source\hspace{0.15cm} symbol}\hspace{0.05cm}. $$
	p_{\rm D}= 0.15 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm E}= 0.13 \hspace{0.3cm}
	\Rightarrow\hspace{0.3cm} H = 2.19\,{\rm bit/source\hspace{0.15cm} symbol}
	\hspace{0.05cm}. $$

	[[File:EN_Inf_T_2_4_S1_v2.png\|right\|frame\|Tree structures according to Shannon-Fano and Huffman]]		[[File:EN_Inf_T_2_4_S1_v2.png\|right\|frame\|Tree structures according to Shannon-Fano and Huffman]]
Line 99:		Line 93:
	* $B_i = 0.25, {\it Δ}_i = 0.10 \ ⇒ \ I_i = \big[0.25, 0.35\big)\text{:}$		* $B_i = 0.25, {\it Δ}_i = 0.10 \ ⇒ \ I_i = \big[0.25, 0.35\big)\text{:}$

	:$$r_i = 0 \cdot 2^{-1} + 1 \cdot 2^{-2} = 0.25 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}		:$$r_i = 0 \cdot 2^{-1} + 1 \cdot 2^{-2} = 0.25 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}{\rm Code} \hspace{0.15cm} \boldsymbol{\rm 01} \in I_i\hspace{0.05cm},$$
	{\rm Code} \hspace{0.15cm} \boldsymbol{\rm 01} \in I_i
	\hspace{0.05cm},$$

	* $B_i = 0.65, {\it Δ}_i = 0.10 \ ⇒ \ I_i = \big[0.65, 0.75\big);$  note:   $0.75$  does not belong to the interval:		* $B_i = 0.65, {\it Δ}_i = 0.10 \ ⇒ \ I_i = \big[0.65, 0.75\big);$  note:   $0.75$  does not belong to the interval:

	:$$r_i = 1 \cdot 2^{-1} + 0 \cdot 2^{-2} + 1 \cdot 2^{-3} + 1 \cdot 2^{-4} = 0.6875 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}		:$$r_i = 1 \cdot 2^{-1} + 0 \cdot 2^{-2} + 1 \cdot 2^{-3} + 1 \cdot 2^{-4} = 0.6875 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}{\rm Code} \hspace{0.15cm} \boldsymbol{\rm 1011} \in I_i\hspace{0.05cm}. $$
	{\rm Code} \hspace{0.15cm} \boldsymbol{\rm 1011} \in I_i\hspace{0.05cm}. $$

	However, to organize the sequential flow, one chooses the number of bits constant to  $N_{\rm Bit} = \big\lceil {\rm log}_2 \hspace{0.15cm} ({1}/{\it \Delta_i})\big\rceil+1\hspace{0.05cm}. $		However, to organize the sequential flow, one chooses the number of bits constant to  $N_{\rm Bit} = \big\lceil {\rm log}_2 \hspace{0.15cm} ({1}/{\it \Delta_i})\big\rceil+1\hspace{0.05cm}. $
Line 135:		Line 126:
	*Often, however, only the middle of the interval – in the example  $0.25488$ – is represented in binary:   '''0.01000010011''' .... The number of bits is obtained as follows:		*Often, however, only the middle of the interval – in the example  $0.25488$ – is represented in binary:   '''0.01000010011''' .... The number of bits is obtained as follows:

	:$${\it Δ}_5 = 0.2592 - 0.25056 = 0.00864 \hspace{0.3cm}\Rightarrow \hspace{0.3cm}N_{\rm Bit} = \left\lceil {\rm log}_2 \hspace{0.15cm} \frac{1}{0.00864} \right\rceil + 1\hspace{0.15cm} =		:$${\it Δ}_5 = 0.2592 - 0.25056 = 0.00864 \hspace{0.3cm}\Rightarrow \hspace{0.3cm}N_{\rm Bit} = \left\lceil {\rm log}_2 \hspace{0.15cm} \frac{1}{0.00864} \right\rceil + 1\hspace{0.15cm} =\left\lceil {\rm log}_2 \hspace{0.15cm} 115.7 \right\rceil + 1 = 8\hspace{0.05cm}.$$
	\left\lceil {\rm log}_2 \hspace{0.15cm} 115.7 \right\rceil + 1 = 8
	\hspace{0.05cm}.$$

	*Thus the arithmetic code for this example with  $N = 5$  input characters is:   '''01000010'''.		*Thus the arithmetic code for this example with  $N = 5$  input characters is:   '''01000010'''.

Maintenance script: Add German interlanguage link

2026-03-16T12:27:30Z

Add German interlanguage link

← Older revision		Revision as of 14:27, 16 March 2026
Line 258:		Line 258:

	{{Display}}		{{Display}}
			[[de:Informationstheorie/Weitere_Quellencodierverfahren]]

Guenter at 17:11, 20 February 2023

2023-02-20T17:11:11Z

← Older revision		Revision as of 19:11, 20 February 2023
Line 54:		Line 54:
	\hspace{0.05cm}. $$		\hspace{0.05cm}. $$

	[[File:~~EN_Inf_T_2_4_S1~~.png\|right\|frame\|Tree structures according to Shannon-Fano and Huffman ~~'''KORREKTUR: ""'''~~]]		[[File:EN_Inf_T_2_4_S1_v2.png\|right\|frame\|Tree structures according to Shannon-Fano and Huffman]]

	The diagram shows the respective code trees for Shannon-Fano (left) and Huffman (right).  The results can be summarized as follows:		The diagram shows the respective code trees for Shannon-Fano (left) and Huffman (right).  The results can be summarized as follows:

Guenter at 15:30, 19 February 2023

2023-02-19T15:30:14Z

← Older revision		Revision as of 17:30, 19 February 2023
Line 128:		Line 128:
	*The only real number in the interval  $I_i = \big[0.25056, 0.2592\big)$, that can be represented with seven bits is		*The only real number in the interval  $I_i = \big[0.25056, 0.2592\big)$, that can be represented with seven bits is
	:$$r_i = 1 · 2^{–2} + 1 · 2^{–7} = 0.2578125.$$		:$$r_i = 1 · 2^{–2} + 1 · 2^{–7} = 0.2578125.$$
	*Thus the ~~coder '''KORREKTUR:~~ encoder~~?'''~~ output is fixed:   '''0100001'''.}}		*Thus the encoder output is fixed:   '''0100001'''.}}

Hwang at 13:45, 16 February 2023

2023-02-16T13:45:58Z

← Older revision		Revision as of 15:45, 16 February 2023
Line 235:		Line 235:
	*For our example, the MTF output sequence is  $323303011002$, also with length  $N = 12$.  The four zeros in the MTF sequence  (also in red font in the diagram)  indicate that at each of these positions the BWT character is the same as its predecessor.		*For our example, the MTF output sequence is  $323303011002$, also with length  $N = 12$.  The four zeros in the MTF sequence  (also in red font in the diagram)  indicate that at each of these positions the BWT character is the same as its predecessor.
	*In large ASCII files, the frequency of the  $0$  may well be more than  $50\%$,  while the other  $255$  indices occur only rarely.  Run-length coding  $\rm (RCL)$  is an excellent way to compress such a text structure.		*In large ASCII files, the frequency of the  $0$  may well be more than  $50\%$,  while the other  $255$  indices occur only rarely.  Run-length coding  $\rm (RCL)$  is an excellent way to compress such a text structure.
	*The block  $\rm RCL0$  in the above coding chain denotes a special  [[Information_Theory/Further_Source_Coding_Methods#Run.E2.80.93Length_coding\|$\text{run-length coding}$]]  for zeros.  The ~~grey~~ shading of the zeros indicates that a long zero sequence has been masked by a specific bit sequence   (shorter than the zero sequence).		*The block  $\rm RCL0$  in the above coding chain denotes a special  [[Information_Theory/Further_Source_Coding_Methods#Run.E2.80.93Length_coding\|$\text{run-length coding}$]]  for zeros.  The gray shading of the zeros indicates that a long zero sequence has been masked by a specific bit sequence   (shorter than the zero sequence).
	*The entropy encoder  $\rm (EC$, for example "Huffman"$)$  provides further compression.  BWT  and  MTF  only have the task in the coding chain of increasing the efficiency of  "RLC0"  and  "EC"  through character preprocessing.  The output file is again binary.		*The entropy encoder  $\rm (EC$, for example "Huffman"$)$  provides further compression.  BWT  and  MTF  only have the task in the coding chain of increasing the efficiency of  "RLC0"  and  "EC"  through character preprocessing.  The output file is again binary.

Hwang at 13:44, 16 February 2023

2023-02-16T13:44:45Z

← Older revision		Revision as of 15:44, 16 February 2023
Line 227:		Line 227:
	==Application scenario for the Burrows-Wheeler transformation==		==Application scenario for the Burrows-Wheeler transformation==
	<br>		<br>
	As an example for embedding the  [[Information_Theory/~~Weitere_Quellencodierverfahren~~#Burrows.E2.80.~~93Wheeler_Transformation~~\|$\text{Burrows–Wheeler Transformation}$]]  (BWT) into a chain of source coding methods, we choose a structure proposed in  [Abel03]<ref>Abel, J.:  Verlustlose Datenkompression auf Grundlage der Burrows-Wheeler-Transformation.  <br>In: PIK - Praxis der Informationsverarbeitung und Kommunikation, no. 3, vol. 26, pp. 140-144, Sept. 2003.</ref>.  We use the same text example  $\text{ANNAS_ANANAS}$  as in the last section.  The corresponding strings after each block are also given in the graphic.		As an example for embedding the  [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation\|$\text{Burrows–Wheeler Transformation}$]]  (BWT) into a chain of source coding methods, we choose a structure proposed in  [Abel03]<ref>Abel, J.:  Verlustlose Datenkompression auf Grundlage der Burrows-Wheeler-Transformation.  <br>In: PIK - Praxis der Informationsverarbeitung und Kommunikation, no. 3, vol. 26, pp. 140-144, Sept. 2003.</ref>.  We use the same text example  $\text{ANNAS_ANANAS}$  as in the last section.  The corresponding strings after each block are also given in the graphic.

	[[File:EN_Inf_T_2_4_S5_v2.png\|center\|frame\|Scheme for Burrows-Wheeler data compression]]		[[File:EN_Inf_T_2_4_S5_v2.png\|center\|frame\|Scheme for Burrows-Wheeler data compression]]

Hwang at 13:43, 16 February 2023

2023-02-16T13:43:25Z

← Older revision		Revision as of 15:43, 16 February 2023
Line 196:		Line 196:
	$\text{Furthermore, it should be noted about the BWT procedure:}$		$\text{Furthermore, it should be noted about the BWT procedure:}$

	*Without an additional measure   ⇒   a downstream ~~„real compression”~~ – the BWT does not lead to any data compression.		*Without an additional measure   ⇒   a downstream "real compression" – the BWT does not lead to any data compression.
	*Rather, there is even a slight increase in the amount of data, since in addition to the  $N$  characters, the primary index  $I$  now also be transmitted.		*Rather, there is even a slight increase in the amount of data, since in addition to the  $N$  characters, the primary index  $I$  now also be transmitted.
	*For longer texts,  however,  this effect is negligible.  Assuming 8 bit–ASCII–characters  (one byte each)  and the block length  $N = 256$  the number of bytes per block only increases from  $256$  to  $257$, i.e. by only  $0.4\%$.}}		*For longer texts,  however,  this effect is negligible.  Assuming 8 bit–ASCII–characters  (one byte each)  and the block length  $N = 256$  the number of bytes per block only increases from  $256$  to  $257$, i.e. by only  $0.4\%$.}}

Hwang at 13:42, 16 February 2023

2023-02-16T13:42:58Z

← Older revision		Revision as of 15:42, 16 February 2023
Line 189:		Line 189:

	*First, an  $N×N$ matrix is generated from the string of length  $N$  with each row resulting from the preceding row by cyclic left shift.		*First, an  $N×N$ matrix is generated from the string of length  $N$  with each row resulting from the preceding row by cyclic left shift.
	*Then the BWT matrix is sorted lexicographically.  The result of the transformation is the last column  ⇒   $\text{~~L–Spalte~~}$.  In the example, this results in  $\text{_NSNNAANAAAS}$.		*Then the BWT matrix is sorted lexicographically.  The result of the transformation is the last column  ⇒   $\text{L–column}$.  In the example, this results in  $\text{_NSNNAANAAAS}$.
	*Furthermore, the primary index  $I$  must also be passed on. This value indicates the row of the sorted BWT matrix that contains the original text  (marked red in the graphic).		*Furthermore, the primary index  $I$  must also be passed on. This value indicates the row of the sorted BWT matrix that contains the original text  (marked red in the graphic).
	*Of course, no matrix operations are necessary to determine the  $\text{L–column}$  and the primary index.  Rather, the BWT result can be found very quickly with pointer technology.		*Of course, no matrix operations are necessary to determine the  $\text{L–column}$  and the primary index.  Rather, the BWT result can be found very quickly with pointer technology.

Hwang at 13:40, 16 February 2023

2023-02-16T13:40:26Z

← Older revision		Revision as of 15:40, 16 February 2023
Line 173:		Line 173:

	However, the example also shows two problems of run-length coding:		However, the example also shows two problems of run-length coding:
	*The lengths  $L_i$  of the substrings are not limited.  Special measures must be taken here if a length  $L_i$  is greater than  $2^5 = 32$  $($valid fo  $N_{\rm Bit} = 5)$, <br>for example the variant  »'''Run–Length Limited Coding'''«  $\rm (RLLC)$.  See also  [Meck09]<ref>Mecking, M.: Information Theory.  Lecture manuscript, Chair of Communications Engineering, Technical University of Munich, 2009.</ref>  and  [[Aufgaben:Aufgabe_2.13:_Burrows-Wheeler-Rücktransformation\|"Exercise 2.13"]].		*The lengths  $L_i$  of the substrings are not limited.  Special measures must be taken here if a length  $L_i$  is greater than  $2^5 = 32$  $($valid for  $N_{\rm Bit} = 5)$, <br>for example the variant  »'''Run–Length Limited Coding'''«  $\rm (RLLC)$.  See also  [Meck09]<ref>Mecking, M.: Information Theory.  Lecture manuscript, Chair of Communications Engineering, Technical University of Munich, 2009.</ref>  and  [[Aufgaben:Aufgabe_2.13:_Burrows-Wheeler-Rücktransformation\|"Exercise 2.13"]].
	*If the sequence does not end with  $\rm B$  – which is rather the normal case with small probability  $p_{\rm B}$  one must also provide special treatment for the end of the file.		*If the sequence does not end with  $\rm B$  – which is rather the normal case with small probability  $p_{\rm B}$  one must also provide special treatment for the end of the file.

Hwang at 13:38, 16 February 2023

2023-02-16T13:38:53Z

← Older revision		Revision as of 15:38, 16 February 2023
Line 128:		Line 128:
	*The only real number in the interval  $I_i = \big[0.25056, 0.2592\big)$, that can be represented with seven bits is		*The only real number in the interval  $I_i = \big[0.25056, 0.2592\big)$, that can be represented with seven bits is
	:$$r_i = 1 · 2^{–2} + 1 · 2^{–7} = 0.2578125.$$		:$$r_i = 1 · 2^{–2} + 1 · 2^{–7} = 0.2578125.$$
	*Thus the coder output is fixed:   '''0100001'''.}}		*Thus the coder '''KORREKTUR: encoder?''' output is fixed:   '''0100001'''.}}