2.3.1 Formel zur Errechnung des Informationsgehalts
Voraussetzung zur Digitalisierung von Signalen, etwa Wahrnehmungsdaten, oder Nachrichten ist eine Kodierung mit Hilfe endlich vieler, wohlunterscheidbarer (diskreter) Symbole.
Kode, fachspr.: Code [] <lat.-fr.-engl.> der; -s, -s: 1. System von Regeln u. Zeichen, das die Zuordnung von Zeichen[folgen] zweier verschiedener Zeichenvorräte erlaubt u. somit einen Schlüssel zur Übertragung verschlüsselter Texte darstellt. 2. Gesamtheit sprachlicher Zeichen u. Regeln u. ihre Verknüpfungen (Sprachw.). 3. durch die Zugehörigkeit zu einer bestimmten sozialen Schicht vorgegebene Verwendungsweise von Sprache (Soziolinguistik)
(c) Dudenverlag
Kodierung heißt also einerseits Verschlüsselung, d.h. Abstraktion von den ursprünglichen Daten, andererseits Umwandlung -- Transformation -- eines Zeichensystems in ein anderes.
Bsp.: Kodierung eines Bildes
Nach Rasterung des Parameters "Raum", also Länge und Breite, und Festlegung der quantisierten Größen, also dem jeweiligen Farbwert des Pixels, kann ein geeignetes Zeichensystem verwendet werden, um das Bild zu verschlüsseln, und so z.B. einem Digitalrechner zur Bearbeitung zu überlassen.
Dabei werden Konventionen getroffen, etwa:
Weitere Beispiele für Kodes:
Der Morsekode
Der Morseapparat
Der Apparat verwendete offenbar einen Kode, der sich an den beweglichen Lettern des Buchdrucks orientierte: jeder Buchstabe wurde zu einer Schablone. Erst später abstrahierte Morse daraus den Punkt-Strich-Kode.
Der Morse-Kode: Abbildung Oberliesen S. 109
-.-.- -.. .- ... .--. ..-. . .-. -.. ..-. .-. .. ... ... - -.- . .. -. . -. --. ..- .-. -.- . -. ... .- .-.. .- - .-.-.
Frage: Warum waren die Kodes für die einzelnen Buchstaben unterschiedlich lang?
Antwort: die Nachrichten werden insgesamt kürzer, wenn die häufigsten Zeichen am kürzesten kodiert werden.
D.h.: die Menge der übertragenen Zeichen in einer Nachricht und die darin enthaltene Information sind zwei verschiedene Dinge.
Man kann Nachrichten mehr oder weniger ökonomisch versenden, mit hoher und mit niedriger Informationsdichte.
Bsp.: Kodierung eines Schwarz-Weiß-Bildes mit zwei Binärziffern pro Pixel.
Version 1:
00 00 11 11 11 11 11
00 11 11 11 11 11 11
00 00 11 11 11 11 11
00 00 00 11 11 11 11
00 00 00 00 00 00 00
Welche Kodierung wäre sparsamer?
Version 2:
0 0 1 1 1 1 1
0 1 1 1 1 1 1
0 0 1 1 1 1 1
0 0 0 1 1 1 1
0 0 0 0 0 0 0
Die Zahl der Zeichen ist nur halb so groß, die Information dieselbe. Dies ist ein erstes Beispiel für die verlustfreie Kompression einer Nachricht.
Frage: wieviel Information steckt tatsächlich in dem Bild und seiner Kodierung?
Was ist überhaupt Information in diesem Zusammenhang?
In|for|ma|ti|on <lat.> die; -, -en: 1. a) Nachricht, Mitteilung, Hinweis; Auskunft; Belehrung, Aufklärung; b) Informationsstand. 2. Gehalt einer Nachricht, die aus Zeichen eines Kodes zusammengesetzt ist (Kybernetik).
(c) Dudenverlag
Es gibt eine sehr schöne umgangssprachliche Definition:
"Information is the difference that makes a difference." (Gregory Bateson)
Im Zusammenhang mit Kodierungsproblemen:
der Informationsgehalt einer Nachricht ist die minimale Länge, die die Nachricht haben kann, denn dann macht jeder Unterschied einen Unterschied. Offenbar macht es ja z.B. keinen Unterschied, ob man das Bild in Version 1 oder Version 2 kodiert, die längere Version 1 hat also keinen höheren Informationsgehalt, viele Details (um genau zu sein: die Hälfte), haben keinen Belang.
Die kürzeste Methode, eine Nachricht aus einer Menge von möglichen und gleich wahrscheinlichen Nachrichten zu kodieren, ist, sie durchzunumerieren und jede Nachricht durch die Nummer zu bezeichnen.
Bei Bildern mit I Pixeln, die schwarz oder weiß sein können, etwa sieht das so aus:
|
I |
|
|
|
1 |
2 |
0 und 1 |
|
2 |
4 |
00, 01, 10 und 11 |
|
3 |
1112+1 = 23 = 8 |
000, 001, 010, 011, 100, 101, 110, 111 |
|
4 |
11112+ 1 = 24 = 16 |
0000 bis 1111 |
|
... |
||
|
i |
2i |
00...000 (n Nullen) bis 11...111 (n Einsen) |
|
35 |
235 = 3,436*1010 |
ganz weiß bis ganz schwarz, etwa 5*7 Punkte wie oben |
Wenn man nun jedes Bild aus I Pixeln binär numeriert hat, wie lang sind dann die Nummern? I Bits lang. D.h.: Version 2 unseres Bildes von oben ist bereits die minimale Kodierung, der Informationsgehalt ist genau 35 Einheiten: 35 Bits.
Wie ist der Fall bei Bildern mit I Pixeln zu je 4 möglichen Farbwerten? Da muß jedes Pixel mit 2 Binärziffern kodiert werden (die Werte sind 00, 01, 10 oder 11), bei I Pixeln sind das dann 22I mögliche Bilder, und die Bitfolgen zur Numerierung sind 2I Bits lang, der Informationsgehalt beträgt 2I Bits.
2I mögliche Nachrichten: Länge der Bitfolge (Informationsgehalt): I
22I mögliche Nachrichten: Informationsgehalt: 2I
Mit anderen Worten, im allgemeinen Fall:
mit I Informationseinheiten lassen sich 2I Nachrichten verschlüsseln. Sind diese alle gleich wahrscheinlich, dann ist also I die minimale Länge der Kodierung für N=2I Nachrichten:
|
|
Der Informationsgehalt einer Nachricht aus einer Menge von N gleich wahrscheinlichen Nachrichten ist gleich dem Zweierlogarithmus von N.
Eigentlich ist die Frage nach dem Informationsgehalt die nach einer optimalen Kodierung, die nicht immer (leicht) zu finden ist.
Beispiel: Verkehrsampel
Kodierungsmethode: Rot, Gelb, Grün, jede der drei Lampen ist an oder aus:
Bei 001 -- Grün leuchtet -- darf man fahren, bei 110 noch nicht.
Wie groß ist der Informationsgehalt einer Nachricht, die den aktuellen Ampelzustand übermittelt? Vielleicht 3, weil die Nachricht mit 3 Binärziffern kodiert ist?
Nein. Der Kode ist nicht optimal, es gibt nicht alle Kombinationen von Rot, Gelb und Grün.
Es gibt nur vier Ampelzustände:
100
110
001
010
Also N=4, mithin I=log2(4) = 2 (weil 22=4)
Es müßten alo 2 Binärstellen genügen, z.B.:
|
Ampelzustand |
kürzeste Kodierung |
|
100 |
00 |
|
110 |
01 |
|
001 |
10 |
|
010 |
11 |
Der Informationsgehalt läßt sich auch noch anders interpretieren:
I ist die Zahl der Auswahlentscheidungen, um die Nachricht aus der Menge aller Nachrichten zu herauszugreifen.
Etwa: seien die Ampelstellungen beliebig gruppiert:
Dann reichen zwei Fragen, um eine bestimmte herauszugreifen:
1. Gehört die gesuchte Ampelstellung zu den beiden linken oder den beiden rechten? (Ja/Nein oder 1/0)
und
2. Ist es dann die linke oder die rechte? (Ja/Nein oder wieder 1/0)
Zwei Fragen, zwei Bit Informationsgehalt.
Beispiel: Balkenwaage
Frage: mit wie vielen Wägungen höchstens auf einer Balkenwaage findet man unter 8 Kugeln die schwerste unter sonst gleich schweren heraus?
Antwort: log2(8) = 3
Verfahren: Aufteilen in 4 und 4, die schwereren 4 wieder in 2 und 2, die verbleibenden 2 schwereren dann wieder unmittelbar miteinander vergleichen: macht drei Auswahleintscheidungen also 3 Bit.
Zurück zum Morse-Kode:
hier sind die verschlüsselten Zeichen nicht alle gleich wahrscheinlich, denn z.B. kommt der Buchstabe "e" in englischen (und auch in deutschen) Texten häufiger vor als der Buchstabe "x".
Häufig vorkommende Nachrichten, also wahrscheinliche Nachrichten, tragen weniger Information als seltene, unwahrscheinliche.
Beispiel: Rennwetten. Hier wird eine Information, der Tip, wer als erster durchs Ziel geht, direkt in Geld ausgedrückt, nämlich in der Gewinnquote, die beim Eintreffen des Ereignisses ausgezahlt wird.
Man gewinnt bei Außenseitern mehr als bei Favoriten.
Wie könnte die Formel aussehen?
Bei gleich wahrscheinlichen Nachrichten gilt (N ist die Gesamtzahl aller Nachrichten)
oder, umgeformt
(weil gilt: log(x) = -log(1/x))
Die Wahrscheinlichkeit p der Nachricht selbst beträgt 1/N, denn es gibt N Nachrichten, und alle sollten gleich wahrscheinlich sein.
Also haben wir:
Jetzt kann man den Informationsgehalt zum Ausdruck bringen, auch wenn man nicht den optimalen Kode kennt. Man braucht dazu nur die Wahrscheinlichkeit, mit der eine bestimmte Nachricht übermittelt wird, zu ermitteln:
Für die n-te Nachricht aus einer Menge von Nachrichten gilt nun in Analogie:
Für das Englische ist ein Kode entwickelt worden, der optimal die Buchstabenhäufigkeiten widerspiegelt, er heißt Huffman-Kode. Er entspricht ungefähr der Wahl Morses für die Länge seiner Zeichensequenz, und ungefähr stimmt dies auch überein mit der Wahrscheinlichkeitsverteilung der Buchstaben in der deutschen Sprache:
|
Zei-chen |
Huffman-Code |
Morse-Kode |
Länge des Huffman-Kodes |
Länge des Morse-Kodes |
pn=Wahr- |
-log2(pn) |
|
e |
IOO |
. |
3 |
1 |
0,1470 |
2,76611194 |
|
t |
OOI |
- |
3 |
1 |
0,0473 |
4,40201601 |
|
n |
IIOO |
-. |
4 |
2 |
0,0884 |
3,49980982 |
|
i |
IOIO |
.. |
4 |
2 |
0,0638 |
3,97029977 |
|
a |
IIII |
.- |
4 |
2 |
0,0433 |
4,52948916 |
|
r |
IOII |
.-. |
4 |
3 |
0,0686 |
3,86564761 |
|
s |
OIIO |
... |
4 |
3 |
0,0539 |
4,21357092 |
|
o |
IIIO |
--- |
4 |
3 |
0,0177 |
5,82010683 |
|
h |
OIOI |
.... |
4 |
4 |
0,0436 |
4,51952805 |
|
m |
OOOII |
-- |
5 |
2 |
0,0213 |
5,55300276 |
|
d |
IIOII |
-.. |
5 |
3 |
0,0439 |
4,50963525 |
|
u |
OOOIO |
..- |
5 |
3 |
0,0319 |
4,97029977 |
|
g |
OOOOI |
--. |
5 |
3 |
0,0267 |
5,22701645 |
|
l |
OIIII |
.-.. |
5 |
4 |
0,0293 |
5,09295553 |
|
c |
OIOOO |
-.-. |
5 |
4 |
0,0267 |
5,22701645 |
|
f |
OIOOI |
..-. |
5 |
4 |
0,0136 |
6,20024954 |
|
y |
OOOOO |
-.-- |
5 |
4 |
0,0002 |
12,2877124 |
|
w |
OIIIOI |
.-- |
6 |
3 |
0,0142 |
6,13796526 |
|
b |
OIIIOO |
-... |
6 |
4 |
0,0160 |
5,96578428 |
|
p |
IIOIOI |
.--. |
6 |
4 |
0,0050 |
7,64385619 |
|
v |
IIOIOOI |
...- |
7 |
4 |
0,0074 |
7,07825901 |
|
k |
IIOIOOOII |
-.- |
9 |
3 |
0,0096 |
6,70274988 |
|
j |
IIOIOOOOO |
.--- |
9 |
4 |
0,0016 |
9,28771238 |
|
x |
IIOIOOOOI |
-..- |
9 |
4 |
0,0001 |
13,2877124 |
|
z |
IIOIOOOIOO |
--.. |
10 |
4 |
0,0142 |
6,13796526 |
|
q |
IIOIOOOIOI |
--.- |
10 |
4 |
0,0001 |
13,2877124 |
I = log2(27) = 4,75
Wie lang im Mittel sind die Kodierungen des Huffman-Kodes: 4,11
Der Überschuß einer Zeichenkodierung zur optimalen heißt Redundanz, unnötig gespeicherte Information.
In einer italienischen Bar wird das Übliche zu sich genommen: Espresso, Cappucino, Cafè doppio, Vecchia Romagna und Grappa Julia. Zumindest sind dies die am häufigsten georderten Getränke.
Nun will Paolo, der Camerière, nicht durch das ganze Etablissement brüllen, deshalb gibt er Luigi, dem Barmann, Zeichen. So hat er eine Zeichensprache entwickelt, die er Neros Urteil über die Gladiatoren entlehnt hat (man erinnere sich an "Quo vadis"): Daumen rauf und Daumen runter. Ihre Aufgabe ist nun, erst einmal zu bestimmen, wie lang die Zeichenfolgen sein müssen, um ein bestimmtes Getränk zu ordern (das muß ungefähr der Informationsgehalt in Bit sein). Wenn man sich bei dem Kode dann an diese Längen hält, gibt das das wenigste Gefuchtele, jedenfalls im langjährigen Mittel.
Dazu müssen Sie wissen, wie häufig die einzelnen Orders auftreten. Langwierige und uneigennützige Feldstudien haben ergeben, daß man mit folgenden Häufigkeiten zu rechnen hat:
Espresso: 48%
Cappucino: 26%
Cafè doppio: 14%
Vecchia Romagna: 7%
Grappa Julia: 5%
Also: wieviel Information steckt in jeder Bestellung?
Jetzt kann man Paolo einen Kode vorschlagen. Da Luigi nicht nur immer an die Arbeit denkt, muß das ein Kode sein, bei dem ein Zeichen nie der Anfang eines anderen ist. Denn man stelle sich vor, Luigi achtet brav erst einmal auf Paolos Order, dann betritt Claudia die Bar, weshalb er den Rest des Gezeiges von Paolo nicht mehr mitkriegt, mit dem Resultat, daß der Besucher Koffein statt Alkohol bekommt. Nicht auszudenken. So also bitte nicht.
Übrigens nennt man diese Gegenmaßnahme gegen Unaufmerksamkeit die Fano-Bedingung (der auch der Huffman-Kode genügt), aber das können Sie sofort wieder vergessen.
Wenn Ihr Taschrechner nur Zehnerlogarithmen kennt, dann können Sie folgende Formel benutzen, um die Zweierlogarithmen auszurechnen:
log2(x) = 3,32192809 * log10(x)
Weiter geht's mit Fragen der Berechenbarkeit!