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 pi der einzelnen Ereignisse abhängende „Entropie“ H(p1,…,pn) definieren, die drei Bedingungen genügen sollte. Sie soll stetig von den pi abhängen. Für Gleichverteilungen pi=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 pi 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 H(p_1,\ldots,p_n)=-\Sigma_{i=1}^np_i\log p_i 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 L2-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 x(t) = \sum_{n=-\infty}^{\infty} x(nT)\cdot \mathrm{sinc} \left( \frac{t - nT}{T}\right) 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

Kommentare (7)

  1. #1 hwied
    28. Oktober 2020

    Wenn ich das richtig verstehe, dann ist das Abtasttheorem für analog-digital-Wandler nützlich.

  2. #2 Frank Wappler
    30. Oktober 2020

    Thilo schrieb (22. Oktober 2020):
    > […] wollte Shannon eine von den Wahrscheinlichkeiten p_i der einzelnen Ereignisse abhängende „Entropie“ H[ \, p_1, \ldots, 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.

    Gemeint ist womöglich die Additivitätsbedingung:

    H[ \, p_1, \ldots, p_k, \ldots, p_n \, ] =
    H[ \, \sum[ \, p_1, \ldots, p_k \, ], \sum[ \, p_{(k + 1)}, \ldots, p_n \, ] \, ] +
    (\sum[ \, p_1, \ldots, p_k \, ]) \, H[ \, (p_1 / \sum[ \, p_1, \ldots, p_k \, ]), \ldots, (p_k / \sum[ \, p_1, \ldots, p_k \, ]) \, ] +
    (\sum[ \, p_{k + 1}, \ldots, p_n \, ]) \, H[ \, (p_{k + 1} / \sum[ \, p_{k + 1}, \ldots, p_k \, ]), \ldots, (p_n / \sum[ \, p_{k + 1}, \ldots, p_n \, ]) \, ],

    wobei der erste Term der Summe offenbar nicht zur “gewichteten Summe der beiden einzelnen H gehört.

    > Im Beispiel

    … entsprechend dem im obigen ScienceBlog-Artikel gezeigte und verlinkte Bild https://i2.wp.com/scienceblogs.de/mathlog/files/2020/08/12931861-232D-4BDC-9B81-A126E12CF15B.png?ssl=1

    > soll H[ \, 1/2, 1/3, 1/6 \, ] = H[ \, 1/2, 1/2 \, ] + (1/2) \, H[ \, 1/3, 2/3 \, ] sein, wobei der Faktor (1/2) der Wahrscheinlichkeit des zweiten Prozesses entspricht.

    In Anwendung der oben vorgeschlagenen Additivitätsbedingung auf dieses Beispiel, d.h. mit Identifikation der Einzelwahrscheinlichkeiten p_1, p_2, p_3 “von unten nach oben” mit k = 2 ist tatsächlich

    H[ \, 1/6, 1/3, 1/2 \, ] =

    H[ \, (1/6 + 1/3), 1/2 \, ] +
    (1/6 + 1/3) \, H[ \, ((1/6) / (1/6 + 1/3)), ((1/3) / (1/6 + 1/3)) \, ] +
    (1/2) \, H[ \, ((1/2) / (1/2)) \, ] =

    H[ \, 1/2, 1/2 \, ] + (1/2) H[ \, ((1/6) / (1/2)), ((1/3) / (1/2)) \, ] + (1/2) \, H[ \, 1 \, ] =

    H[ \, 1/2, 1/2 \, ] + (1/2) H[ \, 1/3, 2/3 \, ] + 0.

    > Shannon bewies in seiner Arbeit, dass die (bis auf Multiplikation mit einem konstanten Faktor) einzige Funktion mit diesen Eigenschaften
    > H[ \, p_1, \ldots, p_n \, ] = -\Sigma_{i=1}^n[ \, p_i \text{Log}[ \, p_i \, ] \, ] ist, […]

    Reichen die drei oben angegebenen Bedingungen aus, um zu garantieren, dass die gesuchte „Entropie“-Funktion H symmetrisch in all ihren Argumenten ist (sofern das mehr als nur ein einziges Argument ist),
    d.h. dass H[ \, \ldots, p_j, \ldots, p_q, \ldots \, ] = H[ \, \ldots, p_q, \ldots, p_j, \ldots \, ] für alle Indexpaare (j, q) ?
    Oder wäre das eine ausdrücklich zusätzliche, vierte Bedingung an H ?

  3. #3 Frank Wappler
    30. Oktober 2020

    p.s. — ScienceBlogs-Kommentar-HTML-Test:

    “Wahrscheinlichkeiten p<sub>i</sub>” wird dargestellt als “Wahnscheinlichkeiten pi”.

  4. #4 Thilo
    30. Oktober 2020

    Ich denke, dass die Symmetrie nicht vorausgesetzte werden muss. Einen Beweis der Eindeutigkeit findet man z.B. in https://en.wikipedia.org/wiki/Entropy_(information_theory)#Characterization

  5. #5 Frank Wappler
    30. Oktober 2020

    Thilo schrieb (30. Oktober 2020):
    > Einen Beweis der Eindeutigkeit findet man z.B. in https://en.wikipedia.org/wiki/Entropy_(information_theory)#Characterization

    Die dort gezeigte Additivitätsbedingung (ausgedrückt unter Verwendung der obigen Symbolik), H[ \, p_1, p_2 \, ] = H[ \, p_1 \, ] \, + \, H[ \, p_2 \, ], ist allerdings offenbar keine gewichtete Summe, die im obigen ScienceBlog erwähnt wurde.

    > Ich denke, dass die Symmetrie nicht vorausgesetzte werden muss.

    Mit der Wikipedia-Additivitätsbedingung, oder zumindest ihrer Verallgemeinerung zu

    H[ \, p_1, p_2, \ldots, p_n \, ] = H[ \, p_1 \, ] \, + \, H[ \, p_2 \, ] \ldots + H[ \, p_n \, ],

    wäre allerdings die Symmetrie von H direkt durch die Symmetrie des “+“-Operators (für reelle Zahlen) gegeben, die ihrerseits zweifellos vorausgesetzt werden kann und muss.

  6. #7 Theorema Magnum – Mathlog
    19. Februar 2022

    […] Die Leray-Spektralsequenz Konditionierung linearer Gleichungssysteme Das Simplex-Verfahren Das WKS-Abtasttheorem Adelische Poisson-Summation Der Vergleichssatz von Rauch Die Berechnung des Kobordismusrings Die […]