Aufgaben:Aufgabe 2.10: Shannon-Fano-Codierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(6 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2465__Inf_A_2_10.png |right|frame|Baumdiagramm der Shannon–Fano–Codierung]]
+
[[Datei:P_ID2465__Inf_A_2_10.png |right|frame|Baumdiagramm der <br>Shannon–Fano–Codierung]]
Ein weiterer Algorithmus zur Entropiecodierung wurde 1949 von [https://de.wikipedia.org/wiki/Claude_Shannon Claude Elwood Shannon] und [https://de.wikipedia.org/wiki/Robert_Fano|Robert Fano] angegeben, der im Theorieteil angegeben ist.
+
Ein weiterer Algorithmus zur Entropiecodierung wurde 1949 von&nbsp; [https://de.wikipedia.org/wiki/Claude_Shannon Claude Elwood Shannon]&nbsp; und&nbsp; [https://de.wikipedia.org/wiki/Robert_Fano Robert Fano]&nbsp; angegeben, der im Theorieteil beschrieben ist.
  
Diese spezielle Art von Quellencodierung soll hier an einem einfachen Beispiel für den Symbolumfang $M = 4$ und die folgenden Symbolwahrscheinlichkeiten beschrieben werden:
+
Diese spezielle Art von Quellencodierung soll hier an einem einfachen Beispiel für den Symbolumfang&nbsp; $M = 4$&nbsp; und die folgenden Symbolwahrscheinlichkeiten beschrieben werden:
  
:$$p_{\rm A} = 0.2 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.3 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.4 \hspace{0.05cm},\hspace{0.2cm}
+
:$$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}. $$
 
p_{\rm D}= 0.1 \hspace{0.05cm}. $$
  
Die Grafik zeigt das dazugehörige Baumdiagramm. Man geht folgendermaßen vor:
+
Die Grafik zeigt das dazugehörige Baumdiagramm.&nbsp; Man geht folgendermaßen vor:
  
:1. Man ordnet die Symbole nach fallender Auftrittswahrscheinlichkeit, hier $\rm C$ &ndash; $\rm B$ &ndash; $\rm A$ &ndash; $\rm D$.
+
:1. Man ordnet die Symbole nach fallender Auftrittswahrscheinlichkeit, hier&nbsp; $\rm C$ &ndash; $\rm B$ &ndash; $\rm A$ &ndash; $\rm D$.
  
:2. Man teilt die Symbole in zwei etwa gleichwahrscheinliche Gruppen ein, hier $\rm C$ und $\rm BAD$.
+
:2. Man teilt die Symbole in zwei etwa gleichwahrscheinliche Gruppen ein, hier&nbsp; $\rm C$&nbsp; und&nbsp; $\rm BAD$.
  
:3. Der unwahrscheinlicheren Gruppe wird das Binärsymbol <b>0</b>, der anderen die <b>1</b> zugeordnet.
+
:3. Der unwahrscheinlicheren Gruppe wird das Binärsymbol&nbsp; <b>0</b>, der anderen Gruppe  die&nbsp; <b>1</b>&nbsp; zugeordnet.
  
 
:4. Sind in einer Gruppe mehr als ein Zeichen, so ist der Algorithmus rekursiv anzuwenden.
 
:4. Sind in einer Gruppe mehr als ein Zeichen, so ist der Algorithmus rekursiv anzuwenden.
  
Für dieses Beispiel ergibt sich die folgende Codezuordnung (im Baumdiagramm markiert eine rote Verbindung eine <b>1</b> und eine blaue eine <b>0</b>:
+
Für dieses Beispiel ergibt sich die folgende Codezuordnung (im Baumdiagramm markiert eine rote Verbindung eine&nbsp; <b>1</b>&nbsp; und eine blaue eine&nbsp; <b>0</b>):
  
: &nbsp; &nbsp; &nbsp; $\rm A$ &#8594; <b>111</b>, &nbsp; &nbsp; $\rm B$ &#8594; <b>10</b>, &nbsp; &nbsp; $\rm C$ &#8594; <b>0</b>, &nbsp; &nbsp; $\rm D$ &#8594; <b>110</b>.
+
: &nbsp; &nbsp; &nbsp; $\rm A$ &nbsp; &#8594; &nbsp; <b>111</b>, &nbsp; &nbsp; $\rm B$ &nbsp; &#8594; &nbsp; <b>10</b>, &nbsp; &nbsp; $\rm C$ &nbsp; &#8594; &nbsp; <b>0</b>, &nbsp; &nbsp; $\rm D$ &nbsp; &#8594; &nbsp; <b>110</b>.
  
 
Damit ergibt sich für die mittlere Codewortlänge:
 
Damit ergibt sich für die mittlere Codewortlänge:
 
:$$L_{\rm M} = 0.4 \cdot 1 + 0.3 \cdot 2 + (0.2 + 0.1) \cdot 3 = 1.9\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
 
:$$L_{\rm M} = 0.4 \cdot 1 + 0.3 \cdot 2 + (0.2 + 0.1) \cdot 3 = 1.9\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
  
Der Huffman-Algorithmus würde hier zwar einen geringfügig anderen Code erzeugen, aber auch bei diesem würde $\rm C$ mit einem Bit, $\rm B$ mit zwei Bit und $\rm A$ und $\rm D$ mit jeweils drei Bit codiert. Damit ergäbe sich ebenfalls $L_{\rm M} = 1.9 \ \rm bit/Quellensymbol$.
+
Der Huffman-Algorithmus würde hier zwar einen geringfügig anderen Code erzeugen, aber auch bei diesem würde&nbsp;
 +
*$\rm C$&nbsp; mit einem Bit,&nbsp;
 +
*$\rm B$&nbsp; mit zwei Bit und&nbsp;
 +
*$\rm A$ und&nbsp; $\rm D$&nbsp; mit jeweils drei Bit&nbsp;
  
In dieser Aufgabe sollen Sie den Shannon&ndash;Fano&ndash;Code für $M = 8$ und die Wahrscheinlichkeiten
 
:$$p_{\rm A} = 0.10 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.40 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.02 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D}= 0.14 \hspace{0.05cm},\hspace{0.2cm}
 
p_{\rm E} = 0.17 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm F}= 0.03 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm G}= 0.05 \hspace{0.05cm},\hspace{0.2cm}p_{\rm H}= 0.09$$
 
ermitteln. Sie werden erkennen, dass sich mit diesen Wahrscheinlichkeiten &bdquo;Shannon&ndash;Fano&rdquo; auch hinsichtlich Effizienz von &bdquo;Huffman&rdquo; unterscheiden wird. Beim Huffman&ndash;Code ergibt sich mit den vorliegenden Wahrscheinlichkeiten die folgende Zuordnung:
 
  
: &nbsp; &nbsp; &nbsp; $\rm A$ &#8594; <b>100</b>, &nbsp; &nbsp;  $\rm B$ &#8594; <b>0</b>, &nbsp; &nbsp;  $\rm C$ &#8594; <b>111100</b>, &nbsp; &nbsp; $\rm D$ &#8594; <b>101</b>, &nbsp; &nbsp; $\rm E$ &#8594; <b>110</b>,  &nbsp; &nbsp; $\rm F$ &#8594; <b>111101</b>, &nbsp; &nbsp; $\rm G$ &#8594; <b>11111</b>, &nbsp; &nbsp; $\rm H$ &#8594; <b>1110</b>.
+
codiert.&nbsp; Damit ergäbe sich ebenfalls&nbsp; $L_{\rm M} = 1.9 \ \rm bit/Quellensymbol$.
 +
 
 +
In dieser Aufgabe sollen Sie den Shannon&ndash;Fano&ndash;Code für&nbsp; $M = 8$&nbsp; und die Wahrscheinlichkeiten
 +
:$$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$$
 +
ermitteln.&nbsp; Sie werden erkennen, dass sich mit diesen Wahrscheinlichkeiten &bdquo;Shannon&ndash;Fano&rdquo; auch hinsichtlich der Effizienz von &bdquo;Huffman&rdquo; unterscheiden wird.&nbsp;
 +
 
 +
Beim Huffman&ndash;Code ergibt sich mit den vorliegenden Wahrscheinlichkeiten die folgende Zuordnung:
 +
 
 +
: &nbsp; &nbsp; &nbsp; $\rm A$ &nbsp; &#8594; &nbsp; <b>100</b>, &nbsp; &nbsp;  $\rm B$ &nbsp; &#8594; &nbsp; <b>0</b>, &nbsp; &nbsp;  $\rm C$ &nbsp; &#8594; &nbsp; <b>111100</b>, &nbsp; &nbsp; $\rm D$ &nbsp; &#8594; &nbsp; <b>101</b>, &nbsp; &nbsp; $\rm E$ &nbsp; &#8594; &nbsp; <b>110</b>,  &nbsp; &nbsp; $\rm F$ &nbsp; &#8594; &nbsp; <b>111101</b>, &nbsp; &nbsp; $\rm G$ &nbsp; &#8594; &nbsp; <b>11111</b>, &nbsp; &nbsp; $\rm H$ &nbsp; &#8594; &nbsp; <b>1110</b>.
 +
 
  
  
Zeile 42: Zeile 51:
  
 
''Hinweise:''  
 
''Hinweise:''  
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Weitere_Quellencodierverfahren|Weitere Quellencodierverfahren]].
+
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren|Weitere Quellencodierverfahren]].
*Insbesondere wird  Bezug genommen auf die Seite [[Informationstheorie/Weitere_Quellencodierverfahren#Der_Shannon.E2.80.93Fano.E2.80.93Algorithmus|Der Shannon-Fano-Algorithmus]].
+
*Insbesondere wird  Bezug genommen auf die Seite&nbsp; [[Informationstheorie/Weitere_Quellencodierverfahren#Der_Shannon.E2.80.93Fano.E2.80.93Algorithmus|Der Shannon-Fano-Algorithmus]].
*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul [[Applets:Huffman_Shannon_Fano|Shannon&ndash;Fano&ndash; und Huffman&ndash;Codierung]].
+
*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das folgende Interaktionsmodul:&nbsp; [[Applets:Huffman_Shannon_Fano|Huffman- und Shannon-Fano-Codierung&nbsp; &rArr; &nbsp; $\text{SWF}$&ndash;Version]].
 
   
 
   
  
Zeile 52: Zeile 61:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Wie groß ist die mittlere Codewortlänge beim Huffman&ndash;Code?
+
{Wie groß ist die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; beim&nbsp; <u>Huffman&ndash;Code</u>?
 
|type="{}"}
 
|type="{}"}
$\text{Huffman:} \ \ L_{\rm M}\ = \ $ { 2.54 3% } $\ \rm bit/Quellensymbol$
+
$L_{\rm M}\ = \ $ { 2.54 3% } $\ \rm bit/Quellensymbol$
  
  
{Was geschieht im ersten Schritt der Shannon&ndash;Fano&ndash;Codierung? Alle anderen Symbole werden in der zweiten Gruppe zusammengefasst.
+
{Was geschieht im ersten Schritt der&nbsp; <u>Shannon&ndash;Fano&ndash;Codierung</u>?&nbsp; <u>Hinweis</u>:&nbsp; Alle anderen Symbole werden in der zweiten Gruppe zusammengefasst.
|type="[]"}
+
|type="()"}
- Man fasst <b>A</b> und <b>B</b> zur ersten Gruppe zusammen.
+
- Man fasst&nbsp; $\rm A$&nbsp; und&nbsp; $\rm B$&nbsp; zur ersten Gruppe zusammen.
+ Man fasst <b>B</b> und <b>E</b> zur ersten Gruppe zusammen.
+
+ Man fasst&nbsp; $\rm B$&nbsp; und&nbsp; $\rm E$&nbsp; zur ersten Gruppe zusammen.
- Die erste Gruppe besteht nur aus dem Symbol <b>B</b>.
+
- Die erste Gruppe besteht nur aus dem Symbol&nbsp; $\rm B$.
  
  
{Welche Zuordnungen ergeben sich für den Shannon&ndash;Fano&ndash;Algorithmus?
+
{Welche Zuordnungen ergeben sich für den&nbsp; <u>Shannon&ndash;Fano&ndash;Algorithmus</u>?
 
|type="[]"}
 
|type="[]"}
+ Das Zeichen <b>A</b> wird binär mit <b>010</b> codiert.
+
+ Das Zeichen&nbsp; $\rm A$&nbsp; wird binär mit&nbsp; <b>010</b>&nbsp; codiert.
+ Das Zeichen <b>B</b> wird binär mit <b>11</b> codiert.
+
+ Das Zeichen&nbsp; $\rm B$&nbsp; wird binär mit&nbsp; <b>11</b>&nbsp; codiert.
+ Das Zeichen <b>C</b> wird binär mit <b>00110</b> codiert.
+
+ Das Zeichen&nbsp; $\rm C$&nbsp; wird binär mit&nbsp; <b>00110</b>&nbsp; codiert.
  
  
{Wie groß ist die mittlere Codewortlänge beim Shannon&ndash;Fano&ndash;Code?
+
{Wie groß ist die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; beim&nbsp; <u>Shannon&ndash;Fano&ndash;Code</u>?
 
|type="{}"}
 
|type="{}"}
$\text{Shannon-Fano:} \ \ L_{\rm M}\ = \ $ { 2.58 3% } $\ \rm bit/Quellensymbol$
+
$L_{\rm M}\ = \ $ { 2.58 3% } $\ \rm bit/Quellensymbol$
  
  
 
{Welche Aussagen gelten für beliebige Wahrscheinlichkeiten?
 
{Welche Aussagen gelten für beliebige Wahrscheinlichkeiten?
 
|type="[]"}
 
|type="[]"}
- $L_{\rm M}$ könnte bei Shannon&ndash;Fano kleiner sein als bei Huffman.
+
- $L_{\rm M}$&nbsp; könnte bei &bdquo;Shannon&ndash;Fano&rdquo; kleiner sein als bei &bdquo;Huffman&rdquo;.
+ $L_{\rm M}$ könnte bei Shannon&ndash;Fano größer sein als bei Huffman.
+
+ $L_{\rm M}$&nbsp; könnte bei &bdquo;Shannon&ndash;Fano&rdquo; größer sein als bei &bdquo;Huffman&rdquo;.
+ $L_{\rm M}$ könnte bei Shannon&ndash;Fano und Huffman gleich groß sein.
+
+ $L_{\rm M}$&nbsp; könnte bei &bdquo;Shannon&ndash;Fano&rdquo; und &bdquo;Huffman&rdquo; gleich groß sein.
  
  
Zeile 90: Zeile 99:
 
'''(1)'''&nbsp; Für den angegebenen Huffman&ndash;Code erhält man:
 
'''(1)'''&nbsp; Für den angegebenen Huffman&ndash;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}. $$
 
:$$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)'''&nbsp; Richtig ist die <u>Antwort 2</u>:
 
'''(2)'''&nbsp; Richtig ist die <u>Antwort 2</u>:
*Vor Anwendung des Shannon&ndash;Fano&ndash;Algorithmus müssen die Zeichen zuerst noch nach ihren Auftrittswahrscheinlichkeiten sortiert werden. Damit ist die Antwort 1 falsch.
+
*Vor Anwendung des Shannon&ndash;Fano&ndash;Algorithmus müssen die Zeichen erst nach ihren Auftrittswahrscheinlichkeiten sortiert werden.&nbsp; 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 bedeutet dies:
+
*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}.$$
 
:$${\rm Pr}(\boldsymbol{\rm BE})  = 0.57\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm DAHGFC})  = 0.43  \hspace{0.05cm}.$$
 +
[[Datei:P_ID2466__Inf_A_2_10c.png|right|frame|Baumdiagramm der Shannon–Fano–Codierung]]
 
*Bei der Aufteilung gemäß Lösungsvorschlag 3 würde die Gleichverteilung noch weniger erreicht:
 
*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}.$$
 
:$${\rm Pr}(\boldsymbol{\rm B})  = 0.40\hspace{0.05cm}, \hspace{0.2cm}{\rm Pr}(\boldsymbol{\rm EDAHGFC})  = 0.60  \hspace{0.05cm}.$$
  
[[Datei:P_ID2466__Inf_A_2_10c.png|right|Baumdiagramm der Shannon–Fano–Codierung]]
+
 
 +
 
 +
 
 
'''(3)'''&nbsp; <u>Alle Lösungsvorschläge</u> sind richtig:
 
'''(3)'''&nbsp; <u>Alle Lösungsvorschläge</u> sind richtig:
 
*Die Grafik zeigt das Baumdiagramm der Shannon&ndash;Fano&ndash;Codierung.  
 
*Die Grafik zeigt das Baumdiagramm der Shannon&ndash;Fano&ndash;Codierung.  
*Daraus ergibt sich folgende Zuordnung (eine rote Verbindung weist auf <b>1</b> hin, eine blaue auf <b>0</b>):
+
*Daraus ergibt sich folgende Zuordnung (eine rote Verbindung weist auf eine&nbsp; <b>1</b>&nbsp; hin, eine blaue auf eine&nbsp; <b>0</b>):
: <u><b>A</b> &#8594; <b>010</b></u>,  
+
: $\underline{\rm A}$ &nbsp; &#8594; &nbsp; <u><b>010</b></u>, &nbsp; &nbsp;  $\underline{\rm B}$ &nbsp; &#8594; &nbsp; <u><b>11</b></u>, &nbsp; &nbsp;  $\underline{\rm C}$ &nbsp; &#8594; &nbsp; <u><b>00110</b></u>,  
: <u><b>B</b> &#8594; <b>11</b></u>,  
+
: ${\rm D}$ &nbsp; &#8594; &nbsp; <b>011</b>, &nbsp; &nbsp; ${\rm E}$ &nbsp; &#8594; &nbsp; <b>10</b>, &nbsp; &nbsp; ${\rm F}$ &nbsp; &#8594; &nbsp; <b>00111</b>, &nbsp; &nbsp; ${\rm G}$ &nbsp; &#8594; &nbsp; <b>0010</b>, &nbsp; &nbsp; ${\rm H}$ &nbsp; &#8594; &nbsp; <b>000</b>.
: <u><b>C</b> &#8594; <b>00110</b></u>,  
 
: <b>D</b> &#8594; <b>011</b>, <b>E</b> &#8594; <b>10</b>, <b>F</b> &#8594; <b>00111</b>,  
 
: <b>G</b> &#8594; <b>0010</b>, <b>H</b> &#8594; <b>000</b>.
 
  
  
'''(4)'''&nbsp; Mit dem Ergebnis der Teilaufgabe (3) erhält man:
+
 
 +
'''(4)'''&nbsp; Mit dem Ergebnis der Teilaufgabe&nbsp; '''(3)'''&nbsp; 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}. $$
 
:$$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)'''&nbsp; Richtig sind die <u>Aussagen 2 und 3</u>:
 
'''(5)'''&nbsp; Richtig sind die <u>Aussagen 2 und 3</u>:

Aktuelle Version vom 12. August 2021, 12:59 Uhr

Baumdiagramm der
Shannon–Fano–Codierung

Ein weiterer Algorithmus zur Entropiecodierung wurde 1949 von  Claude Elwood Shannon  und  Robert Fano  angegeben, der im Theorieteil beschrieben ist.

Diese spezielle Art von Quellencodierung soll hier an einem einfachen Beispiel für den Symbolumfang  $M = 4$  und die folgenden Symbolwahrscheinlichkeiten beschrieben werden:

$$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}. $$

Die Grafik zeigt das dazugehörige Baumdiagramm.  Man geht folgendermaßen vor:

1. Man ordnet die Symbole nach fallender Auftrittswahrscheinlichkeit, hier  $\rm C$ – $\rm B$ – $\rm A$ – $\rm D$.
2. Man teilt die Symbole in zwei etwa gleichwahrscheinliche Gruppen ein, hier  $\rm C$  und  $\rm BAD$.
3. Der unwahrscheinlicheren Gruppe wird das Binärsymbol  0, der anderen Gruppe die  1  zugeordnet.
4. Sind in einer Gruppe mehr als ein Zeichen, so ist der Algorithmus rekursiv anzuwenden.

Für dieses Beispiel ergibt sich die folgende Codezuordnung (im Baumdiagramm markiert eine rote Verbindung eine  1  und eine blaue eine  0):

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

Damit ergibt sich für die mittlere Codewortlänge:

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

Der Huffman-Algorithmus würde hier zwar einen geringfügig anderen Code erzeugen, aber auch bei diesem würde 

  • $\rm C$  mit einem Bit, 
  • $\rm B$  mit zwei Bit und 
  • $\rm A$ und  $\rm D$  mit jeweils drei Bit 


codiert.  Damit ergäbe sich ebenfalls  $L_{\rm M} = 1.9 \ \rm bit/Quellensymbol$.

In dieser Aufgabe sollen Sie den Shannon–Fano–Code für  $M = 8$  und die Wahrscheinlichkeiten

$$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$$

ermitteln.  Sie werden erkennen, dass sich mit diesen Wahrscheinlichkeiten „Shannon–Fano” auch hinsichtlich der Effizienz von „Huffman” unterscheiden wird. 

Beim Huffman–Code ergibt sich mit den vorliegenden Wahrscheinlichkeiten die folgende Zuordnung:

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




Hinweise:



Fragebogen

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–CodierungHinweis:  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

(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.