Was Shannon als Information bezeichnete
Shannon definierte Information durch das Messen von Überraschung. Eine Nachricht mit Wahrscheinlichkeit p trägt:
I = −log₂(p) Bit
Ein bestimmtes Ereignis (p = 1) trägt 0 Bit - keine Überraschung, keine Information. Eine seltene Ereignis (p = 1/1024) trägt 10 Bit.
Hamming weist sofort auf das Problem hin: dies ist eine Formel zur Messung einer Größe, nicht eine Definition des Begriffs. Sie misst überraschungsähnliche Überraschung, nicht menschliche Bedeutung. Ein Student, der bereits die Antwort auf eine Frage kennt, erhält 0 Bit von der Antwort - unabhängig davon, wie wichtig die Antwort für andere ist.
Die Formel ist gut für Telefonanlagen, Radio, Computer geeignet. Sie ist für menschliche Kommunikation, Biologie oder Bedeutung nicht geeignet. Hamming's bevorzugter Name: 'Kommunikationstheorie' anstelle von 'Informationstheorie.'
Entropie
Für ein Alphabet mit q Symbolen mit Wahrscheinlichkeiten p₁, p₂, ..., p_q ist die durchschnittliche Information pro Symbol die Entropie:
H = −Σᵢ pᵢ log₂(pᵢ)
H erreicht seinen Höchstwert, wenn alle Wahrscheinlichkeiten gleich sind: H_max = log₂(q) Bit. Jede nicht-uniforme Verteilung hat eine niedrigere Entropie.
Berechnung der Entropie
Binäre Entropie: Eine Quelle mit zwei Symbolen, P(0) = p, P(1) = 1−p.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H(p) = 0 bei p = 0 oder p = 1 (völlig vorhersagbar). H(p) = 1 Bit bei p = 0,5 (völlig unvorhersagbar).
Gibbs' Ungleichung & Noiseless Coding
Gibbs' Ungleichung: für zwei Wahrscheinlichkeitsverteilungen p = {pᵢ} und q = {qᵢ}:
−Σ pᵢ log₂(pᵢ) ≤ −Σ pᵢ log₂(qᵢ)
mit Gleichheit nur dann, wenn p = q. Dies beruht auf dem elementaren Fakten, dass ln(x) ≤ x − 1 für alle x > 0, mit Gleichheit bei x = 1.
Folgerung: Die Entropie H(p) wird maximiert, wenn alle Symbole gleich wahrscheinlich sind. Für q Symbole: H_max = log₂(q).
Störungsfreie Codiertheorie: Bei einer eindeutig dekodierbaren Code gibt die Kraft-Ungleichung Σ 2^(−lᵢ) ≤ 1 vor, wobei lᵢ die Länge des Codes für Symbol i ist. Gemäß Gibbs' Ungleichung erfüllt die durchschnittliche Codenlänge L = Σ pᵢ lᵢ die Bedingung:
L ≥ H(p) = −Σ pᵢ log₂(pᵢ)
Man kann im Durchschnitt nicht besser als die Entropie tun. Huffman-Codierung erreicht L < H + 1.
Kanal-Kapazität
Ein binäres synchrones Kanal (BSC) ändert jede Bit unabhängig voneinander mit einer Fehlerwahrscheinlichkeit Q = 1 − P. Die Kapazität des BSC - die maximale zuverlässige Informationsrate - ist:
C = 1 + P log₂(P) + Q log₂(Q) = 1 − H(Q)
wobei H(Q) = −Q log₂(Q) − (1−Q) log₂(1−Q) die Binärentropie der Fehlerrate ist.
Bei Q = 0 (keine Fehler): C = 1 Bit/Übertragung (perfekter Kanal). Bei Q = 0,5 (zufällige Umkehrungen): C = 0 (Kanal trägt keine Information). Bei Q = 1 (alle Bits ändern sich): C = 1 (wir wissen genau, was der Sender geschickt hat, einfach alles umkehren).
C misst das maximale Übertragungssatz R, bei dem Sie mit beliebig kleiner Fehlerwahrscheinlichkeit senden können. Wenn R < C, existieren solche Codes. Wenn R > C, existieren sie nicht - kein Code kann die Kapazität übertreffen.
Berechnung der Kanalkapazität
Mit P = 0,9 (10% Fehlerquote, Q = 0,1):
C = 1 + 0,9 log₂(0,9) + 0,1 log₂(0,1)
log₂(0,9) ≈ −0,152, log₂(0,1) ≈ −3,322
C ≈ 1 + 0,9×(−0,152) + 0,1×(−3,322) = 1 − 0,137 − 0,332 ≈ 0,531 Bits/Übertragung
Was beweist das Theorem
Shannons grundlegendes Theorem: für jede Geschwindigkeit R < C existieren Codes mit Blocklänge n (mit n → ∞), die eine Fehlerwahrscheinlichkeit P_E → 0 erreichen.
Der Beweis verwendet eine überraschende Argumentation: zufällige Codes. Statt einen spezifischen Code zu konstruieren, wählte Shannon zufällig Codebücher (Würfel-Flip-Encoding) aus. Er zeigte, dass der durchschnittliche Fehler bei allen möglichen Codebüchern klein ist. Wenn der Durchschnitt klein ist, erreicht mindestens ein Code einen kleinen Fehler.
Kugelbasierte Analyse: Der Sender wählt eine Nachricht aᵢ → Kugel mit dem Radius n(Q + ε₂) um aᵢ in n-dimensionalen binären Raum. Für große n liegt die empfangene Wort bⱼ mit hoher Wahrscheinlichkeit innerhalb dieser Kugel. Der Empfänger decodiert auf die Codewort ab, dessen Kugel bⱼ enthält.
Vier Fälle bestimmen die Fehlerwahrscheinlichkeit P_E:
``
aᵢ im Kugelbereich other aⱼ im Kugelbereich Ausgang
ja nein korrekt (kein Fehler)
yes ja unbestimmte → Fehler
nein ja falsche Dekodierung → Fehler
nein nein außerhalb aller Kugelbereiche → Fehler
``
Die Schranke für P_E ergibt sich zu: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) für geeignet gewählte d und ε₂. Wählt man ε₂ so, dass H(Q+ε₂) < C, wird der Exponent negativ. Für große n geht der zweite Term gegen 0.
Die existenzielle Natur des Satzes
Hamming war präzise darüber, was der Satz beweist und was nicht.
Was es beweist: Zuverlässige Kommunikation mit einer Rate R < C ist für große genug n möglich, theoretisch gesehen.
Was es nicht bietet: explizite Codekonstruktion. Eine zufällige Codebuchlänge n, die die Kapazität annähert, hat ein Codebuch der Größe M × n Bits, wobei sowohl M als auch n astronomisch groß sind. Sie können es nicht speichern oder berechnen.
Fehlertolerierende Codes vs. Shannon: Fehlertolerierende Codes (Hamming, Reed-Solomon, Turbo, LDPC) bieten explizite, berechenbare Konstruktionen. Sie opfern einige Abstand zur Kapazität im Austausch für praktische Encoder und Decoder. Mit wachsendem n und der Korrektur von mehr Fehlern pro Block können praktische Codes die Kapazität eng erreichen.
Das Beispiel der Satelliten im Raum: Voyager und Pioneer nutzten mächtige fehlertolerierende Codes, um über Milliarden Meilen auf 5-20 Watt Strom zu kommunizieren. Lange Blöcke erlaubten es, mehr Fehler pro Block zu korrigieren, was trotz des enormen Rauschens durch die Entfernung nahe an die Kapazität herankam.
Kritische Bewertung
Hamming schloss Kapitel 13 mit einer breiteren Kritik an Definitionen in der Wissenschaft. Shannons Informationsformel misst Maschinen-Überraschung, nicht menschliche Bedeutung. Der Name 'Information Theory' verspricht zu viel. Der Fischernetz-Analogie: Ein Fischer, der nur Fische fängt, die größer als die Maschen des Netzes sind, stellt fest, dass es keine kleineren Fische gibt. Die Einschränkungen des Werkzeugs werden zu den scheinbaren Einschränkungen der Welt.
Das Problem mit Definitionen
Hamming nutzte die Informationstheorie, um einen größeren methodischen Punkt zu vermitteln: Ursprüngliche Definitionen bestimmen mehr, was Sie finden, als die meisten Menschen ahnen.
Shannon wählte, 'Information' als Überraschung zu definieren. Diese Definition war für die Kommunikationstechnik produktiv. Aber sie trug eine bestimmte Reichweite - maschinenähnliche Systeme - in ein Wort ('Information') ein, das universelle Anwendbarkeit nahelegt.
Das Fischernetz-Analogon: Ein Netz mit einem 6-Zoll-Maschendraht fängt nur große Fische. Der Fischer schließt: Mindestgroßezuordnung der Fische beträgt 6 Zoll. Die Schlussfolgerung spiegelt die Werkzeugwahl wider, nicht die Welt.
Intelligenz-Test als Parallele: Ein Test, der 'Intelligenz' messen soll, wird auf eine Normalverteilung kalibriert und dann als Intelligenz definiert. Das Werkzeug formt den Begriff.
Hamming's Empfehlung: Jedes Mal, wenn Sie eine Definition treffen, fragen Sie: (1) wie gut stimmt sie mit Ihrer vorherigen Intuition überein? (2) wie viel verzerrt sie? (3) unter welchen Bedingungen wurde sie formuliert? (4) wird sie jetzt unter anderen Bedingungen angewendet?