Information und Kommunikation
Hartmut KlauckUniversität Frankfurt
SS 0730.4.
Information & Kommunikation 5
2
Huffman Coding
• Wir beschreiben nun eine einfache Prozedur, die einen optimalen präfixfreien Code ermittelt.
• Wir beginnen mit einem Beispiel
Information & Kommunikation 5
3
Huffman Coding, Beispiel
• Wir wollen X binär kodieren, X nehme Werte 1,2,3,4,5 an mit Wahrscheinlichkeiten0.25,0.25,0.2,0.15,0.15
• Die längsten Codeworte sollten für 4 und 5 verwertet werden
• Beobachtung: die größte Codewortlänge kommt mindestens 2 mal vor
• Wir kombinieren nun 4 und 5 in ein neues Symbol mit Wahrscheinlichkeit 0.3
• Dieses Verfahren iterieren wir• Nachdem nur noch zwei Symbole übrig sind,
vergeben wir rückwärts Codeworte
Information & Kommunikation 5
4
Huffman Coding, Beispiel
Information & Kommunikation 5
5
Huffman Coding, Beispiel
• Wir konstruieren nun eine ternären Code
• Es ist zu beachten, dass wir eventuell Dummy Symbole verwenden müssen, wenn wir nicht 3 Symbole verschmelzen können
Information & Kommunikation 5
6
Huffman Coding, Beispiel
Information & Kommunikation 5
7
Huffman Coding
• Der Algorithmus für Huffman Coding ist ein greedy Algorithmus.
• In jedem Schritt werden die D unwahrscheinlichsten Symbole zusammengefasst
• Wir betrachten dies als die Konstruktion eines Baumes von Codeworten
• Wir beginnen mit m Blättern, deren Wahrscheinlichkeiten durch p(i) gegeben sind.
Information & Kommunikation 5
8
Huffman Coding
• Als Datenstruktur verwenden wir einen Heap (oder eine andere priority queue) mit den folgenden Operationen:– MakeHeap: Erzeugt einen Heap mit m
Elementen, Zeit O(m)– ExtractMin: Entfernt (und gibt uns) das
Element mit minimalem Schlüssel aus dem Heap, Zeit O(log m)
– Insert: Fügt ein neues Element in den Heap ein, Zeit O(log m)
Information & Kommunikation 5
9
Huffman Coding• Zu Beginn werden alle Blätter in einen Heap eingefügt (Zeit
O(m))– In jedem Schritt wird der Heap um D-1 Blätter verkleinert– Wir brauchen daher genügend dummy-Blätter, damit
insgesamt D+(D-1)k Blätter (für ein k) vorhanden sind– Dummies haben p(i)=0
• In jedem Schritt werden nun D Extract-Min Operationen ausgeführt, und die erhaltenen D Knoten werden zu Kindern eines neuen Knoten
• Der neue Knoten wird mit der addierten Gesamtwahrscheinlichkeit der Kinder in der Heap eingefügt
• Dies wird iteriert, bis ein einzelner Baum entstanden ist (d.h. der Heap leer ist)
• Die Baumkanten werden an jedem Knoten mit dem Alphabet bezeichnet, und die Codeworte ergeben sich entlang der Wege von der Wurzel zu den Blättern
Information & Kommunikation 5
10
Huffman Coding
• Laufzeit:– Insgesamt gibt es so O(m/D) viele Insert
Operationen und O(m) viele Extract-Min Operationen
– Insgesamt Laufzeit O(m log m)
Information & Kommunikation 5
11
Huffman Coding• Optimalität: Wir wollen zeigen, dass Huffman
Codes die minimale erwartete Codewortlänge haben unter allen Präfixcodes
• D.h. p(i)li ist minimal• Wir nehmen an, dass p(1)¸ … ¸ p(m)• Wir betrachten der Einfachheit halber nur binäre
Codes• Lemma 5.1
– Für jede Verteilung p gibt es einen optimalen präfixfreien Code über {0,1} mit den folgenden Eigenschaften:1. Wenn p(j)>p(k), dann lj· lk2. Die zwei längsten Codeworte haben dieselbe Länge3. Die zwei unwahrscheinlichsten Symbole m-1,m haben
Codeworte maximaler Länge, die sich nur im letzten Bit unterscheiden
Information & Kommunikation 5
12
Beweis
• Wir betrachten einen optimalen Code C, und ändern diesen schrittweise ab
• 1) Angenommen p(j)>p(k) aber lk<lj:Wir tauschen die Codeworte von k und j und erhalten einen Code C‘– 0·L(C‘)-L(C) (da C optimal)
=i p(i)li - i p(i)l‘i
=p(j)lk + p(k)l(j) - p(j)lj - p(k)lk=(p(j)-p(k)) (lk-lj)
– Da p(j)-p(k)>0 erhalten wir einen Widerspruch wenn lk<lj und es muss lk¸li gelten.
Information & Kommunikation 5
13
Beweis
• 2) Angenommen, die längsten zwei Codeworte C(j), C(k) in C haben nicht die gleiche Länge– Wir entfernen das letzte Bit des längeren
Wortes C(k). Dies ergibt einen neuen Code, der immer noch präfixfrei ist
– Wir wiederholen dies, bis j und k gleichlange Codeworte haben
– Da die erwartete Codewortlänge sinkt, gilt die Eigenschaft bereits in C
Information & Kommunikation 5
14
Beweis• 3) Die zwei unwahrscheinlichsten Symbole m-1,m
haben Codeworte maximaler Länge, die sich nur im letzten Bit unterscheiden– Diese Eigenschaft gilt nicht in jedem optimalen Code– Wir konstruieren eine optimalen Code mit dieser
Eigenschaft• Wenn es ein längstes Codewort C(k) gibt, dessen Bruder im
Codewortbaum (C(k) mit dem letzten Bit geflipt) kein Codewort ist, dann kann C(k) um 1 Bit gekürzt werden
• Dies kann nicht sein, da Optimalität verletzt wäre• Jedes maximal lange Codewort in C hat als einen Bruder
der ebenfalls Codewort ist.• Die Symbole, die Codeworte der maximalen Länge haben,
können ihre Codes beliebig austauschen, ohne die Optimalität zu verletzen
• Wenn C(m-1) nicht bereits der Bruder von C(m) ist, können wir C(m-1) mit dem Bruder von C(m) tauschen.
Information & Kommunikation 5
15
Optimalität
• Theorem 5.2– Binäre Huffman Codes sind optimal
• Beweis:– Durch Induktion über m, die Anzahl der zu
kodierenden Worte– Induktionsanfang ist trivial (m=2)– Für gegebenes m>2 und eine beliebige
Verteilung p auf {1,…,m} fassen wir die zwei unwahrscheinlichsten Symbole m-1,m zusammen, und erhalten eine Verteilung p‘ auf {1,…,m-1} mit p‘(m-1)=p(m-1)+p(m) und p‘(i)=p(i) sonst
– Per Induktion ist ein Huffman Code C‘ für p‘ optimal
Information & Kommunikation 5
16
Optimalität
• Wir erzeugen Code Huffman Code C für p: C(i)=C‘(i) für 1· i· m-2C(m-1)=C‘(m-1)±0 und C(m)=C‘(m-1)±1
• Angenommen, Codes C,C‘ unterscheiden sich nur darin, dass in C ein Knoten wie oben „expandiert“ ist.
• Dann gilt: L(C)-L(C‘)=i p(i)li - i p‘(i)l‘i
=(p(m-1)+p(m))(l‘m-1+1) - (p(m-1)+p(m)) l‘m-1 = p(m-1)+p(m)• Behauptung: C ist optimal
– Angenommen es gäbe einen Code C‘‘ für p, mit L(C‘‘)<L(C)– Wir ändern C‘‘ so ab, dass m-1 und m Geschwister sind, und längste
Codewortlänge in C‘‘ haben (wie in 5.1)– Wir ersetzen m-1 und m durch ihren Vaterknoten, und erhalten einen
Code C‘‘‘ für p‘– L(C‘‘‘)¸ L(C‘) per Induktion
– L(C‘‘)=L(C‘‘‘)+p(m-1)+p(m) wie oben¸ L(C‘)+p(m-1)+p(m)=L(C). Widerspruch!
Information & Kommunikation 5
17
Kanäle und Kapazitäten
• Wir wollen nun das Kanalmodell in der Informationstheorie genauer betrachten
• Definition 5.3– Ein Kanal mit Eingabealphabet X and
Ausgabealphabet Y ist durch eine Matrix M(x,y)=p(y|x) gegeben, die bedingten Wahrscheinlichkeiten von y gegeben x
– y p(y|x)=1 für alle x
• Ein Kanal heisst gedächtnislos, wenn p nicht von vorherigen Eingaben abhängt
Information & Kommunikation 5
18
Kanalkapazitäten
• Wenn wir eine Verteilung p(x) auf dem Eingabealphabet X betrachten, ergibt sich eine Verteilung p(x,y)=p(x)¢p(y|x) mit der Matrix des Kanals. X, Y fassen wir auch als Zufallsvariablen auf.
• Definition 5.4Die Kapazität eines gedächtnislosen Kanals ist durch
C=maxp(x) I(X:Y) gegeben, wobei p(x) über alle Verteilungen auf X läuft.
• Wir werden die Kanalkapazität charakterisieren durch die Anzahl Bits, die pro Benutzung des Kanals „sicher“ übertragen werden können.
Information & Kommunikation 5
19
Beispiele
• 1) Der fehlerlose binäre Kanal– 0 wird als 0 übertragen, 1 als 1– Matrix:
– Die Kapazität wir maximiert durch p(0)=p(1)=1/2.
– Es gilt C=I(X:Y)=H(X)=1
Information & Kommunikation 5
20
Beispiele
• 2) Kanal mit nichtüberlappenden Ausgaben:
– C=I(X:Y)=1 für X uniform
– Der Kanal ist in Wirklichkeit fehlerfrei
Information & Kommunikation 5
21
Beispiele
• 3) „Schreibmaschinenkanal“– Jedes Zeichen i aus {1,…,m} wird mit
Wahrscheinlichkeit 1/2 auf i und 1/2 auf i+1 mod m abgebildet
– Wir können m/2 Symbole fehlerfrei abbilden, also ist die Kapazität mindestens log (m/2)
Information & Kommunikation 5
22
Beispiele
• 4) Binärer symmetrischer Kanal– Matrix:
– I(X:Y)=H(Y)-H(Y|X)=H(Y)-x p(x) H(Y|X=x)
=H(Y)-x p(x) H(p)
=H(Y)-H(p) · 1-H(p)– Wenn X uniform verteilt ist, gilt H(Y)=1 und
somit C=I(X:Y)=1-H(p)