Difference between revisions of "Aufgaben:Exercise 2.7: Huffman Application for Binary Two-Tuples"
From LNTwww
| Line 3: | Line 3: | ||
}} | }} | ||
| − | [[File:P_ID2455__Inf_A_2_7.png|right|frame| | + | [[File:P_ID2455__Inf_A_2_7.png|right|frame|Three binary codes for $M = 4$]] |
| − | + | The application of the Huffman algorithm in its original form assumes a symbol set $M > 2$ and is therefore useless for data compression of binary sources. | |
| − | + | However, if one combines several consecutive binary characters of the message source into a new symbol, one can usefully apply Huffman data compression to the new symbol set. | |
| − | + | In this task we start from the symbol set $\{$ $\rm X$, $\rm Y$ $\}$ ⇒ aus $(M = 2)$ and form two-tuples according to the table above with the symbol set $\{$ $\rm A$, $\rm B$, $\rm C$, $\rm D$ $\}$ ⇒ $(M\hspace{0.03cm}' = M^2 = 4)$. | |
| − | + | For example, the binary source symbol sequence $\rm XYXXYXXXYY$ thus becomes the quaternary sequence $\rm BACAD$. | |
| − | + | Furthermore, three codes are given in the above table, some of which have been created by the Huffman algorithm. The binary output sequences then result for our example as follows: | |
* $\text{Code 1}$: <b>1011011100</b>, | * $\text{Code 1}$: <b>1011011100</b>, | ||
| Line 19: | Line 19: | ||
| − | + | Again for understanding: | |
| − | * | + | *From the original symbol set $\{$ $\rm X$, $\rm Y$ $\}$ a quaternary set with symbol set $\{$ $\rm A$, $\rm B$, $\rm C$, $\rm D$ $\}$ is obtained by forming two-tuples. |
| − | * | + | *The sequence length $N$ is thereby halved to $N\hspace{0.03cm}' = N/2 $ . |
| − | * | + | *Huffman coding again results in a binary sequence whose symbol set is designated $\{$<b>0</b>, <b>1</b>$\}$ for better differentiation. |
| − | * | + | *The application of Huffman coding makes sense exactly when the length $L$ of the initial sequence is smaller than $N$ (on statistical average). |
| − | + | This task is intended to clarify which of the given binary codes make sense under which boundary conditions. | |
| − | * | + | *Let the binary message source $\{$ $\rm X$, $\rm Y$ $\}$ be memoryless and be described solely by the symbol probability $p_{\rm X}$ . |
| − | * | + | *The second probability is then always $p_{\rm Y} = 1 - p_{\rm X}$. |
| Line 37: | Line 37: | ||
| − | '' | + | ''Hints:'' |
| − | * | + | *The task belongs to the chapter [[Information_Theory/Entropiecodierung_nach_Huffman|Entropy Coding according to Huffman]]. |
| − | * | + | *In particular, reference is made to the page [[Information_Theory/Entropiecodierung_nach_Huffman#Application_of_Huffman_coding_to_.7F.27.22.60UNIQ-MathJax168-QINU.60.22.27.7F.E2.80.93tuples|Application of Huffman coding to $k$-tuples]] Bezug genommen. |
| − | * | + | *The mean codeword length per two-tuple is $L_{\rm M}\hspace{0.03cm}' = p_{\rm A} \cdot L_{\rm A} +$ ... $ + p_{\rm D} \cdot L_{\rm D} \hspace{0.05cm}$. With respect to a source symbol, $L_{\rm M} = L_{\rm M}\hspace{0.03cm}'/2$. |
| − | * | + | *A comparable task with ternary input symbols is treated in [[Aufgaben:2.7Z_Huffman-Codierung_für_Zweiertupel_einer_Ternärquelle|exercise 2.7Z]] . |
| − | * | + | *The idea for this task arose during a lecture by [http://www.uni-ulm.de/nt/staff/professors/fischer/ Prof. Robert Fischer] from the University of Ulm at the Technical University of Munich on the topic of "Der goldene Schnitt in der Nachrichtentechnik". |
| − | === | + | ===Questions=== |
<quiz display=simple> | <quiz display=simple> | ||
| − | { | + | {Give the code word lengths with redundancy-free binary source. |
|type="{}"} | |type="{}"} | ||
| − | $\text{Code 1}$: $L_{\rm M} \ = \ $ { 1 1% } $\ \rm bit/ | + | $\text{Code 1}$: $L_{\rm M} \ = \ $ { 1 1% } $\ \rm bit/source symbol$ |
| − | $\text{Code 2}$: $L_{\rm M} \ = \ $ { 1.125 1% } $\ \rm bit/ | + | $\text{Code 2}$: $L_{\rm M} \ = \ $ { 1.125 1% } $\ \rm bit/source symbol$ |
| − | $\text{Code 3}$: $L_{\rm M} \ = \ $ { 1.25 1% } $\ \rm bit/ | + | $\text{Code 3}$: $L_{\rm M} \ = \ $ { 1.25 1% } $\ \rm bit/source symbol$ |
| − | { | + | {Determine the Huffman code with respect to two-tuple for $p_{\rm X}= 0.6$. |
|type="[]"} | |type="[]"} | ||
| − | + | + | + The result is $\text{Code 1}$. |
| − | - | + | - The result is $\text{Code 2}$. |
| − | - | + | - The result is $\text{Code 3}$. |
| − | { | + | {What is the mean codeword length of the best Huffman code for $p_{\rm X}= 0.6$ ? |
|type="{}"} | |type="{}"} | ||
| − | $L_{\rm M} \ = \ $ { 1 1% } $\ \rm bit/ | + | $L_{\rm M} \ = \ $ { 1 1% } $\ \rm bit/source symbol$ |
| − | { | + | {Determine the Huffman code with respect to two-tuple for $p_{\rm X}= 0.8$. |
|type="[]"} | |type="[]"} | ||
| − | - | + | - The result is $\text{Code 1}$. |
| − | + | + | + The result is $\text{Code 2}$. |
| − | - | + | - The result is $\text{Code 3}$. |
| − | { | + | {What is the mean codeword length of the best Huffman code for $p_{\rm X}= 0.8$ ? |
|type="{}"} | |type="{}"} | ||
| − | $L_{\rm M} \ = \ $ { 0.78 1% } $\ \rm bit/ | + | $L_{\rm M} \ = \ $ { 0.78 1% } $\ \rm bit/source symbol$ |
| − | {In | + | {In what range may the probability $p_{\rm X}$ for the symbol $\rm X$ lie so that the $\text{code 1}$ results according to Huffman? |
|type="{}"} | |type="{}"} | ||
$p_\text{X, min}\ = \ $ { 0.382 1% } | $p_\text{X, min}\ = \ $ { 0.382 1% } | ||
| Line 92: | Line 92: | ||
</quiz> | </quiz> | ||
| − | === | + | ===Solution=== |
{{ML-Kopf}} | {{ML-Kopf}} | ||
'''(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: | '''(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: | ||
Revision as of 13:20, 3 August 2021
Three binary codes for $M = 4$
The application of the Huffman algorithm in its original form assumes a symbol set $M > 2$ and is therefore useless for data compression of binary sources.
However, if one combines several consecutive binary characters of the message source into a new symbol, one can usefully apply Huffman data compression to the new symbol set.
In this task we start from the symbol set $\{$ $\rm X$, $\rm Y$ $\}$ ⇒ aus $(M = 2)$ and form two-tuples according to the table above with the symbol set $\{$ $\rm A$, $\rm B$, $\rm C$, $\rm D$ $\}$ ⇒ $(M\hspace{0.03cm}' = M^2 = 4)$.
For example, the binary source symbol sequence $\rm XYXXYXXXYY$ thus becomes the quaternary sequence $\rm BACAD$.
Furthermore, three codes are given in the above table, some of which have been created by the Huffman algorithm. The binary output sequences then result for our example as follows:
- $\text{Code 1}$: 1011011100,
- $\text{Code 2}$: 0110011000,
- $\text{Code 3}$: 10011001110.
Again for understanding:
- From the original symbol set $\{$ $\rm X$, $\rm Y$ $\}$ a quaternary set with symbol set $\{$ $\rm A$, $\rm B$, $\rm C$, $\rm D$ $\}$ is obtained by forming two-tuples.
- The sequence length $N$ is thereby halved to $N\hspace{0.03cm}' = N/2 $ .
- Huffman coding again results in a binary sequence whose symbol set is designated $\{$0, 1$\}$ for better differentiation.
- The application of Huffman coding makes sense exactly when the length $L$ of the initial sequence is smaller than $N$ (on statistical average).
This task is intended to clarify which of the given binary codes make sense under which boundary conditions.
- Let the binary message source $\{$ $\rm X$, $\rm Y$ $\}$ be memoryless and be described solely by the symbol probability $p_{\rm X}$ .
- The second probability is then always $p_{\rm Y} = 1 - p_{\rm X}$.
Hints:
- The task belongs to the chapter Entropy Coding according to Huffman.
- In particular, reference is made to the page Application of Huffman coding to $k$-tuples Bezug genommen.
- The mean codeword length per two-tuple is $L_{\rm M}\hspace{0.03cm}' = p_{\rm A} \cdot L_{\rm A} +$ ... $ + p_{\rm D} \cdot L_{\rm D} \hspace{0.05cm}$. With respect to a source symbol, $L_{\rm M} = L_{\rm M}\hspace{0.03cm}'/2$.
- A comparable task with ternary input symbols is treated in exercise 2.7Z .
- The idea for this task arose during a lecture by Prof. Robert Fischer from the University of Ulm at the Technical University of Munich on the topic of "Der goldene Schnitt in der Nachrichtentechnik".
Questions
Solution
(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.
