Theorema Magnum MCMIL: das WKS–Abtasttheorem

Claude Shannons 1948 veröffentlichte Arbeit „A mathematical theory of communication“ gilt heute als Beginn der Informationstheorie, unter anderem wegen des dort erstmals definierten Begriffs der Entropie.
Am Beginn der Arbeit stand die Definition des Bits als Informationseinheit, und die Definition von Kommunikationssystemen entsprechend dem folgenden Schema:

Im Weiteren unterscheidet Shannon diskrete, stetige und gemischte Systeme.
Diskrete Informationen werden als Markow-Ketten kodiert. Shannon veranschaulichte das am Beispiel unterschiedlich guter künstlicher Approximationen der englischen Sprache. Die schlechteste Approximation erhält man, indem man Buchstaben zufällig und gleichverteilt wählt. Die nächstbeste Approximation wählt Buchstaben zufällig entsprechend ihrer Häufigkeit in der englischen Sprache. Als bessere Approximationen kann man dann Paare oder Tripel von Buchstaben nach ihrer Häufigkeit im Englischen wählen. Und schließlich kann man auch ganze Worte oder sogar Wortpaare zufällig entsprechend ihrer Häufigkeit im Englischen wählen. Man bekommt immer bessere Annäherungen an die englische Sprache.

Um die von einer Markow-Kette produzierte Information zu messen, wollte Shannon eine von den Wahrscheinlichkeiten p_i der einzelnen Ereignisse abhängende „Entropie“ H(p₁,…,p_n) definieren, die drei Bedingungen genügen sollte. Sie soll stetig von den p_i abhängen. Für Gleichverteilungen p_i=1/n soll sie eine monoton wachsende Funktion in n sein. Und sie soll eine Additivitätsbedingung erfüllen: wenn eine Möglichkeit mit Wahrscheinlichkeit p_i in zwei Möglichkeiten zerlegt werden kann, dann soll das ursprüngliche H die gewichtete Summe der beiden einzelnen H sein.

Im Beispiel soll H(1/2,1/3,1/6)=H(1/2,1/2)+1/2H(1/3,2/3) sein, wobei der Faktor 1/2 der Wahrscheinlichkeit des zweiten Prozesses entspricht.
Shannon bewies in seiner Arbeit, dass die (bis auf Multiplikation mit einem konstanten Faktor) einzige Funktion mit diesen Eigenschaften ist, die er als „Entropie“ bezeichnete. (Es wird kolportiert, John von Neumann habe ihm diese Bezeichnung nahegelegt: niemand wisse, was Entropie ist, so dass er in Diskussionen immer einen Vorteil haben werde.) Shannon bewies dann einen „Fundamentalsatz“, in dem er die Entropie H der Quelle und die Kapazität C des Kanals in Beziehung setzte: man könne bis zu C/H Symbole pro Sekunde übertragen. Mit Hilfe des Entropiebegriffs weiß man nun also, was die effizienteste Kodierung einer Nachricht ist. Einen ähnlichen Fundamentalsatz bewies er auch für diskrete Kanäle mit Rauschen.
Schließlich wurden im Hauptteil der Arbeit stetige Prozesse diskutiert, wo er in der Definition der Entropie die Summe durch ein Integral ersetzte und mit dieser Definition verschiedene mathematische Sätze bewies.

Die 1948 erschienene Arbeit war bei den Ingenieuren sofort ein voller Erfolg und ist bis heute die Grundlage der Informationstheorie. Im folgenden Jahr 1949 veröffentlichte Shannon dann die Arbeit „Communication in the presence of noise“. Dort bewies er (neben anderen Sätzen) das Abtasttheorem:
Eine Funktion, die keine Frequenzen höher als W enthält, ist eindeutig bestimmt durch ihre Funktionswerte in einer Reihe von jeweils im Abstand W/2 auseinanderliegenden Punkten.

Was bedeutet dieser Satz mathematisch? Als Frequenz einer periodischen Funktion bezeichnet man das Inverse f=1/T ihrer kleinsten Periode T. Die von Shannon betrachteten Funktionen sind L²-Funktionen, die sich bekanntlich in eine Fourier-Reihe als Summe periodischer Funktion zerlegen lassen. Mit den Frequenzen einer Funktion sind die Frequenzen der periodischen Funktionen in der Fourier-Entwicklung gemeint.

Der Beweis des Abtasttheorems ist konstruktiv. Aus den Funktionswerten x(nT) in den ganzzahligen Vielfachen der Periode T kann man die Funktion x(t) mit der Interpolationsformel rekonstruieren.
Das Bild zeigt die Notwendigkeit der Bedingung: bei zunehmender Frequenz gibt es mehrere interpolierende Funktionen mit denselben Funktionswerten.

Shannon schrieb in seiner Arbeit, der Abtastsatz sei „common knowledge in the communication art“. Tatsächlich war die Interpolationsformel schon 1898 von Borel und 1915 von Whittaker gefunden worden. Das Abtasttheorem hatten Kostelnikow 1933 und Raabe 1939 formuliert. Shannons Beweis fußte wesentlich auf Nyquists Arbeiten über trigonometrische Polynome, deren Ergebnisse ebenfalls parallel von anderen gefunden worden waren. Aber erst durch die Entwicklung der Informationstheorie als Folge von Shannons Grundlagenarbeit bekam dieser Satz seine Bedeutung.

Shannons Arbeit legte die theoretischen Grundlagen der Kodierungstheorie, in der es darum geht, durch möglichst effizientes Einfügen von Redundanzen eine Absicherung gegen auftretende Fehler zu erreichen.
Für handhabbare Algorithmen verwendet man Codes, die algebraische Strukturen verwenden wie zum Beispiel Vektorräume über endlichen Körpern. Ebenfalls noch 1949 wurden die ersten solchen Codes gefunden: die Golay-Codes und die Hamming-Codes.

Bild: https://informatik.rostfrank.de/info/lex06/shannon.html