View source for Information Theory/Entropy Coding According to Huffman

 
{{Header
|Untermenü=Source Coding - Data Compression
|Vorherige Seite=Compression According to Lempel, Ziv and Welch
|Nächste Seite=Further Source Coding Methods
}}

==The Huffman algorithm==  
<br>
We now assume that the source symbols&nbsp; $q_\nu$&nbsp; originate from an alphabet&nbsp; $\{q_μ\} = \{$ $\rm A$,&nbsp; $\rm B$ ,&nbsp; $\rm C$ , ...$\}$&nbsp; with the symbol set size&nbsp; $M$&nbsp; and they are statistically independent of each other.&nbsp; For example, for the symbol set size&nbsp; $M = 8$:
 
:$$\{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm B}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm C}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm D}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm E}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm F}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm G}\hspace{0.05cm},\hspace{0.05cm} \boldsymbol{\rm H}\hspace{0.05cm}
\}\hspace{0.05cm}.$$

In 1952 - i.e. shortly after Shannon's groundbreaking publications,&nbsp; [https://en.wikipedia.org/wiki/David_A._Huffman $\text{David A. Huffman}$]&nbsp; gave an algorithm for the construction of optimal prefix-free codes.&nbsp; This&nbsp; &raquo;'''Huffman Algorithm'''&laquo;&nbsp; is to be given here without derivation and proof, whereby we restrict ourselves to binary codes.&nbsp; That is: &nbsp; For the code symbols, let&nbsp; $c_ν ∈ \{$'''0''',&nbsp; '''1'''$\}$ always hold. 

Here is the&nbsp; "recipe":
# &nbsp; Order the symbols according to decreasing probabilities of occurrence.
# &nbsp;  Combine the two most improbable symbols into a new symbol.
# &nbsp; Repeat&nbsp; '''(1)'''&nbsp; and&nbsp; '''(2)''', until only two&nbsp; (combined)&nbsp; symbols remain.
# &nbsp; Encode the more probable set of symbols with&nbsp; '''1'''&nbsp; and the other set with&nbsp; '''0'''.
# &nbsp; In the opposite direction&nbsp; (i.e. from bottom to top)&nbsp;, add&nbsp; '''1'''&nbsp; or&nbsp; '''0''' to the respective binary codes of the split subsets according to the probabilities.


{{GraueBox|TEXT=
$\text{Example 1:}$&nbsp; Without limiting the generality, we assume that the&nbsp; $M = 6$&nbsp; symbols&nbsp; $\rm A$, ... , $\rm F$&nbsp;  are already ordered according to their 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 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}.$$

By pairwise combination and subsequent sorting, the following symbol combinations are obtained in five steps&nbsp; (resulting probabilities in brackets):
:1. &nbsp; $\rm A$&nbsp; (0.30), $\rm B$&nbsp; (0.24), $\rm C$&nbsp; (0.20), $\rm EF$&nbsp; (0.14), $\rm D$&nbsp; (0.12),
:2. &nbsp; $\rm A$&nbsp; (0.30), $\rm EFD$&nbsp; (0.26), $\rm B$&nbsp; (0.24), $\rm C$&nbsp; (0.20),
:3. &nbsp; $\rm BC$&nbsp; (0.44), $\rm A$&nbsp; (0.30), $\rm EFD$&nbsp; (0.26),
:4. &nbsp; $\rm AEFD$&nbsp; (0.56), $\rm BC$&nbsp; (0.44),
:5. &nbsp; Root&nbsp; $\rm AEFDBC$&nbsp; (1.00).
Backwards &ndash; i.e. according to steps&nbsp; '''(5)'''&nbsp; to&nbsp; '''(1)'''&nbsp; &ndash; the assignment to binary symbols then takes place. &nbsp; An&nbsp; "'''x'''"&nbsp; indicates that bits still have to be added in the next steps:
:5. &nbsp; $\rm AEFD$ &nbsp; → &nbsp; '''1x''', &nbsp; &nbsp;  $\rm BC$ &nbsp; → &nbsp; '''0x''',
:4. &nbsp; $\underline{\rm A}$ &nbsp; → &nbsp; '''<u>11</u>''', &nbsp; &nbsp;  $\rm EFD$ &nbsp; → &nbsp; '''10x''',
:3. &nbsp; $\underline{\rm B}$ &nbsp; → &nbsp; '''<u>01</u>''', &nbsp; &nbsp; $\underline{\rm C}$ &nbsp; → &nbsp; '''<u>00</u>''',
:2. &nbsp; $\rm EF$ &nbsp; → &nbsp; '''101x''',  &nbsp; &nbsp; $\underline{\rm D}$ &nbsp; → &nbsp; '''<u>100</u>''',
:1. &nbsp; $\underline{\rm E}$ &nbsp; → &nbsp; '''<u>1011</u>''',  &nbsp; &nbsp; $\underline{\rm F}$ &nbsp; → &nbsp; '''<u>1010</u>'''.
The underlines mark the final binary coding.}}


	 	 
==On the term&nbsp; "Entropy Coding"==  	 
<br>
We continue to assume the probabilities and assignments of the last example:
  
:$$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};$$

:$$\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 11} \hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 01} \hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 00} \hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm D} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 100} \hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm E} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1011} \hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1010} \hspace{0.05cm}.$$

Thus, of the six source symbols, three are encoded with two bits each, one with three bits and two symbols&nbsp;  $(\rm E$&nbsp;  and&nbsp;  $\rm F)$&nbsp;  with four bits each.

The average code word length thus results in
 
:$$L_{\rm M} = (0.30 \hspace{-0.05cm}+ \hspace{-0.05cm}0.24 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.20) \cdot 2  + 0.12 \cdot 3 + (0.10 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.04 ) \cdot 4 = 2.4 \,{\rm bit/source\hspace{0.15cm}symbol}
\hspace{0.05cm}.$$

From the comparison with the source entropy&nbsp;  $H = 2.365 \ \rm bit/source\hspace{0.15cm}symbol$&nbsp;  one can see the efficiency of the Huffman coding.

{{BlaueBox|TEXT=
$\text{Note:}$&nbsp; 
There is no prefix-free&nbsp;  $($⇒ &nbsp; immediately decodable$)$&nbsp;  code that leads to a smaller average code word length&nbsp;  $L_{\rm M}$&nbsp;  than the Huffman code by exploiting the occurrence probabilities alone. &nbsp;  '''In this sense, the Huffman code is optimal'''.}}


{{GraueBox|TEXT=
$\text{Example 2:}$&nbsp; If the symbol probabilities were
 
:$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/4 \hspace{0.05cm},\hspace{0.2cm}
p_{\rm D} = 1/8 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = p_{\rm F} = 1/16 
\hspace{0.05cm},$$

then the same would apply to the entropy and to the average code word length:
 
:$$H =   3 \cdot 1/4 \cdot {\rm log_2}\hspace{0.1cm}(4)  + 1/8 \cdot {\rm log_2}\hspace{0.1cm}(8) + 2 \cdot 1/16 \cdot {\rm log_2}\hspace{0.1cm}(16) = 2.375 \,{\rm bit/source\hspace{0.15cm} symbol}\hspace{0.05cm},$$
:$$L_{\rm M}  =  3 \cdot 1/4 \cdot 2  + 1/8 \cdot 3 + 2 \cdot 1/16 \cdot 4 = 2.375 \,{\rm bit/source\hspace{0.15cm} symbol}
\hspace{0.05cm}.$$}}


This property&nbsp;  $L_{\rm M} = H +\varepsilon$&nbsp;  with positive&nbsp;  $\varepsilon \to 0$&nbsp;  at suitable symbol probabilities explains the term&nbsp;  &raquo;'''Entropy Coding'''&laquo;:

In this form of source coding, one tries to adapt the length&nbsp;  $L_μ$&nbsp;  of the binary sequence&nbsp;  (consisting of zeros and ones)&nbsp;  for the symbol&nbsp;  $q_μ$&nbsp;  according to the entropy calculation to its symbol probability&nbsp;  $p_μ$&nbsp;  as follows:
 
:$$L_{\mu} =  {\rm log}_2\hspace{0.1cm}(1/p_{\mu} )  \hspace{0.05cm}.$$

Of course, this does not always succeed, but only if all symbol probabilities&nbsp;  $p_μ$&nbsp;  can be represented in the form&nbsp;  $2^{–k}$&nbsp;  with&nbsp;  $k = 1, \ 2,  \ 3,$ ...  
*In this special case - and only in this case - the average code word length&nbsp;  $L_{\rm M}$&nbsp;  coincides exactly with the source entropy&nbsp;  $H$&nbsp; &nbsp;  $(\varepsilon = 0$,&nbsp;  see&nbsp; $\text{Example 2})$. 
*According to the&nbsp;  [[Information_Theory/General_Description#Source_coding_theorem|$\text{Source Coding Theorem}$]]&nbsp;  there is no&nbsp; (decodable)&nbsp; code that gets by with fewer binary characters per source symbol on average.

	 
==Representation of the Huffman code as a tree diagram==
<br>
A&nbsp;  &raquo;'''tree structure'''&laquo;&nbsp;   is often used to construct the Huffman code.&nbsp;  For the example considered so far, this is shown in the following diagram:

[[File:EN_Inf_T_2_3_S3.png|frame|Tree representation of the Huffman coding for&nbsp;  $\text{Example 1}$]]

It can be seen:
*At each step of the Huffman algorithm, the two branches with the smallest respective probabilities are combined. 
*The node in the first step combines the two symbols&nbsp;  $\rm E$&nbsp;  and&nbsp;  $\rm F$&nbsp;  with the currently smallest probabilities.&nbsp;  This new node is labelled&nbsp;  $p_{\rm E} + p_{\rm F} = 0.14$&nbsp; .
*The branch running from the symbol with the smaller probability&nbsp;  $($here&nbsp;  $\rm F)$&nbsp;  to the sum node is drawn in blue, the other branch&nbsp;   $($here&nbsp; $\rm E)$&nbsp;  in red.
*After five steps, we arrive at the root of the tree with the total probability&nbsp;  $1.00$&nbsp;.&nbsp;  


If you now trace the course from the root&nbsp;  (in the graphic with yellow filling)&nbsp;  back to the individual symbols, you can read off the symbol assignment from the colours of the individual branches.

For example, with the assignments&nbsp; "red" &nbsp;  → &nbsp;  '''1''' and&nbsp; "blue"  &nbsp;  → &nbsp;  '''0''', the following results from the root to the symbol
*$\rm A$:   &nbsp;  red, red  &nbsp;  → &nbsp;  '''11''',
*$\rm B$:   &nbsp; blue, red  &nbsp;  → &nbsp;  '''01''',
*$\rm C$:   &nbsp; blue, blue  &nbsp;  → &nbsp;  '''00''',
*$\rm D$:   &nbsp; red, blue, blue  &nbsp;  → &nbsp;  '''100''',
*$\rm E$:   &nbsp; red, blue, red, red  &nbsp;  → &nbsp;  '''1011''',
*$\rm F$:   &nbsp; red, blue, red, blue  &nbsp;  → &nbsp;  '''1010'''.


The&nbsp; (uniform)&nbsp; assignment&nbsp; "red"  &nbsp;  → &nbsp;  '''0'''&nbsp; and&nbsp; "blue"  &nbsp;  → &nbsp;  '''1'''&nbsp; would also lead to an optimal prefix-free Huffman code.
  
{{GraueBox|TEXT=
$\text{Example 3:}$&nbsp; 
The following graph shows the Huffman coding of&nbsp;  $49$&nbsp; symbols&nbsp; $q_ν ∈ \{$ $\rm A$,&nbsp; $\rm B$,&nbsp; $\rm C$,&nbsp; $\rm D$,&nbsp; $\rm E$,&nbsp; $\rm F$ $\}$ &nbsp;with the assignment derived in the last section.&nbsp; The different colours serve only for better orientation.
*The binary encoded sequence has the average code word length&nbsp; 
:$$L_{\rm M} = 125/49 = 2.551.$$  

*Due to the short sequence&nbsp; $(N = 49)$&nbsp;, the frequencies&nbsp; $h_{\rm A}$, ... ,&nbsp; $h_{\rm F}$&nbsp; of the simulated sequences deviate significantly from the given probabilities&nbsp; $p_{\rm A}$, ... ,&nbsp; $p_{\rm F}$&nbsp;:
[[File:EN_Inf_T_2_3_S3b.png|right|frame|Example sequences for Huffman coding]] 

:$$p_{\rm A} = 0.30 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm A} = 16/49 \approx 0.326 \hspace{0.05cm},$$
:$$p_{\rm B} = 0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm B} = 7/49 \approx 0.143 \hspace{0.05cm},$$ 
:$$p_{\rm C} =0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm C}= 9/49 \approx  0.184 \hspace{0.05cm},$$
:$$p_{\rm D} = 0.12 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm D} = 7/49 \approx  0.143 \hspace{0.05cm},$$
:$$p_{\rm E}=0.10 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102 \hspace{0.05cm},$$
:$$p_{\rm F} = 0.04 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102 
\hspace{0.05cm}.$$

*This results in a slightly larger entropy value:
  
:$$H ({\rm regarding}\hspace{0.15cm}p_{\mu}) = 2.365 \ {\rm bit/source\hspace{0.15cm} symbol}\hspace{0.3cm} 
\Rightarrow \hspace{0.3cm} 
H ({\rm regarding}\hspace{0.15cm}h_{\mu}) = 2.451 \ {\rm bit/source\hspace{0.15cm} symbol}
\hspace{0.05cm}.$$

If one were to form the Huffman code with these&nbsp; "new probabilities"&nbsp; $h_{\rm A}$, ... , $h_{\rm F}$&nbsp; the following assignments would result:
 
:&nbsp; &nbsp; &nbsp;$\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''11'''$\hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''100'''$\hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''00'''$\hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm D} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''101'''$\hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm E} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''010'''$\hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''011'''$\hspace{0.05cm}.$

Now only&nbsp; $\rm A$&nbsp; and&nbsp; $\rm C$&nbsp; would be represented by two bits, the other four symbols by three bits each.
*The encoded sequence would then have a length of &nbsp; $(16 + 9) · 2 + (7 + 7 + 5 + 5) · 3 = 122$ &nbsp; bits, &nbsp; &rArr; &nbsp; three bits shorter than under the previous coding.
*The average code word length would then be&nbsp; $L_{\rm M} = 122/49 ≈ 2.49$&nbsp;  bit/source symbol&nbsp; instead of&nbsp; $L_{\rm M}≈ 2.55$&nbsp;  bit/source symbol.}}


The (German language) interactive applet&nbsp; [[Applets:Huffman_Shannon_Fano|"Huffman- und Shannon-Fano-Codierung&nbsp; &rArr; &nbsp; $\text{SWF}$&nbsp;version"]]&nbsp; illustrates the procedure for two variants of entropy coding.

{{BlaueBox|TEXT=
$\text{This example can be interpreted as follows:}$&nbsp; 
*Huffman coding thrives on the&nbsp; (exact)&nbsp; knowledge of the symbol probabilities.&nbsp; If these are known to both the transmitter and the receiver, the average code word length&nbsp; $L_{\rm M}$&nbsp; is often only insignificantly larger than the source entropy&nbsp; $H$.
*Especially with small files, there may be deviations between the&nbsp; (expected)&nbsp; symbol probabilities&nbsp; $p_μ$&nbsp; and the&nbsp; (actual)&nbsp; frequencies&nbsp; $h_μ$&nbsp;.&nbsp; It would be better here to generate a separate Huffman code for each file based on the actual circumstances&nbsp; $(h_μ)$.
*In this case, however, the specific Huffman code must also be communicated to the decoder.&nbsp; This leads to a certain overhead, which again can only be neglected for longer files.&nbsp; With small files, this effort is not worthwhile.}}
	 	 

==Influence of transmission errors on decoding== 	
<br>
Due to the property&nbsp; "prefix-free" &nbsp; &rArr; &nbsp; the Huffman code is lossless. 
*This means that the source symbol sequence can be completely reconstructed from the binary encoded sequence.
*However, if an error occurs during transmission&nbsp; $($"'''0'''"&nbsp; &nbsp; &rArr; &nbsp; "'''1'''"&nbsp; or&nbsp; "'''1'''"&nbsp; &nbsp; &rArr; &nbsp; "'''0'''"$)$,&nbsp;, the sink symbol sequence&nbsp; $〈v_ν〉$&nbsp; naturally also does not match the source symbol sequence&nbsp; $〈q_ν〉$.


The following two examples show that a single transmission error can sometimes result in a multitude of errors regarding the source text.

{{GraueBox|TEXT=
$\text{Example 4:}$&nbsp; 
We consider the same source symbol sequence and the same Huffman code as in the previous section. 

[[File:EN_Inf_T_2_3_S4b_v2.png|frame|On the influence of transmission errors in Huffman coding]]

*The upper diagram shows that with error-free transmission, the original source sequence&nbsp; '''111011'''...&nbsp; can be reconstructed from the coded binary sequence&nbsp; $\rm AEBFCC$...
*However, if for example bit 6 is falsified&nbsp; $($from&nbsp; '''1'''&nbsp; to&nbsp; '''0''', red marking in the middle graphic$)$, the source symbol&nbsp; $q_2 = \rm E$&nbsp; becomes the sink symbol&nbsp; $v_2 =\rm F$.
*A falsification of bit 13&nbsp; $($from&nbsp; '''0'''&nbsp; to&nbsp;  '''1''', red marking in the lower graphic$)$&nbsp; even leads to a falsification of four source symbols: &nbsp; $\rm CCEC$&nbsp;   →&nbsp;   $\rm DBBD$.}}


{{GraueBox|TEXT=
$\text{Example 5:}$&nbsp; 
Let a second source with symbol set size&nbsp; $M = 6$&nbsp; be characterized by the following symbol probabilities:
 
:$$p_{\rm A} = 0.50 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.19 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.11 \hspace{0.05cm},\hspace{0.2cm}
p_{\rm D} = 0.09 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.06 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.05 
\hspace{0.05cm}.$$

Here the Huffman algorithm leads to the following assignment:

:&nbsp; &nbsp; &nbsp;$\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''0'''$\hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''111'''$\hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''101'''$\hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm D} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''100'''$\hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm E} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''1101'''$\hspace{0.05cm},\hspace{0.2cm}
\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''1100'''$\hspace{0.05cm}.$

[[File:EN_Inf_T_2_3_S4c_v2.png|right|frame|On the error propagation of the Huffman coding]]
 
The source symbol sequence&nbsp; $\rm ADABD$...&nbsp; (upper diagram) is thus represented by the encoded sequence&nbsp; '''0'100'0'111'100' '''...&nbsp;.&nbsp; The inverted commas are only for the reader's orientation.

During transmission, the first bit is falsified:&nbsp; Instead of&nbsp; '''01000111100'''...&nbsp; one receives&nbsp; '''11000111100'''... 
*After decoding, the first two source symbols&nbsp; $\rm AD$&nbsp; →&nbsp; '''0100'''&nbsp; become the sink symbol&nbsp; $\rm F$&nbsp; →&nbsp; '''1100'''. 
*The further symbols are then detected correctly again, but now no longer starting at position&nbsp; $ν = 3$, but at&nbsp; $ν = 2$.


Depending on the application, the effects are different:
*If the source is a&nbsp; "natural text"&nbsp; and the sinker is a&nbsp; "human",&nbsp; most of the text remains comprehensible to the reader.
*If, however, the sink is an automaton that successively compares all&nbsp; $v_ν$&nbsp; with the corresponding&nbsp; $q_ν$,&nbsp;  the result is a distortion frequency of well over&nbsp; $50\%$.
*Only the blue symbols of the sink symbol sequence&nbsp; $〈v_ν〉$&nbsp; then&nbsp; (coincidentally)&nbsp; match the source symbols&nbsp; $q_ν$&nbsp; while red symbols indicate errors.}}


	 
==Application of Huffman coding to&nbsp; $k$–tuples == 	
<br>
The Huffman algorithm in its basic form delivers unsatisfactory results when
*there is a binary source&nbsp; $(M = 2)$&nbsp;, for example with the symbol set&nbsp; $\{$ $\rm X$,&nbsp; $\rm Y \}$,
*there are statistical dependencies between adjacent symbols of the input sequence,
*the probability of the most frequent symbol is clearly greater than&nbsp; $50\%$.


The remedy in these cases is
*by grouping several symbols together, and
*applying the Huffman algorithm to a new set of symbols&nbsp; $\{$ $\rm A$,&nbsp; $\rm B$, $\rm C$,&nbsp; $\rm D$, ... $\}$&nbsp;.


If&nbsp; $k$–tuples are formed, the symbol set size&nbsp; $M$&nbsp; increases to&nbsp; $M\hspace{-0.01cm}′ = M^k$. 

In the following example, we will illustrate the procedure using a binary source.&nbsp; Further examples can be found in
*[[Aufgaben:Exercise_2.7:_Huffman_Application_for_Binary_Two-Tuples|"Exercise 2.7"]],
*[[Aufgaben:Exercise_2.7Z:_Huffman_Coding_for_Two-Tuples_of_a_Ternary_Source|"Exercise 2.7Z"]],
*[[Aufgaben:Exercise_2.8:_Huffman_Application_for_a_Markov_Source|"Exercise 2.8"]]. 


{{GraueBox|TEXT=
$\text{Example 6:}$&nbsp; Let a memoryless binary source $(M = 2)$ with the symbols&nbsp; $\{$ $\rm X$,&nbsp;  $\rm Y \}$ be given:
*Let the symbol probabilities be&nbsp; $p_{\rm X} = 0.8$ &nbsp;and&nbsp; $p_{\rm Y} = 0.2$.&nbsp; Thus the source entropy is&nbsp; $H = 0.722$&nbsp; bit/source symbol.
*We consider the symbol sequence &nbsp; $\{\rm XXXYXXXXXXXXYYXXXXXYYXXYXYXXYX\ \text{...} \}$&nbsp; with only a few&nbsp; $\rm Y$ symbols at positions 4, 13, 14, ...


The Huffman algorithm cannot be applied directly to this source, that is, one also needs a bit for each binary source symbol without further action. But:
If one combines two binary symbols at a time into a tuple of two&nbsp; $(k = 2)$&nbsp; corresponding to &nbsp; $\rm XX$ &nbsp; → &nbsp; $\rm A$, &nbsp; $\rm XY$ &nbsp; → &nbsp; $\rm B$, &nbsp; $\rm YX$ &nbsp; → &nbsp; $\rm C$, &nbsp;  $\rm YY$ &nbsp; → &nbsp; $\rm D$ &nbsp;, one can apply&nbsp;  "Huffman"&nbsp; to the resulting sequence&nbsp; → &nbsp; $\rm ABAACADAABCBBAC$ ...&nbsp; → &nbsp;  with $M\hspace{-0.01cm}′ = 4$.&nbsp;  Because of&nbsp; 
:$$p_{\rm A}= 0.8^2 = 0.64 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.8 \cdot 0.2 = 0.16 = p_{\rm C} \hspace{0.05cm}, \hspace{0.2cm}
p_{\rm D}= 0.2^2 = 0.04,$$
we get &nbsp; $\rm A$ &nbsp; → &nbsp; '''1''', &nbsp;  $\rm B$ &nbsp; → &nbsp; '''00''', &nbsp;  $\rm C$ &nbsp; → &nbsp; '''011''', &nbsp;  $\rm D$ &nbsp; → &nbsp; '''010''' &nbsp; as well as
  
:$$L_{\rm M}\hspace{0.03cm}' = 0.64 \cdot 1 + 0.16 \cdot 2 + 0.16 \cdot 3 + 0.04 \cdot 3 =1.56\,\text{bit/two-tuple}$$

:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.03cm}'}/{2}  = 0.78\ {\rm bit/source\hspace{0.15cm}symbol}\hspace{0.05cm}.$$

Now we form tuples of three&nbsp;  $(k = 3)$,&nbsp; corresponding to 
:&nbsp; &nbsp; &nbsp; $\rm XXX$ &nbsp; → &nbsp; $\rm A$, &nbsp; $\rm XXY$ &nbsp; → &nbsp; $\rm B$, &nbsp; $\rm XYX$ &nbsp; → &nbsp; $\rm C$, &nbsp; $\rm XYY$ &nbsp; → &nbsp; $\rm D$, &nbsp; $\rm YXX$ &nbsp; → &nbsp; $\rm E$, &nbsp; $\rm YXY$ &nbsp; → &nbsp; $\rm F$, &nbsp; $\rm YYX$ &nbsp; → &nbsp; $\rm G$, &nbsp; $\rm YYY$ &nbsp; → &nbsp; $\rm H$.

*For the input sequence given above, one arrives at the equivalent output sequence &nbsp;  $\rm AEBAGADBCC$ ...&nbsp; (based on the new symbol set size $M\hspace{-0.01cm}′ = 8$) and to the following probabilities:
 
:$$p_{\rm A}= 0.8^3 = 0.512 \hspace{0.05cm}, \hspace{0.5cm}p_{\rm B}=   p_{\rm C}= p_{\rm E} = 0.8^2 \cdot 0.2 = 0.128\hspace{0.05cm},\hspace{0.5cm}
p_{\rm D}=   p_{\rm F}= p_{\rm G} = 0.8 \cdot 0.2^2 = 0.032 \hspace{0.05cm}, \hspace{0.5cm}p_{\rm H}=   0.2^3 = 0.008\hspace{0.05cm}.$$

*The Huffman coding is thus:
:&nbsp; &nbsp; &nbsp; $\rm A$ &nbsp; → &nbsp; '''1''', &nbsp; $\rm B$ &nbsp; → &nbsp; '''011''', &nbsp; $\rm C$ &nbsp; → &nbsp; '''010''', &nbsp; $\rm D$ &nbsp; → &nbsp; '''00011''', &nbsp; $\rm E$ &nbsp; → &nbsp; '''001''', &nbsp; $\rm F$ &nbsp; → &nbsp; '''00010''', &nbsp; $\rm G$ &nbsp; → &nbsp; '''00001''', &nbsp; $\rm H$ &nbsp; → &nbsp; '''00000'''. 
*Thus, for the average code word length we obtain:

:$$L_{\rm M}\hspace{0.03cm}' = 0.512 \cdot 1 + 3 \cdot 0.128 \cdot 3 + (3 \cdot 0.032 + 0.008)  \cdot 5 =2.184 \,{\text{bit/three-tuple} } $$  

:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.03cm}'}/{3}  = 0.728\ {\rm bit/source\hspace{0.15cm} symbol}\hspace{0.05cm}.$$

*In this example, therefore, the source entropy&nbsp; $H = 0.722$&nbsp; bit/source symbol is almost reached already with&nbsp; $k = 3$.}}


 	 
==Exercises for the chapter==	 
<br>
[[Aufgaben:Exercise_2.6:_About_the_Huffman_Coding|Exercise 2.6: About the Huffman Coding]]

[[Aufgaben:Exercise_2.6Z:_Again_on_the_Huffman_Code|Exercise 2.6Z: Again on the Huffman Code]]

[[Aufgaben:Exercise_2.7:_Huffman_Application_for_Binary_Two-Tuples|Exercise 2.7: Huffman Application for Binary Two-Tuples]]

[[Aufgaben:Exercise_2.7Z:_Huffman_Coding_for_Two-Tuples_of_a_Ternary_Source|Exercise 2.7Z: Huffman Coding for Two-Tuples of a Ternary Source]]
 
[[Aufgaben:Exercise_2.8:_Huffman_Application_for_a_Markov_Source|Exercise 2.8: Huffman Application for a Markov Source]]

[[Aufgaben:Exercise_2.9:_Huffman_Decoding_after_Errors|Exercise 2.9: Huffman Decoding after Errors]]


{{Display}}