Information Theory/Further Source Coding Methods - Revision history

Guenter at 17:11, 20 February 2023

2023-02-20T17:11:11Z

Guenter at 15:30, 19 February 2023

2023-02-19T15:30:14Z

Hwang at 13:45, 16 February 2023

2023-02-16T13:45:58Z

Hwang at 13:44, 16 February 2023

2023-02-16T13:44:45Z

Hwang at 13:43, 16 February 2023

2023-02-16T13:43:25Z

Hwang at 13:42, 16 February 2023

2023-02-16T13:42:58Z

Hwang at 13:40, 16 February 2023

2023-02-16T13:40:26Z

Hwang at 13:38, 16 February 2023

2023-02-16T13:38:53Z

Hwang at 13:38, 16 February 2023

2023-02-16T13:38:03Z

Hwang at 13:37, 16 February 2023

2023-02-16T13:37:32Z

@@ Line 54: / Line 54: @@
 \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).&nbsp; The results can be summarized as follows:

@@ Line 128: / Line 128: @@
 *The only real number in the interval&nbsp; $I_i = \big[0.25056, 0.2592\big)$, that can be represented with seven bits is&nbsp;
 :$$r_i = 1 · 2^{–2} + 1 · 2^{–7} = 0.2578125.$$
-*Thus the coder '''KORREKTUR: encoder?''' output is fixed: &nbsp;  '''0100001'''.}}
+*Thus the encoder output is fixed: &nbsp;  '''0100001'''.}}

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

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

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

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

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

@@ Line 116: / Line 116: @@
 $\text{Example 4:}$&nbsp; Now let the symbol set size be&nbsp; $M = 3$&nbsp; and let the symbols be denoted by&nbsp; $\rm X$,&nbsp; $\rm Y$&nbsp; and&nbsp; $\rm Z$:
 *The character sequence&nbsp; $\rm XXYXZ$ &nbsp;  ⇒ &nbsp;  length of the source symbol sequence: &nbsp; $N = 5$.
-*Assume the probabilities&nbsp; $p_{\rm X} = 0.6$,&nbsp; $p_{\rm Y} = 0.2$&nbsp; und&nbsp; $p_{\rm Z} = 0.2$.
+*Assume the probabilities&nbsp; $p_{\rm X} = 0.6$,&nbsp; $p_{\rm Y} = 0.2$&nbsp; and&nbsp; $p_{\rm Z} = 0.2$.
 [[File:EN_Inf_T_2_4_S2.png|right|frame|About the arithmetic coding algorithm]]

@@ Line 108: / Line 108: @@
 {\rm Code} \hspace{0.15cm} \boldsymbol{\rm 1011} \in I_i\hspace{0.05cm}. $$
-However, to organise the sequential flow, one chooses the number of bits constant to&nbsp; $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&nbsp; $N_{\rm Bit} = \big\lceil {\rm log}_2 \hspace{0.15cm}  ({1}/{\it \Delta_i})\big\rceil+1\hspace{0.05cm}. $
 *With the interval width&nbsp; ${\it Δ}_i = 0.10$&nbsp; results&nbsp; $N_{\rm Bit} = 5$.
 *So the actual arithmetic codes would be &nbsp; '''01000''' &nbsp; and &nbsp; '''10110''' respectively.}}