källkodningsteorin

Källkodningsteorin är en gren av informationsteorin som studerar hur information från en källa kan representeras med minimalt antal symboler och samtidigt hantera fel och distortion. Den omfattar både förlustfri källkodning och förlustig källkodning (rate-distortion). Målet är att nå så nära teoretiska gränser som möjligt för lagring och överföring.

Historiskt introducerade Claude E. Shannon begreppen i 1948 års verk A Mathematical Theory of Communication. Den centrala idén är entropin H(X), som beskriver den genomsnittliga mängden information per symbol. För en diskret minneslös källa gäller att den genomsnittliga källkoden per symbol L för en prefixkod uppfyller H(X) ≤ L ≤ H(X) + 1. Genom blockkodning av n symboler kan den genomsnittliga kostnaden per symbol närma sig H(X) när n ökar.

Denna teori omfattar även förlustig källkodning genom rate-distortion-teorin, som anger den minimala överföringshastigheten R(D) som krävs för att representera källan med en viss förvrängning D. Förlustfri källkodning betonar att entropin sätter en teoretisk gräns för den optimala kodningshastigheten, medan praktiska koder som Huffman-kodning och aritmetisk kodning närmar sig dessa gränser. Rate-distortion-teorin utgör grunden för lossy-kompression och hur mycket information som kan bevaras vid en given kvalitetsnivå.

Användningsområden inkluderar data­kompression för lagring och kommunikation, videoströmning, bild- och ljudkomprimering samt standarder inom telekommunikation. Teorin förutsätter ofta kända eller approximativa statistiska modeller av källan och antaganden om stationäritet; i praktiken uppstår utmaningar som osäkerhet och beräkningskomplexitet som påverkar hur nära gränserna man kan komma.