Codarea aritmetica

Metoda codarii aritmetice a fost sugerata de Elias si prezentata de Abramson.

In codarea aritmetica un ansamblu sursa este reprezentat de un interval real intre 0 si 1. Fiecare simbol al ansamblului ingusteaza acest interval. Cu cat intervalul devine mai mic, numarul de biti necesari pentru a-l specifica creste. Codarea aritmetica presupune un model probabilistic explicit al sursei. Este o schema care foloseste probabilitatile mesajelor sursa sa ingusteze succesiv intervalul folosit pentru a reprezenta ansamblul. Un mesaj cu probabilitate mare ingusteaza intervalul mai putin decat un mesaj cu probabilitate scazuta, astfel incat mesajele cu probabilitate ridicata contribuie cu mai putini biti la ansamblul codat.

Aceasta metoda incepe cu o lista neordonata de mesaje sursa si probabilitatile lor. Linia numerelor este partitionata in subintervale bazate pe probabilitati cumulative.

Vom folosi un mic exemplu pentru a ilustra ideea codarii aritmetice. Avand date mesajelor sursa cu probabilitatile urmatoarea figura demonstreaza partitionarea initiala a liniei de numere.

Mesaj Probabilitatea Probabilitatea Cumulativa Range
sursa
A .2 .2 [0,.2)
B .4 .6 [.2,.6)
C .1 .7 [.6,.7)
D .2 .9 [.7,.9)
# .1 1.0 [.9,1.0)
Model de codare aritmetica

Simbolul A corespunde primei parti de 1/5 din intervalul [0,1) ; B corespunde urmatoarei parti de 2/5 ; D subintervalului de marime 1/5 care incepe la 70% din drumul de la partea stanga la dreapta. Cand incepe codarea, ansamblul sursa este reprezentat de intregul interval [0,1). Pentru ansamblul AADB#, primul A reduce intervalul la [0,.2) si urmatorul A il reduce la [0,.04) (prima 1/5 din intervalul precedent). In continuare, D ingusteaza intervalul la [.028, .036); (1/5 din marimea precedenta, incepand cu 70% din distanta de la stanga la dreapta). Apoi B ingusteaza intervalul la [.0296, .0328) si # produce intervalul final [.03248,.0328). Intervalul astfel obtinut, sau in mod alternativ orice numar si cuprins in interval, poate fi folosit acum pentru a reprezenta ansamblul sursa.
Pentru a defini procesul de ingustare, exista doua ecuatii cu urmatoarele forme:
■Stanga_curenta=stanga_precedenta+stanga_mesaj*marime_pre-cedenta (1)
■ Marime_curenta = marime_precedenta*marime_mesaj (2)
In prima ecuatie capatul stang al intervalului este calculat din intervalul precedent si mesajul sursa curent. Capatul stang al sirului asociat cu mesajul curent, specifica ce procent din intervalul precedent trebuie scos, astfel incat sa formeze noul interval.
De exemplu pentru D, noul capat stang este mutat cu .7*.04 (adica 70% din marimea intervalului precedent).
A doua ecuatie calculeaza marimea noului interval din marimea intervalului precedent si probabilitatea mesajului curent (care este echivalent cu marimea sirului asociat). Acestea fiind spuse, marimea intervalului determinat de D este .04*.2 si capatul drept este: .028 + .008 = .036 (capatul stang + marimea).
Marimea subintervalului final determina numarul de biti necesari pentru specificarea unui numar din acel sir. Numarul de biti necesari pentru a specifica un subinterval din [0,1), de marime s este -log s. Cum marimea subintervalului final reprezinta produsul dintre probabilitatile mesajelor sursa din ansamblu (adica s = P p(i), i=1,n , unde i este mesaj sursa si n este lungimea ansamblului), avem : -log s = - S log p(i) = - S p(a(i)) log p(a(i)), I=1,n , unde n este numarul mesajelor sursa unice a(1), a(2), a(n).
Cu toate acestea, numarul de biti generati de tehnica codarii aritmetice este exact egal cu entropia, H. Aceasta demonstreaza faptul ca compresia facuta prin codare aritmetica este aproape exacta cu cea a entropiei sursei.
Pentru a se putea reface ansamblul original, decodorul trebuie sa cunoasca modelul sursei folosit de programul care codeaza (de exemplu mesajele sursa si intervalele asociate) si un singur numar din interiorul intervalului determinat de program. Decodarea consta intr-o serie de comparatii ale numarului i cu intervalele care reprezinta mesajele sursa. Pentru acest exemplu, i poate fi .0325 (.03248, .0326 sau .0327 sunt deasemenea bune). Decodorul foloseste i pentru a simula actiunile programului codor. In cazul in care i se afla intre 0 si .2, decodorul deduce ca prima litera a fost A (pentru ca intervalul [0,.2) corespunde mesajului sursa A). Aceasta ingusteaza intervalul la [0,.2). Decodorul poate acum deduce ca urmatorul mesaj va micsora in continuare intervalul in unul dintre urmatoarele moduri: la [0,.04) pentru A, la [.04,.12) pentru B, la [.12,.14) pentru C, la [.14,.18) pentru D, si la [.18,.2) pentru #. Cum i pica in intervalul [0,.04), el stie ca al doilea mesaj este din nou A. Acest proces continua pana cand intregul ansamblu a fost refacut.
Cateva dificultati devin evidente cand se incearca implementarea codarii aritmetice.
Prima este aceea ca decodorul are nevoie sa stie in vreun fel cand trebuie sa se opreasca. Ca dovada a acestui fapt, numarul 0 ar putea reprezenta oricare dintre sursele A, AA, AAA, etc. Doua solutii au fost sugerate acestei probleme: una este ca programul care codeaza sa transmita marimea ansamblului ca parte a descrierii modelului ; alta este ca un simbol special sa fie inclus in model cu scopul de a semnala sfarsitul mesajului. Simbolul # din exemplul dat, foloseste acestui scop.
A doua alternativa este de preferat, din cateva motive. In primul rand, pentru a trimite dimensiunea ansamblului este necesar un proces in doi pasi (two-pass) si cere folosirea codarii aritmetice ca parte a schemei codurilor hibride. In al doilea rand, metodele adaptive ale codarii aritmetice sunt usor de realizat si un prim pas in determinarea marimii ansamblului este necorespunzator intr-o schema adaptiva on-line.
Al doilea subiect lasat nerezolvat de conceptul fundamental de codare aritmetica este cel al transmisiei incrementale si al receptiei. Din ceea ce s-a scris mai sus reiese ca algoritmul de codare nu transmite nimic pana cand se determina si ultimul interval. Totusi, aceasta intarziere nu este necesara. Cu cat intervalul se micsoreaza, bitii de fond ai capatului stang de interval si cei ai capatului drept devin identici. Oricare dintre bitii de fond care sunt la fel, pot fi transmisi imediat si ei nu vor fi afectati de micsorarea din continuare.
Al treilea motiv este cel al preciziei. Din descrierea codarii aritmetice reiese ca precizia necesara creste fara masura cand lungimea ansamblului creste. Registrii cu precizie fixa pot fi folositi atata timp cat este detectat si controlat underflow si overflow.
Gradul compresiei realizata prin implementarea codarii aritmetice nu este exact H, asa cum rezulta din conceptul de codare aritmetica. In egala masura, utilizarea terminatorilor de mesaje si a lungimii fixe, reduce eficacitatea codarii. Oricum, este clar faptul ca un simbol de sfarsit de mesaj nu va avea un efect semnificativ asupra unui ansamblu sursa vast. De asemenea deplasarea in utilizarea preciziei fixe la 10^-4 pe mesaj sursa, este neglijabila.
Modelul codarii aritmetice pentru ansamblul EXAMPLE este dat de urmatoarea figura. Marimea intervalului final este:
p(a)^2*p(b)^3*p(c)^4*p(d)^5*p(e)^6*p(f)^7*p(g)^8*p(space)^5
Numarul de biti necesari pentru a specifica o valoare din interval este -log(1.44*10^-35)=115.7. Astfel excluzand deplasarea, codarea aritmetica transmite EXAMPLE in 116 biti, cu un bit mai putin decat codarea statica Huffman.
Mesaj Probabilitati Probabilitati cumulative Intervalul
sursa
a .05 .05 [0,.05)
b .075 .125 [.05,.125)
c .1 .225 [.125,.225)
d .125 .35 [.225,.35)
e .15 .5 [.35,.5)
f .175 .675 [.5,.675)
g . 2 .875 [.675,.875)
space .125 1.0 [.875,1.0)
Modelul codarii aritmetice pentru EXAMPLE.