Källa → Kanal: Tvåstegs kodning
Hammings kapitel 10 börjar med Shannons kommunikationsmodell, som gäller för varje system som flyttar information: telefonsamtal, radio, hårddiskar, DNA-replikering, datorminnne.
Tvåstegs arkitekturen
Steg 1: Källkodning (komprimering). Konvertera källmeddelandet till en kompakt representation. Mål: ta bort redundans som är naturlig för källan. Morsekod gör detta: vanliga bokstäver får korta koder, sällsynta bokstäver får långa koder.
Steg 2: Kanalkodning (felskydd). Lägg till kontrollerad redundans anpassad till kanalens bullrigenskaper. En bullrig telefonledning behöver mer redundans än en fiberoptisk kabel. De två stegen är oberoende: optimera varje steg själv för sin egen uppgift.
Det gemensamma gränssnittet mellan de två stegen — en standardiserad bitström — betyder att vilken källa som helst kan paras med vilken kanal som helst. Denna modularitet är Shannons nyckelinsikt för arkitektur.
Lagring som kommunikation. Hamming noterar att att skicka ett meddelande genom rum (transmission) och att skicka det genom tid (lagring) använder samma modell. En säkerhetskopia är en bullrig kanal i tiden.
Bullrets roll
Shannons modell gör ett radikalt antagande: buller är oundvikligt. Varje kanal, varje lagringsmedium, varje omkopplkrets introducerar någon sannolikhet för fel. Frågan är inte 'hur eliminerar vi buller?' utan 'hur återhämtar vi originalmeddelandet trots buller?'
Detta kontrasterar med klassisk fysik, där buller kommer som en eftergift (osäkerhetsprincipen). Shannon behandlar buller som det grundläggande villkoret — all teori bygger på det.
För nu fokuserar kapitel 10 på det bullerfria fallet: källkodning utan fel. Kanalkodningsproblemet (felkorrigering) väntar på senare kapitel.
När kan du avkoda unikt?
För att en kod med variabel längd ska vara användbar måste mottagaren avkoda en bitström entydigt. Hamming illustrerar med en 4-symbols kod som misslyckas detta test, sedan presenterar han lösningen: prefixfria koder.
Prefixfritt villkor
En kod är prefixfri (eller omedelbar) om ingen kodord är ett prefix för någon annan kodord. Givet en mottagen bitström, du vet att en symbol har avslutats när du når ett blad i avkodningsträdet — ingen framåtblick krävs.
Exempel på prefixfri kod för {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Verifiera: 0 är inte ett prefix för 10, 110, eller 111. 10 är inte ett prefix för 110 eller 111 (10 följt av fler bitar ger 100... eller 101..., ingen av vilka börjar med 110 eller 111). Koden kvalificerar sig.
Avkodningsproceduren: följ trädet, förgrena dig på varje inkommande bit, emit symbolen när du träffar ett blad, återgå till roten.
Krafts olikhet
För vilken prefixfri binär kod som helst med kodordslängder l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
Likhet gäller när koden är fullständig (löv fyller det fullständiga binära trädet utan luckor). Detta är ett nödvändigt villkor: ingen prefixfri kod kan bryta mot det. Omvänt, för vilken uppsättning längder som helst som uppfyller Krafts olikhet, finns en prefixfri kod.
Tillämpa Krafts olikhet
Givet kodordslängder, verifiera Kraft: Σ 2^(−l_i) ≤ 1.
För {s1=0, s2=10, s3=110, s4=111}: längderna är 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Shannon-entropi
Den genomsnittliga kodordslängden för en kod med variabel längd: L = Σ p_i · l_i, där p_i är sannolikheten för symbol s_i och l_i är dess kodordslängd.
Hur kort kan L bli? Shannons svar: inte under källans entropi.
Shannon-entropi: H = −Σ p_i · log₂(p_i) (enheter: bitar/symbol)
Entropi mäter den genomsnittliga informationen per symbol. Hög entropi betyder att symboler är ungefär lika sannolika (maximal oförutsägbarhet). Låg entropi betyder att vissa symboler dominerar (höga förutsägbarhet, mer komprimerbar).
Förlustfri kodningssats
För vilken prefixfri kod som helst, H(källa) ≤ L ≤ H(källa) + 1.
Ingen kod kan slå entropi. Huffman-kodning (nästa kapitel) uppnår övre gräns: L < H + 1. För blockkoder över n symboler, stramningen: H ≤ L/n < H + 1/n.
Entropi är också den teoretiska komprimeringsgränsen: du kan inte komprimera en källa under H bitar per symbol utan att förlora information.
Beräkna entropi
Exempel: 4 symboler med sannolikheter 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 bitar/symbol
Och Huffman-koden {0, 10, 110, 111} uppnår L = 1.75 = H exakt.
Varför entropi är en nedre gräns
Den förlustfria kodningssatsens nedre gräns är inte bara en formel — den återspeglar något djupt om information: du kan inte komprimera vad som redan är maximalt oförutsägbart.
När alla symboler är lika sannolika (likformig fördelning), entropi H = log₂(n) för n symboler. En blockkod av längd log₂(n) bitar uppnår exakt H. Ingen kod kan göra bättre.
När en symbol dominerar (säg, p(A) = 0.99, p(B) = 0.01), H är små — nära 0. En kod med variabel längd kan tilldela A en mycket kort kod, vilket kodar strömmen mycket effektivt.
Den praktiska slutsatsen: stora komprimeringsvinstrar existerar bara när symbols sannolikheter skiljer sig väsentligt. Om källan redan är 'likformig' (slumpmässig), får Huffman-kodning ingenting.