Aufgaben:Aufgabe 2.7: Huffman-Anwendung für binäre Zweiertupel: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(5 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2455__Inf_A_2_7.png|right|frame|Beispielhafte Binärcodes für $M = 4$]]
+
[[Datei:P_ID2455__Inf_A_2_7.png|right|frame|Drei Binärcodes für  $M = 4$]]
Die Anwendung des Huffman–Algorithmus in seiner ursprünglichen Form setzt einen Symbolumfang $M > 2$ voraus und ist deshalb zur Datenkomprimierung von Binärquellen unbrauchbar.
+
Die Anwendung des Huffman–Algorithmus in seiner ursprünglichen Form setzt einen Symbolumfang  $M > 2$  voraus und ist deshalb zur Datenkomprimierung von Binärquellen unbrauchbar.
  
 
Fasst man aber mehrere aufeinanderfolgende Binärzeichen der Nachrichtenquelle zu einem neuen Symbol zusammen, so kann man auf die neue Symbolmenge die Huffman–Datenkomprimierung sinnvoll anwenden.
 
Fasst man aber mehrere aufeinanderfolgende Binärzeichen der Nachrichtenquelle zu einem neuen Symbol zusammen, so kann man auf die neue Symbolmenge die Huffman–Datenkomprimierung sinnvoll anwenden.
  
Wir gehen in dieser Aufgabe von der Symbolmenge $\{$ $\rm X$, $\rm Y$ $\}$   ⇒  aus  $M = 2$ und bilden gemäß der obigen Tabelle Zweiertupel mit dem Symbolvorrat $\{$ $\rm A$, $\rm B$, $\rm C$, $\rm D$ $\}$  ⇒  $M\hspace{-0.01cm}' = M^2 = 4$. Beispielsweise wird somit aus der binären Quellensymbolfolge $\rm XYXXYXXXYY$ die quaternäre Folge  $\rm BACAD$.
+
Wir gehen in dieser Aufgabe von der Symbolmenge  $\{$ $\rm X$,  $\rm Y$ $\}$   ⇒  aus  $(M = 2)$  und bilden gemäß obiger Tabelle Zweiertupel mit dem Symbolvorrat  $\{$ $\rm A$,  $\rm B$,  $\rm C$,  $\rm D$ $\}$  ⇒  $(M\hspace{0.03cm}' = M^2 = 4)$. 
 +
 
 +
Beispielsweise wird somit aus der binären Quellensymbolfolge  $\rm XYXXYXXXYY$  die quaternäre Folge  $\rm BACAD$.
  
 
Desweiteren sind in obiger Tabelle drei Codes angegeben, von denen manche durch den Huffman–Algorithmus entstanden sind. Die binären Ausgangsfolgen ergeben sich dann für unser Beispiel wie folgt:
 
Desweiteren sind in obiger Tabelle drei Codes angegeben, von denen manche durch den Huffman–Algorithmus entstanden sind. Die binären Ausgangsfolgen ergeben sich dann für unser Beispiel wie folgt:
Zeile 18: Zeile 20:
  
 
Nochmals zum Verständnis:  
 
Nochmals zum Verständnis:  
*Aus der ursprünglichen Symbolmenge $\{$ $\rm X$, $\rm Y$ $\}$ erhält man durch Bildung von Zweiertupeln eine Quaternärmenge mit  Symbolvorrat $\{$ $\rm A$, $\rm B$, $\rm C$, $\rm D$ $\}$. Die Folgenlänge $N$ wird dadurch auf $N\hspace{-0.01cm}' = N/2 $ halbiert.  
+
*Aus der ursprünglichen Symbolmenge  $\{$ $\rm X$,  $\rm Y$ $\}$  erhält man durch Bildung von Zweiertupeln eine Quaternärmenge mit  Symbolvorrat  $\{$ $\rm A$,  $\rm B$,  $\rm C$,  $\rm D$ $\}$. 
*Durch Huffman&ndash;Codierung ergibt sich wieder eine Binärfolge, deren Symbolmenge zur besseren Unterscheidung mit $\{$<b>0</b>,&nbsp;<b>1</b>$\}$ bezeichnet wird.  
+
*Die Folgenlänge $N$ wird dadurch auf&nbsp; $N\hspace{0.03cm}' = N/2 $&nbsp; halbiert.  
*Die Anwendung der Huffman&ndash;Codierung macht genau dann Sinn, wenn die Länge $L$ der Ausgangsfolge (im statistischen Mittel) kleiner ist als $N$.
+
*Durch Huffman&ndash;Codierung ergibt sich wieder eine Binärfolge, deren Symbolmenge zur besseren Unterscheidung mit&nbsp; $\{$<b>0</b>,&nbsp; <b>1</b>$\}$&nbsp; bezeichnet wird.  
 +
*Die Anwendung der Huffman&ndash;Codierung macht genau dann Sinn, wenn die Länge&nbsp; $L$&nbsp; der Ausgangsfolge (im statistischen Mittel) kleiner ist als&nbsp; $N$.
  
  
 
Mit dieser Aufgabe soll geklärt werden, welche der vorgegebenen Binärcodes bei welchen Randbedingungen sinnvoll sind.  
 
Mit dieser Aufgabe soll geklärt werden, welche der vorgegebenen Binärcodes bei welchen Randbedingungen sinnvoll sind.  
*Die binäre Nachrichtenquelle $\{$ $\rm X$, $\rm Y$ $\}$ sei gedächtnislos und wird allein durch die Symbolwahrscheinlichkeit $p_{\rm X}$ beschrieben.  
+
*Die binäre Nachrichtenquelle&nbsp; $\{$ $\rm X$,&nbsp; $\rm Y$ $\}$&nbsp; sei gedächtnislos und wird allein durch die Symbolwahrscheinlichkeit&nbsp; $p_{\rm X}$&nbsp; beschrieben.  
*Die zweite Wahrscheinlichkeit ist dann stets $p_{\rm Y} = 1 - p_{\rm X}$.
+
*Die zweite Wahrscheinlichkeit ist dann stets&nbsp; $p_{\rm Y} = 1 - p_{\rm X}$.
 +
 
 +
 
 +
 
  
  
Zeile 32: Zeile 38:
  
 
''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 auf die Seite [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_k.E2.80.93Tupel|Anwendung der Huffman-Codierung auf k-Tupel]]  Bezug genommen.
+
*Insbesondere wird auf die Seite&nbsp; [[Informationstheorie/Entropiecodierung_nach_Huffman#Anwendung_der_Huffman.E2.80.93Codierung_auf_.7F.27.22.60UNIQ-MathJax164-QINU.60.22.27.7F.E2.80.93Tupel|Anwendung der Huffman-Codierung auf&nbsp; $k$-Tupel]]&nbsp; Bezug genommen.
*Die mittlere Codewortlänge pro Zweiertupel ist  $L_{\rm M}' = p_{\rm A} \cdot L_{\rm A} +$ ... $ + p_{\rm D} \cdot L_{\rm D} \hspace{0.05cm}$. Bezogen auf ein Quellensymbol gilt $L_{\rm M} = L_{\rm M}'/2$.
+
*Die mittlere Codewortlänge pro Zweiertupel ist&nbsp; $L_{\rm M}\hspace{0.03cm}' = p_{\rm A} \cdot L_{\rm A} +$&nbsp; ... &nbsp;$ + p_{\rm D} \cdot L_{\rm D} \hspace{0.05cm}$.&nbsp; Bezogen auf ein Quellensymbol gilt&nbsp; $L_{\rm M} = L_{\rm M}\hspace{0.03cm}'/2$.
*Eine vergleichbare Aufgabenstellung mit ternären Eingangssymbolen wird in der  [[Aufgaben:2.7Z_Huffman-Codierung_für_Zweiertupel_einer_Ternärquelle|Zusatzaufgabe 2.7Z]] behandelt.
+
*Eine vergleichbare Aufgabenstellung mit ternären Eingangssymbolen wird in der&nbsp;   [[Aufgaben:2.7Z_Huffman-Codierung_für_Zweiertupel_einer_Ternärquelle|Aufgabe 2.7Z]]&nbsp; behandelt.
 
   
 
   
*Die Idee zu dieser Aufgabe entstand bei einem Vortrag von [http://www.uni-ulm.de/nt/staff/professors/fischer/ Prof. Robert Fischer] von der Universität Ulm an der TU München zum Thema &bdquo;Der goldene Schnitt in der Nachrichtentechnik&rdquo;.
+
*Die Idee zu dieser Aufgabe entstand bei einem Vortrag von&nbsp; [http://www.uni-ulm.de/nt/staff/professors/fischer/ Prof. Robert Fischer]&nbsp; von der Universität Ulm an der TU München zum Thema &bdquo;Der goldene Schnitt in der Nachrichtentechnik&rdquo;.
 +
 
 +
 
  
  
Zeile 45: Zeile 53:
 
{Geben Sie die Codewortlängen bei redundanzfreier Binärquelle an.
 
{Geben Sie die Codewortlängen bei redundanzfreier Binärquelle an.
 
|type="{}"}
 
|type="{}"}
Code 1:  &nbsp; $L_{\rm M} \ = \ $ { 1 1% } $\ \rm bit/Quellensymbol$
+
$\text{Code 1}$:  &nbsp; $L_{\rm M} \ = \ $ { 1 1% } $\ \rm bit/Quellensymbol$
Code 2:  &nbsp; $L_{\rm M} \ = \ $ { 1.125 1% } $\ \rm bit/Quellensymbol$
+
$\text{Code 2}$:  &nbsp; $L_{\rm M} \ = \ $ { 1.125 1% } $\ \rm bit/Quellensymbol$
Code 3:  &nbsp; $L_{\rm M} \ = \ $ { 1.25 1% } $\ \rm bit/Quellensymbol$
+
$\text{Code 3}$:  &nbsp; $L_{\rm M} \ = \ $ { 1.25 1% } $\ \rm bit/Quellensymbol$
  
  
  
{Ermitteln Sie den Huffman&ndash;Code hinsichtlich Zweiertupel für  $p_{\rm X}= 0.6$.
+
{Ermitteln Sie den Huffman&ndash;Code hinsichtlich Zweiertupel für  &nbsp;$p_{\rm X}= 0.6$.
 
|type="[]"}
 
|type="[]"}
+ Es ergibt sich Code 1.
+
+ Es ergibt sich&nbsp; $\text{Code 1}$.
- Es ergibt sich Code 2.
+
- Es ergibt sich&nbsp; $\text{Code 2}$.
- Es ergibt sich Code 3.
+
- Es ergibt sich&nbsp; $\text{Code 3}$.
  
  
{Wie groß ist die mittlere Codewortlänge des für $p_{\rm X}= 0.6$ besten Huffman&ndash;Codes?
+
{Wie groß ist die mittlere Codewortlänge des für &nbsp;$p_{\rm X}= 0.6$&nbsp; besten Huffman&ndash;Codes?
 
|type="{}"}
 
|type="{}"}
 
$L_{\rm M} \ = \ $ { 1 1% } $\ \rm bit/Quellensymbol$
 
$L_{\rm M} \ = \ $ { 1 1% } $\ \rm bit/Quellensymbol$
  
  
{Ermitteln Sie den Huffman&ndash;Code hinsichtlich Zweiertupel für $p_{\rm X}= 0.8$.
+
{Ermitteln Sie den Huffman&ndash;Code hinsichtlich Zweiertupel für &nbsp;$p_{\rm X}= 0.8$.
 
|type="[]"}
 
|type="[]"}
- Es ergibt sich Code 1.
+
- Es ergibt sich&nbsp; $\text{Code 1}$.
+ Es ergibt sich Code 2.
+
+ Es ergibt sich&nbsp; $\text{Code 2}$.
- Es ergibt sich Code 3.
+
- Es ergibt sich&nbsp; $\text{Code 3}$.
  
  
{Wie groß ist die mittlere Codewortlänge des für $p_{\rm X}= 0.8$ besten Huffman&ndash;Codes?
+
{Wie groß ist die mittlere Codewortlänge des für &nbsp;$p_{\rm X}= 0.8$&nbsp; besten Huffman&ndash;Codes?
 
|type="{}"}
 
|type="{}"}
 
$L_{\rm M} \ = \ $ { 0.78 1% } $\ \rm bit/Quellensymbol$
 
$L_{\rm M} \ = \ $ { 0.78 1% } $\ \rm bit/Quellensymbol$
  
  
{In welchem Bereich darf die Wahrscheinlichkeit $p_{\rm X}$ für das Symbol <b>X</b> liegen, damit sich nach Huffman der Code 1 ergibt?
+
{In welchem Bereich darf die Wahrscheinlichkeit &nbsp;$p_{\rm X}$&nbsp; für das Symbol&nbsp; $\rm X$&nbsp; liegen, damit sich nach Huffman der&nbsp; $\text{Code 1}$&nbsp; ergibt?
 
|type="{}"}
 
|type="{}"}
 
$p_\text{X, min}\ = \ $ { 0.382 1% }
 
$p_\text{X, min}\ = \ $ { 0.382 1% }
Zeile 86: Zeile 94:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Bei redundanzfreier Binärquelle (<i>p</i><sub>X</sub> = <i>p</i><sub>Y</sub> = 1/2) erhält man <i>p</i><sub>A</sub> = <i>p</i><sub>B</sub> = <i>p</i><sub>C</sub> = <i>p</i><sub>D</sub> = 1/4 und mit der angegebenen Gleichung:
+
'''(1)'''&nbsp; Bei redundanzfreier Binärquelle &nbsp;$(p_{\rm X} = p_{\rm Y} = 0.5)$&nbsp; erhält man &nbsp;$p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} = 0.25$&nbsp; und mit der angegebenen Gleichung:
 
:$$L_{\rm M} =  \big [ \hspace{0.05cm}p_{\rm A} \cdot L_{\rm A} + p_{\rm B} \cdot L_{\rm B} + p_{\rm C} \cdot L_{\rm C} + p_{\rm D} \cdot L_{\rm D} \hspace{0.05cm} \big ] / 2 = \big [ \hspace{0.05cm} L_{\rm A} +  L_{\rm B} +  L_{\rm C} +  L_{\rm D}\hspace{0.05cm} \big ] / 8  
 
:$$L_{\rm M} =  \big [ \hspace{0.05cm}p_{\rm A} \cdot L_{\rm A} + p_{\rm B} \cdot L_{\rm B} + p_{\rm C} \cdot L_{\rm C} + p_{\rm D} \cdot L_{\rm D} \hspace{0.05cm} \big ] / 2 = \big [ \hspace{0.05cm} L_{\rm A} +  L_{\rm B} +  L_{\rm C} +  L_{\rm D}\hspace{0.05cm} \big ] / 8  
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
 
Berücksichtigt man die angegebenen Zuordnungen, so erhält man für
 
Berücksichtigt man die angegebenen Zuordnungen, so erhält man für
* Code 1:&nbsp;&nbsp;&nbsp; <i>L</i><sub>M</sub> <u>= 1.000 bit/Quellensymbol</u>,
+
* $\text{Code 1}$:&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 1.000 \ {\rm bit/Quellensymbol} }$,
* Code 2:&nbsp;&nbsp;&nbsp; <i>L</i><sub>M</sub> <u>= 1.125 bit/Quellensymbol</u>,
+
* $\text{Code 2}$:&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 1.125 \ {\rm bit/Quellensymbol} }$,
* Code 3:&nbsp;&nbsp;&nbsp; <i>L</i><sub>M</sub> <u>= 1.250 bit/Quellensymbol</u>.
+
* $\text{Code 3}$:&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 1.250 \ {\rm bit/Quellensymbol} }$.
 +
 
 +
::Im Verlauf der Aufgabe wird sich zeigen, dass die beiden ersten Codes durchaus als Ergebnis des Huffman&ndash;Algorithmus möglich sind&nbsp; (natürlich nur bei geeigneten Symbolwahrscheinlichkeiten).&nbsp; Der&nbsp; $\text{Code 3}$&nbsp; ist zwar ebenfalls präfixfrei, aber hinsichtlich der mittleren Codewortlänge nie optimal.
  
  
Im Verlauf der Aufgabe wird sich zeigen, dass die beiden ersten Codes durchaus als Ergebnis des Huffman&ndash;Algorithmus möglich sind (natürlich nur bei geeigneten Symbolwahrscheinlichkeiten). Code 3 ist zwar ebenfalls präfixfrei, aber hinsichtlich der mittleren Codewortlänge nie optimal.
 
  
 
'''(2)'''&nbsp; Die Wahrscheinlichkeiten der möglichen Zweiertupel lauten:
 
'''(2)'''&nbsp; Die Wahrscheinlichkeiten der möglichen Zweiertupel lauten:
:$$p_{\rm A} = 0.6^2 = 0.36 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.6 \cdot 0.4 = 0.24 =  p_{\rm C} \hspace{0.05cm},\hspace{0.2cm}
+
:$$p_{\rm A} = 0.6^2 = 0.36 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm B}= 0.6 \cdot 0.4 = 0.24 =  p_{\rm C} \hspace{0.05cm},\hspace{0.4cm}
 
p_{\rm D}= 0.4^2 = 0.16 \hspace{0.05cm}.$$
 
p_{\rm D}= 0.4^2 = 0.16 \hspace{0.05cm}.$$
Damit ergibt sich das linke Baumdiagramm (siehe Grafik) und der folgende Huffman&ndash;Code:
+
*Damit ergibt sich das&nbsp; <u>linke Baumdiagramm</u>&nbsp; (in nebenstehender Grafik) und der folgende Huffman&ndash;Code:
 +
[[Datei:P_ID2456__Inf_A_2_7b.png|right|frame|Huffman–Baumdiagramm für zwei unterschiedliche Zweiertupel–Konstellationen]]
 +
:&nbsp;&nbsp;&nbsp; $\rm A$ &nbsp; &#8594; &nbsp; <b>11</b>,&nbsp;&nbsp; $\rm B$ &nbsp; &#8594; &nbsp; <b>10</b>,&nbsp;&nbsp; $\rm C$ &nbsp; &#8594; &nbsp; <b>01</b>,&nbsp;&nbsp; $\rm D$ &nbsp; &#8594; &nbsp; <b>00</b>.
 +
*Es handelt sich um den&nbsp; $\text{Code 1}$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <u>Lösungsvorschlag 1</u>.
  
:&nbsp;&nbsp;&nbsp; <b>A</b> &#8594; <b>11</b>,&nbsp;&nbsp; <b>B</b> &#8594; <b>10</b>,&nbsp;&nbsp; <b>C</b> &#8594; <b>01</b>,&nbsp;&nbsp; <b>D</b> &#8594; <b>00</b>.
 
  
Es handelt sich um den Code 1 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <u>Lösungsvorschlag 1</u>.
+
'''(3)'''&nbsp; Jedes Zweiertupel wird durch zwei Bit dargestellt.&nbsp; Damit ist
 +
:$$L_{\rm M} \hspace{0.15cm}\underline{= 1.000 \ {\rm bit/Quellensymbol} }.$$
  
[[Datei:P_ID2456__Inf_A_2_7b.png|Huffman–Baumdiagramm für zwei unterschiedliche Zweiertupel–Konstellationen]]
 
 
'''(3)'''&nbsp; Jedes Zweiertupel wird durch zwei Bit dargestellt. Damit ist <i>L</i><sub>M</sub> <u> = 1 bit/Quellensymbol</u>.
 
  
 
'''(4)'''&nbsp; Hier lauten die Wahrscheinlichkeiten der einzelnen Zweiertupel:
 
'''(4)'''&nbsp; Hier lauten die Wahrscheinlichkeiten der einzelnen Zweiertupel:
:$$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 A} = 0.8^2 = 0.64 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm B}= 0.8 \cdot 0.2 = 0.16 \hspace{0.05cm}, $$
 +
:$$p_{\rm C}  =  p_{\rm B}= 0.8 = 0.16 \hspace{0.05cm},\hspace{0.4cm}
 
p_{\rm D}= 0.2^2 = 0.04 \hspace{0.05cm}. $$
 
p_{\rm D}= 0.2^2 = 0.04 \hspace{0.05cm}. $$
Entsprechend dem rechten Baumdiagramm ergibt sich nun Code 2 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <u>Lösungsvorschlag 2</u>:
+
Entsprechend dem <u>rechten Baumdiagramm</u> ergibt sich nun der&nbsp; $\text{Code 2}$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <u>Lösungsvorschlag 2</u>:
 +
 
 +
:&nbsp;&nbsp;&nbsp; $\rm A$ &nbsp; &#8594; &nbsp; <b>1</b>,&nbsp;&nbsp; $\rm B$ &nbsp; &#8594; &nbsp; <b>01</b>,&nbsp;&nbsp; $\rm C$ &nbsp; &#8594; &nbsp; <b>001</b>,&nbsp;&nbsp; $\rm D$ &nbsp; &#8594; &nbsp; <b>010</b>.
 +
 
  
:&nbsp;&nbsp;&nbsp; <b>A</b> &#8594; <b>1</b>,&nbsp;&nbsp; <b>B</b> &#8594; <b>01</b>,&nbsp;&nbsp; <b>C</b> &#8594; <b>011</b>,&nbsp;&nbsp; <b>D</b> &#8594; <b>010</b>.
 
  
'''(5)'''&nbsp; Bei Code 2 gilt für die mittlere Zweiertupellänge bzw. die mittlere Codewortlänge:
+
'''(5)'''&nbsp; Beim&nbsp; $\text{Code 2}$&nbsp; gilt für die mittlere Zweiertupellänge bzw. die mittlere Codewortlänge:
:$$L_{\rm M}' = 0.64 \cdot 1 + 0.16 \cdot 2 + (0.16 + 0.04) \cdot 3 = 1.56\,{\rm bit/Zweiertupel}\hspace{0.3cm}
+
:$$L_{\rm M}\hspace{0.01cm}' = 0.64 \cdot 1 + 0.16 \cdot 2 + (0.16 + 0.04) \cdot 3 = 1.56\,{\rm bit/Zweiertupel}\hspace{0.3cm}
\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}'}/{2}\hspace{0.15cm}\underline{  = 0.78\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
+
\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{2}\hspace{0.15cm}\underline{  = 0.78\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$
 +
 
  
 
'''(6)'''&nbsp; Aus den früheren Teilaufgaben hat sich ergeben:
 
'''(6)'''&nbsp; Aus den früheren Teilaufgaben hat sich ergeben:
*Für <i>p</i><sub>X</sub> = 0.6 ist der Code 1 optimal und die mittlere Codewortlänge ist <i>L</i><sub>M</sub> = 1 bit/Quellensymbol (dieses Ergebnis ist unabhängig von <i>p</i><sub>X</sub>).
+
*Für &nbsp;$p_{\rm X} = 0.6$&nbsp; ist der&nbsp; $\text{Code 1}$&nbsp; optimal und die mittlere Codewortlänge dieses Codes ist&nbsp; $($unabhängig von &nbsp;$p_{\rm X})$&nbsp; $L_{\rm M} = 1$&nbsp; bit/Quellensymbol.  
*Für <i>p</i><sub>X</sub> = 0.8 entsprechend der Teilaufgabe (4) der Code 2 optimal und die mittlere Codewortlänge beträgt <i>L</i><sub>M</sub> = 0.78 bit/Quellensymbol.  
+
*Für &nbsp;$p_{\rm X} = 0.8$&nbsp; entsprechend der Teilaufgabe&nbsp; '''(4)'''&nbsp; ist der&nbsp; $\text{Code 2}$&nbsp; optimal und die mittlere Codewortlänge beträgt&nbsp; $L_{\rm M} = 0.78$&nbsp; bit/Quellensymbol.  
  
  
Der gesuchte Maximalwert <i>p</i><sub>X,&nbsp;max</sub> wird zwischen 0.6 und 0.8 liegen. Die Bestimmungsgleichung ist dabei, dass für den Grenzfall <i>p</i><sub>X</sub> = <i>p</i><sub>X,&nbsp;max</sub> beide Codes genau die gleiche mittlere Codewortlänge <i>L</i><sub>M</sub> = 1 bit/Quellensymbol besitzen, bzw. <i>L</i>&prime;<sub>M</sub> = 2 bit/Zweiertupel.
+
Der gesuchte Maximalwert &nbsp;$p_\text{X, max}$&nbsp; wird somit zwischen &nbsp;$0.6$&nbsp; und &nbsp;$0.8$&nbsp; liegen. &nbsp;Die Bestimmungsgleichung ist dabei, dass für den Grenzfall &nbsp;$p_\text{X} = p_\text{X, max}$&nbsp; beide Codes genau die gleiche mittlere Codewortlänge &nbsp;$L_{\rm M} = 1$&nbsp; bit/Quellensymbol besitzen, bzw. &nbsp;$L_{\rm M}\hspace{0.03cm}' = 2$&nbsp; bit/Zweiertupel.
  
Mit der Abkürzung <i>p</i> = <i>p</i><sub>X, max</sub> lautet die entsprechende Bestimmungsgleichung:
+
*Mit der Abkürzung &nbsp;$p = p_\text{X, max}$&nbsp; lautet die entsprechende Bestimmungsgleichung:
:$$L_{\rm M}'\hspace{0.15cm}{\rm (Code \hspace{0.15cm}2)} = p^2 \cdot 1 + p \cdot (1-p) \cdot 2 + p \cdot (1-p) \cdot 3
+
:$$L_{\rm M}\hspace{0.01cm}'\hspace{0.15cm}{\rm (Code \hspace{0.15cm}2)} = p^2 \cdot 1 + p \cdot (1-p) \cdot 2 + p \cdot (1-p) \cdot 3
 
+  (1-p)^2 \cdot 3 \stackrel{!}{=} 2 \hspace{0.05cm}.$$
 
+  (1-p)^2 \cdot 3 \stackrel{!}{=} 2 \hspace{0.05cm}.$$
Dies führt zum zahlenmäßigen Ergebnis:
+
*Dies führt zum zahlenmäßigen Ergebnis:
 
:$$p^2 + p - 1 \stackrel{!}{=} 0 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}
 
:$$p^2 + p - 1 \stackrel{!}{=} 0 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}
 
  p_{\rm X,\hspace{0.05cm}max} = p = \frac{\sqrt{5}-1}{2} \hspace{0.15cm}\underline{  \approx 0.618}  
 
  p_{\rm X,\hspace{0.05cm}max} = p = \frac{\sqrt{5}-1}{2} \hspace{0.15cm}\underline{  \approx 0.618}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
Da sich die grundsätzliche Huffman&ndash;Struktur durch Vertauschen von <b>X</b> und <b>Y</b> nicht ändert, gilt für die untere Grenze:
+
*Da sich die grundsätzliche Huffman&ndash;Struktur durch Vertauschen von &nbsp;$\rm X$&nbsp; und &nbsp;$\rm Y$&nbsp; nicht ändert, gilt für die untere Grenze:
 
:$$p_{\rm X,\hspace{0.05cm}min} = 1 -  p_{\rm X,\hspace{0.05cm}max}\hspace{0.15cm}\underline{  \approx 0.382}  
 
:$$p_{\rm X,\hspace{0.05cm}min} = 1 -  p_{\rm X,\hspace{0.05cm}max}\hspace{0.15cm}\underline{  \approx 0.382}  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
Die Darstellung der Zweiertupel durch unterschiedlich lange Bitfolgen (Code 2) macht also nur Sinn, wenn sich die Symbolwahrscheinlichkeiten von <b>X</b> und <b>Y</b> signifikant unterscheiden. Liegen diese dagegen zwischen 0.382 und 0.618,  so ist Code 1 anzuwenden.
 
  
Die Aufteilung einer Strecke der Länge 1 in zwei Abschnitte der Länge 0.618... und 0.382... bezeichnet man als [https://de.wikipedia.org/wiki/Goldener_Schnitt Goldenen Schnitt], auf den man in den verschiedensten Fachgebieten immer wieder stößt.
+
Die Darstellung der Zweiertupel durch unterschiedlich lange Bitfolgen&nbsp; $\text{(Code 2)}$&nbsp; macht also nur Sinn, wenn sich die Symbolwahrscheinlichkeiten von &nbsp;$\rm X$&nbsp; und &nbsp;$\rm Y$&nbsp; signifikant unterscheiden.&nbsp; Liegen diese dagegen zwischen&nbsp; $0.382$&nbsp; und&nbsp; $0.618$,  so ist der&nbsp; $\text{Code 1}$&nbsp; anzuwenden.
 +
 
 +
::Die Aufteilung einer Strecke der Länge&nbsp; $1$&nbsp; in zwei Abschnitte der Länge&nbsp; $0.618$...&nbsp; und&nbsp; $0.382$...&nbsp; bezeichnet man als&nbsp; [https://de.wikipedia.org/wiki/Goldener_Schnitt Goldenen Schnitt], auf den man in den verschiedensten Fachgebieten immer wieder stößt.
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Version vom 25. Januar 2020, 17:02 Uhr

Drei Binärcodes für  $M = 4$

Die Anwendung des Huffman–Algorithmus in seiner ursprünglichen Form setzt einen Symbolumfang  $M > 2$  voraus und ist deshalb zur Datenkomprimierung von Binärquellen unbrauchbar.

Fasst man aber mehrere aufeinanderfolgende Binärzeichen der Nachrichtenquelle zu einem neuen Symbol zusammen, so kann man auf die neue Symbolmenge die Huffman–Datenkomprimierung sinnvoll anwenden.

Wir gehen in dieser Aufgabe von der Symbolmenge  $\{$ $\rm X$,  $\rm Y$ $\}$  ⇒  aus  $(M = 2)$  und bilden gemäß obiger Tabelle Zweiertupel mit dem Symbolvorrat  $\{$ $\rm A$,  $\rm B$,  $\rm C$,  $\rm D$ $\}$  ⇒  $(M\hspace{0.03cm}' = M^2 = 4)$. 

Beispielsweise wird somit aus der binären Quellensymbolfolge  $\rm XYXXYXXXYY$  die quaternäre Folge  $\rm BACAD$.

Desweiteren sind in obiger Tabelle drei Codes angegeben, von denen manche durch den Huffman–Algorithmus entstanden sind. Die binären Ausgangsfolgen ergeben sich dann für unser Beispiel wie folgt:

  • $\text{Code 1}$:   1011011100,
  • $\text{Code 2}$:   0110011000,
  • $\text{Code 3}$:   10011001110.


Nochmals zum Verständnis:

  • Aus der ursprünglichen Symbolmenge  $\{$ $\rm X$,  $\rm Y$ $\}$  erhält man durch Bildung von Zweiertupeln eine Quaternärmenge mit Symbolvorrat  $\{$ $\rm A$,  $\rm B$,  $\rm C$,  $\rm D$ $\}$. 
  • Die Folgenlänge $N$ wird dadurch auf  $N\hspace{0.03cm}' = N/2 $  halbiert.
  • Durch Huffman–Codierung ergibt sich wieder eine Binärfolge, deren Symbolmenge zur besseren Unterscheidung mit  $\{$01$\}$  bezeichnet wird.
  • Die Anwendung der Huffman–Codierung macht genau dann Sinn, wenn die Länge  $L$  der Ausgangsfolge (im statistischen Mittel) kleiner ist als  $N$.


Mit dieser Aufgabe soll geklärt werden, welche der vorgegebenen Binärcodes bei welchen Randbedingungen sinnvoll sind.

  • Die binäre Nachrichtenquelle  $\{$ $\rm X$,  $\rm Y$ $\}$  sei gedächtnislos und wird allein durch die Symbolwahrscheinlichkeit  $p_{\rm X}$  beschrieben.
  • Die zweite Wahrscheinlichkeit ist dann stets  $p_{\rm Y} = 1 - p_{\rm X}$.





Hinweise:

  • Die Aufgabe gehört zum Kapitel  Entropiecodierung nach Huffman.
  • Insbesondere wird auf die Seite  Anwendung der Huffman-Codierung auf  $k$-Tupel  Bezug genommen.
  • Die mittlere Codewortlänge pro Zweiertupel ist  $L_{\rm M}\hspace{0.03cm}' = p_{\rm A} \cdot L_{\rm A} +$  ...  $ + p_{\rm D} \cdot L_{\rm D} \hspace{0.05cm}$.  Bezogen auf ein Quellensymbol gilt  $L_{\rm M} = L_{\rm M}\hspace{0.03cm}'/2$.
  • Eine vergleichbare Aufgabenstellung mit ternären Eingangssymbolen wird in der  Aufgabe 2.7Z  behandelt.
  • Die Idee zu dieser Aufgabe entstand bei einem Vortrag von  Prof. Robert Fischer  von der Universität Ulm an der TU München zum Thema „Der goldene Schnitt in der Nachrichtentechnik”.



Fragebogen

1

Geben Sie die Codewortlängen bei redundanzfreier Binärquelle an.

$\text{Code 1}$:   $L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$
$\text{Code 2}$:   $L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$
$\text{Code 3}$:   $L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

2

Ermitteln Sie den Huffman–Code hinsichtlich Zweiertupel für  $p_{\rm X}= 0.6$.

Es ergibt sich  $\text{Code 1}$.
Es ergibt sich  $\text{Code 2}$.
Es ergibt sich  $\text{Code 3}$.

3

Wie groß ist die mittlere Codewortlänge des für  $p_{\rm X}= 0.6$  besten Huffman–Codes?

$L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

4

Ermitteln Sie den Huffman–Code hinsichtlich Zweiertupel für  $p_{\rm X}= 0.8$.

Es ergibt sich  $\text{Code 1}$.
Es ergibt sich  $\text{Code 2}$.
Es ergibt sich  $\text{Code 3}$.

5

Wie groß ist die mittlere Codewortlänge des für  $p_{\rm X}= 0.8$  besten Huffman–Codes?

$L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

6

In welchem Bereich darf die Wahrscheinlichkeit  $p_{\rm X}$  für das Symbol  $\rm X$  liegen, damit sich nach Huffman der  $\text{Code 1}$  ergibt?

$p_\text{X, min}\ = \ $

$p_\text{X, max}\ = \ $


Musterlösung

(1)  Bei redundanzfreier Binärquelle  $(p_{\rm X} = p_{\rm Y} = 0.5)$  erhält man  $p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} = 0.25$  und mit der angegebenen Gleichung:

$$L_{\rm M} = \big [ \hspace{0.05cm}p_{\rm A} \cdot L_{\rm A} + p_{\rm B} \cdot L_{\rm B} + p_{\rm C} \cdot L_{\rm C} + p_{\rm D} \cdot L_{\rm D} \hspace{0.05cm} \big ] / 2 = \big [ \hspace{0.05cm} L_{\rm A} + L_{\rm B} + L_{\rm C} + L_{\rm D}\hspace{0.05cm} \big ] / 8 \hspace{0.05cm}.$$

Berücksichtigt man die angegebenen Zuordnungen, so erhält man für

  • $\text{Code 1}$:    $L_{\rm M} \hspace{0.15cm}\underline{= 1.000 \ {\rm bit/Quellensymbol} }$,
  • $\text{Code 2}$:    $L_{\rm M} \hspace{0.15cm}\underline{= 1.125 \ {\rm bit/Quellensymbol} }$,
  • $\text{Code 3}$:    $L_{\rm M} \hspace{0.15cm}\underline{= 1.250 \ {\rm bit/Quellensymbol} }$.
Im Verlauf der Aufgabe wird sich zeigen, dass die beiden ersten Codes durchaus als Ergebnis des Huffman–Algorithmus möglich sind  (natürlich nur bei geeigneten Symbolwahrscheinlichkeiten).  Der  $\text{Code 3}$  ist zwar ebenfalls präfixfrei, aber hinsichtlich der mittleren Codewortlänge nie optimal.


(2)  Die Wahrscheinlichkeiten der möglichen Zweiertupel lauten:

$$p_{\rm A} = 0.6^2 = 0.36 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm B}= 0.6 \cdot 0.4 = 0.24 = p_{\rm C} \hspace{0.05cm},\hspace{0.4cm} p_{\rm D}= 0.4^2 = 0.16 \hspace{0.05cm}.$$
  • Damit ergibt sich das  linke Baumdiagramm  (in nebenstehender Grafik) und der folgende Huffman–Code:
Huffman–Baumdiagramm für zwei unterschiedliche Zweiertupel–Konstellationen
    $\rm A$   →   11,   $\rm B$   →   10,   $\rm C$   →   01,   $\rm D$   →   00.
  • Es handelt sich um den  $\text{Code 1}$   ⇒   Lösungsvorschlag 1.


(3)  Jedes Zweiertupel wird durch zwei Bit dargestellt.  Damit ist

$$L_{\rm M} \hspace{0.15cm}\underline{= 1.000 \ {\rm bit/Quellensymbol} }.$$


(4)  Hier lauten die Wahrscheinlichkeiten der einzelnen Zweiertupel:

$$p_{\rm A} = 0.8^2 = 0.64 \hspace{0.05cm}, \hspace{0.4cm}p_{\rm B}= 0.8 \cdot 0.2 = 0.16 \hspace{0.05cm}, $$
$$p_{\rm C} = p_{\rm B}= 0.8 = 0.16 \hspace{0.05cm},\hspace{0.4cm} p_{\rm D}= 0.2^2 = 0.04 \hspace{0.05cm}. $$

Entsprechend dem rechten Baumdiagramm ergibt sich nun der  $\text{Code 2}$   ⇒   Lösungsvorschlag 2:

    $\rm A$   →   1,   $\rm B$   →   01,   $\rm C$   →   001,   $\rm D$   →   010.


(5)  Beim  $\text{Code 2}$  gilt für die mittlere Zweiertupellänge bzw. die mittlere Codewortlänge:

$$L_{\rm M}\hspace{0.01cm}' = 0.64 \cdot 1 + 0.16 \cdot 2 + (0.16 + 0.04) \cdot 3 = 1.56\,{\rm bit/Zweiertupel}\hspace{0.3cm} \Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.01cm}'}/{2}\hspace{0.15cm}\underline{ = 0.78\,{\rm bit/Quellensymbol}}\hspace{0.05cm}.$$


(6)  Aus den früheren Teilaufgaben hat sich ergeben:

  • Für  $p_{\rm X} = 0.6$  ist der  $\text{Code 1}$  optimal und die mittlere Codewortlänge dieses Codes ist  $($unabhängig von  $p_{\rm X})$  $L_{\rm M} = 1$  bit/Quellensymbol.
  • Für  $p_{\rm X} = 0.8$  entsprechend der Teilaufgabe  (4)  ist der  $\text{Code 2}$  optimal und die mittlere Codewortlänge beträgt  $L_{\rm M} = 0.78$  bit/Quellensymbol.


Der gesuchte Maximalwert  $p_\text{X, max}$  wird somit zwischen  $0.6$  und  $0.8$  liegen.  Die Bestimmungsgleichung ist dabei, dass für den Grenzfall  $p_\text{X} = p_\text{X, max}$  beide Codes genau die gleiche mittlere Codewortlänge  $L_{\rm M} = 1$  bit/Quellensymbol besitzen, bzw.  $L_{\rm M}\hspace{0.03cm}' = 2$  bit/Zweiertupel.

  • Mit der Abkürzung  $p = p_\text{X, max}$  lautet die entsprechende Bestimmungsgleichung:
$$L_{\rm M}\hspace{0.01cm}'\hspace{0.15cm}{\rm (Code \hspace{0.15cm}2)} = p^2 \cdot 1 + p \cdot (1-p) \cdot 2 + p \cdot (1-p) \cdot 3 + (1-p)^2 \cdot 3 \stackrel{!}{=} 2 \hspace{0.05cm}.$$
  • Dies führt zum zahlenmäßigen Ergebnis:
$$p^2 + p - 1 \stackrel{!}{=} 0 \hspace{0.3cm}\Rightarrow\hspace{0.3cm} p_{\rm X,\hspace{0.05cm}max} = p = \frac{\sqrt{5}-1}{2} \hspace{0.15cm}\underline{ \approx 0.618} \hspace{0.05cm}.$$
  • Da sich die grundsätzliche Huffman–Struktur durch Vertauschen von  $\rm X$  und  $\rm Y$  nicht ändert, gilt für die untere Grenze:
$$p_{\rm X,\hspace{0.05cm}min} = 1 - p_{\rm X,\hspace{0.05cm}max}\hspace{0.15cm}\underline{ \approx 0.382} \hspace{0.05cm}.$$

Die Darstellung der Zweiertupel durch unterschiedlich lange Bitfolgen  $\text{(Code 2)}$  macht also nur Sinn, wenn sich die Symbolwahrscheinlichkeiten von  $\rm X$  und  $\rm Y$  signifikant unterscheiden.  Liegen diese dagegen zwischen  $0.382$  und  $0.618$, so ist der  $\text{Code 1}$  anzuwenden.

Die Aufteilung einer Strecke der Länge  $1$  in zwei Abschnitte der Länge  $0.618$...  und  $0.382$...  bezeichnet man als  Goldenen Schnitt, auf den man in den verschiedensten Fachgebieten immer wieder stößt.