Aufgaben:Exercise 2.10: Shannon-Fano Coding

• Return to book

Baumdiagramm der
Shannon-Fano coding

Another algorithm for entropy coding was given in 1949 by  Claude Elwood Shannon  and  Robert Fano , which is described in the theory section.

This special type of source coding will be described here using a simple example for the symbol range  $M = 4$  and the following symbol probabilities:

$$p_{\rm A} = 0.2 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm B}= 0.3 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm C}= 0.4 \hspace{0.05cm},\hspace{0.4cm} p_{\rm D}= 0.1 \hspace{0.05cm}. $$

The graph shows the corresponding tree diagram.  Proceed as follows:

1. Order the symbols according to decreasing probability of occurrence, here  $\rm C$ – $\rm B$ – $\rm A$ – $\rm D$.

2. Divide the symbols into two groups of approximately equal probability, here  $\rm C$  and  $\rm BAD$.

3. The binary symbol  0is assigned to the less probable group,  1  to the other group.

4. If there is more than one symbol in a group, the algorithm is to be applied recursively.

For this example, the following code assignment results (in the tree diagram, a red connection marks a  1  and a blue one a  0:

      $\rm A$   →   111,     $\rm B$   →   10,     $\rm C$   →   0,     $\rm D$   →   110.

This gives the following for the mean codeword length:

$$L_{\rm M} = 0.4 \cdot 1 + 0.3 \cdot 2 + (0.2 + 0.1) \cdot 3 = 1.9\,\,{\rm bit/source\:symbol}\hspace{0.05cm}.$$

The Huffman algorithm would produce a slightly different code here, but even in this case 

• $\rm C$  is coded with one bit, 
• $\rm B$  with two bits and  
• $\rm A$ and  $\rm D$  with three bits each. 

  This would also result in  $L_{\rm M} = 1.9 \ \rm bit/source\:symbol$.

In this task you are to calculate the Shannon-Fano code for  $M = 8$  and the probabilities

$$p_{\rm A} = 0.10 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm B}= 0.40 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm C}= 0.02 \hspace{0.05cm},\hspace{0.4cm} p_{\rm D}= 0.14 \hspace{0.05cm},\hspace{0.4cm} p_{\rm E} = 0.17 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm F}= 0.03 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm G}= 0.05 \hspace{0.05cm},\hspace{0.4cm}p_{\rm H}= 0.09$$

determine.  You will see that with these probabilities "Shannon-Fano" will also differ from "Huffman" in terms of efficiency. 

With the Huffman code, the following assignment results with the probabilities at hand:

      $\rm A$   →   100,     $\rm B$   →   0,     $\rm C$   →   111100,     $\rm D$   →   101,     $\rm E$   →   110,     $\rm F$   →   111101,     $\rm G$   →   11111,     $\rm H$   →   1110.

Hints:

• The assignment belongs to the chapter  Other source coding methods.
• In particular, reference is made to the page  The Shannon-Fano algorithm.
• To check your results, please refer to the interactive applet  Huffman and Shannon-Fano coding.

Questions

1

Wie groß ist die mittlere Codewortlänge  $L_{\rm M}$  beim  Huffman–Code?

$L_{\rm M}\ = \ $ $\ \rm bit/Quellensymbol$

2

Was geschieht im ersten Schritt der  Shannon–Fano–Codierung?  Hinweis:  Alle anderen Symbole werden in der zweiten Gruppe zusammengefasst.

	Man fasst  $\rm A$  und  $\rm B$  zur ersten Gruppe zusammen.
	Man fasst  $\rm B$  und  $\rm E$  zur ersten Gruppe zusammen.
	Die erste Gruppe besteht nur aus dem Symbol  $\rm B$.

3

Welche Zuordnungen ergeben sich für den  Shannon–Fano–Algorithmus?

	Das Zeichen  $\rm A$  wird binär mit  010  codiert.
	Das Zeichen  $\rm B$  wird binär mit  11  codiert.
	Das Zeichen  $\rm C$  wird binär mit  00110  codiert.

4

Wie groß ist die mittlere Codewortlänge  $L_{\rm M}$  beim  Shannon–Fano–Code?

$L_{\rm M}\ = \ $ $\ \rm bit/Quellensymbol$

5

Welche Aussagen gelten für beliebige Wahrscheinlichkeiten?

	$L_{\rm M}$  könnte bei "Shannon–Fano" kleiner sein als bei "Huffman".
	$L_{\rm M}$  könnte bei "Shannon–Fano" größer sein als bei "Huffman".
	$L_{\rm M}$  könnte bei "Shannon–Fano" und "Huffman" gleich groß sein.

Musterlösung

Solution

(1)  Für den angegebenen Huffman–Code erhält man:

$$L_{\rm M} = 0.4 \cdot 1 + (0.17 + 0.14 + 0.10) \cdot 3 + 0.09 \cdot 4 + 0.05 \cdot 5 + (0.03 + 0.02) \cdot 6 =\underline{ 2.54 \,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$

(2)  Richtig ist die Antwort 2:

• Vor Anwendung des Shannon–Fano–Algorithmus müssen die Zeichen erst nach ihren Auftrittswahrscheinlichkeiten sortiert werden.  Damit ist die Antwort 1 falsch.
• Alle sortierten Zeichen müssen so in zwei Gruppen eingeteilt werden, dass die Gruppenwahrscheinlichkeiten möglichst gleich sind. Für den ersten Schritt:

$${\rm Pr}(\boldsymbol{\rm BE}) = 0.57\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm DAHGFC}) = 0.43 \hspace{0.05cm}.$$

Baumdiagramm der Shannon–Fano–Codierung

• Bei der Aufteilung gemäß Lösungsvorschlag 3 würde die Gleichverteilung noch weniger erreicht:

$${\rm Pr}(\boldsymbol{\rm B}) = 0.40\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm EDAHGFC}) = 0.60 \hspace{0.05cm}.$$

(3)  Alle Lösungsvorschläge sind richtig:

• Die Grafik zeigt das Baumdiagramm der Shannon–Fano–Codierung.
• Daraus ergibt sich folgende Zuordnung (eine rote Verbindung weist auf eine  1  hin, eine blaue auf eine  0):

$\underline{\rm A}$   →   010,     $\underline{\rm B}$   →   11,     $\underline{\rm C}$   →   00110,

${\rm D}$   →   011,     ${\rm E}$   →   10,     ${\rm F}$   →   00111,     ${\rm G}$   →   0010,     ${\rm H}$   →   000.

(4)  Mit dem Ergebnis der Teilaufgabe  (3)  erhält man:

$$L_{\rm M}= (0.40 + 0.17) \cdot 2 + (0.14 + 0.10 + 0.09) \cdot 3 + 0.05 \cdot 4 + (0.03 + 0.02) \cdot 5 =\underline{ 2.58 \,\,{\rm bit/Quellensymbol}}\hspace{0.05cm}. $$

(5)  Richtig sind die Aussagen 2 und 3:

• Im vorliegenden Beispiel ergibt sich bei Shannon–Fano ein ungünstigerer Wert als bei Huffman.
• In den meisten Fällen – so auch im Beispiel auf der Angabenseite – ergibt sich für Huffman und Shannon–Fano ein gleichwertiger Code und damit auch die gleiche mittlere Codewortlänge.
• Einen effektiveren Code als Huffman liefert Shannon–Fano dagegen nie.