Bron → Kanaal: tweestadige codering
Hammings Hoofdstuk 10 begint met het communicatiemodel van Shannon, dat van toepassing is op elk systeem dat informatie verplaatst: telefoongesprekken, radio, harde schijven, DNA-replicatie, computergeheugen.
De tweestadige architectuur
Fase 1: Broncodering (compressie). Converteer het bronbericht naar een compacte weergave. Doel: verwijder redundantie die inherent is aan de bron. Morsecode doet dit: veelvoorkomende letters krijgen korte codes, zeldzame letters krijgen lange codes.
Fase 2: Kanaalcodering (foutbescherming). Voeg gecontroleerde redundantie toe die aangepast is aan de ruiskarakteristieken van het kanaal. Een lawaaierige telefoonlijn heeft meer redundantie nodig dan een glasvezelkabel. De twee fasen ontkoppelen: optimaliseer elk onafhankelijk voor zijn eigen taak.
De gemeenschappelijke interface tussen de twee fasen — een gestandaardiseerde bitstroom — betekent dat elke bron met elk kanaal kan worden gekoppeld. Deze modulariteit is het sleutelinzicht van Shannon in architectuur.
Opslag als communicatie. Hamming merkt op dat het verzenden van een bericht door de ruimte (transmissie) en het verzenden ervan door de tijd (opslag) hetzelfde model gebruiken. Een back-upschijf is een lawaaierig kanaal in de tijd.
De rol van lawaai
Het model van Shannon gaat uit van een radicale aanname: lawaai is onvermijdelijk. Elk kanaal, elk opslagmedium, elk schakelbord introduceert een zekere foutenwaarschijnlijkheid. De vraag is niet 'hoe elimineren we lawaai?' maar 'hoe herstellen we het originele bericht ondanks lawaai?'
Dit contrasteert met klassieke fysica, waar lawaai als nagedachte optreedt (het onzekerheidsprincipe). Shannon beschouwt lawaai als de fundamentele voorwaarde — alle theorie bouwt erop voort.
Voor nu richt Hoofdstuk 10 zich op het ruisloze geval: broncodering zonder fouten. Het kanaalcoderingssprobleem (foutcorrectie) wacht op latere hoofdstukken.
Wanneer kunt u uniek decoderen?
Om een code met variabele lengte nuttig te zijn, moet de ontvanger een bitstroom ondubbelzinnig kunnen decoderen. Hamming illustreert dit met een 4-symboolcode die deze test niet doorstaat, en introduceert vervolgens de oplossing: prefix-vrije codes.
Prefix-vrije voorwaarde
Een code is prefix-vrij (of onmiddellijk) als geen codewoord een voorvoegsel is van enig ander codewoord. Gegeven een ontvangen bitstroom, weet u dat een symbool is beëindigd op het moment dat u een blad in de decodingboom bereikt — geen vooruitkijken nodig.
Voorbeeld van prefix-vrije code voor {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Verifiëren: 0 is geen voorvoegsel van 10, 110, of 111. 10 is geen voorvoegsel van 110 of 111 (10 gevolgd door meer bits geeft 100... of 101..., waarvan geen begint met 110 of 111). De code voldoet.
De decodingprocedure: volg de boom, vertakking op elke inkomende bit, geef het symbool uit wanneer u een blad bereikt, keer terug naar de wortel.
De ongelijkheid van Kraft
Voor elke prefix-vrije binaire code met codewoordlengten l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
Gelijkheid geldt wanneer de code volledig is (bladeren vullen de volledige binaire boom zonder gaten). Dit is een noodzakelijke voorwaarde: geen prefix-vrije code kan deze schenden. Omgekeerd geldt: voor elke set van lengten die aan de ongelijkheid van Kraft voldoet, bestaat er een prefix-vrije code.
De ongelijkheid van Kraft toepassen
Gegeven codewoordlengten, controleer Kraft: Σ 2^(−l_i) ≤ 1.
Voor {s1=0, s2=10, s3=110, s4=111}: de lengten zijn 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Shannon-entropie
De gemiddelde codelengte van een code met variabele lengte: L = Σ p_i · l_i, waarbij p_i de waarschijnlijkheid van symbool s_i is en l_i de lengte van de code is.
Hoe kort kan L worden? Het antwoord van Shannon: niet onder de bronentropie.
Shannon-entropie: H = −Σ p_i · log₂(p_i) (eenheden: bits/symbool)
Entropie meet de gemiddelde informatie per symbool. Hoge entropie betekent dat symbolen ongeveer even waarschijnlijk zijn (maximale onvoorspelbaarheid). Lage entropie betekent dat sommige symbolen domineren (hoge voorspelbaarheid, beter comprimeerbaar).
Ruisloze coderingstelling
Voor elke prefix-vrije code geldt: H(bron) ≤ L ≤ H(bron) + 1.
Geen code kan entropie verslaan. Huffman-codering (volgend hoofdstuk) bereikt de bovengrens: L < H + 1. Voor blockcode over n symbolen wordt de grens strakker: H ≤ L/n < H + 1/n.
Entropie is ook de theoretische compressielimiet: u kunt een bron niet onder H bits per symbool comprimeren zonder informatie te verliezen.
Entropie berekenen
Voorbeeld: 4 symbolen met waarschijnlijkheden p = [1/2, 1/4, 1/8, 1/8].
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bits/symbol
En de Huffman-code {0, 10, 110, 111} bereikt L = 1.75 = H precies.
Waarom entropie een ondergrens is
De ondergrens van het ruisloze coderingstelling is niet slechts een formule — het weerspiegelt iets dieps over informatie: u kunt niet comprimeren wat al maximaal onvoorspelbaar is.
Wanneer alle symbolen even waarschijnlijk zijn (uniforme verdeling), is entropie H = log₂(n) voor n symbolen. Een blokcode met lengte log₂(n) bits bereikt exact H. Geen code kan het beter doen.
Wanneer één symbool domineert (zeg, p(A) = 0.99, p(B) = 0.01), is H klein — dicht bij 0. Een code met variabele lengte kan A een zeer korte code toewijzen, wat het coderen van de stroom zeer efficiënt maakt.
De praktische les: grote compressiewinsten bestaan alleen wanneer symboolwaarschijnlijkheden aanzienlijk verschillen. Als de bron al 'uniform' is (willekeurig uitziend), levert Huffman-codering niets op.