|
Quellen
Eine Voraussetzung die wir zu Beginn treffen ist die, daß unter den beliebig vielen Zeichen und Merkmalen die wir betrachten, nur eine endliche Anzahl N von unterscheidbaren Zeichen vorhanden ist (z.B. ein geschriebener Text, der nur aus 30 verschiedenen Zeichen mit Zwischen-räumen und Satzzeichen besteht). Die Anzahl der unterscheidbaren Zeichen wie als Zeichen-vorrat oder Alphabet bezeichnet. Meist treten irgendwelche Zeichen in typischen Kombination-en auftreten. Solche Kombinationen oder Zeichenserien fast man der Einfachheit halber zu einem neuen Zeichen zusammen, das als Superzeichen bezeichnet wird (z.B. folgt nach einem q stets ein u Superzeichen qu). Es können aber auch ganze Wörter als Superzeichen aufgefasst werden. In diesem Fall sind die Buchstaben zeichen und die Wörter Superzeichen. Dies kann man noch weiter Fortsetzen: Mehrere Wörter bilden ganze Sätze, die wiederum Absätze bilden usw. Ein solches Ordnungsschema bezeichnet man als Hierarchie.
Im folgenden soll sunächst nur der Fall interessieren, daß die einzelnen Zeichen keine statist-ische Bindung untereinander haben. Das heißt, daß die Wahrscheinlichkeit für das auftreteneine speziellen Zeichens unabhängig davon Ist, welche anderen Zeichen die Informationsquelle zuvor abgegeben hat.
2.1.1 Informationsgehalt von gleichwahrscheinlichen Zeichen
Betrachtet wird eine Quelle mit einem Zeichenvorrat von N' Zeichen. Die Wahrscheinlichkeit das von diesen Zeichen ein bestimmtes auftritt ist für alle Zeichen gleich. Es ergibt sich somit:
.... Auftrittswahrscheinlichkeit eines bestimmten Zeichens
Der Informationsgehalt H¬e eines beliebigen einzelnen Zeichens wird nun definiert als der Logarithmus des Zeichenvorrats N', oder dem Logarithmus aus der reziproken Wahrschein-lichkeit, wobei die Basis des Logarithmus vorerst offeinbleibt.
.... Informationsgehalt
Hiermit bestätigt sich die vorher getroffene Aussage, wonach ein Zeichen mit der Wahrschein-lichkeit P=1 keinen Informationsgehalt besitzt. Denn setzen wir für P=1 in die Formel für den Informationsgehalt He ein, ergibt dieser null. Die Informationsmenge He eines eher unwahr-scheinlichen Zeichens ist daher sehr groß.
Die Wahrscheinlichkeit für das nacheinanderfolgende Auftreten zweier bestimmter Zeichen ergibt sich aus dem Produkt der einzelnen Wahrscheinlichkeiten. Da in unserem Beispiel die Wahrscheinlichkeit für jedes Zeichen groß ist ergibt sich P2. Damit ergibt sich auch der doppelte Informationsgehalt. Somit ergeben x Zeichen den x-fachen Informationsgehalt. Es ist auch ersichtlich und logisch, daß der Informationsgehalt immer positiv ist.
Die Einheit des Informationsgehalts wird durch die Wahl der Basis des Logarithmus bestimmt. Die Logarithmen aus einer Zahl N' zur Basis 10, zur Basis 2 oder zu irgendeiner anderen Basis unterscheiden sich nur durch einen konstanten Faktor. Es gilt:
logx(N') = logx(Y)*logy(N')
Für uns sind eigentlich nur drei verschiedene Logarithmen interessant. Nämlich der zur Basis 10, der zur Basis 2 und der zur Basis e. Meist werden folgende Abkürzungen benutzt:
log2 = ld ... dyadischer Logarithmus, Einheit [bit]
loge = ln ... natürlicher Logarithmus, Einheit [nit]
log10 = lg ... Brigg'scher Logarithmus, Einheit [dit]
Es ergeben sich somit verschiedene Faktoren für die Umrechnung eines Logarithmus in einen Anderen:
ld(N') = 3,322*lg(N') lg(N') = 0,301*ld(N')
ld(N') = 1,443*ln(N') ln(N') = 0,693*ld(N')
ln(N') = 2,304*lg(N') lg(N') = 0,434*ln(N')
Wird für die Berechnung des Informationsgehaltes He der dyadische Logarithmus verwendet, ist seine Einheit 1bit, beim natürlichen Logarithmus 1nit und beim Brigg'schen Logarithmus 1dit. Die Bezeichnung bit kommt vom englischen binary digit (Binärziffer).
Wenn der Informationsgehalt He mit dem dyadischen Logarithmus ld berechnet wird, dann gibt er an, wieviele Binärentscheidungen zur Auswahl eines beliebigen Zeichens aus dem Zeichen-vorrat N' benötigt werden. Die diesbezügliche Aussage des Quellencodierungssatzes lautet:
Jedes von N' gleichwahrscheinlichen Zeichen in einer langen Zeichenfolge läßt sich im Durchschnitt mit minimal ld(N')+ Binärziffern codieren. Hierbei ist eine positive Größe, die beliebig klein vorgegeben werden kann.
Betrachten wir nun ein Beispiel mit einer Informationsquelle, deren Zeichenvorrat aus N' = 8 = 23 verschiedenen Zeichen a, b, c, d, e, f, g, h besteht. Alle Zeichen besitzen die gleiche Wahr-scheinlichkeit. Um jedes der acht Zeichen zu erhalten, kann man den Auswahlvorgang in mehrere Binärentscheidungen zerlegen, indem man beispielsweise eine Pyramide mit drei digitalen Schaltern aufbaut (Bild2.1). Durch die Angabe in welcher Schalterstellung sich die Schalter befinden, kann jedes Zeichen ausgewählt werden. Für den Buchstaben d gilt z.B. die Entscheidungsfolge 011 (Schalter1 offen, Schalter2 und Schalter3 geschlossen). Das Verzweig-ungsschema nennt man Codebaum. Aus diesem graphischen Codebaum (Bild 2.2) kann man die jeweilige Entscheidungsfolge eines jeden Zeichens ablesen. In diesem Beispiel wird jedes Zeichen nicht durchschnittlich, sondern mit genau He = ld8 = 3 Binärschritten ausgewählt.
Ist N' keine ganzzahlige Potenz von 2, dann kann jedes Zeichen mit durchschnittlich ld(N')+ Binärschritten ausgewählt werden, wobei die Größe durch eine entsprechend günstige Codierung klein gemacht werden kann. Zur Erklärung dazu dient das nächste Beispiel.
Der Zeichenvorrat sei N'=3. Daher erhält man für He = ld(3) = 1,585. Der Zeichenvorrat besteht aus den gleichwahrscheinlichen Zeichen a, b und c. Bild 2.3 zeigt den einfachsten Codebaum zur Codierung dieser drei Zeichen. Die Buchstaben a und b werden durch zwei, c durch einen Binärschritt erreicht. Da alle Buchstaben gleichwahrscheinlich sind, wird Jeder mit durchschnit-tlich 5/3 = 1,667 Binärschritten (Gesamtanzahl der Binärschritte/ Zeichenanzahl) ausgewählt. Günstiger wird es, wenn je zwei Zeichen ein gemeinsames Codewort erhalten, was in Bild 2.4 dargestellt ist. Mit diesen Zweierkombinationen läßt sich ebenfalls jede Zeichenfolge aus den drei Zeichen a, b und c codieren, da es ja nur diese Zeichen gibt, keine Pausen oder Zwischen-räume. Sieht man sich den Codebaum an so erkennt man, daß jede Zweierkombination mit durchschnittlich 29/18 = 1,611 Binärschritten codiert werden. Dieser Wert ist schon bedeuted näher an ld8 als der vorherige. Durch Codierung längerer Zeichenketten kann dieser Wert erreicht werden, wobei definitionsgemäß null wird.
2.1.2 Informationsgehalt von nichtgleichwahrscheinlichen Zeichen
Wichtig ist es in einer langen Zeichenkette mit nichtgleichwahrscheinlichen Zeichen den Informationsgehalt He pro Zeichen zu erhalten. Betrachten wir zum Beispiel eine diskrete Quelle die wiederum nur die Zeichen a, b und c ausgiebt. Diesmal treten die Zeichen aber mit unter-schiedlicher Wahrscheinlichkeit auf. Dabei soll das Zeichen a mit der Wahrscheinlichkeit P(a) auftreten, b mit P(b) und c mit P(c). Für die Summe aller Wahrscheinlichkeiten gilt natürlich
P(a)+P(b)+P(c) = 1. Allgemeiner auch
Der Informationsgehalt des Zeichens a ist mit He,a = ld(1/P(a)) definiert. Betrachten wir nun eine sehr lange Zeichenkette mit n Zeichen, so tritt a mit n*P(a) nach dessen Wahrscheinlichkeit auf. Zählt man nun alle Informationsgehälter aller Zeichen a zusammen, so erhält man den Informationsbeitrag Ba mit .
Somit ergibt sich der gesamte Informationsgehalt der Nachricht mit den Zeichen a, b und c mit:
Wollen wir nun den durchschnittlichen Informationsgehalt pro Zeichen, müssen wir den Informationsbeitrag B pro Zeichen n berechnen. Dazu braucht man die obige Formel nur umformen und erhält:
Allgemein würde diese Formel wiefolgt aussehen:
H(x) ist nun der durchschnittliche Informationsgehalt pro Zeichen für eine diskrete Informations-quelle mit N' verschiedenen, voneinander unabhängigen Zeichen xi (i = 1,2..N'), von denen das i-te Zeichen mit der Wahrscheinlichkeit P(xi) auftritt. Der durchschnittliche Informationsgehalt pro Zeichen ist derselbe wie der Erwartungswert, d.h. jener Wert den man für den Informations-gehalt des Zeichens erwartet.
Es sei angenommen das die Zeichen mit gleicher Wahrscheinlichkeit auftreten. Setzten wir nun in die Formel für nichtgleichwahrscheinliche Zeichen, die allgemeine Gültigkeit besitzt, ein, so erhalten wir wenn gilt: P(xi) = 1/N' . Der durchschnittliche Informationsgehalt pro Zeichen muß bei gleichwahrscheinlichen Zeichen Natürlich gleich dem Informationsgehalt eines jeden einzelnen Zeichen sein (siehe Kapitel 2.1.1). H wird auch als Entropie der Quelle bezeichnet (manchmal auch als Negentropie). Bei gleichwahrscheinlichen Zeichen wird die Entropie noch dazu maximal. Dies läßt sich einfach an einem Beispiel mit einer Binärquelle veranschaulichen:
Eine Binärquelle liegt dann vor, wenn die Quelle nur zwei verschiedene Zeichen x1=a und x2=b aussenden kann. N' ist daher gleich zwei. Diese zwei Zeichen können dargestellt werden durch die logischen Zustände 0 und 1 bei digitalen Systemen. Tritt nun das Zeichen a mit der Wahr-scheinlichkeit P auf, so muß das Zeichen b mit der Wahrscheinlichkeit 1-P auftreten. Die Entropie, oder druchschnittliche Informationsgehalt pro Zeichen, ist demnach also:
Zur Bestimmung derjenigen Wahrscheinlichkeit P, bei welcher H maximal wird, müssen wir vorher den natürlichen Logarithmus einführen, da dieser beim Ableiten gebraucht wird:
Diese Beziehung wird nun in die obige Gleichung für H eingesetzt.
Nun können wir das Maximum berechnen, indem wir die Ableitung bilden
Diese Gleichung müssen wir nun null setzen um die Extremstellen zu erhalten. Für P=0,5 wird die Gleichung null und wir erhalten eine Extremstelle. P=0,5 bedeutet das beide Zeichen glechwahrscheinlich sind. Ob es sich bei dieser Extremstelle um ein Minimum, oder ein Maximum handelt, wird die zweite Ableitung zeigen.
Der mittlere Informationsgehalt pro Zeichen erreicht also ein Maximum, wenn beide Zeichen glechwahrscheinlich sind. Dasselbe Ergebnis erhält man für eine Quelle mit einem Zeichenvorrat von N' Zeichen. Da die allgemeine Ableitung aber etwas länger dauert und zum Verständnis nicht viel beiträgt wird sie hier übergangen. Es soll lediglich ncoh anhand eines Beispiels einer Quelle mit vier Zeichen a, b, c und d unterschiedlicher Wahrscheinlichkeit (Fall 1) gezeigt werden, daß man mit weniger Binärschritten auskommt, als wenn alle Zeichen gleichwahr-
scheinlich währen (Fall 2).
Zeichen xi x1 = a x2 = b x3 = c x4 = d
(1) P1(xi) P1(a) = 1/2 P1(b) = ¼ P1(c) = 1/8 P1(d) = 1/8
(2) P2(xi) P2(a) = 1/4 P2(b) = ¼ P2(c) = 1/4 P2(d) = 1/4
Tabelle 2.1
Fall 1 liefert für H:
Fall 2 liefert für H:
Bei den ungleichen Wahrscheinlichkeiten von Fall 1 benötigt man also im Durchschnitt ¼ bit pro Zeichen weniger als im Fall 1 bei gleichen Wahrscheilichkeiten.
2.1.3 Quellencodierung, Redundanz, Informationsfluß
Am Ende des vorigen Kapitels wurden zwei Quellen betrachtet, die je vier verschiedene Zeichen erzeugen können, einmal mit gleicher Wahrscheinlichkeit, einmal mit ungleicher Wahrschein-lichkeit. In der unteren Tabelle sind diese Werte noch einmal angeführt. Die Bedeutung der anderen Zeichen wird später erklärt.
Zeichen xi a b c d
Wahrscheinlichkeit
P(xi) P1(xi) 1/2 1/4 1/8 1/8
P2(xi) 1/4 1/4 1/4 1/4
Code Code 1 0 10 110 111
Code 2 00 01 10 11
Binärstellenzahl m(xi)
Je CW Code 1 1 2 3 3
Code2 2 2 2 2
Tabelle 2.2
Bild 2.5 zeigt zwei Codebäume zur Codierung der Zeichen a, b, c und d. Es wird behauptet, daß Code 2 zur Codierung von Fall 2 optimal ist und zur Codierung von Fall 1 ungünstig. Anders-herum ist Code 1 zur Codierung von Fall 1 optimal und für Fall 2 ungünstig. Die Codes 1 und 2 sind aus der Tabelle ersichtlich. Auch kann man die Anzahl m der Binärstellen je Codewort ablesen. Es sei noch darauf hingewiesen, daß der Code 1 mit verschieden langen Codewörtern ohne Trennzeichen in Serie übertragen werden kann, da kein kurzes Codewort gleich dem Anfang eines langen Codewortes ist. Man kann daher jedes Codewort unterscheiden.
Betrachten wir nun eine Zeichenfolge aus n Zeichen. Berechnet werden soll die Anzahl m' der tatsächlich dabei im Mittel aufgewendeten Binärstellen, wenn beide Codes in beiden Fällen angewendet werden. Im folgenden wird die konkrete Binärstelle durch Bit ausgedrückt, während der abstrakte Informationsgehalt weiterhin in bit angegeben wird.
Die Anwendung von Code 1 im Fall 1 ergibt für die Anzahl m' der im Mittel aufgewendeten Binärstellen:
Die Anwendung von Code 1 auf Fall 2:
Code 1 erweist sich also im Fall 1 optimal, hingegen im Fall 2 ungünstig, da er dort mehr Bit/Zeichen aufwendet, als der mittlere Informationsgehalt angiebt.
Die Anwendung von Code 2 im Fall 1 ergibt für die Anzahl m' der im Mittel aufgewendeten Binärstellen:
Die Anwendung con Code 2 im Fall 2 ergiebt:
Code 2 erweist sich also im Fall 2 als optimal, hingegen ist er für Fall 1 ungünstig. Die aufgeführten Beispiele machen plausibel, daß allgemein der folgende Quellencodierungssatz gilt:
Für jede diskrete Quelle der Entropie H läßt sich ein Code so finden, daß die im Mittel aufgewendete Anzahl m' von Binärstellen pro Zeichen der Beziehung H m' H+ folgt, wobei >0 beliebig klein vorgegeben werden kann. Es gibt keinen Code, der im Mittel mit weniger als H Binärstellen pro Zeichen auskommt.
Im nächsten Abschnitt werden zwei systematische Verfahren erläutert, die Codes mit kleinem liefern. Zur Beurteilung der informationstheoretischen Eigenschaften von Codes dient der Begriff der Redundanz. Die absolute Redundanz R = m'-H. Die relative Redundanz r ist: . Der bereits verwendete Begriff der Gleichwahrscheinlichkeitsredundanz ergibt sich für den Fall, daß alle Zeichen gleichwahrscheinlich sind, und ihre Codewörter gleiche Länge haben. Bei gleichwahrscheinlichen Codewörtern ist nämlich die Entropie H gleich ld(N'). Weiters ist bei gleich langen Codewörtern die Anzahl der Binärstellen pro Codewort konstant, d.h. m'=ld(N). (Das nicht gestrichene N ist die Anzahl der möglichen Codewörter).
Bei Informationsquellen, welche die einzelnen Zeichen zeitlich nacheinander abgeben, bezeichnet man die auf die Zeit t0 bezogene Entropie als Informationsfluß H'
Dieser Informationsfluß gehört zu digitalen Signalen, sofern pro Zeiteinheit nicht unendlich viele Zeichen von der Quelle abgegeben werden.
Bei flächenhaften Anordnungen wird H entsprechend auf die Fläche A bezogen. Man nennt diese Größe die Informationsdichte .
2.1.4 Optimale, redundanzsparende Codes
Es wurden bereits zwei Verfahren angekündigt, mit denen Codes geringer Redundanz, d.h. mit sehr kleinem , aufgestellt werden können. Dies sind die Verfahren nach Fano und Huffman.
2.1.4.1 Codierung nach Fano
Gegeben sind die N' verschiedenen Zeichen xi der Gesamtheit einer Quelle mit ihren unterschiedlichen Auftrittswahrscheinlichkeiten P(xi). Diese werden nach fallender Wahrscheinlichkeit untereinander und notiert ihre Wahrscheinlichkeit P(xi) in der rechts danebenstehenden Spalte. Dann bildet man von unten nach oben die Teilsummen und unterteilt die Spalte möglichst nahe bei si = 50% = 0,5. Als nächstes schreibt man in alle Zeilen der oberen Hälfte eine 0, in alle Zeilen der unteren Hälfte eine 1. Damit ist die erste Stelle der Codewörter festgelegt. Dann werden die beiden Hälften wiederum möglichst nahe an deren arithmetischen Mittelwert der Teilsummen geteilt. Die Zeilen der beiden unteren Hälften (die der unter und die der oberen Hälfte) werden wieder mit 0 beschrieben, die Oberen mit 1. So fährt man fort, bis sich nur noch Teile mit je einem einzigen Zeichen xi ergeben. Die Anzahl der Binärstellen m(xi) der Zeichen xi, d.h. die Länge der Codewörter, nimmt von oben nach unten bei richtigem Vorgehen monoton zu.
xi x1 x2 x3 x4 x5 ... xN'
P(xi) P(x1) P(x2) P(x3) P(x4) P(x5) ... P(xN')
si 1,0
... 0,0
Tabelle 2.3
Zur Erläuterung dieses Verfahrens wird in Tabelle 2.4 die Codierung der Zeichen a, b, c und d mit den in Tabelle 2.2 Fall 1 angegebenen Wahrscheinlichkeiten durchgeführt. Es zeigt sich, daß dieses Verfahren zwangsläufig auf den Code 2 von Tabelle 2.2 führt, der sich bereits als optimal erwiesem hat.
xi P(xi) si Unterteilung Code M(xi)
1,000
a 0,5 0 1
0,500
b 0,25 10 2
0,250
c 0,125 110 3
0,125
d 0,125 111 3
0,000
Tabelle 2.4
Zuerst teilt man, wie bereits beschrieben, die Tabelle in der Nähe von 50% (0,5) in zwei Hälften. Die obere Hälte wäre in unserem Fall a und die Untere b,c und d. a bekommt nun eine 0, b, c und d eine 1 in iheren Code. Da die obere Hälfte nur ein Zeichen besitzt, kann sie nicht mehr geteilt werden, die Untere jedoch schon. In der unteren Hälfte ist die Summe si = 0,5. Teilt man beim arithmetischen Mittelwert, welcher 0,25 ist, so steht b in der oberen Hälfte, c und d in der Unteren. b bekommt somit eine 0, c und d eine 1. Die untere Hälfte mit c und d kann nochmals bei 0,125 geteilt werden, womit c eine 0 in seinen Code bekommt und d eine 1.
2.1.4.2 Codierung nach Huffmann
Dieses Verfahren liefert manchmal bessere Ergebnisse als jenes von Fano und soll einfachheitshalber an einem Beispiel erklärt werden (Bild 2.6). Die Zeichen werden wieder nach ihrer fallenden Wahrscheinlichkeit untereinander geschrieben. Die beiden Zeichen mit der geringsten Auftrittswahrscheinlichkeit werden in eine Gruppe mit der Klassenbezeichnung I zusammengefasst. Nun wird eine neue Spalte aufgestellt, in derdie neue Klasse I entsprechend ihrer Wahrscheinlichkeit eingeordnet wird (die beiden Zeichen der Klasse I werden natürlich nicht mehr angeschrieben). Man wiederholt dieses Verfahren solange, bis nur mehr eine Klasse, in unserem Beispiel Klasse IV, über bleibt. Wenn man die Zusammen-fassungen rückwärts auflistet, so ergibt sich daraus der Codebaum. Die Anzahl der Binärent-scheidungen ist somit festgelegt. Für die Zuordnung der Binärziffern ist nicht festgelegt, in unserem Beispiel wird für die oberen Äste 0 und für die Unteren 1 gewählt.
Wenn alle auftretenden Wahrscheinlichkeiten von der Form 2-ni (ni ganzzahlig) sind, z.B. 2-1, 2-2
2-3, dann ist bei optimaler Codierung (nach Fano oder Huffman) die Redundanz gleich Null. Normalerweise sind Wahrscheinlichkeiten aber nicht von der Form 2-ni. Dies bedingt, daß die im Mittel aufzuwendende Anzahl von Binärschritten m' etwas größer als H wird, also die relative Redundanz einen gewissen positiven Wert erhält. Durch Codierung von Zeichenkombinationen läßt sich die Redundanz jedoch verringern.
Als weiteres Beispiel wird die Wahrscheinlichkeit des Auftretens der einzelnen Buchstaben in einem deutschen Text betrachtet (siehe Tabelle 2.5). In der Buchstabenspalte ist das oberste Zeichen das Leerzeichen. Satzzeichen wurden dabei nicht brücksichtigt. Der Code in Spalte 5 wurde nach dem beschriebenen Verfahren von Fano gebildet.
Der mittlere Informationsgehalt pro Zeichen (Buchstabe) H ergiebt sich entsprechend durch Aufsummieren aller Zahlen in Spalte 8, die den Informationsgehalt des jeweiligen Zeichens angibt.
Lfd.Nr.
i Buch-stabe
xi Wahrschein-lichkeit
P(xi) Summe
si Code (Fano) Binär-stellen je Buch-stabe P(xi)m(xi)
1 2 3 4 5 6 7 8
1 0,15149 1 000 3 0,45447 0,41246
2 E 0,147 0,84851 001 3 0,441 0,40661
3 N 0,08835 0,70151 010 3 0,26505 0,30928
4 R 0,06858 0,61316 0110 4 0,27432 0,26513
5 I 0,06377 0,54458 0111 4 0,25508 0,25322
6 S 0,05388 0,48081 1000 4 0,21552 0,22705
7 T 0,04731 0,42693 1001 4 0,18924 0,20824
8 D 0,04385 0,37962 1010 4 0,1754 0,19781
9 H 0,04355 0,33577 10110 5 0,21775 0,19689
10 A 0,04331 0,29222 10111 5 0,21655 0,19615
11 U 0,03188 0,24891 11000 5 0,1594 0,15848
12 L 0,02931 0,21703 11001 5 0,14655 0,14926
13 C 0,02673 0,18772 11010 5 0,13365 0,13967
14 G 0,02667 0,16099 11011 5 0,13335 0,13944
15 M 0,02134 0,13432 111000 6 0,12804 0,11844
16 O 0,01772 0,11298 111001 6 0,10632 0,1031
17 B 0,01597 0,09526 111010 6 0,09582 0,09531
18 Z 0,01423 0,07929 111011 6 0,08538 0,08729
19 W 0,0142 0,06506 111100 6 0,0852 0,08715
20 F 0,0136 0,05086 111101 6 0,0816 0,08432
21 K 0,00956 0,03726 1111100 7 0,06692 0,06413
22 V 0,00735 0,0277 1111101 7 0,05145 0,05209
23 Ü 0,0058 0,02035 11111100 8 0,0464 0,04309
24 P 0,00499 0,01455 11111101 8 0,03992 0,03815
25 Ä 0,00491 0,00956 11111110 8 0,03928 0,03766
26 Ö 0,00255 0,00465 111111110 9 0,02295 0,02196
27 J 0,00165 0,0021 1111111110 10 0,0165 0,01525
28 Y 0,00017 0,00045 11111111110 11 0,00187 0,00212
29 Q 0,00015 0,00028 111111111110 12 0,0018 0,0019
30 X 0,00013 0,00013 111111111111 12 0,00156 0,00167
0
Im Mittel aufgewendete Binärschritte
Mittlerer Informationsgehalt
Tabelle 2.5 Buchstabenhäufigkeit in der deutschen Sprache und Code nach Fano
Zur Berechnung der Redundanz des Codes von Spalte 5 wird die im Mittel pro Buchstabe aufgewendete Anzahl m' an Binärschritten benötigt. Dazu betrachten wir eine genügend lange (theoretisch unendlich lange) Buchstabenfolge mit n Zeichen. In dieser Folge kommt der 1. Buchstabe (i=1) mit m(x1) = 3 Binärstellen n(Px1)-mal vor, der Zweite mit m(x2) Binärstellen
n(Px2)-mal vor usw. Die Gesamtzahl der Binärstellen in der Folge von n Buchstaben ist also mit Aufsummierung von Spalte 7
Daraus ergeben sich absolute und relative Redundanz R und r
R = m'-H = 0,03373 [bit/Buchstabe]
Würden die 30 Buchstaben (einschließlich des Leerzeichens) mit gleicher Wahrscheinlichkeit auftreten, so ergäbe sich der mittlere Informationsgehalt H
H = ld(30) = 4,9 [bit/Buchstabe]
Wir haben also festgestellt, daß der mittlere Informationsgehalt der Buchstaben in deutschen Texten etwa 4,11 bit beträgt. Dies gilt allerdings nur unter der Vernachlässigun, daß alle Zeichen voneinander statistisch unabhängig sind. Man darf daher nicht den Schluß ziehen, daß der mittlere Informationsgehalt eines zusammenhängenden Textes sich als Produkt der Buchstabenzahl und diesen 4,11 bit/Buchstabe erechnen ließe. In Wirklichkeit sind die aufeinanderfolgenden Buchstaben nicht statistisch unabhängig voneinander. Beispielsweise folgt auf ein q fast sicher ein u, was bedeutet, das dieses u hinter einem q überhaupt keinen Informationsinhalt besitzt. Auf den Buchstaben j folgt im Deutschen fast stets ein Vokal, auf c folgt meist h oder k usw. Durch diese statistischen Bindungen ist der wirkliche mittlere Informationsgehalt wesentlich kleiner als 4,11 bit/Buchstabe. Mit diesem Thema beschäfitgt sich das nächste Kapitel.
|
