Kleinere Schriftzeichen   

Information, Bits, Bytes und der Zweier-Logarithmus:

Inhalt:  
1. Ratespiele und Bits:

Der Logarithmus zur Basis 2, kurz Zweier-Logarithmus, wird dann mit Vorliebe verwendet, wenn es um den Begriff der Information geht.

Information hat mit der Frage zu tun, wieviel wir über etwas wissen. In diesem Sinn könnte man sie auch "Wissen" oder "Kenntnisstand" nennen. Diesen Begriff quantitativ zu fassen, d.h. messen zu können, ist schwieriger, wie es auf den ersten Blick aussehen mag. Genau genommen ist Information nicht das "Wissen" als solches, sondern ein Maß für die Schwierigkeit, es - in einer bestimmten Art von Situationen - zu erlangen! Die mit ihr verbundene "Einheit" ist das Bit. Ein Bit ist der maximale Informationsgewinn, den wir uns durch die Beantwortung einer Ja-Nein-Frage erwarten können.

Um uns näher anzusehen, was das bedeutet, stellen wir uns vor, zwei Personen, Alice und Bob, vertreiben sich mit einem Ratespiel die Zeit: Alice denkt sich eine ganze Zahl zwischen 1 und 8 aus, und Bob soll sie durch Ja-Nein-Fragen herausfinden. Wie viele Fragen benötigt er dazu?

Schlechte Strategie: Bob versucht es zunächst mit einer naiven Rate-Strategie. Er geht alle Zahlen zwischen 1 und 8 (in einer beliebigen Reihenfolge) durch und fragt von jeder, ob sie die gesuchte ist. Klarerweise benötigt er manchmal mehr, manchmal weniger Fragen, um ans Ziel zu gelangen. Wie viele Fragen wird er durchschnittlich benötigen, um die gesuchte Zahl zu ermitteln, falls das Spiel oft gespielt wird? Wenn Bob davon ausgehen kann, dass Alice keine Vorliebe für bestimmte Zahlen hat, wird er durchschnittlich Spätestens nach der 7. Frage ist er also am Ziel. Durchschnittlich wird er 35/8 = 4.375 Fragen dazu benötigen. (Sie können diese Zahl als Mittelwert (1 + 2 + 3 + 4 + 5 + 6 + 7 + 7)/8 berechnen).

Gute Strategie: Nach einiger Zeit ist Bob zu Recht unzufrieden: Es gibt bessere Strategien als naives Raten! Die beste Strategie besteht darin, die Fragen so zu stellen, dass ein "Nein" und ein "Ja" sein Wissen immer um denselben "Informationsbetrag" erhöht. Um das zu illustrieren, nehmen wir an, Alice hat die Zahl 6 gewählt. Das Spiel könnte so ablaufen: Jetzt weiss Bob, dass die gesuchte Zahl 6 ist. Er hat lediglich 3 Fragen benötigt, und mit dieser Strategie kommt er immer nach 3 Fragen zum Ziel.

Es lässt sich zeigen, dass diese Strategie (oder eine ähnliche, die ebenso mit jeder Frage auf die Hälfte der jeweils noch verbleibenden Möglichkeiten abzielt) tatsächlich die beste ist. Bob kennt die gesuchte Zahl immer (genau) nach der dritten Frage, im Gegensatz zu den durchschnittlich benötigten 4.375 Fragen für planloses Raten. Besser (mit durchschnittllich weniger als 3 Fragen) geht es nicht. Da 1 Bit nach unserer obigen Definition den maximalen von einer Ja-Nein-Frage erwarteten Informationsgewinn darstellt, hat jede Frage Bobs Kenntnisstand um 1 Bit erhöht, und wir können - ein bisschen salopp - feststellen:

Eine von 8 Möglichkeiten zu kennen, stellt eine Information von 3 Bit dar.

Genau genommen gilt das nur, wenn keine der 8 Möglichkeiten vor einer anderen bevorzugt ist, d.h. wenn sie "gleich wahrscheinlich" sind (bzw. "gleich oft" und "zufällig verteilt" vorkommen, wenn das Spiel oft wiederholt wird). Falls Alice etwa eine Vorliebe für gerade Zahlen hat oder Zahlen nach irgend einer fixen Regel auswählt, und Bob das im Laufe des Spiels mitbekommt, wird er seine Strategie ändern und im Schnitt mit weniger Fragen auskommen. Wir können die Information auch als das vorab erwartete Maß an Überraschung, das die Beantwortung einer Frage bringen wird, ansehen. Wenn sich beispielsweise Alice nie eine ungerade Zahl ausdenkt und Bob bereits weiss, dass die gesuchte Zahl zwischen 5 und 6 ist, bietet die Antwort auf die Frage "Ist die Zahl 5?" keinerlei Überraschung mehr, denn sie ist mit Sicherheit "Nein". Nur dann, wenn beide möglichen Antworten "gleich überraschend" sind, ist mit der Beantwortung einer Frage 1 Bit Information gewonnen.

Wir können das Spiel abändern, indem sich Alice eine von 16 Zahlen ausdenkt. Nun benötigt Bob für die beste Strategie 4 Fragen. Denkt sich Alice eine von 128 Zahlen aus, benötigt Bob 7 Fragen. Wie kann die Zahl der benötigten Fragen aus der Gesamtzahl n der Möglichkeiten, aus denen Alice wählen kann, berechnet werden?

Analysieren wir den Fall n = 8, den wir zuerst durchgespielt haben: 8 lässt sich als 23, d.h. 2 × 2 × 2 darstellen. Nach der Beantwortung der ersten Ja-Nein-Frage sind nur mehr 22, d.h. 2 × 2 Möglichkeiten offen, nach der Beantwortung der zweiten Ja-Nein-Frage sind nur mehr 21, d.h. 2, und nach der Beantwortung der dritten Ja-Nein-Frage sind nur mehr 20, d.h. eine einzige Möglichkeit offen, m.a.W. die gesuchte Zahl ist gefunden. Die Anzahl 3 der notwendigen Fragen ist also gerade der Exponent in der Darstellung 8 = 23. Ein ganz analoges Argument lässt sich anwenden, wenn n eine beliebige Potenz von 2 mit natürlichem Exponenten, d.h. von der Form 2s (für eine natürliche Zahl s) ist: In diesem Fall sind s Fragen notwendig, d.h.:

Eine von 2s (gleich wahrscheinlichen) Möglichkeiten zu kennen,
stellt eine Information von s Bit dar.

Nun erinnern wir uns, was wir über den Logarithmus wissen: Ist n = 2s, so ist

s  =  2log n.

Die Zahl s der benötigten Fragen ist also gleich dem Zweier-Logarithmus von n, der Gesamtzahl der Möglichkeiten. Das ist der Grund für die Wichtigkeit des Zweier-Logarithmus, wenn es um den Begriff der Information geht. Oberflächlich könnte man sagen, dass "2log n der Informationsgehalt ist, der in der Zahl n steckt".
Randbemerkung:

Im mathematischen Spezialgebiet der Informationstheorie wird gezeigt, dass diese Formel auch dann gilt, wenn n keine Potenz von 2 mit natürlichem Exponenten ist. (Darf sich Alice also beispielsweise eine von 10 Zahlen aussuchen, und wählt Bob eine clevere Strategie, so wird er, wenn das Spielt oft wiederholt wird, im Durchschnitt nach 2log(10) » 3.32 Fragen die gesuchte Zahl herausgefunden haben). Wir wollen dieses Resultat glauben und halten fest:

Eine von n (gleich wahrscheinlichen) Möglichkeiten zu kennen,
stellt eine Information von 2log n Bit dar.

Sind die n Möglichkeiten nicht alle gleich wahrscheinlich (d.h. nicht "gleich überraschend"), so muss diese Formel abgeändert werden und führt auf die so genannte "Shannon-Entropie" (oder das "Shannon-Informationsmaß"). Wir gehen auf sie hier nicht ein, sondern merken lediglich für Interessierte an, daß die Information in Bits dann durch

s  =  - p1 2log p1 - p2 2log p2 - ... - pn 2log pn

gegeben ist, wobei p1, p2,... pn die Wahrscheinlichkeiten für das Eintreten der n Möglichkeiten sind. (Sind sie alle gleich 1/n, so reduziert sich dies auf den obigen Ausdruck s = 2log n).
 
2. Computer und Bytes:

Diese Erkenntnisse haben durchaus praktische Konsequenzen für die Übertragung, Verarbeitung und Speicherung von Information. Insbesondere können wir mit ihrer Hilfe verstehen, was es mit der Angabe von Dateigrößen und Speicherplätzen in Bytes (bzw. Kilo-, Mega- und Gigabytes) auf sich hat.

Die meisten modernen Computer und Datenträger benutzen ein "Alphabet" aus 256 ( = 28) Zeichen (die Standard-Buchstaben, Ziffern und eine Reihe von Zusatzzeichen). Der Informationsgewinn, der mit der Kenntnis von einem aus 256 möglichen Zeichen verbunden ist, beträgt nach unseren obigen Erkenntnissen 2lg(256) Bit, das sind 8 Bit, was auch als 1 Byte bezeichnet wird. Hier eine Übersicht über die in der Informationstechnologie verwendeten Einheiten:

1 Byte = 8 Bit
1 Kilobyte º 1 KB = 1024 Byte = 8192 Bit
1 Megabyte º 1 MB = 1024 KB = 1048576 Byte = 8388608 Bit
1 Gigabyte º 1 GB = 1024 MB = 1073741824 Byte = 8589934592 Bit

Jedes in einem gegebenen Datensatz (z.B. einer Datei) enthaltene Zeichen stellt also einen Informationsgehalt von 1 Byte dar. Was bedeutet das für die Computertechnologie?

Die (durchschnittlich) beste Strategie, um ein Zeichen aus 256 eindeutig zu ermitteln, benötigt 8 Ja-Nein-Fragen. Die sparsamste Art, diese Zeichen zu "codieren", besteht darin, 1 Bit logisch als 0 oder 1 darzustellen und jedes der 256 Zeichen als Sequenz von 8 Bits, d.h. als "Wort" aus 8 Buchstaben, die nur 0 oder 1 sein können, zu betrachten. Insgesamt gibt es genau 256 solcher Sequenzen. Dieses System wird "binäre Darstellung" oder "binärer Code" genannt. Hier eine Auswahl von Zeichen in der binären Darstellung (nach dem so genannten ASCII-Standard):

     1   00110001      A   01000001
     2 00110010      B 01000010
     3 00110011      C 01000011
     a 01100001      / 00101111
     b 01100010      . 00101110
     c 01100011      $ 00100100

Um also beispielsweise ein "a" auf einen Datenträger zu speichern, muss die Sequenz "01100001" physikalisch realisiert werden. Der Wert jedes einzelnen Bits (0 oder 1) stellt logisch gesehen die (maximale) Information dar, die durch die Beantwortung einer Ja-Nein-Frage erwartet werden kann, ganz analog zum Ratespiel von Alice und Bob, das wir zu Beginn besprochen haben. Wird die gespeicherte Sequenz später vom Computer "gelesen", so sind dazu 8 Einzelschritte (Ja-Nein-Fragen) nötig.

Unsere technischen Hilfsmittel, um Daten zu übertragen, zu verarbeiten und zu speichern, kommen dieser Darstellungsform entgegen: Sie funktionieren bitweise, d.h. nach einer Ja-Nein-Logik. Oft wird das so ausgedrückt, dass "ein Computer nur 0 oder 1 versteht", wobei es verschiedene physikalische Arten gibt, 0 oder 1 darzustellen. So brennt beispielsweise bei der Speicherung von Daten auf einer CD-ROM ein Laserstrahl eine Vertiefung in eine dafür vorgesehene Stelle (1) oder nicht (0). Das führt zu einer physikalischen Sichtweise der Information als "benötigter Speicherplatz": Man kann sich 1 Bit als ein physikalisches System vorstellen, das zwei Zustände (0 oder 1) einnehmen kann. So ist beispielsweise 1 Bit Speicherplatz auf einer CD-ROM als eine für die Datenaufnahme reservierte Stelle realisiert, die eine Vertiefung (1) oder keine Vertiefung (0) aufweisen kann. Um also ein "a" auf eine CD-ROM zu speichern, wird die Sequenz "01100001" physikalisch realisiert, indem in die zweite, dritte und achte Position des dafür vorgesehenen 8-Bit-Speicherplatzes eine Vertiefung gebrannt wird (1), in die übrigen nicht (0). Um 5 Zeichen (d.h. eine Information von 5 Byte) zu speichern, sind dann 5 solcher 8-Bit-Speicherplätze nötig.

Sie können das Zustandekommen von Dateigrößen nach dieser Logik auf Ihrem Computer nachvollziehen: Legen Sie eine Text-Datei an (*.txt, d.h. "reiner Text", keine Word-Datei oder ähnliches! Unter Windows benutzen Sie z.B. den integrierten "Editor" - englisch "Notepad" - dazu). Schreiben Sie einen einzigen Buchstaben hinein! Die "Größe" (genauer sollte man sagen: der Informationsgehalt) dieser Datei wird dann (rechte Maustaste ® Eigenschaften) als 1 Byte angezeigt. Schreiben Sie 5 Buchstaben (in einer Zeile) hinein, ist die Dateigröße 5 Byte. (Wenn Sie das anhand eines längeren Texts überprüfen wollen, müssen Sie bedenken, dass Zeilenenden durch besondere - im Editor unsichtbare - Steuerzeichen gekennzeichnet sind, die ebenfalls zum 256-Zeichen-Alphabet gehören und daher mitgezählt werden). Eine Text-Datei, die einen Brief mit 1000 Zeichen (Buchstaben, Zahlen, Leerzeichen, Satzzeichen und - unsichtbare - Steuerzeichen) enthält, hat daher eine Größe von 1000 Byte. (Das ist etwas weniger als 1 KB).

 
3. Nachbemerkung zur Kompression von Daten:

Für viele Arten von Daten ist eine weitere Reduktion des benötigten Speicherplatzes möglich. Wir erinnern uns, dass die beste Strategie, eine von n (gleich wahrscheinlichen) Möglichkeiten durch Ja-Nein-Fragen herauszufinden, durchschnittlich 2log n Fragen benötigt. Der springende Punkt ist die Formulierung "gleich wahrscheinlich" (was wir auch als "gleich überraschend" ausgedrückt haben). Das bedeutet, dass an jeder Stelle eines Datensatzes (z.B. einer Datei) jedes Zeichen stehen kann, keines mit mehr Zuversicht erwartet wird als ein anderes, und dass keine Regelmäßigkeiten in der Zeichenabfolge bestehen.

In der Praxis sind diese Bedingungen oft nicht erfüllt. So sind etwa in manchen Sprachen manche Buchstaben häufiger vertreten als andere. In Text-Dateien werden manche Steuerzeichen seltener vertreten sein als Buchstaben, Ziffern und Satzzeichen. Besonders ausgeprägt ist diese Situation im Fall von Bild-Dateien: Zunächst wird (in so genannten "Pixelgraphik"-Formaten) die nötige Farbinformation für jedes einzelne Pixel codiert (das geschieht ebenfalls mit Hilfe des 256 Zeichen-Alphabets). Wenn nun ein Bild beispielsweise ein kleines Objekt vor einer großen hellblauen Fläche zeigt, so ist es "Informationsverschwendung", wenn die Farbinformation für identische Hintergrundpixel abertausend Mal aufgelistet wird. Günstiger ist es, die Gesamtstruktur zu erkennen, als eigene Information zu codieren und die Information für ein Hintergrundpixel nur ein einziges Mal zu speichern.

Um derartige Ideen zu realisieren, gibt es zahlreiche Techniken und Computerprogramme, deren Aufgabe es ist, Dateigrößen möglichst klein zu halten. Manchmal ist man sogar bereit, auf einen Teil der ursprünglichen Information zu verzichten (wie bei den Grafikformaten *.gif und *.jpg oder beim Audioformat *.mp3). Für andere Zwecke (z.B. in der Textverarbeitung) ist das nicht zulässig. Eine Reihe von Programmen ist in der Lage, Dateien zu "komprimieren", die dann (beispielsweise als so genanntes *.zip-Archiv) übertragen und danach vom Empfänger in der ursprünglichen Form (z.B. als Word-Datei) wiederhergestellt werden können.