Codare aritmetică

1. OBIECTIVELE LUCRaRII

Obiectivele lucrarii sunt urmatoarele:

- studiul algoritmilor de codificare aritmetica a secventelor de simboluri;

- studiul posibilitatilor de implementare a acestor algoritmi folosind tehnica de calcul.

2. BREVIAR TEORETIC

2.1.Algoritmul de codificare aritmetica

Caracteristica esentiala a codificarii aritmetice este aceea ca realizeaza o codificare a secventelor de simboluri si nu a fiecarui simbol individual. Ea asociaza fiecarei secvente de simboluri un subinterval al numerelor reale cuprinse intre 0 si 1 si face codificarea secventei printr-un numar oarecare apartinand acestui subinterval.

Se prezinta, in continuare, o exemplificare a modului de codificare aritmetica.

Fie caracterele A, C, R, P cu probabilitatile de aparitie 0,5; 0,25; 0,15; 0,1. Din aceste caractere se formeaza mesajul CAP pe care urmeaza sa-l codificam.

Algoritmul de codificare aritmetica presupune parcurgerea urmatorilor pasi:

- se imparte subintervalul (0,1) proportional cu probabilitatile simbolurilor din setul de litere si se retine intervalul (0,5; 0,75), corespunzator primului simbol din mesaj - C

- se imparte apoi subintervalul retinut proportional cu probabilitatile de aparitie a simbolurilor din setul de litere si se retine (0,5; 0,625) care corespunde simbolului A

- se procedeaza analog pentru cel de-al treilea simbol, P, obtinand intervalul (0,6125; 0,625).

- pentru codificarea mesajului poate fi aleasa o valoare oarecare din acest subinterval, de exemplu 0,62.

Dupa cum se observa, fiecare nou simbol al mesajului ingusteaza intervalul de alegere a cuvantului de cod. Un subinterval de marime s poate fi reprezentat prin - logs biti.

Deoarece dimensiunea intervalului final este produsul probabilitatilor simbolurilor sursa, se poate scrie:

(5.1)

unde:

n = lungimea secventei de mesaje;

m = numarul de mesaje distincte.

Se subliniaza in acest mod faptul ca numarul de biti generati de codificarea aritmetica este egal cu entropia H.

Pentru refacerea mesajului la receptie (decodificare), se determina succesiv subintervalele in care se incadreaza codul, deducandu-se succesiunea de simboluri.

Pentru terminarea procesului de decodificare este insa necesara cunoasterea lungimii mesajului. in acest scop, se include de regula in mesaj un simbol special, care marcheaza sfarsitul lui.

2.2. Solutii de implementare

in ipotezele:

- intregul sir de date este considerat un mesaj pentru care se va calcula un cuvant de cod corespunzator;

- simbolurile sursei sunt notate cu 1, 2, 3, , fiecare cu o probabilitate de aparitie prob[i];

- mesajul se incheie cu un simbol terminator special,

se calculeaza probabilitatile cumulate. Acestea vor fi pastrate intr-un vector, denumit prob cum [numar simboluri +1], astfel incat simbolului i sa-i corespunda domeniul de probabilitati intre prob cum [i] si prob cum [ i-1].

Vectorul prob cum [ ] are elementele in ordine descrescatoare, cu proprietatea prob cum [0] = 1 (acumularea se face de la dreapta spre stanga).

Intervalul curent va fi dat de [inf, sup), initializat la [0,1) atat la codificare, cat si la decodificare.

Se propun urmatoarele frecvente simplificate de program pentru algoritmii de codificare si decodificare:

void codifica simbol (simbol, prob cum)-

domeniu = inf- sup;

sup = inf+domeniu*prob cum[simbol-1];

inf = inf+domeniu*prob cum[simbol];

-

int decodifica simbol (prob cum) -

gaseste simbol astfel ca prob cum [simbol]<=(valoare-inf)/(inf-sup)<

prob cum [simbol-1];

domeniu=sup-inf;

sup = inf+domeniu*prob cum[simbol-1];

inf = inf+domeniu*prob cum[simbol];

return simbol