Wat Shannon Informatie Noemde
Shannon definieerde informatie door verrassing te meten. Een bericht met waarschijnlijkheid p bevat:
I = −log₂(p) bits
Een zeker gebeuren (p = 1) bevat 0 bits — geen verrassing, geen informatie. Een zeldzaam gebeuren (p = 1/1024) bevat 10 bits.
Hamming wijst onmiddellijk op het probleem: dit is een formule voor het meten van een hoeveelheid, niet een definitie van het concept. Het meet machine-achtige verrassing, niet menselijke betekenis. Een student die het antwoord op een vraag al kent, ontvangt 0 bits van het antwoord — ongeacht hoe belangrijk het antwoord voor anderen is.
De formule werkt goed voor telefoonystemen, radio, computers. Het werkt slecht voor menselijke communicatie, biologie, of betekenis. Hamming's voorkeursnaam: 'Communicatietheorie', niet 'Informatietheorie.'
Entropie
Voor een alfabet van q symbolen met waarschijnlijkheden p₁, p₂, ..., p_q, is de gemiddelde informatie per symbool de entropie:
H = −Σᵢ pᵢ log₂(pᵢ)
H bereikt zijn maximum wanneer alle waarschijnlijkheden gelijk zijn: H_max = log₂(q) bits. Elke niet-uniforme verdeling heeft lagere entropie.
Entropie Berekenen
Binaire entropie: een bron met twee symbolen, P(0) = p, P(1) = 1−p.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H(p) = 0 bij p = 0 of p = 1 (volledig voorspelbaar). H(p) = 1 bit bij p = 0,5 (volledig onvoorspelbaar).
Gibbs' Ongelijkheid & Ruis-Vrije Codering
Gibbs' ongelijkheid: voor elke twee waarschijnlijkheidsverdelingen p = {pᵢ} & q = {qᵢ}:
−Σ pᵢ log₂(pᵢ) ≤ −Σ pᵢ log₂(qᵢ)
met gelijkheid alleen wanneer p = q. Dit steunt op het elementaire feit dat ln(x) ≤ x − 1 voor alle x > 0, met gelijkheid bij x = 1.
Gevolg: entropie H(p) wordt gemaximaliseerd wanneer alle symbolen gelijk waarschijnlijk zijn. Voor q symbolen: H_max = log₂(q).
Ruis-vrije coderingstelling: gegeven een uniek decodeerbare code, vereist de Kraft-ongelijkheid Σ 2^(−lᵢ) ≤ 1 waarbij lᵢ de lengte van de code voor symbool i is. Door Gibbs' ongelijkheid, voldoet de gemiddelde codelengde L = Σ pᵢ lᵢ aan:
L ≥ H(p) = −Σ pᵢ log₂(pᵢ)
Je kunt gemiddeld niet beter doen dan entropie. Huffman-codering bereikt L < H + 1.
Kanaalcapaciteit
Een binair symmetrisch kanaal (BSC) keert elk bit onafhankelijk om met foutenwaarschijnlijkheid Q = 1 − P. De capaciteit van het BSC — maximale betrouwbare informatiefrequentie — is:
C = 1 + P log₂(P) + Q log₂(Q) = 1 − H(Q)
waarbij H(Q) = −Q log₂(Q) − (1−Q) log₂(1−Q) de binaire entropie van de foutfrequentie is.
Bij Q = 0 (geen fouten): C = 1 bit/transmissie (perfect kanaal). Bij Q = 0,5 (willekeurig omkeuren): C = 0 (kanaal voert geen informatie). Bij Q = 1 (alle bits keuren om): C = 1 (je weet precies wat de zender zond, keer gewoon alles om).
C meet de maximale frequentie R waarbij je kunt zenden met willekeurig kleine foutwaarschijnlijkheid. Als R < C, bestaan dergelijke codes. Als R > C, bestaan ze niet — geen code kan capaciteit verslaan.
Kanaalcapaciteit Berekenen
Met P = 0,9 (10% foutfrequentie, 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/transmissie
Wat de Stelling Bewijst
Shannon's fundamentale stelling: voor elke frequentie R < C, bestaan codes van bloklengte n (met n → ∞) die foutwaarschijnlijkheid P_E → 0 bereiken.
Het bewijs gebruikt een verrassend argument: willekeurige codes. In plaats van een specifieke code te construeren, middelde Shannon over alle mogelijke willekeurige codeboeken (muntworp-codering). Hij toonde aan dat de gemiddelde fout over alle codeboeken klein is. Als het gemiddelde klein is, bereikt minstens één code kleine fout.
Bol-gebaseerde analyse: de zender kiest bericht aᵢ → bol met straal n(Q + ε₂) rond aᵢ in n-dimensionale binaire ruimte. Voor grote n ligt het ontvangen woord bⱼ met hoge waarschijnlijkheid in deze bol. De ontvanger decodeert naar het codewoord waarvan de bol bⱼ bevat.
Vier gevallen bepalen foutwaarschijnlijkheid P_E:
``
aᵢ in bol andere aⱼ in bol uitkomst
ja nee juist (geen fout)
ja ja dubbelzinnig → fout
nee ja foutieve decodering → fout
nee nee buiten alle bollen → fout
``
De grens op P_E wordt: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) voor geschikt gekozen d & ε₂. Kies ε₂ zodat H(Q+ε₂) < C maakt de exponent negatief. Voor grote n, de tweede term → 0.
De Existentiële Aard van de Stelling
Hamming was nauwkeurig over wat de stelling wel & niet biedt.
Wat het bewijst: betrouwbare communicatie bij frequentie R < C is in principe mogelijk, voor groot genoeg n.
Wat het niet biedt: expliciete codeconstructie. Een willekeurige code van lengte n groot genoeg om capaciteit te benaderen, heeft een codeboek van grootte M × n bitjes, waarbij beide M & n astronomisch groot zijn. Je kunt het niet opslaan of mee rekenen.
Foutcorrectiecodes versus Shannon: foutcorrectiecodes (Hamming, Reed-Solomon, turbo, LDPC) bieden expliciete, berekenbare constructies. Ze offeren enige afstand tot capaciteit op in ruil voor praktische codeers- & decodeersapparatuur. Als n groeit & meer fouten per blok worden gecorrigeerd, kunnen praktische codes capaciteit dicht benaderen.
Het ruimtevaartuigenvoorbeeld: Voyager & Pioneer gebruikten krachtige foutcorrectiecodes om te communiceren over miljarden kilometers op 5–20 watt vermogen. Lange blok lengtes stelden meer fouten per blok in staat gecorrigeerd te worden, wat capaciteit dicht benaderde ondanks de enorme ruis van afstand.
Kritische Beoordeling
Hamming sloot Hoofdstuk 13 af met een breder kritiek op definities in wetenschap. Shannon's informatieformule meet machine-verrassing, niet menselijke betekenis. De naam 'Informatietheorie' belooft teveel. De visnettaanwijzing: een visser die alleen vis groter dan het netmaas vangt, concludeert dat er geen kleinere vis is. De tool's beperkingen worden de wereld's schijnbare restricties.
Het Probleem met Definities
Hamming gebruikte informatietheorie om een groter methodologisch punt te maken: initiale definities bepalen wat je vindt, meer dan de meeste mensen zich realiseren.
Shannon koos ervoor om 'informatie' als verrassing te definiëren. Die definitie was productief voor communicatietechniek. Maar het importeerde een specifiek bereik — machine-achtige systemen — in een woord ('informatie') dat universele toepasselijkheid suggereert.
De visnettaanwijzing: een net met 6-inch mazen vangt alleen grote vis. De visser concludeert: minimale visgrootte is 6 inch. De conclusie weerspiegelt de tool, niet de wereld.
IQ als parallel: een test ontworpen om 'intelligentie' te meten, gekalibreerd om normale verdeling te produceren, dan gebruikt om intelligentie te definiëren. De tool geeft vorm aan het concept.
Hamming's aanbeveling: telkens wanneer je een definitie tegenkomen, vraag jezelf (1) hoeveel stemt het overeen met je voorafgaande intuïtie? (2) hoeveel vervormt het? (3) onder welke omstandigheden werd het gesteld? (4) wordt het nu onder verschillende omstandigheden toegepast?