Aufgaben:Aufgabe 2.6: Zur Huffman-Codierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(12 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2451__Inf_A_2_6.png|right|Baumdiagramm des Huffman–Verfahrens]]
+
[[Datei:P_ID2451__Inf_A_2_6.png|right|frame|Huffman–Baumdiagramm]]
Wir betrachten hier eine Quellensymbolfolge $\langle q_\nu  \rangle$ mit dem Symbolumfang $M = 8$:
+
Wir betrachten hier eine Quellensymbolfolge  $\langle q_\nu  \rangle$  mit dem Symbolumfang  $M = 8$:
:$$q_{\nu} = \{ \hspace{0.05cm}q_{\mu} \} = \{ \boldsymbol{\rm A} \hspace{0.05cm}, \boldsymbol{\rm B}\hspace{0.05cm}, \boldsymbol{\rm C}\hspace{0.05cm}, \boldsymbol{\rm D}\hspace{0.05cm}, \boldsymbol{\rm E}\hspace{0.05cm}, \boldsymbol{\rm F}\hspace{0.05cm}, \boldsymbol{\rm G}\hspace{0.05cm}, \boldsymbol{\rm H}\hspace{0.05cm}
+
:$$q_{\nu} \in \{ \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}.$$
 
\}\hspace{0.05cm}.$$
Sind die Symbole gleichwahrscheinlich, also gilt $p_{\rm A} =  p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$, so macht Quellencodierung keinen Sinn. Bereits mit dem Dualcode <b>A</b> &#8594; <b>000</b>, <b>B</b>&nbsp;&#8594;&nbsp;<b>001</b>, ... , <b>H</b> &#8594; <b>111</b>, erreicht nämlich die mittlere Codewortlänge $L_{\rm M}$ ihre untere Schranke $H$ gemäß dem Quellencodierungstheorem ($H$ bezeichnet hierbei die <i>Quellenentropie</i>):
+
Sind die Symbole gleichwahrscheinlich,&nbsp; gilt also&nbsp; $p_{\rm A} =  p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$,&nbsp; so macht Quellencodierung keinen Sinn.&nbsp; Bereits mit dem Dualcode&nbsp; $\rm A$&nbsp; &#8594;&nbsp; <b>000</b>,&nbsp; $\rm B$&nbsp; &#8594;&nbsp; <b>001</b>, ... ,&nbsp; $\rm H$&nbsp; &#8594;&nbsp; <b>111</b>, erreicht nämlich dann die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; ihre untere Schranke&nbsp; $H$&nbsp; gemäß dem Quellencodierungstheorem&nbsp; $(H$ bezeichnet hierbei die Quellenentropie$)$:
 
:$$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/Quellensymbol} \hspace{0.05cm}.$$
 
:$$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/Quellensymbol} \hspace{0.05cm}.$$
  
 
Die Symbolwahrscheinlichkeiten seien aber in dieser Aufgabe wie folgt gegeben:
 
Die Symbolwahrscheinlichkeiten seien aber in dieser Aufgabe wie folgt gegeben:
 
:$$p_{\rm A} \hspace{-0.05cm}= \hspace{-0.05cm} 0.04  \hspace{0.05cm},\hspace{0.1cm}p_{\rm B} \hspace{-0.05cm}= \hspace{-0.05cm} 0.08  \hspace{0.05cm},\hspace{0.1cm}p_{\rm C} \hspace{-0.05cm}= \hspace{-0.05cm} 0.14  \hspace{0.05cm},\hspace{0.1cm}
 
:$$p_{\rm A} \hspace{-0.05cm}= \hspace{-0.05cm} 0.04  \hspace{0.05cm},\hspace{0.1cm}p_{\rm B} \hspace{-0.05cm}= \hspace{-0.05cm} 0.08  \hspace{0.05cm},\hspace{0.1cm}p_{\rm C} \hspace{-0.05cm}= \hspace{-0.05cm} 0.14  \hspace{0.05cm},\hspace{0.1cm}
p_{\rm D} \hspace{-0.05cm}= \hspace{-0.05cm} 0.25  \hspace{0.05cm},$$
+
p_{\rm D} \hspace{-0.05cm}= \hspace{-0.05cm} 0.25  \hspace{0.05cm},\hspace{0.1cm} p_{\rm E} \hspace{-0.05cm}= \hspace{-0.05cm} 0.24  \hspace{0.05cm},\hspace{0.1cm}p_{\rm F} \hspace{-0.05cm}= \hspace{-0.05cm} 0.12  \hspace{0.05cm},\hspace{0.1cm}p_{\rm G} \hspace{-0.05cm}= \hspace{-0.05cm} 0.10  \hspace{0.05cm},\hspace{0.1cm}
:$$p_{\rm E} \hspace{-0.05cm}= \hspace{-0.05cm} 0.24  \hspace{0.05cm},\hspace{0.1cm}p_{\rm F} \hspace{-0.05cm}= \hspace{-0.05cm} 0.12  \hspace{0.05cm},\hspace{0.1cm}p_{\rm G} \hspace{-0.05cm}= \hspace{-0.05cm} 0.10  \hspace{0.05cm},\hspace{0.1cm}
 
 
p_{\rm H} \hspace{-0.05cm}= \hspace{-0.05cm} 0.03  \hspace{0.05cm}.$$
 
p_{\rm H} \hspace{-0.05cm}= \hspace{-0.05cm} 0.03  \hspace{0.05cm}.$$
Es liegt hier also eine redundante Nachrichtenquelle vor, die man durch Huffman&ndash;Codierung komprimieren kann. Der Algorithmus wurde 1952 &ndash; also kurz nach Shannons bahnbrechenden Arbeiten zur Informationstheorie &ndash; von [https://de.wikipedia.org/wiki/David_A._Huffman David Albert Huffman] veröffentlicht und erlaubt die Konstruktion von optimalen präfixfreien Codes.
+
*Es liegt hier also eine redundante Nachrichtenquelle vor, die man durch Huffman&ndash;Codierung komprimieren kann.  
 +
*Dieser Algorithmus wurde 1952 &ndash; also kurz nach Shannons bahnbrechenden Arbeiten zur Informationstheorie &ndash; von&nbsp; [https://de.wikipedia.org/wiki/David_A._Huffman David Albert Huffman]&nbsp; veröffentlicht und erlaubt die Konstruktion von optimalen präfixfreien Codes.
  
Der Algorithmus soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns auf Binärcodes beschränken (die Codesymbolfolge besteht nur aus Nullen und Einsen):
 
  
:1. Man ordne die Symbole nach fallenden Auftrittswahrscheinlichkeiten.
+
Der Algorithmus soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns auf Binärcodes beschränken &nbsp; &rArr; &nbsp; die Codesymbolfolge besteht nur aus Nullen und Einsen:
  
:2. Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen.
+
:'''(1)''' &nbsp; Man ordne die Symbole nach fallenden Auftrittswahrscheinlichkeiten.
  
:3. Man wiederhole Schritt 1 und 2, bis nur zwei (zusammengefasste) Symbole übrig bleiben.
+
:'''(2)''' &nbsp;  Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen.
  
:4. Die wahrscheinlichere Symbolmenge wird mit <b>1</b>  binär codiert, die andere Menge mit <b>0</b>.
+
:'''(3)''' &nbsp;  Man wiederhole Schritt&nbsp; '''(1)'''&nbsp; und&nbsp; '''(2)''', bis nur zwei (zusammengefasste) Symbole übrig bleiben.
  
:5. Man ergänze schrittweise (von unten nach oben) die aufgespaltenen Teilcodes mit <b>1</b> bzw. <b>0</b>.
+
:'''(4)''' &nbsp;  Die wahrscheinlichere Symbolmenge wird mit&nbsp; <b>1</b>&nbsp;  binär codiert, die andere Menge mit&nbsp; <b>0</b>.
  
Oft wird dieser Algorithmus durch ein Baumdiagramm veranschaulicht. Die obige Grafik zeigt dieses für den vorliegenden Fall. Sie haben folgende Aufgaben:
+
:'''(5)''' &nbsp;  Man ergänze schrittweise (von unten nach oben) die aufgespaltenen Teilcodes mit&nbsp; <b>1</b>&nbsp; bzw.&nbsp; <b>0</b>.
  
: (a): Zuordnung der Symbole <b>A</b>, ... , <b>H</b> zu den mit [1], ... , [8] bezeichneten Eingängen.
 
  
: (b): Bestimmung der Summenwahrscheinlichkeiten <i>U</i>, ... , <i>Z</i> sowie <i>R</i> (<i>Root</i>).
+
Oft wird dieser Algorithmus durch ein Baumdiagramm veranschaulicht. Die Grafik zeigt dieses für den vorliegenden Fall.  
  
: (c) Zuordnung der Symbole <b>A</b>, ... , <b>H</b> zu den entsprechenden Huffman&ndash;Binärfolgen; eine rote Verbindung im Baumdiagramm entspricht einer <b>1</b> und eine blaue Verbindung einer <b>0</b>.
+
Sie haben folgende Aufgaben:
 +
 
 +
:'''(a)''' &nbsp; Zuordnung der Symbole&nbsp; $\rm A$, ... , $\rm H$&nbsp; zu den mit&nbsp; '''[1]''', ... , '''[8]'''&nbsp; bezeichneten Eingängen.
 +
 
 +
:'''(b)''' &nbsp; Bestimmung der Summenwahrscheinlichkeiten&nbsp; $U$, ... ,&nbsp; $Z$&nbsp; sowie&nbsp; $R$&nbsp; (&bdquo;Root&rdquo;).
 +
 
 +
:'''(c)''' &nbsp; Zuordnung der Symbole&nbsp; $\rm A$, ... ,&nbsp; $\rm H$&nbsp; zu den entsprechenden Huffman&ndash;Binärfolgen. Eine rote Verbindung entspricht einer&nbsp; <b>1</b>, eine blaue Verbindung einer&nbsp; <b>0</b>.
  
 
Sie werden feststellen, dass die mittlere Codewortlänge
 
Sie werden feststellen, dass die mittlere Codewortlänge
 
:$$L_{\rm M} =  \sum_{\mu = 1}^{M}\hspace{0.05cm} p_{\mu} \cdot L_{\mu} $$
 
:$$L_{\rm M} =  \sum_{\mu = 1}^{M}\hspace{0.05cm} p_{\mu} \cdot L_{\mu} $$
bei Huffman&ndash;Codierung nur unwesentlich größer ist als die Quellenentropie $H$. In dieser Gleichung gelten für den vorliegenden Fall folgende Werte: $M = 8$,  $p_1 = p_{\rm A}$, ... , $p_8 = p_{\rm H}$. Die jeweilige Bitanzahl der Codesymbole für <b>A</b>, ... , <b>H</b> ist mit $L_1$, ... , $L_8$ bezeichnet.
+
bei Huffman&ndash;Codierung nur unwesentlich größer ist als die Quellenentropie&nbsp; $H$.&nbsp; In dieser Gleichung gelten für den vorliegenden Fall folgende Werte:  
 +
*$M = 8$,&nbsp; $p_1 = p_{\rm A}$,&nbsp; ... ,&nbsp; $p_8 = p_{\rm H}$.  
 +
*Die jeweilige Bitanzahl der Codesymbole für&nbsp; $\rm A$, ... ,&nbsp; $\rm H$&nbsp; ist mit&nbsp; $L_1$, ... ,&nbsp; $L_8$&nbsp; bezeichnet.
 +
 
 +
 
 +
 
 +
 
 +
 
  
  
 
''Hinweise:''  
 
''Hinweise:''  
*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]].
+
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Entropiecodierung_nach_Huffman|Entropiecodierung nach Huffman]].
*Insbesondere wird  Bezug genommen auf die Seiten [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus|Der Huffman-Algorithmus]], sowie [[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm|Darstellung des Huffman-Codes als Baumdiagramm]].
+
*Insbesondere wird  Bezug genommen auf die Seiten&nbsp;
*Zur Kontrolle Ihrer Ergebnisse verweisen wir auf das Interaktionsmodul [[Shannon&ndash;Fano&ndash; und Huffman&ndash;Codierung]].
+
** [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus|Der Huffman-Algorithmus]],
*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
+
**[[Informationstheorie/Entropiecodierung_nach_Huffman#Darstellung_des_Huffman.E2.80.93Codes_als_Baumdiagramm|Darstellung des Huffman-Codes als Baumdiagramm]].
 +
*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 54: Zeile 67:
 
{Welche Eingänge im Baumdiagramm stehen für
 
{Welche Eingänge im Baumdiagramm stehen für
 
|type="{}"}
 
|type="{}"}
Eingangsnummer  $ \ = \ $  { 7 } &nbsp; &rArr; &nbsp; Symbol '''A'''
+
Eingangsnummer  $ \ = \ $  { 7 } &nbsp; &rArr; &nbsp; Symbol $\rm A$
Eingangsnummer  $ \ = \ $  { 6 } &nbsp; &rArr; &nbsp; Symbol '''B'''
+
Eingangsnummer  $ \ = \ $  { 6 } &nbsp; &rArr; &nbsp; Symbol $\rm B$
Eingangsnummer  $ \ = \ $  { 3 } &nbsp; &rArr; &nbsp; Symbol '''C'''
+
Eingangsnummer  $ \ = \ $  { 3 } &nbsp; &rArr; &nbsp; Symbol $\rm C$
Eingangsnummer  $ \ = \ $  { 1 } &nbsp; &rArr; &nbsp; Symbol '''D'''
+
Eingangsnummer  $ \ = \ $  { 1 } &nbsp; &rArr; &nbsp; Symbol $\rm D$
  
  
{Welche Zahlenwerte (Wahrscheinlichkeiten sollten bei den Knoten im Baumdiagramm stehen?
+
{Welche Zahlenwerte (Wahrscheinlichkeiten) sollten bei den Knoten im Baumdiagramm stehen?
 
|type="{}"}
 
|type="{}"}
Wahrscheinlichkeit  $ \ = \ $ { 0.07 1% } &nbsp; bei Knoten '''U'''
+
Wahrscheinlichkeit  $ \ = \ $ { 0.07 1% } &nbsp; bei Knoten $\rm U$
Wahrscheinlichkeit  $ \ = \ $ { 0.15 1% } &nbsp; bei Knoten '''V'''
+
Wahrscheinlichkeit  $ \ = \ $ { 0.15 1% } &nbsp; bei Knoten $\rm V$
Wahrscheinlichkeit  $ \ = \ $ { 0.22 1% } &nbsp; bei Knoten '''W'''
+
Wahrscheinlichkeit  $ \ = \ $ { 0.22 1% } &nbsp; bei Knoten $\rm W$
Wahrscheinlichkeit  $ \ = \ $ { 0.54 1% } &nbsp; bei Knoten '''Z'''
+
Wahrscheinlichkeit  $ \ = \ $ { 0.29 1% } &nbsp; bei Knoten $\rm X$
Wahrscheinlichkeit  $ \ = \ $ { 1 1% } &nbsp; bei '''Root'''
+
Wahrscheinlichkeit  $ \ = \ $ { 0.46 1% } &nbsp; bei Knoten $\rm Y$
 +
Wahrscheinlichkeit  $ \ = \ $ { 0.54 1% } &nbsp; bei Knoten $\rm Z$
 +
Wahrscheinlichkeit  $ \ = \ $ { 1 1% } &nbsp; bei $\rm Root$
  
  
Zeile 72: Zeile 87:
 
{Welche Binärcodes (darzustellen mit Nullen und Einsen) ergeben sich für
 
{Welche Binärcodes (darzustellen mit Nullen und Einsen) ergeben sich für
 
|type="{}"}
 
|type="{}"}
Binärcode  $ \ = \ $ { 11101 } &nbsp; &rArr; &nbsp; Symbol '''A'''
+
Binärcode  $ \ = \ $ { 11101 } &nbsp; &rArr; &nbsp; Symbol $\rm A$
Binärcode  $ \ = \ $ { 1111 } &nbsp; &rArr; &nbsp; Symbol '''B'''
+
Binärcode  $ \ = \ $ { 1111 } &nbsp; &rArr; &nbsp; Symbol $\rm B$
Binärcode  $ \ = \ $ { 110 } &nbsp; &rArr; &nbsp; Symbol '''C'''
+
Binärcode  $ \ = \ $ { 110 } &nbsp; &rArr; &nbsp; Symbol $\rm C$
Binärcode  $ \ = \ $ { 10 } &nbsp; &rArr; &nbsp; Symbol '''D'''
+
Binärcode  $ \ = \ $ { 10 } &nbsp; &rArr; &nbsp; Symbol $\rm D$
  
  
 
{Wie groß ist die mittlere Codewortlänge?
 
{Wie groß ist die mittlere Codewortlänge?
 
|type="{}"}
 
|type="{}"}
$L_{\rm M} \ = $  { 2.73 3% } $\ \rm bit/Quellensymbol$
+
$L_{\rm M} \ = \ $  { 2.73 3% } $\ \rm bit/Quellensymbol$
  
  
{Wie groß ist die Quellenentropie $H$? <i>Hinweis:</i> Es gibt genau eine Lösung.
+
{Wie groß ist die Quellenentropie&nbsp; $H$?  
|type="[]"}
+
|type="()"}
 
+ $H = 2.71\ \rm  bit/Quellensymbol.$
 
+ $H = 2.71\ \rm  bit/Quellensymbol.$
 
- $H = 2.75\ \rm  bit/Quellensymbol.$
 
- $H = 2.75\ \rm  bit/Quellensymbol.$
Zeile 95: Zeile 110:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Vor dem Huffman&ndash;Algorithmus müssen die Symbole nach ihren Auftrittswahrscheinlichkeiten sortiert werden. Da die zwei unwahrscheinlichsten Symbole schon im ersten Schritt zusammengefasst werden, nehmen die Auftrittswahrscheinlichkeiten von oben nach unten ab (in der unteren Grafik zu dieser Musterlösung von links nach rechts). Durch Vergleich mit dem Angabenblatt erhält man:
+
'''(1)'''&nbsp; Vor dem Huffman&ndash;Algorithmus müssen die Symbole nach ihren Auftrittswahrscheinlichkeiten sortiert werden.  
 +
*Da die zwei unwahrscheinlichsten Symbole schon im ersten Schritt zusammengefasst werden, nehmen die Auftrittswahrscheinlichkeiten von oben nach unten ab <br>(in der Grafik zu dieser Musterlösung von links nach rechts).  
 +
*Durch Vergleich mit dem Angabenblatt erhält man:
 +
 
 +
:Symbol $\rm A$:&nbsp;  <u>Eingang 7</u>,  &nbsp; &nbsp; Symbol $\rm B$:&nbsp;  <u>Eingang 6</u>, &nbsp; &nbsp; Symbol $\rm C$:&nbsp;  <u>Eingang 3</u>, &nbsp; &nbsp; Symbol $\rm D$:&nbsp;  <u>Eingang 1</u>.
  
:Symbol <b>A</B>:  <u>Eingang 7</u>,  &nbsp; &nbsp; Symbol <b>B</B>:  <u>Eingang 6</u>, &nbsp; &nbsp; Symbol <b>C</B>:  <u>Eingang 3</u>, &nbsp; &nbsp; Symbol <b>D</B>:  <u>Eingang 1</u>.
+
[[Datei:P_ID2452__Inf_A_2_6a.png|right|right|frame|An die Aufgabe angepasstes Baumdiagramm]]
  
  
[[Datei:P_ID2452__Inf_A_2_6a.png|right|An die Aufgabe angepasstes Baumdiagramm]]
 
'''(2)'''&nbsp; Der Knoten '''R''' ist die Baumwurzel (<i>Root</i>). Dieser ist stets mit <u><i>R</i> = 1</u> belegt, unabhängig von den Auftrittswahrscheinlichkeiten.
 
  
Für die weiteren Werte gilt:
 
  
:Schritt 1:&nbsp;&nbsp;&nbsp; <i>U</i> = <i>p</i><sub>A</sub> + <i>p</i><sub>H</sub> = 0.04 + 0.03 = <u>0.07</u>,
+
'''(2)'''&nbsp; Der Knoten&nbsp; $\rm R$&nbsp; ist die Baumwurzel&nbsp; (<i>Root</i>).&nbsp; Dieser ist stets mit&nbsp; $\underline{R=1}$&nbsp; belegt, unabhängig von den Auftrittswahrscheinlichkeiten.  
  
:Schritt 2:&nbsp;&nbsp;&nbsp; <i>V</i> = <i>U</i> + <i>p</i><sub>B</sub> = 0.07 + 0.08 = <u>0.15</u>,
+
Für die weiteren Werte gilt:
  
:Schritt 3:&nbsp;&nbsp;&nbsp; <i>W</i> = <i>p</i><sub>F</sub> + <i>p</i><sub>G</sub> = 0.12 + 0.10 = <u>0.22</u>,
+
:Schritt 1:&nbsp;&nbsp;&nbsp; $p_{\rm U} = p_{\rm A} + p_{\rm H} = 0.04 + 0.03 \hspace{0.15cm}\underline{ =0.07}$,
  
:Schritt 4:&nbsp;&nbsp;&nbsp; <i>X</i> = <i>V</i> + <i>p</i><sub>C</sub> = 0.15 + 0.14 = 0.29,
+
:Schritt 2:&nbsp;&nbsp;&nbsp; $p_{\rm V} = p_{\rm U} + p_{\rm B} = 0.07 + 0.08 \hspace{0.15cm}\underline{ =0.15}$,
  
:Schritt 5:&nbsp;&nbsp;&nbsp; <i>Y</i> = <i>W</i> + <i>p</i><sub>E</sub> = 0.22 + 0.24 = 0.46,
+
:Schritt 3:&nbsp;&nbsp;&nbsp; $p_{\rm W} = p_{\rm F} + p_{\rm G} = 0.12 + 0.10 \hspace{0.15cm}\underline{ =0.22}$,
  
:Schritt 6:&nbsp;&nbsp;&nbsp; <i>Z</i> = <i>X</i> + <i>p</i><sub>D</sub> = 0.29 + 0.25 = <u>0.54</u>.
+
:Schritt 4:&nbsp;&nbsp;&nbsp; $p_{\rm X} = p_{\rm V} + p_{\rm C} = 0.15 + 0.14  \hspace{0.15cm}\underline{ =0.29}$,
  
Damit ergibt sich das hier dargestelle Baumdiagramm.
+
:Schritt 5:&nbsp;&nbsp;&nbsp; $p_{\rm Y} = p_{\rm W} + p_{\rm E} = 0.22 + 0.24  \hspace{0.15cm}\underline{ =0.46}$,
  
 +
:Schritt 6:&nbsp;&nbsp;&nbsp; $p_{\rm Z} = p_{\rm X} + p_{\rm D} = 0.29 + 0.25  \hspace{0.15cm}\underline{ =0.54}$.
 +
<br clear=all>
 +
'''(3)'''&nbsp; Den Huffman&ndash;Code für das Symbol&nbsp; $\rm A$&nbsp; erhält man, wenn man den Weg von der&nbsp; $\rm Root$&nbsp; (gelber Punkt) zum Symbol&nbsp; $\rm A$&nbsp; zurückverfolgt und jeder roten Verbindungslinie eine&nbsp; <b>1</b>&nbsp; zuordnet, jeder blauen eine&nbsp; <b>0</b>.
  
'''(3)'''&nbsp; Den Huffman&ndash;Code für das Symbol <b>A</b> erhält man, wenn man den Weg von der <i>Root</i> (gelber Punkt) zum Symbol <b>A</b> zurückverfolgt und jeder roten Verbindungslinie eine &bdquo;<b>1</b>&rdquo; zuordnet, jeder blauen eine &bdquo;<b>0</b>&rdquo;.
+
* Symbol $\rm A$:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;rot&ndash;blau&ndash;rot &#8594; <b><u>11101</u></b>,
  
* Symbol <b>A</b>:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;rot&ndash;blau&ndash;rot &#8594; <b><u>11101</u></b>,
+
* Symbol $\rm B$:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;rot&ndash;rot &#8594; <b><u>1111</u></b>,
  
* Symbol <b>B</b>:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;rot&ndash;rot &#8594; <b><u>1111</u></b>,
+
* Symbol $\rm C$:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;blau &#8594; <b><u>110</u></b>,
  
* Symbol <b>C</b>:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;blau &#8594; <b><u>110</u></b>,
+
* Symbol $\rm D$:&nbsp;&nbsp;&nbsp; rot&ndash;blau&ndash; &#8594; <b><u>10</u></b>,
  
* Symbol <b>D</b>:&nbsp;&nbsp;&nbsp; rot&ndash;blau&ndash; &#8594; <b><u>10</u></b>,
+
* Symbol $\rm E$:&nbsp;&nbsp;&nbsp; blau&ndash;rot &#8594; <b>01</b>,
  
* Symbol <b>E</b>:&nbsp;&nbsp;&nbsp; blau&ndash;rot &#8594; <b>01</b>,
+
* Symbol $\rm F$:&nbsp;&nbsp;&nbsp; blau&ndash;blau&ndash;rot &#8594; <b>001</b>,
  
* Symbol <b>F</b>:&nbsp;&nbsp;&nbsp; blau&ndash;blau&ndash;rot &#8594; <b>001</b>,
+
* Symbol $\rm G$:&nbsp;&nbsp;&nbsp; blau&ndash;blau&ndash;blau &#8594; <b>000</b>,
  
* Symbol <b>G</b>:&nbsp;&nbsp;&nbsp; blau&ndash;blau&ndash;blau &#8594; <b>000</b>,
+
* Symbol $\rm H$:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;rot&ndash;blau&ndash;blau &#8594; <b>11100</b>.
  
* Symbol <b>H</b>:&nbsp;&nbsp;&nbsp; rot&ndash;rot&ndash;rot&ndash;blau&ndash;blau &#8594; <b>11100</b>.
 
  
 +
'''(4)'''&nbsp; Die Codierung unter Punkt&nbsp; '''(3)'''&nbsp; hat ergeben, dass
  
'''(4)'''&nbsp; Die Codierung unter Punkt (3) hat ergeben, dass
+
* die Symbole&nbsp; $\rm D$&nbsp; und&nbsp; $\rm E$&nbsp; mit zwei Bit,
  
* die Symbole <b>D</b> und <b>E</b> mit zwei Bit,
+
* die Symbole&nbsp; $\rm C$,&nbsp; $\rm F$&nbsp; und&nbsp; $\rm G$&nbsp; mit drei Bit,
  
* die Symbole <b>C</b>, <b>F</b> und <b>G</b> mit drei Bit,
+
* das Symbol&nbsp; $\rm B$&nbsp;  mit vier Bit,&nbsp; und
  
* das Symbol <b>B</b>  mit vier Bit, und
+
* die Symbole&nbsp; $\rm A$&nbsp; und&nbsp; $\rm H$&nbsp; jeweils mit fünf Bit
  
* die Symbole <b>A</b> und <b>H</b> jeweils mit fünf Bit
 
  
dargestellt werden. Damit erhält man für die mittlere Codewortlänge (in &bdquo;bit/Quellensymbol&dquo;):
+
dargestellt werden.&nbsp; Damit erhält man für die mittlere Codewortlänge (in &bdquo;bit/Quellensymbol&rdquo;):
 
:$$L_{\rm M} \hspace{0.2cm} =  \hspace{0.2cm}  (p_{\rm D} + p_{\rm E}) \cdot 2 + (p_{\rm C} + p_{\rm F} + p_{\rm G}) \cdot 3  + p_{\rm B} \cdot 4 +(p_{\rm A} + p_{\rm H}) \cdot 5 =  0.49 \cdot 2 + 0.36 \cdot 3 +0.08 \cdot 4 +0.07 \cdot 5  
 
:$$L_{\rm M} \hspace{0.2cm} =  \hspace{0.2cm}  (p_{\rm D} + p_{\rm E}) \cdot 2 + (p_{\rm C} + p_{\rm F} + p_{\rm G}) \cdot 3  + p_{\rm B} \cdot 4 +(p_{\rm A} + p_{\rm H}) \cdot 5 =  0.49 \cdot 2 + 0.36 \cdot 3 +0.08 \cdot 4 +0.07 \cdot 5  
 
\hspace{0.15cm}\underline{= 2.73}\hspace{0.05cm}.$$
 
\hspace{0.15cm}\underline{= 2.73}\hspace{0.05cm}.$$
  
  
'''(5)'''&nbsp; Richtig ist allein <u>Antwort 1</u>:
+
 
*Die mittlere Codewortlänge <i>L</i><sub>M</sub> kann nicht kleiner sein als die Quellenentropie <i>H</i>. Damit scheiden die Antworten 2 und 3 aus.
+
'''(5)'''&nbsp; Richtig ist allein die <u>Antwort 1</u>:
*Aus den vorgegebenen Auftrittswahrscheinlichkeiten kann  die Quellenentropie zu <i>H</i> = 2.71 bit/Quellensymbol berechnet werden.  
+
*Die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; kann nicht kleiner sein als die Quellenentropie&nbsp; $H$.&nbsp; Damit scheiden die Antworten 2 und 3 aus.
*Man erkennt, dass die vorliegende Huffman&ndash;Codierung die durch das Quellencodierungstheorem vorgegebene Grenze <i>L</i><sub>M, min</sub> = <i>H</i> = 2.71 bit/Quellensymbol nahezu erreicht.
+
*Aus den vorgegebenen Auftrittswahrscheinlichkeiten kann  die Quellenentropie tatsächlich  zu&nbsp; $H = 2.71$ bit/Quellensymbol berechnet werden.  
 +
*Man erkennt, dass diese Huffman&ndash;Codierung die vorgegebene Grenze&nbsp; (Quellencodierungstheorem)&nbsp; $L_{\rm M, \ min } \ge H = 2.71$&nbsp; bit/Quellensymbol nahezu erreicht.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 10. August 2021, 15:11 Uhr

Huffman–Baumdiagramm

Wir betrachten hier eine Quellensymbolfolge  $\langle q_\nu \rangle$  mit dem Symbolumfang  $M = 8$:

$$q_{\nu} \in \{ \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}.$$

Sind die Symbole gleichwahrscheinlich,  gilt also  $p_{\rm A} = p_{\rm B} =$ ... $ = p_{\rm H} = 1/M$,  so macht Quellencodierung keinen Sinn.  Bereits mit dem Dualcode  $\rm A$  →  000,  $\rm B$  →  001, ... ,  $\rm H$  →  111, erreicht nämlich dann die mittlere Codewortlänge  $L_{\rm M}$  ihre untere Schranke  $H$  gemäß dem Quellencodierungstheorem  $(H$ bezeichnet hierbei die Quellenentropie$)$:

$$L_{\rm M,\hspace{0.08cm}min} = H = 3 \hspace{0.15cm}{\rm bit/Quellensymbol} \hspace{0.05cm}.$$

Die Symbolwahrscheinlichkeiten seien aber in dieser Aufgabe wie folgt gegeben:

$$p_{\rm A} \hspace{-0.05cm}= \hspace{-0.05cm} 0.04 \hspace{0.05cm},\hspace{0.1cm}p_{\rm B} \hspace{-0.05cm}= \hspace{-0.05cm} 0.08 \hspace{0.05cm},\hspace{0.1cm}p_{\rm C} \hspace{-0.05cm}= \hspace{-0.05cm} 0.14 \hspace{0.05cm},\hspace{0.1cm} p_{\rm D} \hspace{-0.05cm}= \hspace{-0.05cm} 0.25 \hspace{0.05cm},\hspace{0.1cm} p_{\rm E} \hspace{-0.05cm}= \hspace{-0.05cm} 0.24 \hspace{0.05cm},\hspace{0.1cm}p_{\rm F} \hspace{-0.05cm}= \hspace{-0.05cm} 0.12 \hspace{0.05cm},\hspace{0.1cm}p_{\rm G} \hspace{-0.05cm}= \hspace{-0.05cm} 0.10 \hspace{0.05cm},\hspace{0.1cm} p_{\rm H} \hspace{-0.05cm}= \hspace{-0.05cm} 0.03 \hspace{0.05cm}.$$
  • Es liegt hier also eine redundante Nachrichtenquelle vor, die man durch Huffman–Codierung komprimieren kann.
  • Dieser Algorithmus wurde 1952 – also kurz nach Shannons bahnbrechenden Arbeiten zur Informationstheorie – von  David Albert Huffman  veröffentlicht und erlaubt die Konstruktion von optimalen präfixfreien Codes.


Der Algorithmus soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns auf Binärcodes beschränken   ⇒   die Codesymbolfolge besteht nur aus Nullen und Einsen:

(1)   Man ordne die Symbole nach fallenden Auftrittswahrscheinlichkeiten.
(2)   Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen.
(3)   Man wiederhole Schritt  (1)  und  (2), bis nur zwei (zusammengefasste) Symbole übrig bleiben.
(4)   Die wahrscheinlichere Symbolmenge wird mit  1  binär codiert, die andere Menge mit  0.
(5)   Man ergänze schrittweise (von unten nach oben) die aufgespaltenen Teilcodes mit  1  bzw.  0.


Oft wird dieser Algorithmus durch ein Baumdiagramm veranschaulicht. Die Grafik zeigt dieses für den vorliegenden Fall.

Sie haben folgende Aufgaben:

(a)   Zuordnung der Symbole  $\rm A$, ... , $\rm H$  zu den mit  [1], ... , [8]  bezeichneten Eingängen.
(b)   Bestimmung der Summenwahrscheinlichkeiten  $U$, ... ,  $Z$  sowie  $R$  („Root”).
(c)   Zuordnung der Symbole  $\rm A$, ... ,  $\rm H$  zu den entsprechenden Huffman–Binärfolgen. Eine rote Verbindung entspricht einer  1, eine blaue Verbindung einer  0.

Sie werden feststellen, dass die mittlere Codewortlänge

$$L_{\rm M} = \sum_{\mu = 1}^{M}\hspace{0.05cm} p_{\mu} \cdot L_{\mu} $$

bei Huffman–Codierung nur unwesentlich größer ist als die Quellenentropie  $H$.  In dieser Gleichung gelten für den vorliegenden Fall folgende Werte:

  • $M = 8$,  $p_1 = p_{\rm A}$,  ... ,  $p_8 = p_{\rm H}$.
  • Die jeweilige Bitanzahl der Codesymbole für  $\rm A$, ... ,  $\rm H$  ist mit  $L_1$, ... ,  $L_8$  bezeichnet.




Hinweise:


Fragebogen

1

Welche Eingänge im Baumdiagramm stehen für

Eingangsnummer $ \ = \ $

  ⇒   Symbol $\rm A$
Eingangsnummer $ \ = \ $

  ⇒   Symbol $\rm B$
Eingangsnummer $ \ = \ $

  ⇒   Symbol $\rm C$
Eingangsnummer $ \ = \ $

  ⇒   Symbol $\rm D$

2

Welche Zahlenwerte (Wahrscheinlichkeiten) sollten bei den Knoten im Baumdiagramm stehen?

Wahrscheinlichkeit $ \ = \ $

  bei Knoten $\rm U$
Wahrscheinlichkeit $ \ = \ $

  bei Knoten $\rm V$
Wahrscheinlichkeit $ \ = \ $

  bei Knoten $\rm W$
Wahrscheinlichkeit $ \ = \ $

  bei Knoten $\rm X$
Wahrscheinlichkeit $ \ = \ $

  bei Knoten $\rm Y$
Wahrscheinlichkeit $ \ = \ $

  bei Knoten $\rm Z$
Wahrscheinlichkeit $ \ = \ $

  bei $\rm Root$

3

Welche Binärcodes (darzustellen mit Nullen und Einsen) ergeben sich für

Binärcode $ \ = \ $

  ⇒   Symbol $\rm A$
Binärcode $ \ = \ $

  ⇒   Symbol $\rm B$
Binärcode $ \ = \ $

  ⇒   Symbol $\rm C$
Binärcode $ \ = \ $

  ⇒   Symbol $\rm D$

4

Wie groß ist die mittlere Codewortlänge?

$L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

5

Wie groß ist die Quellenentropie  $H$?

$H = 2.71\ \rm bit/Quellensymbol.$
$H = 2.75\ \rm bit/Quellensymbol.$
$H = 3.00\ \rm bit/Quellensymbol.$


Musterlösung

(1)  Vor dem Huffman–Algorithmus müssen die Symbole nach ihren Auftrittswahrscheinlichkeiten sortiert werden.

  • Da die zwei unwahrscheinlichsten Symbole schon im ersten Schritt zusammengefasst werden, nehmen die Auftrittswahrscheinlichkeiten von oben nach unten ab
    (in der Grafik zu dieser Musterlösung von links nach rechts).
  • Durch Vergleich mit dem Angabenblatt erhält man:
Symbol $\rm A$:  Eingang 7,     Symbol $\rm B$:  Eingang 6,     Symbol $\rm C$:  Eingang 3,     Symbol $\rm D$:  Eingang 1.
An die Aufgabe angepasstes Baumdiagramm



(2)  Der Knoten  $\rm R$  ist die Baumwurzel  (Root).  Dieser ist stets mit  $\underline{R=1}$  belegt, unabhängig von den Auftrittswahrscheinlichkeiten.

Für die weiteren Werte gilt:

Schritt 1:    $p_{\rm U} = p_{\rm A} + p_{\rm H} = 0.04 + 0.03 \hspace{0.15cm}\underline{ =0.07}$,
Schritt 2:    $p_{\rm V} = p_{\rm U} + p_{\rm B} = 0.07 + 0.08 \hspace{0.15cm}\underline{ =0.15}$,
Schritt 3:    $p_{\rm W} = p_{\rm F} + p_{\rm G} = 0.12 + 0.10 \hspace{0.15cm}\underline{ =0.22}$,
Schritt 4:    $p_{\rm X} = p_{\rm V} + p_{\rm C} = 0.15 + 0.14 \hspace{0.15cm}\underline{ =0.29}$,
Schritt 5:    $p_{\rm Y} = p_{\rm W} + p_{\rm E} = 0.22 + 0.24 \hspace{0.15cm}\underline{ =0.46}$,
Schritt 6:    $p_{\rm Z} = p_{\rm X} + p_{\rm D} = 0.29 + 0.25 \hspace{0.15cm}\underline{ =0.54}$.


(3)  Den Huffman–Code für das Symbol  $\rm A$  erhält man, wenn man den Weg von der  $\rm Root$  (gelber Punkt) zum Symbol  $\rm A$  zurückverfolgt und jeder roten Verbindungslinie eine  1  zuordnet, jeder blauen eine  0.

  • Symbol $\rm A$:    rot–rot–rot–blau–rot → 11101,
  • Symbol $\rm B$:    rot–rot–rot–rot → 1111,
  • Symbol $\rm C$:    rot–rot–blau → 110,
  • Symbol $\rm D$:    rot–blau– → 10,
  • Symbol $\rm E$:    blau–rot → 01,
  • Symbol $\rm F$:    blau–blau–rot → 001,
  • Symbol $\rm G$:    blau–blau–blau → 000,
  • Symbol $\rm H$:    rot–rot–rot–blau–blau → 11100.


(4)  Die Codierung unter Punkt  (3)  hat ergeben, dass

  • die Symbole  $\rm D$  und  $\rm E$  mit zwei Bit,
  • die Symbole  $\rm C$,  $\rm F$  und  $\rm G$  mit drei Bit,
  • das Symbol  $\rm B$  mit vier Bit,  und
  • die Symbole  $\rm A$  und  $\rm H$  jeweils mit fünf Bit


dargestellt werden.  Damit erhält man für die mittlere Codewortlänge (in „bit/Quellensymbol”):

$$L_{\rm M} \hspace{0.2cm} = \hspace{0.2cm} (p_{\rm D} + p_{\rm E}) \cdot 2 + (p_{\rm C} + p_{\rm F} + p_{\rm G}) \cdot 3 + p_{\rm B} \cdot 4 +(p_{\rm A} + p_{\rm H}) \cdot 5 = 0.49 \cdot 2 + 0.36 \cdot 3 +0.08 \cdot 4 +0.07 \cdot 5 \hspace{0.15cm}\underline{= 2.73}\hspace{0.05cm}.$$


(5)  Richtig ist allein die Antwort 1:

  • Die mittlere Codewortlänge  $L_{\rm M}$  kann nicht kleiner sein als die Quellenentropie  $H$.  Damit scheiden die Antworten 2 und 3 aus.
  • Aus den vorgegebenen Auftrittswahrscheinlichkeiten kann die Quellenentropie tatsächlich zu  $H = 2.71$ bit/Quellensymbol berechnet werden.
  • Man erkennt, dass diese Huffman–Codierung die vorgegebene Grenze  (Quellencodierungstheorem)  $L_{\rm M, \ min } \ge H = 2.71$  bit/Quellensymbol nahezu erreicht.