Intervallikoodaus (kaistakoodaus) on G. N. N. Martinin vuonna 1979 ehdottama entropiakoodausmenetelmä [1] . Tämä on eräänlainen aritmeettinen koodaus [2] .
Intervallkoodaus koodaa kaikki viestin merkit yhdeksi numeroksi toisin kuin esimerkiksi Huffman-koodissa , joka määrittää kullekin merkille bittisarjan ja ketjuttaa kaikki bittisekvenssit yhteen.
Oletetaan, että haluat salata viestin "AABA<EOM>", jossa <EOM> on viestin loppumerkki . Tässä esimerkissä oletetaan, että dekooderi tietää, että aiomme koodata täsmälleen viisi merkkiä desimaalimuodossa (algoritmi tukee tässä tapauksessa 10 5 erilaista merkkiyhdistelmää alueella [0, 100000)) käyttämällä todennäköisyysjakaumaa {A : 0,60; B: 0,20; <EOM>: 0,20}. Enkooderi jakaa alueen [0, 100000) kolmeen alialueeseen:
V: [ 0, 60000) B: [ 60 000, 80 000) <EOM>: [ 80000, 100000)Koska ensimmäinen merkkimme on A, tämä pienentää aloitusalueemme arvoon [0, 60000). Toinen merkki jakaa tämän alueen kolmeen osaan:
AA: [ 0, 36000) AB: [ 36000, 48000) A<EOM>: [ 48000, 60000)Kun kaksi merkkiä on koodattu, alueemme tulee [0, 36000) ja kolmas merkki tarjoaa seuraavat vaihtoehdot:
AAA: [ 0, 21600) AAB: [ 21600, 28800) AA<EOM>: [ 28800, 36000)Tällä kertaa valinta osuu toiselle kolmesta vaihtoehdosta, joka on viesti, jonka haluamme koodata, ja alueemme tulee [21600, 28800). Saattaa vaikuttaa siltä, että alialueidemme määrittäminen on tässä tapauksessa vaikeutunut, mutta todellisuudessa se ei ole: voimme yksinkertaisesti vähentää alarajan ylärajasta määrittääksemme, että alueellamme on saatavilla 7200 numeroa; näistä ensimmäiset 4320 edustavat 0,60:a kokonaismäärästä, seuraavat 1440 edustavat seuraavaa 0,20:aa ja loput 1440 edustavat loput 0,20:a kokonaismäärästä. Alarajan lisääminen antaa meille alueemme:
AABA: [21600, 25920) AABB: [25920, 27360) AAB<EOM>: [27360, 28800)Lopulta valikoimamme kaveni [21600:een, 25920:een), meille jäi vain yksi merkki koodattavana. Jakamalla alueen ala- ja ylärajan välillä samaa tekniikkaa kuin aiemmin, löydämme kolme jäljellä olevaa alialuetta:
AABAA: [21600, 24192) AABAB: [24192, 25056) AABA<EOM>: [25056, 25920)Ja koska <EOM> on viimeinen merkkimme, lopullinen alueemme on [25056, 25920). Koska kaikki viisinumeroiset numerot, jotka alkavat 251:llä, kuuluvat viimeiselle rivillemme, voimme välittää yhden kolminumeroisista etuliitteistä ilmaistaksemme alkuperäisen viestin yksilöllisesti (se, että tällaisia etuliitteitä on itse asiassa kahdeksan, viittaa siihen, että on mahdollista optimoida algoritmi. Mutta ne syntyivät desimaalilukujärjestelmän käytöstä , ei binääristä ).
Aritmeettinen koodaus on samanlainen kuin intervallikoodaus, käyttää murtolukuja alueella [0,1). Tämän seurauksena aritmeettinen koodi tulkitaan alkavan implisiittisellä "0:lla", koska nämä ovat vain eri tulkintoja samoista koodausmenetelmistä, jolloin mikä tahansa aritmeettinen kooderi on vastaava intervallikooderi ja päinvastoin.
Käytännössä ns. etäisyysantureita kuitenkin yleensä toteutetaan suuressa määrin, kuten Martinin artikkelissa [1] kuvataan, kun taas aritmeettisia koodereita ei kutsuta etäisyysantureiksi ollenkaan. Usein erona on tavujen ja bittien uudelleennormalisointi. Intervallkooderit käyttävät yleensä tavuja bittien sijaan. Vaikka tämä vähentää pakkaustasoa, se on nopeampaa kuin uudelleennormalisointi bittikohtaisesti.
| Puristusmenetelmät _ | |||||||
|---|---|---|---|---|---|---|---|
| Teoria |
| ||||||
| Häviötön |
| ||||||
| Audio |
| ||||||
| Kuvat |
| ||||||
| Video |
| ||||||