Informationstheorie/Entropiecodierung nach Huffman - Versionsgeschichte

Maintenance script: Add English interlanguage link

2026-03-16T12:27:26Z

Add English interlanguage link

← Nächstältere Version		Version vom 16. März 2026, 14:27 Uhr
Zeile 282:		Zeile 282:

	{{Display}}		{{Display}}
			[[en:Information_Theory/Entropy_Coding_According_to_Huffman]]

Maintenance script: Join multi-line formulas for MW 1.43 parser compat

2026-02-24T13:37:46Z

Join multi-line formulas for MW 1.43 parser compat

← Nächstältere Version		Version vom 24. Februar 2026, 15:37 Uhr
Zeile 10:		Zeile 10:
	Wir setzen nun voraus, dass die Quellensymbole  $q_\nu$  einem Alphabet  $\{q_μ\} = \{$ $\rm A$,  $\rm B$ ,  $\rm C$ , ...$\}$  mit dem Symbolumfang  $M$  entstammen und statistisch voneinander unabhängig seien.  Beispielsweise gelte für den Symbolumfang  $M = 8$:		Wir setzen nun voraus, dass die Quellensymbole  $q_\nu$  einem Alphabet  $\{q_μ\} = \{$ $\rm A$,  $\rm B$ ,  $\rm C$ , ...$\}$  mit dem Symbolumfang  $M$  entstammen und statistisch voneinander unabhängig seien.  Beispielsweise gelte für den Symbolumfang  $M = 8$:

	:$$\{ \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}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}.$$

	[https://de.wikipedia.org/wiki/David_A._Huffman David A. Huffman]  hat 1952 – also kurz nach Shannons bahnbrechenden Veröffentlichungen – einen Algorithmus zur Konstruktion von optimalen präfixfreien Codes angegeben.  Dieser  '''Huffman–Algorithmus'''  soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns auf Binärcodes beschränken.  Das heißt:   Für die Codesymbole gelte stets  $c_ν ∈ \{$'''0''',  '''1'''$\}$.		[https://de.wikipedia.org/wiki/David_A._Huffman David A. Huffman]  hat 1952 – also kurz nach Shannons bahnbrechenden Veröffentlichungen – einen Algorithmus zur Konstruktion von optimalen präfixfreien Codes angegeben.  Dieser  '''Huffman–Algorithmus'''  soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns auf Binärcodes beschränken.  Das heißt:   Für die Codesymbole gelte stets  $c_ν ∈ \{$'''0''',  '''1'''$\}$.
Zeile 26:		Zeile 25:
	$\text{Beispiel 1:}$  Ohne Einschränkung der Allgemeingültigkeit setzen wir voraus, dass die  $M = 6$  Symbole  $\rm A$, ... , $\rm F$  bereits nach ihren Wahrscheinlichkeiten geordnet sind:		$\text{Beispiel 1:}$  Ohne Einschränkung der Allgemeingültigkeit setzen wir voraus, dass die  $M = 6$  Symbole  $\rm A$, ... , $\rm F$  bereits nach ihren Wahrscheinlichkeiten geordnet sind:

	:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}		:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04 \hspace{0.05cm}.$$
	p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04
	\hspace{0.05cm}.$$

	Durch paarweises Zusammenfassen und anschießendes Sortieren erhält man in fünf Schritten die folgenden Symbolkombinationen <br>(resultierende Wahrscheinlichkeiten in Klammern):		Durch paarweises Zusammenfassen und anschießendes Sortieren erhält man in fünf Schritten die folgenden Symbolkombinationen <br>(resultierende Wahrscheinlichkeiten in Klammern):
Zeile 50:		Zeile 47:
	Wir gehen weiterhin von den Wahrscheinlichkeiten und Zuordnungen des letzten Beispiels aus:		Wir gehen weiterhin von den Wahrscheinlichkeiten und Zuordnungen des letzten Beispiels aus:

	:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}		:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04 \hspace{0.05cm};$$
	p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04
	\hspace{0.05cm};$$

	:$$\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 11} \hspace{0.05cm},\hspace{0.2cm}		:$$\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 11} \hspace{0.05cm},\hspace{0.2cm}\boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 01} \hspace{0.05cm},\hspace{0.2cm}\boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 00} \hspace{0.05cm},\hspace{0.2cm}\boldsymbol{\rm D} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 100} \hspace{0.05cm},\hspace{0.2cm}\boldsymbol{\rm E} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1011} \hspace{0.05cm},\hspace{0.2cm}\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1010} \hspace{0.05cm}.$$
	\boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 01} \hspace{0.05cm},\hspace{0.2cm}
	\boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 00} \hspace{0.05cm},\hspace{0.2cm}
	\boldsymbol{\rm D} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 100} \hspace{0.05cm},\hspace{0.2cm}
	\boldsymbol{\rm E} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1011} \hspace{0.05cm},\hspace{0.2cm}
	\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.05cm} \boldsymbol{\rm 1010} \hspace{0.05cm}.$$

	Von den sechs Quellensymbolen werden also drei mit je zwei Bit, eines mit drei Bit und zwei Symbole  $(\rm E$  und  $\rm F)$  mit je vier Bit codiert.		Von den sechs Quellensymbolen werden also drei mit je zwei Bit, eines mit drei Bit und zwei Symbole  $(\rm E$  und  $\rm F)$  mit je vier Bit codiert.
Zeile 65:		Zeile 55:
	Die mittlere Codewortlänge ergibt sich damit zu		Die mittlere Codewortlänge ergibt sich damit zu

	:$$L_{\rm M} = (0.30 \hspace{-0.05cm}+ \hspace{-0.05cm}0.24 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.20) \cdot 2 + 0.12 \cdot 3 + (0.10 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.04 ) \cdot 4 = 2.4 \,{\rm bit/Quellensymbol}		:$$L_{\rm M} = (0.30 \hspace{-0.05cm}+ \hspace{-0.05cm}0.24 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.20) \cdot 2 + 0.12 \cdot 3 + (0.10 \hspace{-0.05cm}+ \hspace{-0.05cm} 0.04 ) \cdot 4 = 2.4 \,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$
	\hspace{0.05cm}.$$

	Aus dem Vergleich mit der Quellenentropie  $H = 2.365 \ \rm bit/Quellensymbol$  erkennt man die Effizienz der Huffman–Codierung.		Aus dem Vergleich mit der Quellenentropie  $H = 2.365 \ \rm bit/Quellensymbol$  erkennt man die Effizienz der Huffman–Codierung.
Zeile 78:		Zeile 67:
	$\text{Beispiel 2:}$  Wären die Symbolwahrscheinlichkeiten		$\text{Beispiel 2:}$  Wären die Symbolwahrscheinlichkeiten

	:$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/4 \hspace{0.05cm},\hspace{0.2cm}		:$$p_{\rm A} = p_{\rm B} = p_{\rm C} = 1/4 \hspace{0.05cm},\hspace{0.2cm}p_{\rm D} = 1/8 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = p_{\rm F} = 1/16 \hspace{0.05cm},$$
	p_{\rm D} = 1/8 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = p_{\rm F} = 1/16
	\hspace{0.05cm},$$

	so würde für die Entropie und für die mittlere Codewortlänge gleichermaßen gelten:		so würde für die Entropie und für die mittlere Codewortlänge gleichermaßen gelten:

	:$$H = 3 \cdot 1/4 \cdot {\rm log_2}\hspace{0.1cm}(4) + 1/8 \cdot {\rm log_2}\hspace{0.1cm}(8) + 2 \cdot 1/16 \cdot {\rm log_2}\hspace{0.1cm}(16) = 2.375 \,{\rm bit/Quellensymbol}\hspace{0.05cm},$$		:$$H = 3 \cdot 1/4 \cdot {\rm log_2}\hspace{0.1cm}(4) + 1/8 \cdot {\rm log_2}\hspace{0.1cm}(8) + 2 \cdot 1/16 \cdot {\rm log_2}\hspace{0.1cm}(16) = 2.375 \,{\rm bit/Quellensymbol}\hspace{0.05cm},$$
	:$$L_{\rm M} = 3 \cdot 1/4 \cdot 2 + 1/8 \cdot 3 + 2 \cdot 1/16 \cdot 4 = 2.375 \,{\rm bit/Quellensymbol}		:$$L_{\rm M} = 3 \cdot 1/4 \cdot 2 + 1/8 \cdot 3 + 2 \cdot 1/16 \cdot 4 = 2.375 \,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$}}
	\hspace{0.05cm}.$$}}


Zeile 138:		Zeile 124:
	:$$p_{\rm D} = 0.12 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm D} = 7/49 \approx 0.143 \hspace{0.05cm},$$		:$$p_{\rm D} = 0.12 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm D} = 7/49 \approx 0.143 \hspace{0.05cm},$$
	:$$p_{\rm E}=0.10 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102 \hspace{0.05cm},$$		:$$p_{\rm E}=0.10 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102 \hspace{0.05cm},$$
	:$$p_{\rm F} = 0.04 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102		:$$p_{\rm F} = 0.04 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102 \hspace{0.05cm}.$$
	\hspace{0.05cm}.$$
	*Damit ergibt sich ein etwas größerer Entropiewert:		*Damit ergibt sich ein etwas größerer Entropiewert:

	:$$H ({\rm bez\ddot{u}glich }\hspace{0.15cm}p_{\mu}) = 2.365 \ {\rm bit/Quellensymbol}\hspace{0.3cm}		:$$H ({\rm bez\ddot{u}glich }\hspace{0.15cm}p_{\mu}) = 2.365 \ {\rm bit/Quellensymbol}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} H ({\rm bez\ddot{u}glich }\hspace{0.15cm}h_{\mu}) = 2.451 \ {\rm bit/Quellensymbol}\hspace{0.05cm}.$$
	\Rightarrow \hspace{0.3cm}
	H ({\rm bez\ddot{u}glich }\hspace{0.15cm}h_{\mu}) = 2.451 \ {\rm bit/Quellensymbol}
	\hspace{0.05cm}.$$

	:Würde man den Huffman–Code mit diesen „neuen Wahrscheinlichkeiten”  $h_{\rm A}$, ... , $h_{\rm F}$  bilden, so ergäben sich folgende Zuordnungen:		:Würde man den Huffman–Code mit diesen „neuen Wahrscheinlichkeiten”  $h_{\rm A}$, ... , $h_{\rm F}$  bilden, so ergäben sich folgende Zuordnungen:
Zeile 198:		Zeile 180:
	Eine zweite Nachrichtenquelle mit Symbolumfang  $M = 6$  sei durch folgende Symbolwahrscheinlichkeiten gekennzeichnet:		Eine zweite Nachrichtenquelle mit Symbolumfang  $M = 6$  sei durch folgende Symbolwahrscheinlichkeiten gekennzeichnet:

	:$$p_{\rm A} = 0.50 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.19 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.11 \hspace{0.05cm},\hspace{0.2cm}		:$$p_{\rm A} = 0.50 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.19 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.11 \hspace{0.05cm},\hspace{0.2cm}p_{\rm D} = 0.09 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.06 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.05 \hspace{0.05cm}.$$
	p_{\rm D} = 0.09 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.06 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.05
	\hspace{0.05cm}.$$

	Hier führt der Huffman–Algorithmus zu folgender Zuordnung:		Hier führt der Huffman–Algorithmus zu folgender Zuordnung:
Zeile 259:		Zeile 239:
	*Fasst man jeweils zwei binäre Symbole zu einem Zweiertupel  $(k = 2)$  entsprechend   $\rm XX$   →   $\rm A$,   $\rm XY$   →   $\rm B$,   $\rm YX$   →   $\rm C$,   $\rm YY$   →   $\rm D$   zusammen, so kann man „Huffman” auf die resultierende Folge  →   $\rm ABAACADAABCBBAC$ ...  →   mit $M\hspace{-0.01cm}′ = 4$  →   anwenden. Wegen		*Fasst man jeweils zwei binäre Symbole zu einem Zweiertupel  $(k = 2)$  entsprechend   $\rm XX$   →   $\rm A$,   $\rm XY$   →   $\rm B$,   $\rm YX$   →   $\rm C$,   $\rm YY$   →   $\rm D$   zusammen, so kann man „Huffman” auf die resultierende Folge  →   $\rm ABAACADAABCBBAC$ ...  →   mit $M\hspace{-0.01cm}′ = 4$  →   anwenden. Wegen

	:$$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.2cm}p_{\rm B}= 0.8 \cdot 0.2 = 0.16 = p_{\rm C} \hspace{0.05cm}, \hspace{0.2cm}p_{\rm D}= 0.2^2 = 0.04$$
	p_{\rm D}= 0.2^2 = 0.04$$

	:erhält man   $\rm A$   →   '''1''',   $\rm B$   →   '''00''',   $\rm C$   →   '''011''',   $\rm D$   →   '''010'''   sowie		:erhält man   $\rm A$   →   '''1''',   $\rm B$   →   '''00''',   $\rm C$   →   '''011''',   $\rm D$   →   '''010'''   sowie
Zeile 273:		Zeile 252:
	:Für die oben angegebene Eingangsfolge kommt man zur äquivalenten Folge  $\rm AEBAGADBCC$ ...  (basierend auf dem neuen Symbolumfang $M\hspace{-0.01cm}′ = 8$) und zu folgenden Wahrscheinlichkeiten:		:Für die oben angegebene Eingangsfolge kommt man zur äquivalenten Folge  $\rm AEBAGADBCC$ ...  (basierend auf dem neuen Symbolumfang $M\hspace{-0.01cm}′ = 8$) und zu folgenden Wahrscheinlichkeiten:

	:$$p_{\rm A}= 0.8^3 = 0.512 \hspace{0.05cm}, \hspace{0.5cm}p_{\rm B}= p_{\rm C}= p_{\rm E} = 0.8^2 \cdot 0.2 = 0.128\hspace{0.05cm},\hspace{0.5cm}		:$$p_{\rm A}= 0.8^3 = 0.512 \hspace{0.05cm}, \hspace{0.5cm}p_{\rm B}= p_{\rm C}= p_{\rm E} = 0.8^2 \cdot 0.2 = 0.128\hspace{0.05cm},\hspace{0.5cm}p_{\rm D}= p_{\rm F}= p_{\rm G} = 0.8 \cdot 0.2^2 = 0.032 \hspace{0.05cm}, \hspace{0.5cm}p_{\rm H}= 0.2^3 = 0.008\hspace{0.05cm}.$$
	p_{\rm D}= p_{\rm F}= p_{\rm G} = 0.8 \cdot 0.2^2 = 0.032 \hspace{0.05cm}, \hspace{0.5cm}p_{\rm H}= 0.2^3 = 0.008\hspace{0.05cm}.$$

	:Die Huffman–Codierung lautet somit:		:Die Huffman–Codierung lautet somit:

Guenter am 6. Juli 2021 um 15:34 Uhr

2021-07-06T15:34:33Z

← Nächstältere Version		Version vom 6. Juli 2021, 17:34 Uhr
Zeile 161:		Zeile 161:


	Das folgende interaktive Applet  (in zwei ~~Verrsionen~~)  verdeutlicht die Vorgehensweise bei zwei Varianten einer Entropiecodierung.		Das folgende interaktive Applet  (in zwei Versionen)  verdeutlicht die Vorgehensweise bei zwei Varianten einer Entropiecodierung.
	*  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{HTML 5/JS}$ –Version]],		*  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{HTML 5/JS}$–Version]],
	*  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$ –Version]].		*  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$–Version]].

Guenter am 6. Juli 2021 um 15:29 Uhr

2021-07-06T15:29:31Z

← Nächstältere Version		Version vom 6. Juli 2021, 17:29 Uhr
Zeile 159:		Zeile 159:
	:*Die Codesymbolfolge hätte dann eine Länge von  $(16 + 9) · 2 + (7 + 7 + 5 + 5) · 3 = 122$  Bit, wäre also um drei Bit kürzer als nach der bisherigen Codierung.		:*Die Codesymbolfolge hätte dann eine Länge von  $(16 + 9) · 2 + (7 + 7 + 5 + 5) · 3 = 122$  Bit, wäre also um drei Bit kürzer als nach der bisherigen Codierung.
	:*Die mittlere Codewortlänge wäre dann  $L_{\rm M} = 122/49 ≈ 2.49$  bit/Quellensymbol  anstelle von  $L_{\rm M}≈ 2.55$  bit/Quellensymbol.}}		:*Die mittlere Codewortlänge wäre dann  $L_{\rm M} = 122/49 ≈ 2.49$  bit/Quellensymbol  anstelle von  $L_{\rm M}≈ 2.55$  bit/Quellensymbol.}}


			Das folgende interaktive Applet  (in zwei Verrsionen)  verdeutlicht die Vorgehensweise bei zwei Varianten einer Entropiecodierung.
			*  [[Applets:Huffman-_und_Shannon-Fano-Codierung\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{HTML 5/JS}$ –Version]],
			*  [[Applets:Huffman_Shannon_Fano\|Huffman- und Shannon-Fano-Codierung  ⇒   $\text{SWF}$ –Version]].

Guenter am 3. Juli 2021 um 14:39 Uhr

2021-07-03T14:39:43Z

← Nächstältere Version		Version vom 3. Juli 2021, 16:39 Uhr
Zeile 111:		Zeile 111:
	*Der vom Symbol mit der kleineren Wahrscheinlichkeit  $($hier  $\rm F)$  zum Summenknoten verlaufende Zweig ist blau eingezeichnet, der andere Zweig  $($für $\rm E)$  rot.		*Der vom Symbol mit der kleineren Wahrscheinlichkeit  $($hier  $\rm F)$  zum Summenknoten verlaufende Zweig ist blau eingezeichnet, der andere Zweig  $($für $\rm E)$  rot.
	*Nach fünf Schritten ist man bei der Baumwurzel  („Root”)  mit der Gesamtwahrscheinlichkeit  $1.00$  angelangt.		*Nach fünf Schritten ist man bei der Baumwurzel  („Root”)  mit der Gesamtwahrscheinlichkeit  $1.00$  angelangt.
	~~<br clear=all>~~

	Verfolgt man nun den Verlauf von der Wurzel  (in obiger Grafik mit gelber Füllung)  zu den einzelnen Symbolen zurück, so kann man aus den Farben der einzelnen Zweige die Symbolzuordnung ablesen.		Verfolgt man nun den Verlauf von der Wurzel  (in obiger Grafik mit gelber Füllung)  zu den einzelnen Symbolen zurück, so kann man aus den Farben der einzelnen Zweige die Symbolzuordnung ablesen.

Zeile 131:		Zeile 132:
	*Die binäre Codesymbolfolge weist die mittlere Codewortlänge  $L_{\rm M} = 125/49 = 2.551$  auf.		*Die binäre Codesymbolfolge weist die mittlere Codewortlänge  $L_{\rm M} = 125/49 = 2.551$  auf.
	*Die verschiedenen Farben dienen ausschließlich zur besseren Orientierung.		*Die verschiedenen Farben dienen ausschließlich zur besseren Orientierung.
	~~<br clear=all>~~		*Aufgrund der kurzen Quellensymbolfolge  $(N = 49)$  weichen die Auftrittshäufigkeiten  $h_{\rm A}$, ... ,  $h_{\rm F}$  der simulierten Folgen (manchmal) signifikant von den gegebenen Wahrscheinlichkeiten  $p_{\rm A}$, ... ,  $p_{\rm F}$  ab:
	Aufgrund der kurzen Quellensymbolfolge  $(N = 49)$  weichen die Auftrittshäufigkeiten  $h_{\rm A}$, ... ,  $h_{\rm F}$  der simulierten Folgen (manchmal) signifikant von den gegebenen Wahrscheinlichkeiten  $p_{\rm A}$, ... ,  $p_{\rm F}$  ab:		:$$p_{\rm A} = 0.30 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm A} = 16/49 \approx 0.326 \hspace{0.05cm},$$
			:$$p_{\rm B} = 0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm B} = 7/49 \approx 0.143 \hspace{0.05cm},$$
	:$$p_{\rm A} = 0.30 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm A} = 16/49 \approx 0.326 \hspace{0.05cm},~~\hspace{0.4cm}~~p_{\rm B} = 0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm B} = 7/49 \approx 0.143 \hspace{0.05cm},$$		:$$p_{\rm C} =0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm C}= 9/49 \approx 0.184 \hspace{0.05cm},$$
			:$$p_{\rm D} = 0.12 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm D} = 7/49 \approx 0.143 \hspace{0.05cm},$$
	:$$p_{\rm C} =0.24 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm C}= 9/49 \approx 0.184 \hspace{0.05cm},~~\hspace{0.6cm}~~p_{\rm D} = 0.12 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm D} = 7/49 \approx 0.143 \hspace{0.05cm},$$		:$$p_{\rm E}=0.10 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102 \hspace{0.05cm},$$
			:$$p_{\rm F} = 0.04 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102
	:$$p_{\rm E}=0.10 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102 \hspace{0.05cm},~~\hspace{0.6cm}~~p_{\rm F} = 0.04 \hspace{0.05cm} \Rightarrow \hspace{0.05cm} h_{\rm E} = 5/49 \approx 0.102
	\hspace{0.05cm}.$$		\hspace{0.05cm}.$$
			*Damit ergibt sich ein etwas größerer Entropiewert:
	Damit ergibt sich ein etwas größerer Entropiewert:

	:$$H ({\rm bez\ddot{u}glich }\hspace{0.15cm}p_{\mu}) = 2.365 \ {\rm bit/Quellensymbol}\hspace{0.3cm}		:$$H ({\rm bez\ddot{u}glich }\hspace{0.15cm}p_{\mu}) = 2.365 \ {\rm bit/Quellensymbol}\hspace{0.3cm}
Zeile 148:		Zeile 147:
	\hspace{0.05cm}.$$		\hspace{0.05cm}.$$

	Würde man den Huffman–Code mit diesen ~~„neuen” Wahrscheinlichkeiten~~  $h_{\rm A}$, ... , $h_{\rm F}$  bilden, so ergäben sich folgende Zuordnungen:		:Würde man den Huffman–Code mit diesen „neuen Wahrscheinlichkeiten”  $h_{\rm A}$, ... , $h_{\rm F}$  bilden, so ergäben sich folgende Zuordnungen:

	:     $\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''11'''$\hspace{0.05cm},\hspace{0.2cm}		::     $\boldsymbol{\rm A} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''11'''$\hspace{0.05cm},\hspace{0.2cm}
	\boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''100'''$\hspace{0.05cm},\hspace{0.2cm}		\boldsymbol{\rm B} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''100'''$\hspace{0.05cm},\hspace{0.2cm}
	\boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''00'''$\hspace{0.05cm},\hspace{0.2cm}		\boldsymbol{\rm C} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''00'''$\hspace{0.05cm},\hspace{0.2cm}
Zeile 157:		Zeile 156:
	\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''011'''$\hspace{0.05cm}.$		\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''011'''$\hspace{0.05cm}.$

	Nun würden nur  $\rm A$  und  $\rm C$  mit zwei Bit dargestellt, die anderen vier Symbole durch jeweils drei Bit.		:Nun würden nur  $\rm A$  und  $\rm C$  mit zwei Bit dargestellt, die anderen vier Symbole durch jeweils drei Bit.
	*Die Codesymbolfolge hätte dann eine Länge von  $(16 + 9) · 2 + (7 + 7 + 5 + 5) · 3 = 122$  Bit, wäre also um drei Bit kürzer als nach der bisherigen Codierung.		:*Die Codesymbolfolge hätte dann eine Länge von  $(16 + 9) · 2 + (7 + 7 + 5 + 5) · 3 = 122$  Bit, wäre also um drei Bit kürzer als nach der bisherigen Codierung.
	*Die mittlere Codewortlänge wäre dann  $L_{\rm M} = 122/49 ≈ 2.49$  bit/Quellensymbol  anstelle von  $L_{\rm M}≈ 2.55$  bit/Quellensymbol.}}		:*Die mittlere Codewortlänge wäre dann  $L_{\rm M} = 122/49 ≈ 2.49$  bit/Quellensymbol  anstelle von  $L_{\rm M}≈ 2.55$  bit/Quellensymbol.}}

Guenter am 3. Juli 2021 um 13:10 Uhr

2021-07-03T13:10:08Z

Guenter am 24. Januar 2020 um 17:27 Uhr

2020-01-24T17:27:26Z

Guenter am 24. Januar 2020 um 17:00 Uhr

2020-01-24T17:00:53Z

Änderungen zeigen

Guenter am 24. Januar 2020 um 15:57 Uhr

2020-01-24T15:57:59Z

Änderungen zeigen

Guenter am 26. September 2018 um 13:36 Uhr

2018-09-26T13:36:46Z

← Nächstältere Version		Version vom 26. September 2018, 15:36 Uhr
Zeile 235:		Zeile 235:

	Wir wollen im folgenden Beispiel die Vorgehensweise anhand einer Binärquelle verdeutlichen. Weitere Beispiele finden Sie in		Wir wollen im folgenden Beispiel die Vorgehensweise anhand einer Binärquelle verdeutlichen. Weitere Beispiele finden Sie in
	*der [[Aufgaben:2.~~07_Zweiertupel_~~-~~_Huffman~~\|Aufgabe 2.7]],		*der [[Aufgaben:Aufgabe_2.7:_Huffman-Anwendung_für_binäre_Zweiertupel\|Aufgabe 2.7]],
	*der [[Aufgaben:2.~~07Z_Ternärquelle~~-~~Zweiertupel~~\|Aufgabe 2.7Z]] und		*der [[Aufgaben:Aufgabe_2.7Z:_Huffman-Codierung_für_Zweiertupel_einer_Ternärquelle\|Aufgabe 2.7Z]] und
	*der [[Aufgaben:2.~~08_Markovquelle_und_Huffman~~\|Aufgabe 2.8]].		*der [[Aufgaben:Aufgabe_2.8:_Huffman-Anwendung_bei_einer_Markovquelle\|Aufgabe 2.8]].

← Nächstältere Version		Version vom 3. Juli 2021, 15:10 Uhr
Zeile 13:		Zeile 13:
	\}\hspace{0.05cm}.$$		\}\hspace{0.05cm}.$$

	[https://de.wikipedia.org/wiki/David_A._Huffman David A. Huffman]  hat 1952 – also kurz nach Shannons bahnbrechenden Veröffentlichungen – einen Algorithmus zur Konstruktion von optimalen präfixfreien Codes angegeben.		[https://de.wikipedia.org/wiki/David_A._Huffman David A. Huffman]  hat 1952 – also kurz nach Shannons bahnbrechenden Veröffentlichungen – einen Algorithmus zur Konstruktion von optimalen präfixfreien Codes angegeben.  Dieser  '''Huffman–Algorithmus'''  soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns auf Binärcodes beschränken.  Das heißt:   Für die Codesymbole gelte stets  $c_ν ∈ \{$'''0''',  '''1'''$\}$.
	Dieser  ''Huffman–Algorithmus''  soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns auf Binärcodes beschränken.  Das heißt:   Für die Codesymbole gelte stets  $c_ν ∈ \{$'''0''',  '''1'''$\}$.

	Hier ist das &bdquo;Rezept”:		Hier ist das &bdquo;Rezept”:
Zeile 21:		Zeile 20:
	#   Man wiederhole  '''(1)'''  und  '''(2)''', bis nur mehr zwei (zusammengefasste) Symbole übrig bleiben.		#   Man wiederhole  '''(1)'''  und  '''(2)''', bis nur mehr zwei (zusammengefasste) Symbole übrig bleiben.
	#   Man codiert die wahrscheinlichere Symbolmenge mit  '''1'''  und die andere Menge mit  '''0'''.		#   Man codiert die wahrscheinlichere Symbolmenge mit  '''1'''  und die andere Menge mit  '''0'''.
	#   Man ergänzt in Gegenrichtung  (~~also~~ von unten nach oben)  die jeweiligen Binärcodes der aufgespaltenen Teilmengen gemäß den Wahrscheinlichkeiten mit  '''1'''  bzw.  '''0'''.		#   Man ergänzt in Gegenrichtung  (von unten nach oben)  die jeweiligen Binärcodes der aufgespaltenen Teilmengen gemäß den Wahrscheinlichkeiten mit  '''1'''  bzw.  '''0'''.


	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Beispiel 1:}$  Ohne Einschränkung der Allgemeingültigkeit setzen wir voraus, dass die  $M = 6$ Symbole  $\rm A$, ... , $\rm F$  bereits nach ihren Wahrscheinlichkeiten geordnet sind:		$\text{Beispiel 1:}$  Ohne Einschränkung der Allgemeingültigkeit setzen wir voraus, dass die  $M = 6$  Symbole  $\rm A$, ... , $\rm F$  bereits nach ihren Wahrscheinlichkeiten geordnet sind:

	:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}		:$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm}
Zeile 37:		Zeile 36:
	:4.   $\rm AEFD$  (0.56), $\rm BC$  (0.44),		:4.   $\rm AEFD$  (0.56), $\rm BC$  (0.44),
	:5.   Root  $\rm AEFDBC$  (1.00).		:5.   Root  $\rm AEFDBC$  (1.00).
	Rückwärts – ~~alsogemäß~~ den Schritten  '''(5)'''  bis  '''(1)'''  – erfolgt dann die Zuordnung zu Binärsymbolen.  <br>Ein  '''x'''  weist darauf hin, dass in den nächsten Schritten noch Bit hinzugefügt werden müssen:		Rückwärts – also gemäß den Schritten  '''(5)'''  bis  '''(1)'''  – erfolgt dann die Zuordnung zu Binärsymbolen.  <br>Ein  '''x'''  weist darauf hin, dass in den nächsten Schritten noch Bit hinzugefügt werden müssen:
	:5.   $\rm AEFD$   →   '''1x''',     $\rm BC$   →   '''0x''',		:5.   $\rm AEFD$   →   '''1x''',     $\rm BC$   →   '''0x''',
	:4.   $\underline{\rm A}$   →   '''<u>11</u>''',     $\rm EFD$   →   '''10x''',		:4.   $\underline{\rm A}$   →   '''<u>11</u>''',     $\rm EFD$   →   '''10x''',
Zeile 90:		Zeile 89:


	Aus dieser Eigenschaft  $L_{\rm M} = H +\varepsilon$  mit  $\varepsilon \to 0$  bei geeigneten Auftrittswahrscheinlichkeiten erklärt sich der Begriff  '''Entropiecodierung''':		Aus dieser Eigenschaft  $L_{\rm M} = H +\varepsilon$  mit positivem  $\varepsilon \to 0$  bei geeigneten Auftrittswahrscheinlichkeiten erklärt sich der Begriff  '''Entropiecodierung''':

	Man versucht bei dieser Form von Quellencodierung, die Länge  $L_μ$  der Binärfolge  (bestehend aus Nullen und Einsen)  für das Symbol  $q_μ$  gemäß der Entropieberechnung wie folgt an dessen Auftrittswahrscheinlichkeit  $p_μ$  anzupassen:		Man versucht bei dieser Form von Quellencodierung, die Länge  $L_μ$  der Binärfolge  (bestehend aus Nullen und Einsen)  für das Symbol  $q_μ$  gemäß der Entropieberechnung wie folgt an dessen Auftrittswahrscheinlichkeit  $p_μ$  anzupassen:

	:$$L_{\mu} = {\rm log}_2\hspace{0.1cm}(1/p_{\mu} ) \hspace{0.05cm}.$$		::$$L_{\mu} = {\rm log}_2\hspace{0.1cm}(1/p_{\mu} ) \hspace{0.05cm}.$$

	Natürlich gelingt das nicht immer, sondern nur dann, wenn alle Auftrittswahrscheinlichkeiten  $p_μ$  in der Form  $2^{–k}$  mit  $k = 1, \ 2, \ 3,$ ... dargestellt werden können.		Natürlich gelingt das nicht immer, sondern nur dann, wenn alle Auftrittswahrscheinlichkeiten  $p_μ$  in der Form  $2^{–k}$  mit  $k = 1, \ 2, \ 3,$ ... dargestellt werden können.
	*In diesem Sonderfall – und nur in diesem – stimmt die mittlere Codewortlänge  $L_{\rm M}$  exakt mit der Quellenentropie  $H$  überein  $(\varepsilon = 0$,  siehe $\text{Beispiel 2})$.		*In diesem Sonderfall – und nur in diesem – stimmt die mittlere Codewortlänge  $L_{\rm M}$  exakt mit der Quellenentropie  $H$  überein  $(\varepsilon = 0$,  siehe $\text{Beispiel 2})$.
	*Nach dem  [[Informationstheorie/Allgemeine_Beschreibung#Quellencodierungstheorem\|Quellencodierungstheorem]]  gibt es keinen (decodierbaren) Code, der im Mittel mit weniger Binärzeichen pro Quellensymbol auskommt.		*Nach dem  [[Informationstheorie/Allgemeine_Beschreibung#Quellencodierungstheorem\|Quellencodierungstheorem]]  gibt es keinen  (decodierbaren)  Code, der im Mittel mit weniger Binärzeichen pro Quellensymbol auskommt.


Zeile 111:		Zeile 110:
	*Der Knoten im ersten Schritt fasst die zwei Symbole  $\rm E$  und  $\rm F$  mit den aktuell kleinsten Wahrscheinlichkeiten zusammen.  Dieser neue Knoten ist mit  $p_{\rm E} + p_{\rm F} = 0.14$  beschriftet.		*Der Knoten im ersten Schritt fasst die zwei Symbole  $\rm E$  und  $\rm F$  mit den aktuell kleinsten Wahrscheinlichkeiten zusammen.  Dieser neue Knoten ist mit  $p_{\rm E} + p_{\rm F} = 0.14$  beschriftet.
	*Der vom Symbol mit der kleineren Wahrscheinlichkeit  $($hier  $\rm F)$  zum Summenknoten verlaufende Zweig ist blau eingezeichnet, der andere Zweig  $($für $\rm E)$  rot.		*Der vom Symbol mit der kleineren Wahrscheinlichkeit  $($hier  $\rm F)$  zum Summenknoten verlaufende Zweig ist blau eingezeichnet, der andere Zweig  $($für $\rm E)$  rot.
			*Nach fünf Schritten ist man bei der Baumwurzel  („Root”)  mit der Gesamtwahrscheinlichkeit  $1.00$  angelangt.
	<br clear=all>		<br clear=all>
	~~Nach fünf Schritten ist man bei der Baumwurzel  („Root”)  mit der Gesamtwahrscheinlichkeit  $1.00$  angelangt. ~~ Verfolgt man nun den Verlauf von der Wurzel  (in obiger Grafik mit gelber Füllung)  zu den einzelnen Symbolen zurück, so kann man aus den Farben der einzelnen Zweige die Symbolzuordnung ablesen.		Verfolgt man nun den Verlauf von der Wurzel  (in obiger Grafik mit gelber Füllung)  zu den einzelnen Symbolen zurück, so kann man aus den Farben der einzelnen Zweige die Symbolzuordnung ablesen.

	Mit den Zuordnungen „rot”   →   '''1''' und „blau”   →   '''0''' ergibt sich beispielsweise von der Wurzel zu Symbol		Mit den Zuordnungen „rot”   →   '''1'''  und „blau”   →   '''0'''  ergibt sich beispielsweise von der Wurzel zu Symbol
	*$\rm A$:   rot, rot   →   '''11''',		*$\rm A$:   rot, rot   →   '''11''',
	*$\rm B$:   blau, rot   →   '''01''',		*$\rm B$:   blau, rot   →   '''01''',
Zeile 123:		Zeile 123:


	Die (einheitliche) Zuordnung „rot”   →   '''0''' und „blau”   →   '''1''' würde ebenfalls zu einem optimalen präfixfreien Huffman–Code führen.		Die  (einheitliche)  Zuordnung „rot”   →   '''0''' und „blau”   →   '''1''' würde ebenfalls zu einem optimalen präfixfreien Huffman–Code führen.

	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
Zeile 165:		Zeile 165:
	$\text{Fazit:}$		$\text{Fazit:}$
	Dieses Beispiel lässt sich wie folgt interpretieren:		Dieses Beispiel lässt sich wie folgt interpretieren:
	*Die Huffman–Codierung lebt von der (genauen) Kenntnis der Symbolwahrscheinlichkeiten.  Sind diese sowohl dem Sender als auch dem Empfänger bekannt, so ist die mittlere Codewortlänge  $L_{\rm M}$  oft nur unwesentlich größer als die Quellenentropie  $H$.		*Die Huffman–Codierung lebt von der  (genauen)  Kenntnis der Symbolwahrscheinlichkeiten.  Sind diese sowohl dem Sender als auch dem Empfänger bekannt, so ist die mittlere Codewortlänge  $L_{\rm M}$  oft nur unwesentlich größer als die Quellenentropie  $H$.
	*Insbesondere bei kleinen Dateien kann es zu Abweichungen zwischen den (erwarteten) Symbolwahrscheinlichkeiten  $p_μ$  und den (tatsächlichen) Häufigkeiten  $h_μ$  kommen.  Besser wäre es hier, für jede Datei einen eigenen Huffman–Code zu generieren, der auf den tatsächlichen Gegebenheiten  $(h_μ)$  basiert.		*Insbesondere bei kleinen Dateien kann es zu Abweichungen zwischen den  (erwarteten)  Symbolwahrscheinlichkeiten  $p_μ$  und den  (tatsächlichen)  Häufigkeiten  $h_μ$  kommen.  Besser wäre es hier, für jede Datei einen eigenen Huffman–Code zu generieren, der auf den tatsächlichen Gegebenheiten  $(h_μ)$  basiert.
	*In diesem Fall muss aber dem Decoder auch der spezifische Huffman–Code mitgeteilt werden.  Dies führt zu einem gewissen Overhead, der nur wieder bei längeren Dateien vernachlässigt werden kann.  Bei kleinen Dateien lohnt sich dieser Aufwand nicht.}}		*In diesem Fall muss aber dem Decoder auch der spezifische Huffman–Code mitgeteilt werden.  Dies führt zu einem gewissen Overhead, der nur wieder bei längeren Dateien vernachlässigt werden kann.  Bei kleinen Dateien lohnt sich dieser Aufwand nicht.}}

Zeile 207:		Zeile 207:
	\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''1100'''$\hspace{0.05cm}.$		\boldsymbol{\rm F} \hspace{0.05cm} \rightarrow \hspace{0.15cm}$'''1100'''$\hspace{0.05cm}.$

			[[Datei:P_ID2423__Inf_T_2_3_S4c_neu.png\|right\|frame\|Zur Fehlerfortpflanzung der Huffman–Codierung]]


	Die Quellensymbolfolge  $\rm ADABD$...  (siehe Grafik) wird somit durch die Codesymbolfolge  '''0'100'0'111'100' '''...  dargestellt.  Die Hochkommata dienen hierbei lediglich der Orientierung für den Leser.		Die Quellensymbolfolge  $\rm ADABD$...  (siehe Grafik) wird somit durch die Codesymbolfolge  '''0'100'0'111'100' '''...  dargestellt.  Die Hochkommata dienen hierbei lediglich der Orientierung für den Leser.

	~~[[Datei:P_ID2423__Inf_T_2_3_S4c_neu.png\|center\|frame\|Zur Fehlerfortpflanzung der Huffman–Codierung]]~~

	Bei der Übertragung wird nun das erste Bit verfälscht:  Anstelle von  '''01000111100'''...  empfängt man somit  '''11000111100'''...		Bei der Übertragung wird nun das erste Bit verfälscht:  Anstelle von  '''01000111100'''...  empfängt man somit  '''11000111100'''...
Zeile 245:		Zeile 246:

	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Beispiel 6:}$  Gegeben sei eine gedächtnislose Binärquelle $(M = 2)$ mit den Symbolen  $\{$ $\rm X$,  $\rm Y~~$ $~~\}$:		$\text{Beispiel 6:}$  Gegeben sei eine gedächtnislose Binärquelle  $(M = 2)$  mit den Symbolen  $\{$ $\rm X$,  $\rm Y \}$:
	*Die Symbolwahrscheinlichkeiten seien  $p_{\rm X} = 0.8$  und  $p_{\rm Y} = 0.2$.		*Die Symbolwahrscheinlichkeiten seien  $p_{\rm X} = 0.8$  und  $p_{\rm Y} = 0.2$.
	*Damit ergibt sich die Quellenentropie zu  $H = 0.722$  bit/Quellensymbol.		*Damit ergibt sich die Quellenentropie zu  $H = 0.722$  bit/Quellensymbol.

← Nächstältere Version		Version vom 24. Januar 2020, 19:27 Uhr
Zeile 223:		Zeile 223:


	==Anwendung der Huffman–Codierung auf $k$–Tupel ==		==Anwendung der Huffman–Codierung auf  $k$–Tupel ==
	<br>		<br>
	Der Huffman–Algorithmus in seiner Grundform liefert dann unbefriedigende Ergebnisse, wenn		Der Huffman–Algorithmus in seiner Grundform liefert dann unbefriedigende Ergebnisse, wenn
	*eine Binärquelle $(M = 2)$ vorliegt, zum Beispiel mit dem Symbolvorrat $\{$ $\rm X$, $\rm Y$ $\}$,		*eine Binärquelle  $(M = 2)$  vorliegt, zum Beispiel mit dem Symbolvorrat  $\{$ $\rm X$,  $\rm Y$ $\}$,
	*es statistische Bindungen zwischen den Symbolen der Eingangsfolge gibt,		*es statistische Bindungen zwischen den Symbolen der Eingangsfolge gibt,
	*die Wahrscheinlichkeit des häufigsten Symbols deutlich größer ist als $50\%$.		*die Wahrscheinlichkeit des häufigsten Symbols deutlich größer ist als  $50\%$.


	Abhilfe schafft man in diesen Anwendungsfällen,		Abhilfe schafft man in diesen Anwendungsfällen,
	*in dem man mehrere Symbole zusammenfasst, und		*in dem man mehrere Symbole zusammenfasst, und
	*den Huffman–Algorithmus auf einen neuen Symbolvorrat $\{$ $\rm A$, $\rm B$, $\rm C$, $\rm D$, ... $\}$ anwendet.		*den Huffman–Algorithmus auf einen neuen Symbolvorrat  $\{$ $\rm A$,  $\rm B$, $\rm C$,  $\rm D$, ... $\}$  anwendet.


	Bildet man $k$–Tupel, so steigt der Symbolumfang von $M$ auf $M\hspace{-0.~~03cm~~}′ = M^k$.		Bildet man  $k$–Tupel, so steigt der Symbolumfang von  $M$  auf  $M\hspace{-0.01cm}′ = M^k$.

	Wir wollen im folgenden Beispiel die Vorgehensweise anhand einer Binärquelle verdeutlichen. Weitere Beispiele finden Sie in		Wir wollen im folgenden Beispiel die Vorgehensweise anhand einer Binärquelle verdeutlichen.  Weitere Beispiele finden Sie in
	*der [[Aufgaben:Aufgabe_2.7:_Huffman-Anwendung_für_binäre_Zweiertupel\|Aufgabe 2.7]],		*der  [[Aufgaben:Aufgabe_2.7:_Huffman-Anwendung_für_binäre_Zweiertupel\|Aufgabe 2.7]],
	*der [[Aufgaben:Aufgabe_2.7Z:_Huffman-Codierung_für_Zweiertupel_einer_Ternärquelle\|Aufgabe 2.7Z]] und		*der  [[Aufgaben:Aufgabe_2.7Z:_Huffman-Codierung_für_Zweiertupel_einer_Ternärquelle\|Aufgabe 2.7Z]] und
	*der [[Aufgaben:Aufgabe_2.8:_Huffman-Anwendung_bei_einer_Markovquelle\|Aufgabe 2.8]].		*der  [[Aufgaben:Aufgabe_2.8:_Huffman-Anwendung_bei_einer_Markovquelle\|Aufgabe 2.8]].


	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Beispiel 6:}$  Gegeben sei eine gedächtnislose Binärquelle $(M = 2)$ mit den Symbolen $\{$ $\rm X$, $\rm Y$ $\}$:		$\text{Beispiel 6:}$  Gegeben sei eine gedächtnislose Binärquelle $(M = 2)$ mit den Symbolen  $\{$ $\rm X$,  $\rm Y$ $\}$:
	*Die Symbolwahrscheinlichkeiten seien $p_{\rm X} = 0.8$  und  $p_{\rm Y} = 0.2$.		*Die Symbolwahrscheinlichkeiten seien  $p_{\rm X} = 0.8$  und  $p_{\rm Y} = 0.2$.
	*Damit ergibt sich die Quellenentropie zu $H = 0.722$ bit/Quellensymbol.		*Damit ergibt sich die Quellenentropie zu  $H = 0.722$  bit/Quellensymbol.
	*Wir betrachten die Symbolfolge $\{\rm XXXYXXXXXXXXYYXXXXXYYXXYXYXXYX\ \text{...} \}$ mit nur wenigen $\rm Y$–Symbolen an den Positionen 3, 13, 14, ...		*Wir betrachten die Symbolfolge  $\{\rm XXXYXXXXXXXXYYXXXXXYYXXYXYXXYX\ \text{...} \}$  mit nur wenigen  $\rm Y$–Symbolen an den Positionen 4, 13, 14, ...


	Der Huffman–Algorithmus kann auf diese Quelle direkt nicht angewendet werden, das heißt, man benötigt ohne weitere Maßnahme für jedes binäre Quellensymbol auch ein Bit. Aber:		Der Huffman–Algorithmus kann auf diese Quelle direkt nicht angewendet werden, das heißt, man benötigt ohne weitere Maßnahme für jedes binäre Quellensymbol auch ein Bit. Aber:
	*Fasst man jeweils zwei binäre Symbole zu einem Zweiertupel $(k = 2)$ entsprechend   $\rm XX$ → $\rm A$,   $\rm XY$ → $\rm B$,   $\rm YX$ → $\rm C$,   $\rm YY$ → $\rm D$   zusammen, so kann man „Huffman” auf die resultierende Folge $\rm ABAACADAABCBBAC$ ... mit $M\hspace{-0.~~03cm~~}′ = 4$ anwenden. Wegen		*Fasst man jeweils zwei binäre Symbole zu einem Zweiertupel  $(k = 2)$  entsprechend   $\rm XX$   →   $\rm A$,   $\rm XY$   →   $\rm B$,   $\rm YX$   →   $\rm C$,   $\rm YY$   →   $\rm D$   zusammen, so kann man „Huffman” auf die resultierende Folge  →   $\rm ABAACADAABCBBAC$ ...  →   mit $M\hspace{-0.01cm}′ = 4$  →   anwenden. Wegen

	:$$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.2cm}p_{\rm B}= 0.8 \cdot 0.2 = 0.16 = p_{\rm C} \hspace{0.05cm}, \hspace{0.2cm}
	p_{\rm D}= 0.2^2 = 0.04$$		p_{\rm D}= 0.2^2 = 0.04$$

	:erhält man   $\rm A$ → '''1''',   $\rm B$ → '''00''',   $\rm C$ → '''011''',   $\rm D$ → '''010'''   sowie		:erhält man   $\rm A$   →   '''1''',   $\rm B$   →   '''00''',   $\rm C$   →   '''011''',   $\rm D$   →   '''010'''   sowie

	:$$L_{\rm M}\hspace{0.~~01cm~~}' = 0.64 \cdot 1 + 0.16 \cdot 2 + 0.16 \cdot 3 + 0.04 \cdot 3 =1.56\,{\rm bit/Zweiertupel} $$		:$$L_{\rm M}\hspace{0.03cm}' = 0.64 \cdot 1 + 0.16 \cdot 2 + 0.16 \cdot 3 + 0.04 \cdot 3 =1.56\,{\rm bit/Zweiertupel} $$

	:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.~~01cm~~}'}/{2} = 0.78\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$		:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.03cm}'}/{2} = 0.78\ {\rm bit/Quellensymbol}\hspace{0.05cm}.$$

	*Nun bilden wir Dreiertupel $(k = 3)$ entsprechend		*Nun bilden wir Dreiertupel  $(k = 3)$  →   entsprechend
	:      $\rm XXX$ → $\rm A$,   $\rm XXY$ → $\rm B$,   $\rm XYX$ → $\rm C$,   $\rm XYY$ → $\rm D$,   $\rm YXX$ → $\rm E$,   $\rm YXY$ → $\rm F$,   $\rm YYX$ → $\rm G$,   $\rm YYY$ → $\rm H$.		:      $\rm XXX$   →   $\rm A$,   $\rm XXY$   →   $\rm B$,   $\rm XYX$   →   $\rm C$,   $\rm XYY$   →   $\rm D$,   $\rm YXX$   →   $\rm E$,   $\rm YXY$   →   $\rm F$,   $\rm YYX$   →   $\rm G$,   $\rm YYY$   →   $\rm H$.

	:Für die oben angegebene Eingangsfolge kommt man zur äquivalenten Folge $\rm AEBAGADBCC$ ... (basierend auf dem neuen Symbolumfang $M\hspace{-0.~~03cm~~}′ = 8$) und zu folgenden Wahrscheinlichkeiten:		:Für die oben angegebene Eingangsfolge kommt man zur äquivalenten Folge  $\rm AEBAGADBCC$ ...  (basierend auf dem neuen Symbolumfang $M\hspace{-0.01cm}′ = 8$) und zu folgenden Wahrscheinlichkeiten:

	:$$p_{\rm A}= 0.8^3 = 0.512 \hspace{0.05cm}, \hspace{0.5cm}p_{\rm B}= p_{\rm C}= p_{\rm E} = 0.8^2 \cdot 0.2 = 0.128\hspace{0.05cm},\hspace{0.5cm}		:$$p_{\rm A}= 0.8^3 = 0.512 \hspace{0.05cm}, \hspace{0.5cm}p_{\rm B}= p_{\rm C}= p_{\rm E} = 0.8^2 \cdot 0.2 = 0.128\hspace{0.05cm},\hspace{0.5cm}
Zeile 272:		Zeile 272:

	:Die Huffman–Codierung lautet somit:		:Die Huffman–Codierung lautet somit:
	:      $\rm A$ → '''1''',   $\rm B$ → '''011''',   $\rm C$ → '''010''',   $\rm D$ → '''00011''',   $\rm E$ → '''001''',   $\rm F$ → '''00010''',   $\rm G$ → '''00001''',   $\rm H$ → '''00000'''.		:      $\rm A$   →   '''1''',   $\rm B$   →   '''011''',   $\rm C$   →   '''010''',   $\rm D$   →   '''00011''',   $\rm E$   →   '''001''',   $\rm F$   →   '''00010''',   $\rm G$   →   '''00001''',   $\rm H$   →   '''00000'''.
	:Damit erhält man für die mittlere Codewortlänge:		:Damit erhält man für die mittlere Codewortlänge:

	:$$L_{\rm M}\hspace{0.~~01cm~~}' = 0.512 \cdot 1 + 3 \cdot 0.128 \cdot 3 + (3 \cdot 0.032 + 0.008) \cdot 5 =2.184 \,{\rm bit/Dreiertupel} $$		:$$L_{\rm M}\hspace{0.03cm}' = 0.512 \cdot 1 + 3 \cdot 0.128 \cdot 3 + (3 \cdot 0.032 + 0.008) \cdot 5 =2.184 \,{\rm bit/Dreiertupel} $$

	:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.~~01cm~~}'}/{3} = 0.728\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$		:$$\Rightarrow\hspace{0.3cm}L_{\rm M} = {L_{\rm M}\hspace{0.03cm}'}/{3} = 0.728\ {\rm bit/Quellensymbol}\hspace{0.05cm}.$$

	:In diesem Beispiel wird also bereits mit $k = 3$ die Quellenentropie $H = 0.722$ bit/Quellensymbol nahezu erreicht.}}		:In diesem Beispiel wird also bereits mit  $k = 3$  die Quellenentropie  $H = 0.722$  bit/Quellensymbol nahezu erreicht.}}