> tunstall | variabel | fast <
// Tunstall-kodning – optimal komprimering från variabel till fast längd
V2F‑kodning
Mappar sekvenser med variabel längd till koder med fast längd.
Sannolikhetsbaserad
Ordboksbaserad kodning där ordlistan byggs från symbolernas sannolikhetsfördelning.
Lätt att avkoda
Koder med fast längd gör avkodningen enkel och snabb.
>> teknisk information
Hur Tunstall-kodning fungerar:
Tunstall‑kodning bygger upp en ordlista över sekvenser med variabel längd som mappas till binära koder med fast längd. Man börjar med enskilda symboler och utökar iterativt den mest sannolika sekvensen genom att lägga till varje symbol i alfabetet. Resultatet är en optimal variabel‑till‑fast‑kodsättning där mer sannolika sekvenser får egna kodord.
Tunstall‑exempel:
Text: 'aabaa' med P(a)=0.8, P(b)=0.2 Uppbyggnad av ordlista (3‑bits koder): Initialt: a, b Utöka 'a': aa, ab Utöka 'aa': aaa, aab Utöka 'ab': aba, abb Slutlig ordlista (8 koder): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 Kodning: 'aabaa' → 001 100 (aab + aa)
Varför använda Tunstall‑kodning?:
- ▸Utdata med fasta kodordslängder
- ▸Enkel implementering av avkodare
- ▸Inga synkroniseringsproblem i bitströmmen
- ▸Lämplig för maskinvaruimplementationer
- ▸Optimal för minneslösa källor
>> vanliga frågor
Vad är Tunstall‑kodning?
Tunstall‑kodning är en entropikodningsmetod där indata har variabel längd och utdata har fast längd. Till skillnad från Huffman‑kodning (fast→variabel) mappar Tunstall sekvenser med variabel längd till kodord med fast längd, vilket är idealiskt när man behöver en konstant bithastighet.
Tunstall jämfört med Huffman‑kodning?
Huffman: fast indata → variabel utdata (t.ex. 'a' → '0', 'b' → '10'). Tunstall: variabel indata → fast utdata (t.ex. 'aa' → '000', 'ab' → '001'). Tunstall är bättre för maskinvara och synkronisering, men ger vanligtvis något lägre kompressionsgrad.
Hur byggs ordlistan?
Man börjar med enskilda symboler. Sedan upprepar man: 1) hittar sekvensen med högst sannolikhet, 2) tar bort den och lägger till alla möjliga utökningar med ett symbol, 3) fortsätter tills önskad ordlistestorlek (2^n för n‑bits kod) uppnås.
Var används Tunstall‑kodning?
Tunstall‑kodning används i röstkomprimering, bildkodning och andra sammanhang där man behöver fast utdatahastighet. Den är särskilt användbar i maskinvaruimplementationer och realtidssystem där koder med variabel längd skulle göra tidsstyrningen mer komplex.