Kurzdefinition

Wie kann man über unzuverlässige Kanäle möglichst zuverlässig Information übertragen? Das ist die Kernfrage der Informationstheorie^[4]. Dabei beschäftigt sich die Informationstheorie nicht mit der technischen Verbesserung der Übertragungskanäle (Telephon, Funk, Datenleitungen etc.) sondern mit der Art der übertragenen Information selbst. Das ist hier mit einem Beispiel kurz vorgestellt.

Das Problem mit der Festplatte

In seinen Vorlesung an der Universität Cambridge (England, 2014) verwendete David J. C. Macay als Beispiel einen sogenannten „binären symmetrischen Kanal“: ein Sender schickt ein Bit Information (0 oder 1 = binär), das von einem Empfänger gelesen werden soll. Dabei gibt es eine Wahrscheinlichkeit p, dass fälschlicherweise eine 0 übertragen wird, obwohl eine 1 gesendet war. Zudem gibt es eine gleich große Wahrscheinlichkeit, dass eine 1 übertragen wird obwohl eine 0 gesendet war (symmetrisch). Als Beispiel wählt MacKay eine fiktive Festplatte mit einem Speichervolumen von einem Gigabyte (1000000000 oder 10^9 Byte). Speichert man selbst Daten auf einer Festplatte, die man später selbst wieder lesen möchte, dann ist man selbst sowohl Sender als auch Empfänger und die Festplätte ist der Datenkanal von der Gegenwart in die Zukunft. Die Hersteller von Festplatten streben MacKay zufolge an, dass die Wahrscheinlichkeit für eine fehlerhafte Übertragung von einem einzelnen Bit bei 10 hoch -18 liegen soll. Wenn eine Trillion geschrieben werden, dann ist dabei im Durchschnitt ein fehlerhaftes Bit dabei. Typische Fragen der Informationstheorie ist es nun, wie kann der Sender erkennen, dass ein Bit falsch übertragen wurde und wie kann man die gesendete Information möglichst zuverlässig rekonstruieren?

Beispielhafte Lösungsmöglichkeit: Redundanz

Eine Möglichkeit die Datenübertragung über Festplatten zuverlässiger zu machen ist es, jedes Byte (acht Folgen von Nullen oder Einsen) dreimal zu senden. Ist das korrekte Byte aus Sicht des Senders zum Beispiel 10000001 so wird dieses dreimal gesendet: 10000001 10000001 10000001. Nun kommt beim Empfänger ein Byte in falscher Form an (flipped byte): 00000001 10000001 10000001. Der Empfänger kann nun erkennen, dass die drei Bytes nicht identisch sind, also ein Fehler passiert sein muss. Gleichzeitig sieht er, dass zwei der drei Bytes identisch sind, diese also mit hoher (aber nicht hundertprozentiger) Wahrscheinlichkeit die korrekten Versionen sind. Damit kann der Empfänger trotz der fehlerhaften Datenübertragung die ursprünglich korrekten Daten wieder herstellen. Diese - nicht sehr effiziente - Lösungsmöglichkeit bezeichnet man als Redundanz. Ziel der Informationstheorie ist es, deutlich effektivere und effizientere Methoden zu entwickeln.

Die Binomialverteilung als zentrales mathematisches Konzept

MacKay bezeichnet in der ersten seiner insgesamt 16 Vorlesungen die Binomialverteilung (Bernoullikette) als das einzige mathematische Konzept, das man zum tieferen Verständnis am Anfang wirklich benötigt, aber auch sehr gut beherrschen muss. Mit den entsprechenden Formeln aus der Wahrscheinlichkeitsrechnung kann man zum Beispiel abschätzen, wie oft es im Durschnitt vorkommt, dass von drei gleichartigen versendeten (redundaten) Bytes mehr als eines falsch ist. Umgekehrt kann man mit dieser Rechnung abschätzen, wie gut sich die Redundanz zur Erhöhung der Zuverlässigkeit von Datenübertragungen eignet. Das grundlegende Rechenmodell dazu ist die Bernoulli-Kette ↗

Fußnoten

[1] Claude Elwood Shannon: A Mathematical Theory of Communication. In: Bell System Technical Journal. Short Hills N.J. 27.1948, (Juli, Oktober), S. 379–423, 623–656. ISSN 0005-8580.

[2] Warren Weaver, Claude Elwood Shannon: The Mathematical Theory of Communication. University of Illinois Press, Urbana Ill 1949. ISBN 0-252-72548-4. Deutsch: Mathematische Grundlagen in der Informationstheorie. Übersetzt von Helmut Dressler. Oldenbourg, München 1976. ISBN 3-486-39851-2.

[3] Axel Roch: Claude E. Shannon. Spielzeug, Leben und die geheime Geschichte seiner Theorie der Information. gegenstalt Verlag, Berlin 2009. ISBN 978-3-9813156-0-8.

[4] David J. C. MacKay: Information Theory, Inference, and Learning Algorithms. Cambridge University Press. 2003. 640 Seiten. ISBN: 978-0521642989. Sehr gut verständliche Einführung, viele Beispiele zum Mitdenken.