Coduri universale si reprezentarea intregilor

Un cod este universal daca inlocuieste mesajele sursa prin cuvinte cheie, astfel incat lungimea medie a cuvantului cheie rezultata are limita c1(H + c2). Aceasta inseamna ca fiind data o sursa arbitrara cu entropie nenula, un cod universal are lungimea medie a cuvantului cheie, care este cel mult un timp constant posibilitatea optima pentru acea sursa. Compresia potentiala oferita de un cod universal depinde de magnitudinea constantelor c1 si c2.

Un cod universal optim care are lungimea medie a cuvantului cheie apropiata de entropie si are c1=1 se numeste asimptotic optim. Un avantaj al codurilor universale fata de codurile Huffman este acela ca nu este necesar sa se cunoasca probabilitatile exacte cu care apar mesajele sursa. In timp ce codarea Huffman nu este aplicabila pana cand nu se cunosc probabilitatile, in cazul codarii universale este suficient sa se cunoasca distributia probabilitatii pentru ca mesajele sursa sa poata fi aranjate in ordinea probabilitatilor. Impachetand mesajele aflate in ordine descrescatoare dupa probabilitati, in cuvinte cheie care sunt ordonate crescator dupa lungime, se poate obtine universalitatea. Un alt avantaj al codurilor universale il reprezinta faptul ca pozitiile cuvintelor cheie sunt fixate. Nu este necesar a se calcula pozitia unui cuvant cheie bazata pe statisticile unui ansamblu; orice pozitie a unui cuvant cheie universal se va mentine atat timp cat mesajele sursa sunt ordonate. Procesele de codare si de decodare sunt deci simplificate.

Cum ordonarea mesajelor sursa reprezinta parametrul esential in codarea universala, ne putem gandi la un cod universal ca la enumerarea mesajelor sursa, sau la reprezentarea intregilor, care produc o enumerare.

Elias defineste o secventa de codare universala care inlocuieste setul de intregi pozitivi prin setul de cuvinte cheie binare.

gamma delta
1 1
010 0100
011 0101
00100 01100
00101 01101
00110 01110
00111 01111
0001000 00100000
000010000 001010000
17 000010001 001010001
32 00000100000 0011000000
Codul Elias

Primul cod Elias este unul care este simplu dar nu este optim.

Codul gamma impacheteaza un intreg x intr-o valoare binara si anume valoarea binara a lui x . Aceasta valoare este exprimata in cati mai putini biti posibili si incepe cu cifra 1, care serveste pentru a delimita prefixul. Rezultatul este un cod instantaneu de decodat pentru ca lungimea totala a cuvantului cheie este exact inca o data mai mare decat de doua ori numarul de zerouri din prefix; din aceasta cauza imediat cum se gaseste 1 in cuvantul cheie, se cunoaste lungimea cuvantului.

Codul nu este un cod cu redundanta minima, asa cum raportul dintre lungimea presupusa a cuvantului cheie si entropie se apropie de 2, atunci cand entropia se apropie de infinit.

Al doilea cod, delta, impacheteaza un intreg x intr-un cuvant cheie care consista in gamma (floor[log x] + 1) urmat de valoarea binara a lui x cu cifra 1 din fata stearsa. Cuvantul cheie care rezulta are lungimea:

floor[log x] + 2 floor[log(1 + floor[log x])] + 1. Acest concept poate fi aplicat recursiv pentru a scurta lungimea cuvintelor cheie, dar avantajele scad rapid. Codul delta este asimptotic optim, asa cum limita raportului dintre lungimea cuvantului cheie dorit si entropie este 1. In figura sunt afisate valorile codurilor gamma si delta pentru o mostra de intregi.

Figura urmatoare afiseaza codul Elias pentru sirul EXAMPLE

Mesaj Frecventa Nr Cuvant cheie
sursa
g 8 1 delta(1)=1
f 7 2 delta(2)=0100
e 6 3 delta(3)=0101
d 5 4 delta(4)=01100
space 5 5 delta(5)=01101
c 4 6 delta(6)=01110
b 3 7 delta(7)=01111
a 2 8 delta(8)=00100000
Codul Elias pentru EXAMPLE (lungime cod=161).

Numarul de biti transmisi folosind aceasta codare este 161, ceea ce nu se poate compara cu cei 117 biti transmisi de codul Huffman. Codul Huffman este optim sub forma modelului codarii statice. Chiar si un cod universal asimptotic optim nu se poate compara cu codarea statica Huffman aplicata unei surse careia i se cunosc probabilitatile mesajelor.