> tunstall | variabel | fast <
// Tunstall-koding – optimal komprimering fra variabel til fast lengde
V2F-koding
Mapper sekvenser med variabel lengde til koder med fast lengde.
Sannsynlighetsbasert
Ordboken bygges ut fra sannsynlighetsfordelingen til symbolene.
Enkel dekoding
Koder med fast lengde gjør dekoding enkel og rask.
>> teknisk informasjon
Hvordan Tunstall-koding fungerer:
Tunstall-koding bygger opp en ordbok av sekvenser med variabel lengde som mappes til binære koder med fast lengde. Man starter med enkeltsymboler og utvider iterativt sekvensen med høyest sannsynlighet ved å legge til hvert symbol i alfabetet. Resultatet er en optimal variabel-til-fast lengde-kode der mer sannsynlige sekvenser får egne kodeord.
Tunstall-eksempel:
Tekst: 'aabaa' med P(a)=0.8, P(b)=0.2 Ordboksbygging (3-bits koder): Initial: a, b Utvid 'a': aa, ab Utvid 'aa': aaa, aab Utvid 'ab': aba, abb Endelig ordbok (8 koder): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 Koding: 'aabaa' → 001 100 (aab + aa)
Hvorfor bruke Tunstall-koding?:
- ▸Utdata med fast kodeordlengde
- ▸Enkel implementering av dekoder
- ▸Ingen synkroniseringsproblemer
- ▸Godt egnet for maskinvareimplementasjoner
- ▸Optimal for minneløse kilder
>> ofte stilte spørsmål
Hva er Tunstall-koding?
Tunstall-koding er en entropikodemetode med variabel inngangslengde og fast utgangslengde. I motsetning til Huffman (fast til variabel) mapper Tunstall sekvenser med variabel lengde til kodeord med fast lengde, noe som er ideelt for applikasjoner som krever konstant bitrate.
Tunstall vs. Huffman-koding?
Huffman: fast input → variabel output (f.eks. 'a' → '0', 'b' → '10'). Tunstall: variabel input → fast output (f.eks. 'aa' → '000', 'ab' → '001'). Tunstall er bedre for maskinvare og synkronisering, men gir vanligvis noe lavere kompresjonsgrad.
Hvordan bygges ordboken?
Start med enkeltsymboler. Gjenta: 1) finn sekvensen med høyest sannsynlighet, 2) fjern den og legg til alle mulige utvidelser med ett symbol, 3) fortsett til ønsket ordbokstørrelse (2^n for n‑bits koder) er nådd.
Hvor brukes Tunstall-koding?
Tunstall-koding brukes i tale-komprimering, bildekoding og andre situasjoner der man trenger fast utdatahastighet. Den er særlig nyttig i maskinvareimplementasjoner og sanntidssystemer der variable kodelengder gjør timing vanskelig.