Codarea aritmetică

Introducere

Codarea Huffman a fost considerata multa vreme ca aproape optima pana cand in anii ’70 ai secolului trecut a aparut codarea aritmeticǎ.

Codarea aritmetica este folosita in special cand alfabetul sursei este mic,iar probabilitatile mesajelor sunt dezechilibrate. Cuvintele de cod obtinute in urma acestei codari au lungime variabila.

Prin codare binara Huffman se obtine un numar mediu de biti/mesaj (rata) cuprins intre H(S) si H(S)+1. Limita superioara pentru lungimea medie a cuvintelor in cazul codului Huffman a fost stabilita mai precis la valoarea

max H(S) + p + 0,086 , unde max p este probabilitatea cea mai mare din distributia sursei ce urmeaza a fi codata.In aplicatii in care alfabetul sursei este mare si max p este relativ mic, diferenta dintre limita superioara a lungimii medii a cuvintelor de cod si entropia sursei codate este relativ mica.

Cand alfabetul sursei este mic si probabilitatile de aparitie a diferitelor litere sunt foarte diferite, max p poate fi mare si codul Huffman poate deveni ineficient, privind raportul dintre entropia sursei si lungimea medie a cuvintelor. O modalitate de a evita acest lucru este de a efectua codarea Huffman pentru o extensie a sursei dar acest lucru nu este intotdeauna eficient.Pentru eliminarea acestui inconvenient se foloseste codarea 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.

Codarea aritmetica permite atribuirea cuvintelor de cod unor secvente particulare, fara a trebui sa se genereze cuvintele de cod pentru toate secventele de acea lungime.

Pentru intelegerea codarii aritmetice,aceasta se imparte in doua etape:

- in prima etapa se genereaza o eticheta pentru o secventa data de

mesaje;

- in a doua etapa i se atribuie etichetei un cod binar.

Codarea unei secvente

Pentru a se putea face distinctie intre diferite secvente de mesaje, fiecare este etichetata cu un identificator unic. O modalitate de reprezentare a secventei este de a-i atribui un numar in intervalul [0, 1). O functie care ia valori in acest interval este functia de repartitie a variabilei aleatoare asociate sursei care furnizeaza secventa de mesaje.

Se reaminteste ca o variabila aleatoare realizeaza corespondenta intre evenimente probabilistice si valori pe axa reala. De exemplu, in experimentul de aruncare cu zarul, variabila aleatoare realizeaza corespondenta dintre fetele zarului si numerele 1,2,.,6, care sunt puncte pe axa reala. Pentru a folosi aceasta tehnica este nevoie de a transforma mesajele sursei in numere.

Pentru usurinta, in cele ce urmeaza se va folosi transformarea: x(si)=i; si∈S, unde S = {s1, s2, ., sm} este alfabetul sursei. Variabila aleatoare, pe care o notam in continuare cu x, poate lua valorile 1,2,.,i,.,m, cu probabilitatile cu care sunt furnizate mesajele corespunzatoare.

Aceasta inseamna ca pentru o distributie data a sursei, se poate asocia o functie de repartitie pentru variabila aleatoare x, de forma:

Generarea unei etichete

Procesul de generare a unei etichete incepe cu intervalul [0,1]. Functia de repartitie a variabilei aleatoare asociate sursei este folosita la impartirea intervalului de lungime 1 in subintervale de forma [Fx(xi-1), Fx(xi)], proportionale cu valorile functiei de repartitie. Cum functia de repartitie ia valori intre 0 si 1, aceasta abordare partitioneza exact intervalul unitate. Aparitia primului mesaj din secventa restrictioneaza intervalul care contine eticheta la unul din subintervale. Se presupune ca primul mesaj este sk si x(sk)=xk. Atunci intervalul care contine valoarea etichetei va fi subintervalul [Fx(xi-1), Fx(xi)]. Acesta este partitionat in subintervale proportionale cu valorile functiei de repartitie, la fel ca intervalul original. Fiecare mesaj care urmeaza impune ca eticheta sa fie restrictionata la un subinterval care este partitionat in continuare in aceleasi proportii.