Informationen messen

Betrachte folgendes, Alice und Bob haben herausgefunden, wie sie Nachrichten zwischen ihren Baumhäusern übermitteln können Zuerst benutzten sie nachts Flammen und tagsüber Fensterläden. Dann benutzten sie einen Draht, den sie auf verschiedene Arten zupften. Schließlich elektrifizierten sie diesen Draht, um elektrische Impulse zu senden und sind nun bei der Arbeit an einer experimentellen, drahtlosen Methode. Das Problem ist, dass sie, um für ihre Ausrüstung zu bezahlen, Geld brauchen. Also beschlossen sie, ihre Dienstleistung gegen eine Gebühr anzubieten. Und schon am ersten Tag hatte Alice drei neue Kunden die Nachrichten an ihre Freunde drüben in Bobs Baumhaus übermitteln wollten. Der erste Kunde wollte eine Liste mit 10 Münzwürfen senden, der zweite Kunde wollte ein Wort mit sechs Buchstaben senden, und der dritte Kunde wollte ein Pokerblatt schicken. Die Frage ist nun, wie viel sie verlangen sollte? Nun, der Preis für eine Nachricht sollte davon abhängen wie lange Alice braucht, um sie zu übermitteln. Aber wie kann sie die Länge von verschiedenen Arten von Nachrichten mit einer gemeinsamen Einheit messen? Um das herauszufinden, wollen wir ein Spiel spielen. Stell dir vor, du wärst jetzt Bob, und du weißt, dass Alice dir dir eine Nachricht schicken will, aber alles, was du tun kannst, ist Antworten auf ja-nein Fragen zu bekommen. Alice wird antworten, indem sie eine Folge von Nullen oder Einsen, in verschiedenen Variation verwendet. Erinnere dich daran, dass alle ihre Methoden der Übertragung den Austausch von Unterschieden beinhalten. So könnte eine Eins durch eine offene Flamme dargestellt werden oder ein offener Fensterladen oder ein elektrischer Impuls. Ganz gleich, wie sie sich äußern, wir können sie einfach binäre Ziffern nennen, denn eine Binärziffer kann nur einen von zwei Werten haben: Null oder Eins. Sagen wir also, die Null steht für ein Nein und eine Eins steht für ein Ja. Deine Aufgabe ist es nun, immer die geringstmögliche Anzahl von Fragen zu stellen, um die genaue Botschaft zu ermitteln. Betrachten wir zunächst die Münzwürfe. Für jedes Symbol wird die Absenderin, Alice, eines von zwei verschiedenen Symbolen, Kopf oder Zahl, wählen. Wie viele Fragen musst du jetzt stellen um herauszufinden, welches sie gewählt hat? Eine Frage wie "Ist es es Kopf, reicht aus. Was ist die Mindestanzahl an Fragen für 10 Münzwürfe ? Nun, 10 Würfe mal eine Frage pro Wurf ergibt 10 Fragen oder 10 binäre Ziffern um diese Nachricht zu übermitteln. Betrachten wir nun die Buchstaben. Für jedes Symbol wählt die Absenderin, Alice, eines von 26 verschiedenen Symbolen aus. Beginnen wir mit der einfachsten Nachricht, die nur aus einem Buchstaben besteht. Wie viele Fragen werden benötigt? Ist es A? Ist es B? Ist es C? Ist es D? Und so weiter, aber das ist nicht die Mindestanzahl von Fragen. Das Beste, was du tun kannst, ist, Fragen zu stellen die die Hälfte der Möglichkeiten ausschließen. Zum Beispiel, die Mitte des Alphabets liegt zwischen M und N. Wir könnten also zuerst fragen: Ist das Symbol kleiner als N? Wenn wir eine Eins erhalten, dann schneiden wir die Hälfte ab. und es bleiben 13 Buchstaben übrig, und da wir einen Buchstaben nicht in zwei Hälften teilen können, unterteilen wir die möglichen Buchstaben in Gruppen von sechs und sieben und fragen, ob es kleiner als G ist? Wir erhalten eine Eins, was ja bedeutet, und jetzt bleiben uns noch sechs mögliche Buchstaben, und wir können sie in zwei Hälften teilen und fragen: "Ist es kleiner als D? Wir erhalten eine Null, also ein Nein, Damit bleiben uns drei mögliche Buchstaben, und jetzt können wir uns eine Seite auswählen und fragen: Ist es D? Wir erhalten eine Null, also ein Nein, und schließlich bleiben uns noch zwei Möglichkeiten. Wir fragen: Ist es E? Wir erhalten ein Nein, und nach fünf Fragen, haben wir das Symbol F identifiziert richtig identifiziert. Achte darauf, dass wir nie mehr als fünf Fragen stellen müssen, daher ist die Anzahl der Fragen mindestens vier und höchstens höchstens fünf. Allgemein ausgedrückt, zwei hoch der Anzahl der Fragen ist gleich der Anzahl der möglichen Nachrichten, die wir zuvor als den Nachrichtenraum definiert haben. Wie können wir also den genauen Durchschnitt oder erwartete Anzahl von Fragen bei einem Nachrichtenraum von 26 berechnen ? Wir stellen die umgekehrte Frage. Zwei hoch was ist gleich 26? Um diese Art von Fragen zu beantworten, verwenden wir natürlich eine logarithmische Funktion zur Basis zwei, denn der Logarithmus zur Basis zwei von 26 ist der Exponent auf den die Zahl zwei erhöht werden muss, um 26 zu erhalten, Es ist ungefähr 4,7 Also, im Durchschnitt werden ungefähr 4,7 Fragen pro Buchstabe mindestens benötigt, Da Alice ein Wort mit sechs Buchstaben übermittelt, kann Bob erwarten, dass er mindestens 28,2 Fragen stellen muss Das bedeutet, dass Alice höchstens 29 binäre Ziffern senden muss. Wenden wir nun diese Formel auf eine neue Nachricht, das Pokerblatt, an. Für jedes Symbol muss die Absenderin , Alice, eines von 52 Symbolen auswählen. Auch in diesem Fall, ist die Anzahl der Fragen gleich der Anzahl der Male, die wir den Stapel aufteilen und Alice fragen müssen, in welchem Stapel sich das Symbol befindet, Bis nur noch eine Karte übrig bleibt benötgen wir manchmal 5 und manchmal 6 Fragen, also Aufteilungen. Wir können Zeit sparen und einfach unsere Gleichung verwenden. Der Logarithmus zur Basis zwei von 52 ist ungefähr 5,7, da die Zweierpotenz von 5,7 ungefähr 52 ist. Die Mindestanzahl der Fragen ist also im Durchschnitt 5,7 pro Karte. Ein Pokerblatt besteht aus fünf Karten. Um ein Pokerblatt zu übertragen, braucht man also 28,5 Fragen im Durchschnitt. Wir sind fertig. Wir haben jetzt unsere Einheit. Sie basiert auf der Mindestanzahl von Fragen um die Nachricht zu definieren also die Höhe des Entscheidungsbaums, Da Alice diese Informationen Informationen als binäre Ziffern überträgt können wir dies abkürzen und unsere Einheit Bit nennen, anstelle von Binärziffer. Wir haben also: 10 Münzenwürfe benötigen 10 Bits, das Wort mit sechs Buchstaben benötigt 28,2 Bits, und für das Pokerblatt werden 28,5 Bits benötigt. Alice beschließt dann, einen einen Penny pro Bit zu verlangen und beginnt, ihre Gebühren zu kassieren. Diese Idee kam in den 1920er Jahren auf. Es war eines der abstrakteren Probleme über das Kommunikationsingenieure nachgedacht haben. Ralph Hartley war ein produktiver Elektronik-Forscher der auf den Ideen von Harry Nyquist aufbaute, die beide nach dem Ersten Weltkrieg in den Bell Labs arbeiteten 1928 veröffentlichte Hartley eine wichtige Arbeit mit dem Titel, Die Übertragung von Informationen, Darin definiert er das Wort Information mit Hilfe des Symbols H, denn H ist gleich N mal dem Logarithmus von S, wobei H unsere Information ist, N die Anzahl der Symbole ist, egal ob es sich um Noten, Buchstaben, Zahlen, etc. handelt, und S ist die Anzahl der verschiedenen Symbole die bei jeder Auswahl verfügbar ist. Man kann auch schreiben H ist gleich dem Logarithmus von S zur Potenz von N, Hartley schreibt: "Was wir also getan haben ist, dass wir als praktisches Maß für die Information den Logarithmus der Anzahl der möglichen Symbolfolgen nehmen." Die Information ist also der Logarithmus des Nachrichtenraums; Du musst jedoch beachten, dass wir in dieser Lektion davon ausgegangen sind, dass die Symbolauswahl zufällig ist, dies ist eine praktische Vereinfachung. Wir wissen jedoch, dass in Wirklichkeit die meiste Kommunikation, wie zum Beispiel Sprache, nicht immer zufällig ist. Sie ist eine subtile Mischung aus Vorhersehbarkeit und Überraschung. Wir würfeln nicht, wenn wir Briefe schreiben, und es ist diese Vorhersehbarkeit die helfen kann erheblichen Einsparungen bei Länge der Übertragung zu erreichen denn wenn wir Dinge vorhersagen können, müssen wir nicht so viele Ja- oder Nein-Fragen stellen um sie zu definieren. Aber wie könnten wir diesen subtilen Unterschied formell modellieren? Diese Frage bringt uns zur wichtigste Erkenntnis in unserer Geschichte. Kannst du dir vorstellen, was das sein könnte?