Aritmeettinen koodaus

Aritmeettinen koodaus  on yksi entropian pakkausalgoritmeista .

Toisin kuin Huffman-algoritmi , sillä ei ole kovaa jatkuvaa tulomerkkien vastaavuutta ulostulovirran bittiryhmiin. Tämä antaa algoritmille enemmän joustavuutta murto-osien merkkitaajuuksien esittämisessä.

Pääsääntöisesti se ylittää Huffman-algoritmin pakkaustehokkuuden suhteen, mahdollistaa tietojen pakkaamisen, jonka entropia on alle 1 bitti per koodattu merkki, mutta joissakin versioissa on IBM :n patenttirajoituksia . [yksi]

Ominaisuudet

Tarjoaa lähes optimaalisen pakkaussuhteen Shannon-koodauksen entropiaestimaatin kannalta. Jokaiselle symbolille vaaditaan melkein bitti, missä  on lähteen informaatioentropia .

Toisin kuin Huffman-algoritmi , aritmeettinen koodausmenetelmä osoittaa korkean tehokkuuden koodattujen symbolien todennäköisyysjakauman epäyhtenäisten murto-osien välillä. Kuitenkin, jos merkkijakauma on tasatodennäköinen, esimerkiksi bittijonolle 010101…0101 , jonka pituus on s , aritmeettinen koodausmenetelmä lähestyy etuliite Huffman-koodia ja voi kestää jopa yhden bitin enemmän. [2]

Kuinka se toimii

Olkoon tietty aakkoset sekä tiedot merkkien käyttötiheydestä (valinnainen). Harkitse sitten janaa 0 - 1 koordinaattiviivalla.

Kutsutaan tätä segmenttiä toimivaksi. Järjestetään pisteet siihen siten, että muodostettujen segmenttien pituudet ovat yhtä suuret kuin symbolin käyttötiheys ja jokainen tällainen segmentti vastaa yhtä symbolia.

Otetaan nyt symboli virrasta ja etsitään sille segmentti vasta muodostettujen joukosta, nyt tämän symbolin segmentti on alkanut toimia. Jaetaan se samalla tavalla kuin jaetaan segmentti 0:sta 1:een. Suoritetaan tämä toimenpide tietylle määrälle peräkkäisiä merkkejä. Sitten valitsemme minkä tahansa luvun työsegmentistä. Tämän luvun bitit yhdessä sen bittitietueen pituuden kanssa ovat tulos käytettyjen virtasymbolien aritmeettisesta koodauksesta.

Esimerkki aritmeettisen koodausmenetelmän toiminnasta

Todennäköisyysmalli

Aritmeettisella koodausmenetelmällä voidaan saavuttaa lähes optimaalinen esitys annetulle symbolijoukolle ja niiden todennäköisyyksille ( Shannonin lähdeentropiakoodausteorian mukaan optimaalinen esitysmuoto on yleensä −log 2 P bittiä symbolia kohti, jonka todennäköisyys on P ). Aritmeettista koodausmenetelmää työssään käyttävät tiedonpakkausalgoritmit muodostavat ennen suoraa koodausta syötetietomallin , joka perustuu kvantitatiivisiin tai tilastollisiin ominaisuuksiin sekä kaikkiin koodatusta toisto- tai kuviosarjasta löytyvään lisätietoon - kaikkiin lisätietoihin, jotka mahdollistavat voit selvittää symbolin P esiintymisen todennäköisyyden koodausprosessissa. Ilmeisesti mitä tarkemmin symbolin todennäköisyys määritetään tai ennustetaan, sitä korkeampi pakkausteho on.

Tarkastellaan yksinkertaisinta tapausta staattisesta mallista signaalinkäsittelyjärjestelmästä tulevan tiedon koodaamiseksi. Signaalityypit ja niitä vastaavat todennäköisyydet jakautuvat seuraavasti:

• 60 %:n mahdollisuus saada neutraali signaaliarvo tai NEUTRAALI.
• 20 % mahdollisuus positiiviseen signaaliarvoon tai POSITIIVINEN.
• 10 %:n mahdollisuus negatiiviseen signaaliarvoon tai NEGATIIVINEN.
• 10 %:n mahdollisuus saada sekvenssin loppumerkki tai TIETOJEN LOPPU.

Dekooderin viimeisen symbolin ilmestyminen tarkoittaa, että koko sekvenssi on onnistuneesti dekoodattu (vaihtoehtoisena lähestymistapana, mutta ei välttämättä onnistuneempana, voidaan käyttää kiinteän pituista lohkoalgoritmia) .

On myös huomattava, että mitä tahansa symbolijoukkoa voidaan pitää menetelmän todennäköisyysmallin aakkosena ratkaistavan ongelman ominaisuuksien perusteella. Heuristisemmissa lähestymistavoissa, joissa käytetään aritmeettisen koodausmenetelmän peruskaaviota, sovelletaan dynaamisia tai adaptiivisia malleja . Näiden menetelmien ideana on tarkentaa koodatun merkin todennäköisyyttä ottamalla huomioon edellisen tai tulevan kontekstin todennäköisyys (eli todennäköisyys koodatun merkin esiintymiselle tietyn k:nnen merkkimäärän jälkeen vasemmalle tai oikealle, missä k on kontekstin järjestys).

Viestin koodaus

Otetaan esimerkkinä seuraava sekvenssi:

NEUTRAALI NEGATIIVINEN TIETOJEN LOPPU

Ensin jaetaan segmentti 0:sta 1:een signaalien taajuuksien mukaan. Katkaisemme segmentin yllä mainitussa järjestyksessä: NEUTRAALI - 0 - 0,6; NEGATIIVINEN - 0,6 - 0,8; TIETOJEN LOPPU - 0,8 - 1.

Aloitetaan nyt koodaus ensimmäisestä merkistä. Ensimmäinen merkki - NEUTRAL vastaa segmenttiä 0 - 0,6. Jaetaan tämä segmentti samalla tavalla kuin segmentti 0:sta 1:een.

Koodataan toinen merkki - NEGATIIVINEN. Segmentillä 0 - 0,6 se vastaa segmenttiä 0,48 - 0,54. Jaetaan tämä segmentti samalla tavalla kuin segmentti 0:sta 1:een.

Koodataan kolmas merkki - END-OF-DATA. Segmentillä 0,48 - 0,54 se vastaa segmenttiä 0,534 - 0,54.

Koska tämä oli viimeinen merkki, koodaus on valmis. Koodattu viesti on segmentti 0,534 - 0,54 tai mikä tahansa numero siitä, esimerkiksi 0,538.

Viestin dekoodaus

Oletetaan, että meidän on purettava viesti käyttämällä aritmeettista koodausmenetelmää edellä kuvatun mallin mukaisesti. Koodattua viestiä edustaa murtoluku 0,538 (yksinkertaisuuden vuoksi murto-osan desimaaliesitystä käytetään binäärikannan sijaan). Oletetaan, että koodattu viesti sisältää tarkasteltavassa numerossa tarkalleen niin monta merkkiä kuin on tarpeen alkuperäisen datan yksilöimiseksi palauttamiseksi.

Dekoodausprosessin alkutila on sama kuin koodausprosessi ja väli [0,1) otetaan huomioon. Tunnetun todennäköisyysmallin perusteella murtoluku 0,538 osuu väliin [0, 0,6). Tämän avulla voit määrittää kooderin valitseman ensimmäisen merkin, joten sen arvo tulostetaan dekoodatun viestin ensimmäisenä merkinä.

Muistiinpanot

1. ↑ Tietojen pakkausteorian kehityksen historia Arkistokopio 28. joulukuuta 2010 Wayback Machinessa / Compression.ru, Sarmin Aleksei, 10. maaliskuuta 2011
2. ↑ Dr. Dobb's Data Compression Newsletter arkistoitu 11. joulukuuta 2017 Wayback Machinessa , 13. elokuuta 2001

Linkit

• (13. elokuuta 2001) Dobbin tiedonpakkausuutiskirje