 |
Codierung mit variabler Wortlänge "Vom schweigsamen König, der gern Schweinebraten aß" (Frei nach: Walter R. Fuchs: Knaur's Buch der Denkmaschinen, 1968) In einem fernen Land lebte vor langer, langer Zeit ein kleiner König, der war dick faul und unzufrieden und wollte den lieben langen Tag immer nur essen. Wir wollen hier nur seine Nahrungs- gewohnheiten betrachten - insbesondere, da seine Ernährung recht einseitig war. Den lieben langen Tag aß er nur: (1) Schweinebraten,
(2) Schokoladenpudding,
(3) Essiggurken,
(4) Erdbeertorte.
Zudem war der König sehr maulfaul und mit der Zeit wurde es ihm sogar zu anstrengend, seine Bestellungen aufzugeben (die er sowieso im Telegrammstil kundtat: "Braten, Torte, Gurken"). Eines Tages beschloß er, eine Codierung zu entwickeln, mit der er seine Befehle auch loswurde, ohne den Mund aufzutun. Durch Zufall wurde es sogar eine Binärcodierung:
| Die rechte Hand ein wenig heben heiße: | | Schweinebraten |
| Die linke Hand etwas heben heiße: | | Schokopudding |
| Erst die rechte und dann die linke Hand heben: | | Gurken |
| Zweimal nacheinander die rechte Hand heben: | | Erdbeertorte |
Der Übersichtlichkeit halber wollen wir die Codierung etwas abkürzen.
"R" steht für "rechte Hand heben" und "L"
für "linke Hand heben". Dann ergibt sich folgende Codezuordnung:
R Braten
L Pudding
RL Gurken
RR Torte
Und schon gab es Probleme. Angenommen der König hob dreimal die
rechte Hand (--> RRR). Dann konnte dies bedeuten:
Braten, Braten, Braten oder
Braten, Torte oder
Torte, Braten
Nun mußte der König einmal wirklich viel reden. Er rief seinen
Hofmathematikus zu sich und erklärte den Sachverhalt. "Hmmmm"
überlegte dieser: "Majestät haben Höchstdero Speisewünsche
binär codiert. Vorzüglich, Vorzüglich." "Aber es klappt nicht",
raunzte der König,"jedesmal, wenn ich Schweinebraten und Pudding will,
bringen diese Hornochsen mir Gurken!" und er sank erschöpft auf
seinen Thron zurück. "Mit Verlaub, die Codierung ist nicht ein-
deutig, Majestät", wagte der Mathematikus einzuwerfen. "Ich weiß!
Laß Dir gefälligst was einfallen!" grunzte der König. Und
vor lauter Angst, wieder etwas Falsches zu bekommen, brüllte er:
"Braten und Torte, aber fix!".
Der Mathematiker brütete inzwischen über eine eindeutige binäre
Codierung nach und gelangte zu folgenden Überlegungen:
- Es sind vier Worte binär zu codieren, also brauche ich eine
Codewortlänge von mindestens 2 Binärzeichen.
- Die Codierung der vier Speisewünsche sah folgendermaßen aus:
Braten RR
Pudding RL
Gurken LR
Torte LL
Nun war die Codierung unverwechselbar. Die Zeichenfolge
"LRRLLLRRRRLL" konnte nur noch bedeuten: Gurken, Pudding, Torte,
2 x Braten, Torte.
Zwar war die Codierung eindeutig, aber war sie auch optimal? Bisher wurde
davon ausgegangen, daß der König keine spezielle Vorliebe
für bestimmte Gerichte hat (alle Codewörter sind gleich
wahrscheinlich). Zudem beschwerte sich der König schon nach kurzer
Zeit darüber, daß er viel zu häufig die Hände heben müsse.
Also vergatterte der Mathematikus seinen Assistenten, eine Statistik
der königlichen Essenswünsche aufzustellen. Heraus kam folgendes.
Jeden Tag verspeiste der König im Schnitt 18 Gerichte.
Die Häufigkeitsverteilung stellte sich so dar:
9 x Schweinebraten,
6 x Schokopudding,
1 x Gurken,
2 x Erdbeertorte.
Soll die Codierung optimal, also eindeutig und zweckmäßig sein,
mußte der Matehmatikus versuchen, für den Braten einen möglichst
kurzen Code zu wählen. Dafür darf der Code für eine Grurkenbestellung
ruhig länger sein. Also legte er erst einmal fest:
Braten --> R
Damit ist das "R" 'verbraucht', denn es darf wegen der Eindeutigkeit
kein Codewort mehr mit "R" beginnen (Fano-Bedingung: Kein
Code darf der Beginn eines anderen verwendeten Codes sein). Weiter geht es mit:
Pudding --> LR
Es bleibt somit noch ein zweistelliges Codewort übrig (LL, denn
RR und RL sind wegen der Fano-Bedingung 'verboten'), aber es sind
noch zwei Speisewünsche zu codieren. Also müssen die nächsten
Codes dreistellig sein. Unter Beachtung der Eindeutigkeit ergibt sich:
Torte --> LLR
Gurken --> LLL
wahlweise auch:
Torte --> LLL
Gurken --> LLR
Ist diese Codierung nun wirklich besser, d. h. kürzer? Beim alten
Code benötigte der König für 18 Gerichte 36 bit. Nun sieht es bei
der oben genannten Häufigkeitsverteilung folgendermaßen aus:
9 x Schweinebraten 9 bit
6 x Schokopudding 12 bit
1 x Gurken 3 bit
2 x Erdbeertorte 6 bit
---------
Summe 30 bit
Es wurden also durchschnittlich 6 bit pro Tag gespart. Probieren
wir zum Schluß der Geschichte aus, ob es klappt. Was will der
König bei "LRRRLLR"? Da die Codewortlänge variiert, muß man
schrittweise vorgehen. Das erste "L" bedeutet noch nichts. "LR"
heißt eideutig "Pudding". Dann kommt "R" für "Braten"
und gleich noch einer. Wieder ein "L", das noch nichts besagt. Auch das
folgende "L" liefert noch keine Lösung. Erst das letzte "R"
gibt Aufschluß: "Torte!".
Mathematischer Hintergrund:
Oben war von "Häufigkeiten" die Rede. Es handelt sich dabei um
Erfahrungswerte, die durch Beobachtung gewonnen werden (empirische
Werte). Die empirischen Häufigkeitswerte müssen zu den theoretischen
Wahrscheinlichkeiten in klare Beziehung gebracht werden. Wir wissen
alle, daß beim Münzwurf die Wahlscheinlichkeit
für Kopf oder Zahl jeweils 1/2 beträgt. Um durch empirische
Ermittlung auf die exakte Übereinstimmung zwischen Häufigkeiten
und Wahrscheinlichkeit zu kommen, müßte man unendlich viele Würfe
auswerten. Die praktische Regel der Wahrscheinlichkeitsrechnung
erspart uns Zeit, denn sie besagt, daß sich bei genügend vielen
Versuchen die Häufigkeit eines Ereignisses nur noch sehr wenig
von der Wahrscheinlichkeit für das Eintreten dieses Ereignisses
unterscheidet. Es gilt:
Führt eine n-malige Verwirklichung der geforderten Bedingung in m
Fällen zum zufälligen Ereignis A, dann liegt die Häufigkeit h(A)
= m/n beliebig nahe an der Wahrscheinlichkeit P(A).
Jetzt können wir die Ergebnisse unseres Märchens aufarbeiten. An
der königlichen Tafel sind vier zufällige Ereignisse bedeutsam:
A1: Der König bestellt Braten
A2: Der König bestellt Pudding
A3: Der König bestellt Torte
A4: Der König bestellt Gurken
Auch die Häufigkeiten sind bekannt. Wir nehmen an, daß die Werte
auf genügend vielen Beobachtungen beruhen. Also können wir die
Wahrscheinlichkeiten durch die Häufigkeiten annähern:
P(A1) = 9/18 = 1/2
P(A2) = 6/18 = 1/3
P(A3) = 2/18 = 1/9
P(A4) = 1/18 = 1/18
Die Summe aller Wahrscheinlichkeiten P(A1) + P(A2) + P(A3) +
P(A4) ergibt immer den Wert 1.
Betrachten wir nun den König als Nachrichtenquelle. Seine Nachrichten
sind A1, A2, A3 und A4. Die oben erwähnten Wahrscheinlichkeiten
stellen zusammen mit den zugehörigen Nachrichten das
Bild einer (sehr abstrakten) Nachrichtenquelle dar. Die Nachricht
A1 hat eine relativ hohe, die Nachricht A4 eine relativ geringe
Wahrscheinlichkeit. Mit anderen Worten: A1 dürfte in einer
Nachrichtenfolge öfter auftauchen als A4 (wobei nichts über die
Position von A1 ausgesagt werden kann). Damit können wir auch den
Informationsgehalt definieren:
Je kleiner die Wahrscheinlichkeit des Auftretens einer Nachricht
ist, desto höher ist ihr Informationsgehalt. Als Formel:
I(A) = ld( 1/P(A) ) [bit]
Wenden wir nun diese Formel auf die Nachrichten A1 bis A4 an:
I(A1) = ld( 1/(1/2) ) = ld(2) = 1,000 bit
I(A2) = ld( 1/(1/3) ) = ld(3) = 1,585 bit
I(A3) = ld( 1/(1/9) ) = ld(9) = 3,170 bit
I(A4) = ld( 1/(1/18) ) = ld(18) = 4,170 bit
Nun besitzen wir präzise Zahlenwerte über den Informationsgehalt
der einzelnen Nachrichten. Das Maß für die Unsicherheit darüber,
welche Nachricht nun als nächste in einer Folge kommt, ist die
"mittlere Information" (oder Entropie) H:
H(A1, ..., An) = Summe(P(Ai) * ld(1/P(Ai))) für i=1 ... n
Für unser Königs-Ernährungsproblem ergibt sich:
H = 1,000/2 + 1,585/3 + 3,170/9 + 4,170/18 = 1,614 bit
Dieser Wert sagt uns aber noch nicht viel; wir brauchen Vergleichswerte.
Betrachten wir nun die binär codierten Essenswünsche,
die ja nur noch aus den Zeichen "R" und "L" bestehen.
Zunächst die erste Codierung mit jeweils zwei bit für jedes Codewort
(man schreibe einfach die Codes entsprechend obiger Häufigkeiten
auf und zähle die "R"s und "L"s):
P(R) = 25/36 --> H1(R,L) = 0,883 bit
P(L) = 11/36
Nun sehen wir uns die optimierte Codierung mit unterschiedlicher
Länge der Codeworte an:
P(R) = 17/30 --> H2(R,L) = 0,988 bit
P(L) = 13/30
Also trägt hier jedes Signal mehr Information.
Coderedundanz
Dank der bisher erarbeiteten Formeln läßt sich diese auch nun
exakt berechnen. Alle bisherigen Beispiele zeigen, daß durch die
Codierung im Mittel mindestens soviele Binärstellen m verwendet
werden müssen, wie durch den mittleren Informationsgehalt H berechnet werden.
Es gilt also immer: H <= m.
Es läßt sich aber für eine bestimmte aufgabe ein Code finden, für
den H beliebig nahe an m liegt. Zur Informationstheoretischen
Beurteilung der Eigenschaften von Codes dient die Redundanz:
absolute Redundanz relative Redundanz:
R = m - H r = (m - H)/m = R/m
Wie sieht das für unseren stets hungrigen König aus?
(1) Code mit fester Wortlänge 2:
H = 1,614 bit R = 2 - 1,614 = 0,386
m = 2 bit r = 0,386/2 = 0,193 = 19,3%
(2) Code mit variabler Wortlänge:
H = 1,614 bit R = 1,722 - 1,614 = 0,108
m = 1,722 bit r = 0,108/1,722 = 0,063 = 6,3%
Fassen wir zusammen. Das Shannonsche Codierungstheorem besagt:
- es eine untere Grenze für die mittlere Codewortlänge gibt
- die Redundanz eines Codes beliebig klein werden kann
Die zweite Behauptung impliziert auch, daß es nicht den optimalen
Code gibt, sondern nur einen relativ besten.
Wir haben gesehen, daß Codes redundant sein können. Formelmäßig
läßt sich das Maß für die Redundanz eines Codes allgemein
folgendermaßen festlegen:
absolute Redundanz relative Redundanz:
R = m - H r = (m - H)/m = R/m
m = mittlere Codewortlänge
H = Informationsgehalt
Sind alle Codewörter gleich lang, gilt:
absolute Redundanz relative Redundanz:
R = ld(M) - ld(n) r = (ld(M) - ld(n))/ld(M)
= R/ld(M)
M = Anzahl der möglichen Codewörter
n = Anzahl der verwendeten Codewörter
Beispiel: tetradische Codes (Darstellung der Ziffern 0 bis 9)
Der Informationsgehalt I = ld(10) ist 3,32 bit. Wir müssen also
Codeworte von 4 bit Länge verwenden. Mit 4 bit können jedoch 16
Codeworte dargestellt werden, wir haben also 10 Nutzbits und 6
Pseudoworte. Die Redundanz ergibt sich zu: Rc = 4 - ld(10) = 4 - 3,32
= 0,68 und rc = 0,68 / 4 = 0,17 --> 17%.
Der Morsetelegraph hatte einen dreiwertigen Code (Punkt, Strick, Leerraum)
und variable Codelänge
|
|
|
DIENSTE
