Hauptinhalt
Kurs: Informatik > Lerneinheit 3
Lektion 2: Moderne Informationstheorie- Symbolrate
- Einführung in die Kanalkapazität
- Kanalkapazität erkunden
- Informationen messen
- Ursprung von Markow-Ketten
- Markow-Ketten erforschen
- Eine mathematische Theorie der Kommunikation
- Markow-Ketten erkunden
- Informationsentropie
- Kompressions Kode
- Fehlerkorrektur
- Die Suche nach außerirdischer Intelligenz
© 2024 Khan AcademyNutzungsbedingungenDatenschutzerklärungCookie-Meldung
Eine mathematische Theorie der Kommunikation
Claude Shannon zeigte, wie ein "Englisch aussehender" Text mit Hilfe von Markov-Ketten generiert werden kann. Erstellt von Brit Cruise
Willst du an der Diskussion teilnehmen?
Noch keine Beiträge.
Video-Transkript
Shannon hatte gerade die Entwicklung seiner Theorien zur Kryptographie entwickelt. Ihm war bewusst, dass die menschliche
Kommunikation eine Mischung war aus Zufälligkeit und statistischen Abhängigkeiten. Die Buchstaben in unseren Nachrichten waren offensichtlich abhängig von vorherigen Buchstaben. Im Jahr 1949 veröffentlichte er
einen bahnbrechenden Artikel: "Eine mathematische Theorie der Kommunikation". Darin verwendet er Markov-Modelle als Grundlage dafür, wie wir über Kommunikation denken können. Er beginnt mit einem kleinen Beispiel: Stell dir vor, du siehst einen Haufen Text, geschrieben in einem Alphabet aus A, B und C. Vielleicht weißt du nichts
über diese Sprache, aber du bemerkst, dass As
aneinander zu klumpen scheinen, während Bs und Cs das nicht tun. Er zeigt dann, dass man
eine Maschine entwerfen kann, die ähnlich aussehenden Text erzeugt. Mit Hilfe einer Markov-Kette. Er beginnt mit einer
Annäherung der nullten Ordnung. Das heißt, wir wählen einfach unabhängig jedes Symbol A, B oder C zufällig aus
und bilden eine Abfolge. Beachte jedoch, dass diese Folge nicht wie das Original aussieht. Er zeigt, dass man es besser machen kann mit einer Approximation erster Ordnung. Hier werden die Buchstaben unabhängig
voneinander gewählt, aber nach der Wahrscheinlichkeit der einzelnen Buchstaben in der ursprünglichen Reihenfolge. Das ist etwas besser,
da As nun wahrscheinlicher sind, aber es hat immer noch nicht
die gleiche Struktur. Der nächste Schritt ist entscheidend. Eine Approximation zweiter Ordnung berücksichtigt alle Buchstabenpaare, die vorkommen können. In diesem Fall brauchen wir drei Zustände. Der erste Zustand steht für
alle Paare, die mit A beginnen. Der zweite alle Paare, die mit B beginnen und der dritte Zustand alle
Paare, die mit C beginnen. Beachte nun, dass der A-Becher
viele AA-Paare hat. Das macht Sinn, denn die bedingte Wahrscheinlichkeit für ein A nach einem A höher ist
in unserer ursprünglichen Nachricht. Wir können eine Sequenz mit diesem Modell zweiter Ordnung
relativ einfach erzeugen. Wir beginnen irgendwo und wählen ein Plättchen. Wir notieren uns davon den ersten Buchstaben. und bewegen uns zu dem Becher, der durch
durch den zweiten Buchstaben definiert ist. Dann wählen wir ein neues Plättchen und wiederholen diesen Vorgang unendlich oft. Beachte, dass diese Abfolge nun langsam der ursprünglichen Nachricht ähnlich sieht. Denn dieses Modell erfasst die bedingten Abhängigkeiten zwischen Buchstaben. Wenn wir es noch besser machen wollen, gibt es die Approximation dritter Ordnung. Sie berücksichtigt Folgendes: Gruppen von drei Buchstaben, sogenannte "Trigramme". In diesem Fall würden wir neun Zustände benötigen. Aber als nächstes wendet Shannon genau dieselbe Logik auf einen tatsächlichen englischen Text an,
indem er Statistiken verwendet, die für Buchstaben, Paare und Trigramme etc.
bekannt waren. Er zeigt das gleiche Fortschreiten von
der nullten Ordnung (zufällige Buchstaben) zur ersten Ordnung, zweiter Ordnung und Sequenzen der dritten Ordnung. Anschließend versucht er das Gleiche mit Wörtern anstelle von Buchstaben, und er schreibt: "Die Ähnlichkeit mit gewöhnlichem englischen Text nimmt mit der Tiefe immer weiter zu." In der Tat produzierten diese Maschinen nichtssagenden Text, obwohl sie ungefähr die gleiche statistische Struktur beinhalten, die man auch in der englischen Sprache findet. Shannon definiert dann ein quantitatives Maß für Information, als er feststellt, dass die Menge an Information einer Nachricht
im Design der Maschine gebunden sein muss, welche die ähnlich aussehenden Sequenzen erzeugt. Das bringt uns zu seinem Konzept der Entropie.