Quellencodierung

Wir beginnen mit einem Problem. Alice und Bob leben in Walddörfern die weit voneinander entfernt sind. es besteht keine Sichtverbindung zwischen ihnen und sie müssen kommunizieren Also beschließen sie, ein Kabel zwischen den beiden Häusern zu verlegen Sie ziehen das Kabel stramm und befestigen eine Blechdose an beiden Enden so dass sie leise und undeutlich über das Kabel sprechen können Doch es gibt ein Problem Lärm wenn es stark windet wird es unmöglich, das Signal durch das Rauschen zu hören. Sie brauchen also einen Weg, um das das Energieniveau des Signals zu erhöhen um es vom Rauschen zu trennen. Das bringt Bob auf eine Idee sie können einfach am Draht zupfen was bei dem Lärm viel einfacher zu erkennen ist, aber das führt zu einem neuen Problem. Wie kodieren sie ihre Nachrichten als Zupfer? Nun, da sie Brettspiele über die Distanz spielen möchten nehmen sie die häufigsten Nachrichten zuerst in Angriff: Das Ergebnis von zwei Würfelwürfen. Das ist die Botschaft die sie senden möchten, sie kann als die Wahl eines Symbols aus einer endlichen Anzahl von Symbolen betrachtet werden. In diesem Fall eine der 11 möglichen Zahlenkombinationen. Wir nennen sie eine diskrete Quelle. Sie entscheiden sich zunächst für die die einfachste Methode: sie senden das Ergebnis als die Anzahl der Zupfungen Um eine 3 zu senden, zupfen sie 3 mal. 9 sind neun Zupfungen und 12 sind zwölf Zupfungen. Allerdings merken sie bald, dass dies viel länger dauert, als es nötig wäre. Durch Übung finden sie heraus, dass ihre maximale Zupfgeschwindigkeit zwei Zupfungen pro Sekunde ist. Wenn sie schneller sind, werden sie verwirrt. Zwei Zupfungen pro Sekunde können also als die Rate oder die Kapazität betrachtet werden die zum Senden von Informationen auf diese Weise möglich ist. Es stellt sich heraus, dass der häufigste häufigste Wurf eine 7 ist, es dauert also 3,5 Sekunden um die Zahl sieben zu senden Alice merkt dann, dass sie sich verbessern können, wenn sie ihre Codierungsstrategie ändern Sie stellt fest, dass die Wahrscheinlichkeit eines bestimmten Zahlenwert, einem einfachen Muster folgt: es gibt eine Möglichkeit, eine 2 zu würfeln, zwei Möglichkeiten, eine 3 zu würfeln drei Möglichkeiten, eine 4 zu würfeln, vier Möglichkeiten, eine 5 zu würfeln fünf Möglichkeiten, eine 6 zu würfeln und sechs Möglichkeiten, eine eine 7 zu würfeln (die häufigste Kombination) Es gibt fünf Möglichkeiten, eine 8 zu würfeln vier Möglichkeiten für eine 9 und so weiter zurück zu einer Möglichkeit für eine Zwölf. Und das ist das Diagramm, das die Anzahl der Möglichkeiten, wie jedes Ergebnis auftreten kann darstellt. Das Muster ist offensichtlich. Ändern wir nun die Grafik in Anzahl der Zupfungen gegenüber jeder Kombination. Sie fährt fort, indem sie die häufigste Zahl, sieben, auf das kürzeste Signal, einen Zupfer, legt. Dann geht sie weiter zur nächst- wahrscheinlichsten Zahl und wenn es einen Gleichstand gibt wählt sie eine nach dem Zufallsprinzip aus. In diesem Fall wählt sie die sechs für zwei Zupfer und dann acht für drei Zupfer und dann wieder fünf für vier Zupfungen und neun für fünf Zupfungen und hin und her, bis wir 12 erreichen der 11 Zupfungen zugewiesen werden. Jetzt kann die häufigste Zahl, sieben, in weniger als einer Sekunde gesendet werden. Eine enorme Verbesserung! Mit dieser Symboländerung können sie durchschnittlich mehr Informationen in der gleichen Zeit versenden. Tatsächlich ist diese Kodierungsstrategie für dieses einfache Beispiel optimal da es unmöglich ist, eine eine kürzere Methode zu finden, die Ergebnisse der beiden Würfel mit identischen Zupfungen zu kommunizieren. Aber nachdem sie den Draht einige Zeit benuzt haben kam Bob auf eine neue Idee.