Die Codierungsmethode von Shannon und Fano

 

Thomas Fischer

09.01.1995

 

 

 

 

 

 

 

 

 

1 Einleitung

 

2 Theoretischer Hintergrund

 

3 Codierungsmethode nach Shannon und Fano

 

4 Ein Beispiel

 

5 Alphabetischer Code

 

6 Das 12-Kugel Problem

 

  1. Das herkömmliche Verfahren
  2.  

  3. Ein alternatives Verfahren

 

7 Schluß

 

 

1 Einleitung

 

Im Rahmen des Seminars "Informationstheorie" habe ich mich mit dem 9. Kapitel des Buches "Informationstheorie" von F. Topsoe (1974, Teubner Stuttgard) beschäftigt. Meine Ausarbeitung zur Codierungmethode nach Shannon und Fano hat dieses Kapitel zur Grundlage. Die ersten 8 Kapitel des Buches habe ich vorrausgesetzt, allerdings wiederhole ich die wichtigsten Inhalte der ersten 8 Kapitel kurz.

Alle Gleichungen habe ich mit derselben Nummerierung versehen wie im Buch, auch jegliche Seitenzahlangabe bezieht sich auf das Buch, so daß das Nachschlagen erleichtert wird.

 

Der Abschnitt 6.2 basiert auf meinen eigenen Überlegungen und befaßt sich mit dem 12-Kugel Problem.

 

 

2 Theoretischer Hintergrund

 

Ich will zunächst die wichtigsten Inhalte der ersten 8 Kapitel des Buches "Informationstheorie", auf die ich zurückgreifen muß, zusammenfassen.

 

Die Entropie eines Versuches F wird mit H(F) bezeichnet. Sie ist ein Maß für den Grad der Unbestimmtheit eines Versuches. Die Klasseneinteilung (A1, ... ,An) des Ergebnisraumes eines Versuches und der zugehörige Wahrscheinlichkeitsvektor p=(p1, ... ,pn) mit pi=P(Ai), i=1,...,n charakterisieren einen Versuch F. Deshalb wird auch H(p)=H(p1, ..., pn) geschrieben. Die Entropie der Zufallsvariable X wird entsprechend mit H(X) bezeichnet. Es gilt

 

  1. H(F) = H(p)

Es folgt Satz (Seite 28):

Die Entropie eines Wahrscheinlichkeitsvektors (p1, ..., pn) wird am größten, wenn die Wahrscheinlichkeiten gleich groß sind, d. h.

 

(16)

 

Das Gleichheitszeichen gilt dann und nur dann, wenn pi=1/n " i

 

Als anschauliche Vorstellung kann man sagen, daß die Entropie um so größer ist, je "gleichwahrscheinlicher" die Ereignisse sind.

Durch H(X|Y) wird die bedingte Entropie von X bezüglich Y bezeichnet, d.h. die erwartete Unbestimmtheit von X nach der Beobachtung von Y.

Mit qj =P(Y=yj) gilt:

 

(26) H(X|Y) = qj H(X|Y=yj)

 

Außerdem gilt:

 

  1. H(X, Y) = H(x) + H(Y|X)

 

Als Verallgemeinerung von (29) gilt Satz(Seite 55): Es seien X1, X2, ..., XN zufällige Variable. Dann gilt die Gleichung

 

    1. H(X1,X2,...,XN) = H(X1) +
H(Xr|X1,...,Xr-1)

 

 

Verschiedenen Ereignissen eines Versuches können verschiedene Codewörter zugeordnet werden. Diese bestehen aus Ziffern, z.B. "0" und "1" für einen binären Code

 

Definition eines Codes (Seite 14 ): Es sei A = (A1, ..., An) eine Klasseneinteilung des Ergebnisraumes W . Unter einem Code k von A verstehen wir eine injektive Abbildung, die jedem Ereignis Ai ein Wort k (Ai) Î { Alle endlichen Ziffernfolgen} zuordnet. Wir verlangen ferner, daß keines der Wörter k(A1), ..., k(An) Präfix eines anderen Wortes ist.

 

Die Struktur eines Codes kann durch sogenannte Codebäume veranschaulicht werden. Die Länge eines Wortes m (Anzahl der Ziffern, aus denen m besteht) wird mit |m | bezeichnet.

Definition der mittleren Länge eines Codes (Seite 16): Die mittlere Länge des Codes wird durch E(|k |) bezeichnet und es gilt

E(|k |) =pi × |k (Ai)| mit pi=P(Ai)

 

Die mittlere Länge eines Codes kann man sich anschaulich als die durchschnittliche Anzahl von Fragen vorstellen, die man bei einer entsprechenden Fragestrategie braucht, um den Ausgang eines Versuches zu bestimmen.

Die Huffmansche Codierungsmethode (Kapitel 5) ist von besonderer Bedeutung, da sie einen sogenannten optimalen Code erzeugt.

 

 

3 Codierungsmethode nach Shannon und Fano

 

Ausgangspunkt ist ein Versuch F mit den Ausgängen A1, ... An. Er soll durch die Zufallsvariable X beschrieben werden.

Sei zunächst ein beliebiger Code k mit den Codeworten k(A1),..., k(An) und sei

N:= Max {|k(A1)|,..., |k(An)|} die größte Länge der Codeworte k(A1),..., k(An).

X1, ..., XN seien N Zufallsvariable. Für w Î Ai sei Xr(w ) = r-te Ziffer in k (Ai), wenn |k (Ai)| ³ r,

r=1,...,N.

Der Vektor (X1, ...,XN) nimmt dann n Werte mit derselben Verteilung wie X an.

Daher ist H(X) = H(X1, ..., XN). Aus (40) ergibt sich somit

 

(42) H(x) = H(X1) + H(X2|X1) + ... + H(XN|X1, ..., XN-1)

 

Das Prinzip, das der Codierung von Shannon und Fano zugrunde liegt, besteht nun darin, daß man sich bei der Auswahl jeder Ziffer der Codierung bemüht, die darin enthaltene Menge an Information möglichst groß zu gestalten. Das bedeutet, daß unabhängig vom Wert aller vorhergehenden Ziffern die zu bestimmende Ziffer die für sie möglichen Werte möglichst mit derselben Wahrscheinlichkeit annimmt.

 

Die möglichen Ziffern werden durch die Variable X1, ... XN beschrieben. Die Informationsmenge, die durch die einzelnen Ziffern erhalten wird soll möglichst groß sein, d. h. X1 ,..., XN werden nacheinander so bestimmt, daß das betreffende Glied in (42) zum Maximum gemacht wird. Da dann die Informationsmenge, die aus jeder einzelnen Ziffer gewonnen wird, so groß wie möglich ist, ist davon auszugehen, daß die durchschnittliche Anzahl von Ziffern minimal wird.

 

 

4 Ein Beispiel

 

Ein Versuch sei beschrieben durch die möglichen Ausgänge A1, A2, A3, A4, A5 mit den zugehörigen Wahrscheinlichkeiten P(A1) = 1/2, P(A2) = 3/16, P(A3) = 3/16, P(A4) = 1/16,

P(A5) = 1/16. Es soll ein binärer Code nach der Methode von Shannon und Fano erzeugt werden.

Der erste Schritt besteht darin X1 so zu bestimmen, daß H(X1) maximal wird. Dies entspricht einer Aufteilung der Ereignisse in zwei Teile, von denen der eine aus A1 (X1=0) und der andere aus A2, A3, A4, A5 (X1=1) besteht, da beide Teile gleichwahrscheinlich sind. Nun muß X2 so bestimmt werden, daß H(X2|X1) maximal wird. Es ist H(X2|X1) = P(X1=0) H(X2|X1=0) + P(X1=1) H(X2|X1=1). Also muß X2 so festgelegt werden, daß H(X2|X1=0) und H(X2|X1=0) beide maximal werden. Da X1=0 nur für das eine Ereignis A1 gilt, ist H(X2|X1=0)=0 und X2 braucht bezüglich A1 nicht festgelegt werden. H(X2|X1=1) wird maximal, wenn wir die Ereignisse A2,...,A5 in die beiden Teile A2,A4 (X2=0) und A3,A5 (X2=1) aufteilen, da so beide Teile gleichwahrscheinlich sind. Auf diese Weise muß nur noch X3 festgelegt werden und der Shannon-Fanosche Code ist fertig.

 

Es entsteht also folgender Code, verdeutlicht durch Codebuch und Codebaum:

Ereignis

Wahrscheinlichkeit

Code kShannon

A1

˝

0

A2

3/16

1 0 0

A3

3/16

1 1 0

A4

1/16

1 0 1

A5

1/16

1 1 1

 

 

 

Zum Vergleich erstelle ich nun den zugehörigen Huffmanschen Code:

 

˝ ˝ ˝ ˝

3/16 3/16 5/16 ˝

3/16 3/16 3/16

1/16 2/16

1/16

 

Ereignis

Wahrscheinlichkeit

Code kHuffman

A1

˝

0

A2

3/16

1 0

A3

3/16

1 1 0

A4

1/16

1 1 1 0

A5

1/16

1 1 1 1

 

 

Die mittleren Längen der Codes ergeben

 

E(|kShannon|) = 1 * ˝ + 3 * (3/16 + 3/16 + 1/16 + 1/16) = 2

E(|kHuffman|) = 1 * ˝ + 2 * 3/16 + 3 * 3/16 + 4 * (1/16 + 1/16) = 1,94

 

Es ergibt sich E(|kShannon|) > E(|kHuffman|), d. h., daß der Shannon-Fano-Code nicht optimal sein muß. Allerdings kommt der Shannon-Fano-Code in jedem Fall mit dreistelligen Codewörtern aus, während der Huffman-Code auch vierstellige Codewörter benötigt.

 

 

5 Alphabetischer Code

 

Als alphabetischen Code (Aufgabe 3, Seite 62) bezeichnet man eine Variante der binären Shannon-Fanoschen Methode. Hierbei werden die vorkommenden Wahrscheinlichkeiten zunächst geordnet, so daß p1 ³ p2 ³ ... ³ pn. Danach werden die Wahrscheinlichkeiten in zwei Gruppen zerlegt, die einem Index i entsprechen, für den H(p1 + ... + pi,pi+1+ ...+ pn) maximal wird. In derselben Weise wird fortgefahren.

 

Für P(A1)=40/100, P(A2)=19/100, P(A3)=17/100, P(A4)=12/100, P(A5)=12/100 erstelle ich nun Huffman-,Shannon-Fano- und alphabetischen Code und bestimme die mittleren Codewortlängen.

 

Huffman-Code kHuffmann

 

40/100 40/100 40/100 40/100

19/100 24/100 36/100 60/100

17/100 19/100 24/100

12/100 17/100

12/100

 

Shannon-Fano-Code kShannon

 

 

Alphabetischer Code kalpha

 

 

Ereignis

P(Ai)

kHuffmann

kShannon

kalpha

A1

40/100

0

0 0

0 0

A2

19/100

1 0 0

1 0

0 1

A3

17/100

1 0 1

1 1 0

1 0

A4

12/100

1 1 0

0 1

1 1 0

A5

12/100

1 1 1

1 1 1

1 1 1

 

E(|kHuffmann |) = 1 * 40/100 + 3 * 60/100 = 2,2

E(|kShannon |) = 2 * 71/100 + 3 * 29/100 = 2,29

E(|kalpha |)= 2 * 76/100 + 3 * 24/100 = 2,24

 

6 Das 12-Kugel Problem

 

Das 12-Kugel Problem ist auch als 12-Münzenproblem sehr bekannt, es tritt oft in der Schule schon auf, zumindest aber jede MathematikstudentIn muß sich wohl einmal damit beschäftigen. Ich selbst habe es in meiner Schulzeit als 12-Pillen Problem eines Apothekers kennengelernt.

Es geht darum, daß 12 äußerlich gleichartige Kugeln gegeben sind, von denen jedoch bekannt ist, daß eine von ihnen ein anderes Gewicht hat als die übrigen Kugeln. Man weiß allerdings nicht ob diese Kugel schwerer oder leichter ist als die anderen. Es soll nun mit einer Balkenwaage mit zwei Schalen herausgefunden werden um welche der 12 Kugeln es sich handelt und ob sie schwerer oder leichter ist. Zum Wiegen stehen dabei keine Gewichte zur Verfügung, sondern lediglich die Kugeln selbst. Das Schwierige an der Sache ist nun, daß man das mit nur drei Wägungen schaffen soll.

 

Bei jeder einzelnen Wägung, bei der eine gewisse Anzahl an Kugeln in der rechten und linken Schale liegt, gibt es drei mögliche Ergebnisse. Die linke Schale kann schwerer sein (Bezeichnung: l ), die rechte Schale kann schwerer sein (Bezeichnung: r ) oder sie wiegen gleichviel (Bezeichnung: g ). Jede Kugel i, i=1, ... 12 könnte die gesuchte Kugel sein, außerdem könnte sie schwerer (Bezeichnung: i+) oder leichter (Bezeichnung: i-) sein. Es gibt also 24 mögliche Ausgänge (1+, 1-, 2+, 2-, ..., 12+, 12-), die je die Wahrscheinlichkeit 1/24 haben. Es ist klar, daß man mit 2 Wägungen nicht immer den Ausgang bestimmen kann, denn die Zahl der möglichen Ergebnisse der Wägungen ( [l,l], [l,r], [l,g], ...) ist 3 * 3 < 24.

Wegen 3*3*3 > 24 gibt es einen dreiwertigen Code mit maximaler Codewortlänge 3, der alle 24 Ergebnisse beschreibt. Es geht nun darum einen entsprechenden Wägeprozeß zu finden.

 

 

  1. Das herkömmliche Verfahren

 

Ich werde nun die Methode von Shannon und Fano benutzen, um den Wägeprozeß zu finden. Es geht darum die Zufallsvariable X1, X2, X3 festzulegen, wobei Xi , i=1, 2, 3 die Werte l, r oder g annehmen kann. X1 ist nun so festzulegen, daß H(X1) maximal wird. Dies erreichen wir, wenn die erste Wägung (man könnte im übertragenen Sinn auch sagen: die erste Frage) die 24 möglichen Ausgänge in 3 Gruppen zu 8 Ausgängen teilt. Dann wird nämlich H(X1)=H(8/24, 8/24, 8/24) maximal, wegen der Gleichwahrscheinlichkeit.

Dies erreichen wir, wenn wir bei der ersten Wägung die Kugeln Nr. 1,2,3,4 auf die linke und die Kugeln Nr. 5,6,7,8 auf die rechte Waagschale legen. X1=l reduziert die vorher 24 möglichen Ausgänge auf die 8 mögliche Ausgänge 1+, 2+, 3+, 4+, 5-, 6-, 7-, 8-. Bei X1=r muß einer der 8 Ausgänge 1-, 2-, 3-, 4-, 5+, 6+, 7+, 8+ vorliegen, während bei X1=g einer der 8 Ausgänge 9+, 9-, 10+, 10-, 11+, 11- vorliegen muß.

 

Fall X1=g:

 

X2 soll nun so festgelegt werden, daß H(X2|X1=g) maximal wird. Die 8 Ausgänge 9+, 9-, 10+, 10-, 11+, 11-, 12+, 12- sollen durch die zweite Wägung also wieder in möglichst drei gleichwahrscheinliche Gruppen aufgeteilt werden. 8 läßt sich zwar nicht durch drei teilen, aber der "gleichwahrscheinlichste" Fall ist der, daß die 8 Ausgänge in 3 Gruppen zerlegt werden, von denen 2 aus 3 Ausgängen bestehen und eine aus 2 Ausgängen. In diesem Fall ist die Entropie H(X2|X1=g)=H(3/8, 3/8, 2/8) offensichtlich maximal. Wir erreichen dies, indem wir z.B. die Kugeln Nr. 9, 10, 11 in die linke und drei Kugeln der Nr. 1,2,3,4,5,6,7,8 aus der ersten Wägung (die sind ja alle gleich schwer) in die rechte Waagschale legen. Bei X2=l muß dann 9+, 10+ oder 11+ vorliegen. Bei X2=g liegt 12+ oder 12- vor und bei X2=r muß es sich um 9-, 10- oder 11- handeln. Es ist schon jetzt zu sehen, daß wir den richtigen Ausgang mit der dritten Wägung finden können. Ist X2=g, so wiegen wir Nr. 12 gegen eine der ersten Kugeln Nr. 1,2,3,4,5,6,7,8. Ist X2=l oder X2=r, so wiegen wir Nr. 9 gegen Nr. 10

 

Fall X1=l:

 

Analog zum Fall X1=g geht es nun darum, mit der zweiten Wägung die 8 möglichen Ausgänge 1+, 2+, 3+, 4+, 5-, 6-, 7-, 8- in zwei Gruppen zu 3 Ausgängen und eine Gruppe mit 2 Ausgängen zu teilen, da dann H(X2|X1=l) maximal wird. Es gibt sehr viele Möglichkeiten, das zu erreichen. Ich lege z.B. in die linke Waagschale die Kugeln Nr. 4,5,6,7, in die rechte Waagschale lege ich die Kugel Nr. 8 und drei der Kugeln Nr. 9,10,11,12 (die sind in diesem Fall alle gleich schwer). Im Fall X2=l liegt dann einer der Ausgänge 4+ oder 8- vor. Im dritten Schritt ist dann Nr. 4 gegen eine der Kugeln 9,10,11,12 zu wiegen. Bei X2=g handelt es sich um 1+, 2+ oder 3+, und wir wiegen dann Nr. 1 gegen Nr. 2. Bei X2=r muß es sich um 5-, 6- oder 7- handeln, als nächstes wiegen wir dann Nr. 5 gegen Nr. 6.

 

Fall X1=r:

 

Dieser Fall wird analog zum Fall X1=l behandelt.

 

 

 

6.2 Ein alternatives Verfahren

 

Der eben dargelegte Wägeprozeß scheint zwar irgendwie genial zu sein, allerdings ist er auch sehr umständlich, da jede nächste Wägung davon abhängt, wie die vorhergehende Wägung ausgegangen ist. Anders gesagt handelt es sich doch um eine etwas umständliche Fragestrategie. Es währe schön, wenn ich einfach drei festgelegte Wägungen machen könnte, bei denen die nächste Wägung nicht von der vorhergehenden abhängt. Ich müßte mir einfach das Ergebnis jeder der drei Wägungen (l, r oder g) notieren. Es gibt 27 mögliche 3er-Tupel ([l,l,l], [l,r,l], ...) . Die drei Wägungen müßten so sein, daß jedem der 24 Ausgänge genau ein 3er-Tupel entspricht.

Das funktioniert, allerdings muß dabei folgende Bedingung eingehalten werden:

 

Zwei Kugeln dürfen nie dreimal beide in der gleichen Schale oder dreimal beide genau in gegenüberliegenden Schalen liegen

 

Wenn diese Bedingung nicht erfüllt wird ist es nämlich nicht eindeutig, welche der beiden Kugeln es betrifft, falls es eine der beiden Kugeln betrifft.

 

Folgende drei Wägungen z. B funktionieren, wie sich leicht nachprüfen läßt:

 

  1. Wägung:

 

Nr. 1, 2, 3, 4 gegen Nr. 5, 6, 7, 8

 

  1. Wägung:

 

Nr. 4, 5, 6, 7 gegen Nr. 8, 9, 10, 11

 

  1. Wägung:

 

Nr. 1, 4, 5, 10 gegen Nr. 2, 6, 11, 12

 

 

Wenn z. B die Kugel 1 schwerer ist (Ausgang: 1+) ist der Wägecode (l, g, l) zu erwarten. Bei allen anderen 23 möglichen Ausgängen entsteht ein anderer Wägecode. Wenn Kugel 1 leichter ist bekommen wir das Wägeergebnis (r, g, r). Wenn Kugel 4 leichter ist bekommen wir den Code (r, r, r). Mit Hilfe eines erstellten Codebuches und den oben angegebenen Wägungen kann ich also immer herausfinden um welche Kugel es sich handelt und ob sie leichter oder schwerer ist.

 

 

 

7 Schluß

 

Am Ende stellt sich mir die Frage, welches Codierungsverfahren denn nun zu bevorzugen ist. Diese Frage läßt sich zu diesem Zeitpunkt allerdings nicht klären, da ich keineswegs alle Codierungsmethoden kenne. Klar wurde jedoch, daß ich den Huffman-Code gegenüber Shannon-Fano-Code bevorzugen sollte, wenn ich optimalen Code haben möchte.

Beim 12-Kugel Problem war ich jedoch gezwungen mit maximaler Codewortlänge 3 auszukommen. Beim ersten Beispiel haben wir gesehen, daß die maximale Codewortlänge des Shannon-Fano-Codes kleiner sein kann als die maximale Codewortlänge des Huffman-Codes.

Es ist also zumindest deutlich geworden, daß es praktische Gründe geben kann, bei denen die Codierungsmethode nach Shannon und Fano von Vorteil ist.