Tărniceriu Daniela Tiba Bianca -Veronica [620399]

UNIVERSITATEA TEHNICĂ “GHEORGHE ASACHI” DIN IAȘI

FACULTATEA DE ELECTRONICĂ,TELECOMUNICAȚII ȘI
TEHNOLOGIA INFORMAȚIEI
Specializarea: Tehnologii și sisteme de Telecomunicații

LUCRARE DE DIPLOMĂ

COMPRESIA FĂRĂ PIERDERI PRIN C ODARE HUFFMAN

Coordonator științific : ABSOLVENT: [anonimizat] – 2020

Cuprins

INTRO DUCERE …………………………………………………………….. …………………………………………….. 3
CAPITOLUL I
COMPRESIA ……………………………………………………………………………………
1.1.Noțiuni generale despre compresie ……………………………………………………………
1.2.Compresia fără pierderi ……………………………………………………………………….
1.3.Compresia cu pierderi …………………………………………………………………………
1.4.Evaluarea compresiei ………………… …………………………………………………. ….
CAPITOLUL II
DEFINIREA ȘI CARACTERISTICILE TIPURILOR DE COD ………………………
2.1. Definirea și codurilor nesingulare, unic decod abile și instantanee ………………………………………
2.2. Teorema de existență a codurilor instantanee ……………………………………………………………………
2.3. Lungimea medie a cuvintelor de c od …………………………………………………………………………….
2.4. Eficiența și redundanța unui cod ……… …………………………………………………………………………….
2.5. Teorema codării surselo r discrete, complete și fără memorie
pe canale neperturbate ……………………………………………………………………. …………………………………
CAPITOLUL III
CODAREA BINARĂ HUFFMAN ………………………………….. …………………………………………………
3.1. Procedeul de codare binară Huffman statică …………………………………………………………………..
3.1.1. Coduri Huffman de dispersie minimă ……………………….. …………………………………….
3.1.2. Procedeul de codare binară Shannon – Fano …………………………………………………….

3.1.3. Lungimea medie a cuvintelor de cod în cazul codului
binar Huf fman ……………………. …………………………………………………………………………………….. …
3.1.4. Procedeul de codare Huffman generalizat ……………………………………………………..
3.2. Codarea binară Huffman dinamică ……………………………………………………………………………..
3.2.1. Actualizarea arborelui ………………………………………………………………………………….
3.2.2. Algoritmul de codar e……………… ………………………………………………………………………….
3.2.3. Algoritmul de d ecodarea ………………………………………………………………….
3.3. Aplica ții ale codării Huffman …………………………………………………………………………………….

CONCLUZIE ………………………………………………………………………………………
BIBLIOGRAFIE ……….. ………………………………………………………………………….

INTRODUCERE ÎN COMPRESIA DATELOR

Compresia datelor se ocupă cu reprezentarea informației într -o formă compactă. Acest
lucru se realizează prin iden tificarea și extragerea redundanței din date. Datele pot fi caractere
dintr -un fișier text, numere ce reprezintă eșantioane ale unor semnale vocale sau de imagine etc.
Exemple de compresie :
– codul Morse , care alocă literelor ce apar mai des în cuvintele m ai puține semne (linie,
punct) și celor mai rare, mai multe semne ;
– alfabetul Braille, care folosește tablouri de puncte de dimensiuni 2×3, în care punctele sunt
distribuite în funcție de probabilitățile de apariție a literelor în cuvinte.
În aceste exempl e de compresie s -a folosit structura statistică a cuvintelor , dar mai există
și alte caracteristici ale semnalelor ce pot fi folosite în scopul realizării compresiei. Astfel, în
timpul vorbirii, construc ția fizică a cavității bucale dictează tipul de sunet e ce se produc, adică
mecanica producerii vorbirii im pune structura vorbirii, prin urmare, în loc de a transmite vorbirea
însăși, s -ar putea transmite informații cu privire la conformația caviatății buca le, care ar putea fi
folosite la recepție pentru a si ntetiza vorbirea. În acest sens, o cantitate adec vată de informației
privind conformația cavității bucale poate fi reprecentată mai compact decât numerele ce
reprezintă eșantioanele semnalului vocal.
În compresie mai pot fi folosite caracteristicile utiliz atorului datelor. De multe ori, când se
transmit semnale sonore sau vizuale, acestea sunt destinate percepției umane, dar oamenii nu pot
auzi frecvențe foarte înalte, pe care, însă, unele animale le pot percepe. Așadar, nu are rost a
transmite informații c e nu pot fi percepute, astfel încât informațiile irel evante nu mai trebuie
transmise.
Cu toate ca în ultimul timp capacitatea de stocare și transmitere a informației a crescut mult
(de exemplu compact discul și fibra optică), acesta nu răspunde pe deplin c erințelor practice, motiv
care justifică necesitatea compresiei fișierelor de dimensiuni mari ce trebuie stocate sau transmise.
În cazul stocării, pentru a crește volumul de date ce poate fi s tocat, cum este cazul fișierelor grafice,
se folosesc metode ca re comprimă datele la stocare și le decomprimă la redare. În ca zul
transmiterii, lățimea de bandă a semnalelor digitale este foarte mare, în comparație cu a canalelor
disponibile, astfel încât compresia datelor la emițator este absolut necesară pentru a pu tea folosi
canalul. La recepție are loc operația de decompresie . De exemplu, semnalul TV de înaltă definiție,
HDTV, necesită pentru transmiterea fără compresie aproximativ 884 Mbiți/secundă .

CAPITOLUL I

COMPRESIA

1.1.Noțiuni generale despre compresie
Compresia este procesul de minimizare a spațiului ocupat sau a timpului necesar
transmiterii unei anumite cantități de informație.
Metodele de compresie pot fi împărțite în:
– metode de compresie cu pierdere;
– metode de compresie fără pierder e.
Tehnicile de c ompresie implică două operații realizate de doi algoritmi: algoritmul de compresie
propriu -zis, care furnizează reprezentarea comprimată Xc a datelor de intrare X, și algoritmul de
reconstrucție, care operează asupra Xc și produce semnalul reconstruit Xˆ. În funcție de relația dintre
datele originale X și cele reconstruite Xˆ, schemele de compresie se împart în două clase:
– compresie fără pierderi, când X = 𝑋̂;
– compresie cu pierderi, când X ≠ 𝑋̂ . În acest caz se realizează o compresie m ai mare, cu
prețu l unei reconstrucții inexacte.
Avantajele compresiei sunt:
– reducerea spațiului necesar depozitării unei cantități de informație;
– scăderea timpului de transmitere a unor mesaje , ceea ce duce la scăderea costului per mesaj și
posibilitatea c reșterii traficul ui într -o rețea de transmisiuni;
– scăderea timpului de rulare a unui program datorită timpului de acces la disc;
– distribuției caracterelor (unele caractere au o frecvență de ap ariție mult mai mare decât altele);
– repetării consecutive a unor caractere;
– distr ibuției grupurilor de caractere (unele grupuri sunt mult mai frecvente decât altele și în plus
există grupuri care nu apar deloc);

1.2. Compresia fără pierderi
Compresia fără pierderi nu implică pierderea de informație, datele inițiale fi ind refăcute
exact din cele compresate. Această compresie se folosește de obicei pentru semnale discrete ca
text, date generate de calculator, unele tipuri de informație video, d eoarece refacerea exactă este
esențială în cazul textelor (sensul comunicării) , unor imagini (i magistică pentru diagnostic),
numere (comunicări bancare) etc.
Compresia fără pierderi este cea utilizată de programele uzuale de arhivare a datelor pe un
calcu lator (.zip, .rar).
Conceptul de compresie de date fără pierdere pare imposibi l la prima vedere , dar o analiză
mai atentă face ca această idee, de compresie fără pierdere , să aibă sens. Astfel, dacă ne gândim la
prescurtările din viața de zi cu zi ( abrevieri: prof., etc., CEC, ș.a.) acestea apar ca o formă primitivă
a compresiei de date. Compresia d e date fără pierdere, prezentă în programele de arhivare, în
sistemele de transmisiune a datelor, a ev oluat de -a lungul timpului pornind de la algoritmi s impli
(suprimarea zerourilor, codarea pe șiruri) și ajungând la algoritmii complecși folosiți în preze nt.
Clasificarea algoritmilor de compresie fără pierderi:
Algoritmii de compresie de date fără pierdere pot fi încadrați în una din următoarele categorii:
– Algoritmi statici, care se bazează pe o statistică bine cunoscută a sursei și dau re zultate
bune în c azul în care sursele au o statistică asemănătoare cu cea presupusă. În caz contrar,
rezultatul poate fi o extensie în loc de o compresie.
– Algoritmi semiad aptivi sau în două treceri, algoritmi care folosesc statistica simbolurilor
mesajului , statistică ce s e obține printr -o parcurgere inițială a întregului mesaj. Acești
algoritmi oferă rezultate pentru oric e tip de sursă, dar nu pot fi folosiți într -o transm isiune.
– Algoritmi adaptivi, care sunt de obicei cei mai potriviti pentru orice tip de sursă. Tehnicile
adaptive au ca idee construirea unui "dicționar de codare" al simbolurilor mesajului, paralel
cu codarea pentru compresie a mesajului. Acest dicționar se va construi identic la recepție,
pe baza informației recepționate.

1.3. Compresia cu pierderi

Compre sia cu pierderi conduce la o rată de compresie superioară cu prețul pierderii de
informație, datele care au fost supuse compresiei neputând fi refăcute ex act. Această compresie
este mai eficientă când se aplică semnalelor imagistice sau sonore, caz în care pierderea de
informație din afara percepției vizuale sau auditive umane poate fi tolerată. Multe tehn ici de
compresie cu pierderi pot fi ajustate la dife rite nivele de calitate. Evident, creșterea acurateței
semnalului refăcut se obține cu prețul unei com presii mai reduse. Volumul compresiei depinde
atât de mărimea redundanței sursei, cât și de eficiența reducerii acesteia.
Compresia cu pierderi este frecv entă în cazul semnalelor multimedia (audio: MP3, imagini:
JPEG, video: MPEG) și exp loatează faptul că percepția umană este imperfectă și poate tolera
pierderea unor detalii slab perceptibile din semnal.
Metodele de compresie cu pierdere de informație sunt folosite în special în transmisia
semnalului audio și video, unde pierderea de info rmație are ca rezul tat o scădere a calității
sunetului, respectiv imaginii, ele neconstituind obiectul prezentei lucrări.

1.4. Evaluarea compresiei

Un algoritm de compresie poate fi evaluat în funcție de:
– necesarul de memorie pentru implementarea algorit mului;
– viteza alg oritmului pe o anumită mașină;
– raportul de compresie;
– calitatea reconstrucției.
De obicei, ultimele două criterii sunt esențiale în adoptarea algoritmului de compresie.
Uzual, performanțele compresiei pot fi exprimate prin raportul de comp resie și rata de
compresie.
Raportul de compresie este raportul dintre numărul de biți necesar reprezentării datelor
înainte și după compresie.

Rata de compresie reprezintă numărul mediu de biți necesar reprezentării unui eșantion.
În compresia cu pierderi , versiunea recon struită diferă de varianta originală și, pentru a
determina eficiența algoritmului de compresie, trebuie să existe mijloace de aprec iere a diferenței
dintre semnalul original și cel reconstruit. Diferența dintre semnalul original și cel re construit se
nume ște distorsiune . Tehnicile de compresie cu pierderi se folosesc de obicei pentru compresia
semnalelor analogice, care se mai numesc forme de undă, motiv pentru care compresia
semnalelor analogice mai poartă denumirea de codarea formelor de undă . În cazul c odării
semnalelor video și sonore destinatarul este, de obicei, omul, al cărui răspuns este dificil de
apreciat, motiv pentru care s e folosesc măsuri aproximative de determinare a calității
reconstrucției. Alți termeni folosiți în aprecier ea diferenței din tre semnalul original și cel refăcut
este fidelitatea și calitatea . Acestea sunt cu atât mai ridicate, cu cât diferența dintre versi unea
reconstruită și cea originală a sursei este mai mică.

CAPITOLUL II

DEFINIREA ȘI CARAC TERISTICILE TIPURI LOR D E COD

2.1. Definirea și codurilor nesingulare, unic decodabile și instantanee

În comunicațiile digitale, o problemă importantă o reprezintă transmisia eficientă și
stocarea informației. Pentru stocarea și transmisia digitală a date lor este necesar ca informația să
fie reprezentată într -o formă binară.
Fie S ={ 𝑠1,𝑠2,… ,𝑠𝑁} mulțimea mesajelor unei surse discrete de informație,
X = { 𝑥1,𝑥2,…,𝑥𝑀 }alfabetul codului și C = { 𝑐1,𝑐2,…,𝑐𝑀 }, mulțimea cuvintelor de cod. Prin
operația de codare se realizează bijecția dintre mesajele 𝑠𝑘 ∈ S și cuvintele de cod 𝑐𝑘 ∈ C .
Alfabetul codului cel mai utilizat este alfabetul binar ( X = {1,0} , M=2).
Prin definiție, u n cod se numește nesingu lar, dacă toate cuvintele de cod sunt distincte.
Prin definiție, un cod se numește unic decodabil , dacă fiecărei succesiuni de simboluri
recepționate îi corespunde o singură succesiune de mesaje ale sursei primare S.
Deși se pot ut iliza coduri c el puțin unic decodabile, există si o subclasă a codurilor unic
decodabile numite coduri instantanee. Aceste coduri prezintă proprietăți utile pentru construcția
și analiza lor și sunt potrivite pentru implementarea procesele de codare și dec odare.
Pentru fixarea ideilor, se consideră o sursă discretă de informație S={ 𝑠1,𝑠2 ,𝑠3,𝑠4} și
alfabetul codului X = {0,1}. Dacă mulțimea cuvintelor de cod este C = { 𝑐1,𝑐2,𝑐3,𝑐4 }, cu 𝑐1→1,
𝑐2→01, 𝑐3→10, 𝑐4→11, codul este nesingu lar, deoarece toate cuvintele de cod sunt distincte.
Dacă, însă, se recepționează secvența 1101, aceasta poate fi interpretată în trei moduri diferite, și
anume fie 𝑠2𝑠4, fie 𝑠1𝑠1𝑠2, fie 𝑠1 𝑠3 𝑠1, deci codul respectiv nu e ste unic decodabil.
O posibilitate de obține re a codurilor unic decodabile ar fi utilizarea unui simbol special
în alfabetul codului, care să marcheze fie începutul fiecărui cuvânt de cod, fie sfârșitul acestuia.
De exemplu, dacă si mbolul α marchează sfârș itul fiecărui cuvânt de cod, atunci la recep ționarea

secvenței llα01α în condițiile exemplului considerat, se decide că s -a transmis succesiunea
mesajelor 𝑠2𝑠4, codul devenind astfel unic decodabil.
Datorită ușurinței cu car e se pot genera două stă ri, notate simbolic cu 0, respectiv 1,
alfabetul codului este format numai din aceste două simboluri. De aceea, se pune problema de a
se întocmi coduri unic decodabile folosind alfabetul binar X = {0,1}.
Considerând aceeași sursă di scretă, ce poate furniza patru mesaje și un alfabet de cod
binar, se presupun următoarele două coduri codul A, în care 𝑠1→𝑐1→0, 𝑠2→𝑐2→10,
𝑠3→𝑐3→110, 𝑠4→𝑐4→1110 și codul B, în care 𝑠1→𝑐1→0, 𝑠2→𝑐2→01, 𝑠3→𝑐3→011,
𝑠4→𝑐4→0111. Atât codul A, cât și codul B sunt unic decodabile, deoarece în cazul codului A un
zero marchează sfârșitul fiecărui cuvânt de cod, în timp ce în cazul codului B un zero marchează
începutul fiecărui cuvânt de cod. Deși ambe le coduri sunt unic deco dabile, între acestea există o
diferență importantă în cazul codului A, decodarea (inte rpretarea) fiecărui cuvânt de cod se poate
realiza odată cu recepționarea integrală a acestuia, în timp ce în cazul codului B decodarea
fiecărui cuvânt de cod trebuie să mai aștepte un timp, până la recepționarea primului simbol din
cuvântul următor.
Pentru a stabili diferența dintre cele două coduri, este necesar să se introducă noțiunea de
prefix a unui cuvânt de cod.
Prin definiție, succesiunea 𝑥𝑖1𝑥𝑖2···· 𝑥𝑖𝑘 este prefix al cuvântului de cod 𝑐𝑖 → 𝑥𝑖1𝑥𝑖2····
𝑥𝑖𝑚, dacă k ≤ m .
Prin def iniție, un cod se numește instantaneu , dacă nici un cuvânt de cod nu este prefix
pentru celelalte cuvinte de co d. Evident, dacă un cod este instantaneu, el este și unic decodabil,
reciproca nefiind totdeauna adevărată.
În cazul codului B, cuvântul de cod 𝑐1, este prefix al cuvintelor 𝑐2, 𝑐3 și 𝑐4, cuvântul de
cod 𝑐2 este prefix al cuvinte lor 𝑐3 și 𝑐4, iar cuvân tul de cod 𝑐3 este prefix pentru 𝑐4.
Evident, dacă un cod este instantaneu, el este și unic decodabil, reciproca nefiind
totdeauna adevărată.
Pentru a stabili dacă un cod este instantaneu, i se atașează graful arborescent. Î n general,
dacă alfabetu l codului este X = { 𝑥1,𝑥2,…,𝑥𝑀 }, graful arborescent se întocmește astfel se pleacă

dintr -un nod inițial, numit rădăcina grafului, care se desface în M ramuri (arce) pe care se alocă
arbitrar cele M simboluri 𝑥1,𝑥2,…,𝑥𝑀, din alfa betul codului. Din cele M noduri formate la
capetele celor M ramuri se desfac din nou câte M ramuri, pe care se alocă arbitrar literele din
alfabetul codului și așa mai departe.
Cuvintele de cod se formează citind ramurile, plecându -se de la rădăcina grafu lui
arborescent spre nodurile terminale. Dacă toate cuvintele de cod corespund nodurilor terminale
în graful arborescent, nici un cuvânt de cod nu este prefix pentru altul și, deci, codul este
instantaneu. Grafurile arborescente pe ntru codurile A și B sun t date în Fig. 1.1.

Fig. 1.1.a) Graful arborescent al codului instantaneu A; b) Graful arborescent al codului B

2.2. Teorema de existență a co durilor instantanee

Această teoremă stabilește condiția necesară și suficientă de existență a codurilor instanta nee,
referitoare la lungimile cuvintelor de cod.
Prin definiție, lungimea unui cuvânt de cod reprezintă numărul de simboluri din alfabetul
codului, din care este format cuvântul respectiv.
Pentru o sursă discretă de informație și un alfabet de cod impus, se poate întocmi o
mulțime de coduri instantanee sau unic decodabile. În scopul comparării acestora și a alegerii
celui sau celor mai bune (eficiente), se consideră drept criteriu de comparație timpul necesar
transmiterii informaț iei sursei codate.

Un cod instantaneu va fi cu atât mai eficient, cu cât timpul necesar transmiterii
informației sursei discrete va fi mai mic. Este posibil să se întocmească o multitudine de coduri
instantanee de eficiență maximă. Pentru a compara diverse coduri instantanee, se va defini
lungimea medie a cuvintelor de cod, care este proporțională cu timpul mediu de transmitere a
cuvintelor de cod.
Se conside ră o sursă discretă de informație, caracterizată de mulțimea mesajelor
S={ 𝑠1,𝑠2,… ,𝑠𝑁}, alfabetul codului X = { 𝑥1,𝑥2,…,𝑥𝑀 }, mulțimea cuvintelor de cod
C = { 𝑐1,𝑐2,…,𝑐𝑁 } și mulțimea lungimilor cuvintelor de cod L = { 𝑙1,𝑙2,…,𝑙𝑁 }.
Un cuvânt de cod 𝑐𝑘 este format dintr -o succe siune de 𝑙𝑘 simboluri din alfabetul codului,
de forma :
𝑐𝑘→𝑥𝑖…𝑥𝑗…𝑥𝑙
Condiția necesară și suficientă de existență a codurilor instantanee este dată de inegalitatea
lui Kraft, de forma
(1.1)

unde M este numărul de simboluri din alfabetul codului, N este numărul cuvintelor de cod și
𝑙𝑘- lungimea cuvintelor de cod.
Pentru a demonstra suficiența teoremei de existență, se consideră adevărată r elația ( 1.1) și,
pe baza a cesteia, se întocmește un cod care se va dovedi instantaneu.
Lungimile 𝑙1,𝑙2,…,𝑙𝑁 ale cuvintelor de cod pot fi distincte sau nu. Fie 𝑛1 numărul cuvintelor
de cod formate numai dintr -un singur simbol (lungime ega lă cu unitatea) , 𝑛2 numărul cuvintelor
de cod formate din două simboluri (lungime egală cu doi) și așa mai departe, fie 𝑛𝑙, numărul
cuvintelor de cod de lungimea cea mai mare egală cu l.
Evident
(1.2)

Cu aceste notații, rezultă că în inegalitatea (1.1) suma va conține 𝑛1 termeni de forma 𝑀−1, 𝑛2
termeni de forma 𝑀−2 și așa mai departe , 𝑛𝑙 termini de forma 𝑀−𝑙. În consecință, inegalitatea
(1.1) se poate scrie, echivalent,sub form a

(1.3)
Înmulțind relația (1.3) cu 𝑀𝑙 ≥ 0, rezultă
(1.4)

Negl ijând în relația (1.4) ter menul 𝑛𝑙 ≥ 1 și împărțind apoi noua relație cu M ≥ 2, rezultă
inegalitatea
(1.5)
Neglijând în rela ția (1. 5) termenul 𝑛𝑙−1 ≥ 1 și împărțind apoi noua relație cu M ≥ 2, rezultă
inegalitatea
(1.6)

În mod analog, se poate obține u n șir de inegalități, ultimele trei fiind de forma
𝑛3 ≤ 𝑀3 – 𝑛1𝑀2 – 𝑛2𝑀 (1.7)
𝑛3 ≤ 𝑀2 – 𝑛1𝑀 (1.8)
𝑛1 ≤ 𝑀 (1.9)
Evident, dacă inegalitatea (1.1 ) este satisfăcută, cu atâ t mai mult vor fi satisfăcute
inegalitățile (1.4) pană la (1.9). Pe baza acestor inegalități se poate întocmi un cod instantaneu,
după cum urmează :

Se alege arbitrar un număr 𝑛1 de cuvinte de lungime unu, care respectă inegal itatea (3.9).
Rămân astfel disponibile M – 𝑛1 prefixe formate dintr -un singur simbol, cu care se pot forma
cuvinte de lungime egală cu doi, al căror număr este egal cu
(1.10)
Alegându -se arbitrar dintre acestea 𝑛2 cuvinte ce respectă relația ( 1.8), rămâne disponibil
un număr de prefixe din două simboluri, egal cu 𝑀2 – 𝑛1𝑀 – 𝑛2 , cu care se pot forma cu vinte
de lungime egală cu trei, în număr de
(1.11)

Dintre acestea, se aleg arbitrar 𝑛3 cuvinte care respectă r elația (1.7). În mod analog se formează
și celelalte cuvinte.
Deoarece nici un cuvânt nu devine prefix pentru altul, codul astfel întocmit este
instantaneu, demonstrându -se astfel suficiența teoremei de existență a codurilor insta ntanee.
Deoarece codurile instantanee formează o subclasă a codurilor unic decodabile, rezultă că s -a
demonstrat suficiența teoremei de existență și pentru codurile unic decodabile.
Pentru a demonstra necesitatea teoremei de existență a codurilor instantan ee, se pleacă de
la aserți unea: cuvintele unui cod instantaneu pot fi aranjate totdeauna în nodurile terminale ale
unui graf arborescent. Fie l cea mai mare lungime a cuvintelor de cod. La nivelul l arborele va
avea, evident, un număr de 𝑀𝑙 noduri. Fiecare cuvânt de lungime 𝑙𝑘 ≤ 1 blochează utilizarea
𝑀𝑙−𝑙𝑘 noduri pe nivelul l. De exemplu, dacă l =3 , M =2 , (simbolurile ”0” și ”1”) și se allege un
cuvânt de lungime 𝑙𝑘=2, fie acesta 𝑐𝑘 = 01, atunci pe nivelul l = 3 se blochează utilizarea a
23−2 = 2 noduri, așa cum este arătat în figură care urmează.

Deoarece două cuvinte distincte blochează noduri diferite pe nivelul l, rezultă că numărul
de noduri blocate pe nivelul l, rezultă că numărul de noduri blocate pe nivelul l este mărginit
superior de nu mărul de noduri de pe acest nivel, adică
(1.12)

Simplificând cu 𝑀𝑙 > 0, rezult ă inegalitatea (1.1), care trebuia demonstrată.
Teorema fiind de existență , înseamnă că, dacă lungimile cuvintelor de cod satisfac
inegalitatea ( 1.1), există cel puțin un procedeu de codare prin care să rezulte un cod instantaneu.
Aceasta nu înseamnă că orice cod care satisface ineg alitatea ( 1.1) este instantan eu. Teorema
stabilește că folosindu -se lungimi ale cuvintelor de cod ce satisfac inegalitatea ( 1.1), se poate
întocmi cel puțin un cod instantaneu și, deci, unic decodabil. Dacă pentru un cod dat este
satisfăcută inegalitatea lui Kraft, pentru a decide dac ă acesta este instantaneu, i se atașează graful
arborescent și, dacă toate cuvintele de cod sunt noduri terminale, se decide că este instantaneu.
Dacă pentru un cod dat inegalitatea ( 1.1) nu este satisfăcută, atun ci, cu certitudin e, codul
nu este instantan eu și nici unic decodabil și, prin nici un procedeu de codare care va folosi aceleași
lungimi ale cuvintelor de cod, nu se poate întocmi un cod instantaneu sau unic decodabil.

2.3.Lungimea medie a cuvintelor de cod

Pentru o su rsă discretă de informație și un alfabet de cod impus, se poate întocmi o
mulțime de coduri instantanee sau unic decodabile. În scopul comparării acestora și a alegerii
celui sau celor mai bune (eficiente), se consideră drept criteriu de comparație timpul necesar
transmiterii inform ației sursei codate, de mărimea acestui timp fiind legate o serie de cheltuieli.
Un cod instantaneu va fi cu atât mai eficient, cu cât timpul necesar transmiterii informației sursei
discrete va fi ma i mic. Este posibil să se înto cmească o multitudine de co duri instantanee de
eficiență maximă.
Pentru a compara diverse coduri instantanee, se va defini lungimea medie a cuvintelor de
cod, care, așa cum se va demonstra, este proporțională cu timpul mediu d e transmitere a
cuvintelor de cod. În felul acesta, se va demonstra că cel mai eficient cod instantaneu care se
obține, este cel pentru care lungimea medie a cuvintelor de cod este minimă.
Fie, pentru aceasta, o sursă discretă, completă și fără memorie, caracterizată de distribuția:

(1.13)
Fie, de asemene a, mulțimea simbolurilor di n alfabetul codului X = { 𝑥1,𝑥2,…,𝑥𝑀 } și
mulțimea cuvintelor de cod C = { 𝑐1,𝑐2,…,𝑐𝑁 }.
Datorită corespondenței bijective dintre 𝑠𝑘 ∈ S și 𝑐𝑘 ∈ C , rezultă
𝑝(𝑠𝑘) = 𝑝(𝑐𝑘) (1.14)
unde 𝑝(𝑐𝑘) reprezintă probabilitatea cuvântului 𝑐𝑘 .
Informația atașată mesajului 𝑠𝑘 , notată cu 𝑖(𝑠𝑘), va fi atunci egală cu informația ataș ată
cuvântului 𝑐𝑘, notată cu 𝑖(𝑐𝑘) și se va calcula cu relația clasică
(1.15)

Dacă se notează cu H (X ) entropia codului utilizat, atunci, aceasta măsoară informația medie pe
un simbol din alfabetul codului.
Fie H(S) entropia sursei ce urmează a fi codată, adică informația medie pe un mesaj.
Dacă 𝑙1,𝑙2,…,𝑙𝑁 sunt lungimile cuvintelor de cod, lungimea medie a acestora se calculează
cu relația
(1.16)

Pe de altă parte este evide nt că numărul mediu de simboluri ale unui cuvânt de cod, adică
𝑙̅ , este dat de raportul dintre informația medie pe cuvânt, H(S), și informația medie pe un simbol
constituent, adică
(1.17)

Dacă se ține cont de și (1.16), relația (1.17) se
poate scrie echivalent sub forma

(1.18)

sau

(1.19)

O condiție suficientă, dar nu întotdeauna necesară, pentru satisfacerea relației
este ca

(1.20)
Dacă se notează cu 𝜏̅ durata medi e de transmitere a unui sim bol din alf abetul codului X,
rezultă că dur ata de transmitere 𝑇𝑘 a cuvântului de cod 𝑐𝑘, de lungime 𝑙𝑘, se poate determina cu
relația

(1.21)
Duratele 𝑇𝑘 , k = 1,𝑁̅̅̅̅̅, de transmitere a cuvintelor de c od, determină o nouă varia bilă
aleatoa re discretă, ce poate lua valori cu probabilitățile 𝑝(𝑠𝑘) = 𝑝(𝑐𝑘) și, deci , durata medie de
transmitere a unui cuvânt de cod este
(1.22)

Comparând relațiile (1.16) și (1.22), rezultă
𝑇̅ = 𝜏̅ ∙ 𝑙̅ (1.23)
adică durata medie de transmitere a cuvintelor va fi cu atât mai mică, cu cât lungimea medie a
acestora v a fi mai mică.
Mărirea eficienței transmisiunii se poate, deci, obține selectând a cel cod instantaneu care
asigură o lun gime medie minima a cuvintelor de cod.
Eficiența transmisiunii poate fi definită, dacă există o margine inferioară a lungimii medii,
𝑙̅, a cuvintelor de cod.
Din relația ( 1.17) rezultă că micșorarea lui 𝑙̅ se poate realiza fie prin micșorar ea entropiei
sursei ce urmează a fi codată, fie prin mărirea entropiei codului, adică mărirea informației medii
pe un simbol din alfabetul codului.
Deoarece entropia sursei H(S) nu poate fi modificată fără alterarea sursei iniția le, rezultă
că singura pos ibilitate pe ntru micșorarea lungimii medii a cuvintelor de cod rămâne mărirea
entropiei codului printr -o codare adecvată .

Notând cu 𝑙̅𝑚𝑖𝑛, lungimea medie minima posibilă a cuvintelor de cod, se poate scrie relația

(1.24)
Deoarece în urma codării sursei S, utilizarea simbolurilor din alfabetul codului X depinde,
în general, de unul sau mai multe simboluri folosite a nterior, rez ultă că, în general, sursa secundară
X este o sursă cu memorie. La limită, când sursa secundară X devine fără memorie și simbolurile
acesteia sunt folosite echiprobabil, adică .
(1.25)
rezultă margi nea superioară a entropiei sursei secundare X egală cu log𝑀 și, deci, marginea
inferioar ă a lungimii medii a cu vintelor de este 𝐻 (𝑆)
log𝑀 .
În general , se p oate scrie șir ul de inegalități
(1.26)

În cazul partic ular, frecvent folosit în aplicații, a l codurilor binare, M=2, caz în care relația ( 1.26)
devine
𝑙 ̅≥ 𝑙̅𝑚𝑖𝑛 ≥ H (S) (1.27)
Cu alte cuvinte, în cazul codurilor binare instantanee nu se pot obține lungimi medii ale
cuvintelor de cod mai mici decât entropia sursei ce urmează a fi codată.

2.4. Eficiența și redundanța unui cod

Prin definiție, se numește eficiența unui cod și va fi notată cu η , raportul dintre marg inea
inferioară a lungimii medii a cuvintelor de cod și lungimea medie a acestora, adică

(1.28)

Înloc uind ( 1.20) în relația ( 1.28), rezultă o relație echivalentă de calcul pentru eficiența
unui cod instantaneu, și anume

(1.29)
Prin d efiniție, se numește redundanța unui cod și va fi notată cu ρ, mărimea complementară
eficienței, adică
𝜌 =1− ɳ (1.30)
Din relația ( 1.29) rezultă că valoarea maximă a eficienței este η =1.

Din punct de vedere fizic, entropia măsoară informația medie pe mesaj, respectiv
nedeterminarea medie a sursei respective.
Prin definiție, un cod se numește absolut optimal , dacă eficiența acestuia este maximă.
În cazul codului absolut optimal, din relația ( 1.28) rezultă
𝐻(𝑆)= 𝑙̅log𝑀 (1.31)
Înlocuind în acea stă relație H (S) și 𝑙̅ cu relațiile lor de calcul, rezultă
(1.32)

O condiție suficientă pentru satisfacerea acestei relații este
𝑙𝑘log𝑀+log𝑝(𝑠𝑘)=0 (1.33)
Din ( 1.33) rezultă
𝑝(𝑠𝑘)=𝑀−𝑙𝑘 (1.34)
Sumând după k de la 1 la N în relația ( 1.34), se obține
(1.35)

adică în cazul codurilor absolut optimale inegalitatea lui Kraf t devine egalitate. În acest caz
mesajele trebuie furni zate cu probabilitățile date de relația ( 1.34).

2.5. Teorema codării surselor discrete, complete și fără memorie pe canale
neperturbate

S-a demonstrat în paragra ful precedent că, dacă fiecare mesaj a l unei surse discrete,
complete și fără memorie este furnizat cu probabilitatea data de relația ( 1.34), se poate obține un
cod absolut optimal. Logaritmând în bază doi această relație, rezultă
𝑙𝑘=log𝑝(𝑠𝑘)
log𝑀 (1.36)
Conform definiției lungimii cuvintelor de cod, rezultă că numai în cazul codurilor absolut
optimale raportul −log𝑝(𝑠𝑘)
log𝑀 este u n număr întreg pozitiv, ce poate fi co nsiderat egal cu lungimea
cuvântulu i de cod 𝑐𝑘.
În general, sursa discretă de informație își furnizează mesajele cu diverse probabilități care
nu respectă relația ( 1.34) și, deci, raportul −log𝑝(𝑠𝑘)
log𝑀 nu mai este un număr întreg. În acest caz,
lungimile cuvintelor de cod , 𝑙𝑘 , 𝑘= 1,𝑁̅̅̅̅̅, se aleg numerele întregi pozitive care respectă dubla
inegalitate
−log𝑝(𝑠𝑘)
log𝑀 ≤ 𝑙𝑘 < −log𝑝(𝑠𝑘)
log𝑀 +1 (1.37)
Alegând astfel lungimile cuvintelor de cod, se poate demonstra că inegalitatea iui Kraft
este satisfăcută, deci, cu astfel de lungimi se poate întocmi totdeauna un cod instantaneu.
Într-adevăr, din pr ima inegalitate a relației ( 1.27) rezu ltă
𝑀−𝑙𝑘 ≤ 𝑝(𝑠𝑘) (1.38)
Sumând după k, de la k=l la k=N și ținând cont că sursa discretă de informație este
completă, rezultă
(1.39)
Multiplicând relația ( 1.37) cu 𝑝(𝑠𝑘)>0 și apoi su mând după k, de la k=1 la k=N, rezultă

(1.40)

Ținând cont de (3.18), (3.19) și de faptul că to tdeauna sursele discrete de info rmație sunt
complete, relația (3.40) d evine
𝐻(𝑆)
log𝑀≤𝑙̅<𝐻(𝑆)
log𝑀+1 (1.41)
Relația ( 1.41) este adevărată pentru orice sursă S discretă, completă și fără memorie, deci
va fi adevărată și pentru extens ia sa de ordinul m.
Notând cu 𝐻(𝑆𝑚) entropia extensiei de ordinul m și cu 𝑙𝑚̅̅̅, lungimea medie a cuvintelor
de cod corespunzătoare mesajelor compuse 𝜎𝑘 ale extensiei de ordinul m, relația ( 1.41) se poat e
scrie sub forma
𝐻(𝑆𝑚)
log𝑀≤𝑙𝑚̅̅̅<𝐻(𝑆𝑚)
log𝑀+1 (1.42)
𝐻(𝑆𝑚)= mH(S) (1.43)
Ținând cont de ( 1.43), relația ( 1.42) devine
𝐻(𝑆)
log𝑀≤𝑙𝑚̅̅̅̅
𝑚<𝐻(𝑆)
log𝑀+𝑙
𝑚 (1.44)
Pe de altă parte
𝑙𝑚̅̅̅̅
𝑚 = 𝑙̅ (1.45)
deoarece un mesaj compus este format dintr -o succesiune de m mesaje ale sursei inițiale S.

Din ( 1.44) și ( 1.45) rezultă că, la limită, când m → ∞ , lungimea medie a cuvintelor de cod
atinge marginea inferioară a lungimii m edii a cuvintelor de cod, adică
𝑙̅ =𝐻(𝑆)
log𝑀 (1.46)
obținându -se astfel un cod absolut optimal.
Conform acestei teoreme, rezultă că, efectuându -se codări pe e xtensii ale unei surse
discrete de informație, se pot obține lungimi medii ale cuvintelor de cod cu atât mai mici, cu cât
ordinu l extensiei este mai mare. La limită, când ordinul extensiei tinde la infinit, se obține l ungimea
medie cea m ai mică posibilă a cuvintelor de cod, egală cu marginea inferioară a acestora.
În practică nu se poate coda extensia de ordinul m a sursei primare, când m tinde la infinit.
Ordinul extensiei va avea totdeauna o valoare finită și, cu cât ordinul extensiei este mai mare, cu
atât complexitatea instalației de codare crește. Mai mult, de la o anumită valoare a ordinului
extensiei, creșterea ordinului în continuare va duce la scăderi nesemnificative ale lungimii medi i
a cuvintelor de cod, astfe l că nu se mai justifică prețul de cos t ridicat, dictat de creșterea
complexității instalației de codare. Din această cauză, în practică, în multe situații reale, se
realizează codări pe mesaje individuale, utilizându -se procede e de codare care conduc la c oduri
instantanee de eficiență cât mai ridicată, adică acelea care conduc spre lungimi medii ale cuvintelor
de cod cele mai mici posibile. Dintre procedeele de codare posibile s -au impus, procedeul de
codare Huffman, procedeul d e codare binară Shannon – Fano și codarea aritmetică.

CAPITOLUL III

CODAREA BINARĂ HUFFMAN

În acest capitol se descrie clasa codurilor instantanee cunoscute sub denumirea de coduri
Huffman .
Algoritmul de codare propus de Huffman încearcă să atribuie fiecărui simbol un cuv ânt
de cod de lungime proporțională cu cantitatea de informație transmisă de acel simbol.
Codurile Huffman sunt importante pentru că sunt coduri compacte. Algoritmul H uffman
va produce coduri cu lungimea medie a cuvintelor de cod cea mai mică posibilă, pe ntru un număr
dat de simboluri ale sur sei și un alfabet al codului. De asemenea prin reodonarea adecvată a
simbolurilor vor rezulta coduri care au cea mai mica dispersi e posibilă.

3.1. Procedeu de codare binară Huffman static

Acest procedeu se bazează pe ideea de a partiționa mulțimea mesaje lor sursei
𝑆={𝑠1,𝑠2,…,𝑠𝑁} în submulțimile 𝑆0 și 𝑆1, astfel încât suma probabilităților mesajelor incluse
în 𝑆0 să fie cât mai apropiată de suma probabilităților mesaj elor incluse în 𝑆1. La rândul lor ,
submulțimile 𝑆0 și 𝑆1 pot fi p artiționate în submulțimile 𝑆00 și 𝑆01, respectiv 𝑆10 și 𝑆11 astfel
încât suma probabilităților mesajelor incluse în cele patru submulțimi să fie cât mai apro piate
posibil. Procedeul se continuă î n mod similar până când se obțin submulțimi ce conțin un singur
mesaj.
În felul acesta, pentru orice distribuție a sursei S ce urmează a fi codată se va obține un cod
compact, adică lungimi medii ale cuvintelor de cod ce nu mai pot fi micșorate prin n ici un alt
procedeu de codare.

Pentru ca partițiile să satisfacă condițiile menționate, se procedează astfel:
1. Se ordonează mulțimea mesajelor sursei S în ordinea descrescătoare a probabilităților,
obținându -se astfel mulțim ea ordonată 𝑅0={𝑠1,𝑠2,…,𝑠𝑁} , cu 𝑝(𝑠1)≥𝑝(𝑠2)≥⋯ ≥
𝑝(𝑠𝑁) , cu schimbarea eventuală a indicilor mesajelor pentru realizarea ordonării
respective;
2. Se reunesc ultimele două mesaje (de probabilitățile cele mai mici) într -un nou me saj,
notat cu 𝑟1, căruia i se aloc ă o probabilitate egală cu suma probabilităților mesajelor
componente. Se ordonează din nou mesajele în ordinea descrescătoare a
probabilitățil or, formându -se astfel prima sursă restrânsă 𝑅1={𝑠1,𝑠2,…,𝑟1,…} , cu
𝑝(𝑠1)≥𝑝(𝑠2)≥⋯ ≥𝑝(𝑟1)≥⋯ ;
3. Se reunesc ultimele două mesaje din sursa restrânsă 𝑅1 într-un nou mesaj 𝑟2 , de
probabilitate egală cu suma probabilităților mesajelor componente. Se ordonează
mesajele în ordine descrescătoare, for mându -se astfel sursa restrânsă 𝑅2 . În mod
analog, din 𝑅2 se formează sursa restrânsă 𝑅3 și așa mai departe, până când se obține o
sursă restrânsă formată numai din două mesaje, 𝑅𝑛={𝑟𝑛 ,𝑟𝑛−1} , cu 𝑝(𝑟𝑛)≥𝑝(𝑟𝑛−1).
De fapt, 𝑟𝑛 va fi 𝑆0 și 𝑟𝑛−1 va fi 𝑆1 sau invers .
Din modul de formare a surselor restrânse 𝑅𝑖, rezultă că mulțimea S a mesajelor poate fi
partiționată în două submulțimi 𝑟𝑛 și 𝑟𝑛−1 astfel încât probabilitățile 𝑝(𝑟𝑛) și 𝑝(𝑟𝑛−1) sunt cele
mai apropiate posibil. La rândul lor, submulțimile 𝑟𝑛 și 𝑟𝑛−1 pot fi partiționate în alte do uă
submulțimi, de probabilitățile cele mai apropiate posibil. Partiționările se continuă până se obțin
submulțimi care conțin un singur mesaj.
4. Cuvintele de c od corespunzătoare fiecărui mesaj se obțin astfel :
• submulțimii 𝑟𝑛 i se alocă simbolul ” 0” (sau ” 1”);
• submulțimii 𝑟𝑛−1 , i se aloc ă simbolul ” 1” (sau ” 0”);
• la fiecare partiționare se alocă arbitrar celor dou ă submulțimi ”0” sau ”1”,
operația con tinuându -se până se obțin submulțimi ce conțin un singur mesaj 𝑠𝑘,
𝑘=1,𝑁̅̅̅̅̅ .
Deoarece alocarea lui ”0” și ”1” este arbitrară la fiecare partiționare, rezultă că unei surse
S i se pot atașa o multitudine de codu ri instantanee, toate, însă, având ace eași lungime medie a

cuvintelor de cod, care nu mai poate fi micșorată prin nici un alt procedeu de codare a mesajelor
luate individual.
Dacă sursa primară S poate furniza N mesaje, atunci submulțimea restrânsă 𝑅1 , va avea
N-1, mesaj e, submuțimea res trânsă 𝑅2 va conține N-2 mesaje și așa mai departe, ultima submu lțime
restrânsă 𝑅𝑛 va conține N-n mesaje, care sunt 𝑟𝑛 și 𝑟𝑛−1 , adică se poate scrie :
𝑁−𝑛=2⇒𝑛=𝑁−2 (1.47)
Dacă submulțimii 𝑟𝑛 i se alocă simbolul ” 0” și submulțimii 𝑟𝑛−1 simbolul ” 1”, celor N-2
partiționări putându -li-se aloca arbitrar ”0” sau ”1”, rezultă un total de 2𝑁−2 posibilități de
codare. Dacă, însă, sub mulțimii 𝑟𝑛 i se alocă simbolul ” 1” , iar submulți mii 𝑟𝑛−1 simbolul ” 0” ,
mai rezultă 2𝑁−2 posibilități de codare. Rezultă, deci, că prin acest p rocedeu de codare se pot
realiza 2𝑁−2+2𝑁−2=2𝑁−1 coduri instantanee, toate având toa te aceeași lungime medie a
cuvintelor de cod.
Prin definiție, se numește cod compact, codul care realizează lungimea medie minimă a
cuvintelor de cod. Deoarece prin procedeul de codare Huffman se obține cea mai mică lu ngime
medie a cuvintelor de cod, însea mnă că prin acest procedeu se obțin coduri ins tantanee
compacte. Evident, un cod absolut optimal este și compact, reciproca nefiind totdeauna valabilă.

Exempl u 1 :
Se presupune sursa discretă de informație caracterizată de distribuția:

Codarea binară Huffman a acestei surse se poate realiza astfel:

Graful și cuvintele de cod corespunzătoare codării efectuate sun t astfel scrise :

3.1.1. Coduri Huffman de dispersie minima

Codurile Huffman de dispersie mi nimă se obțin când la reordonarea surs ei restrânse,
simbolul compus se plasează pe poziția cea mai de sus posibil în sursa restrânsă. În felul acesta
cuvântul de cod atribuit simbolului compus va avea cea mai mică lungime posibilă. Cum acest
cuvânt va deve ni prefix pentru simbolurile constitue nte, cuvintele de cod c orespunzătoare acestora
vor avea o lungime cu o unitate mai mare decât lungimea prefixului, deci și acestea vor rezulta de
lungime minimă. Ca urmare, diferențele dintre lungimile cuvintelor de co d devin minime, ceea ce
va conduce, ev ident, și la o dispersi e minimă.
Pentru fixarea ideilor, se presupune sursa discretă de informație caracterizată de distribuția:

𝑆:(𝑠1 𝑠2 𝑠3
0,20,40,2 𝑠4
0,1 𝑠5
0,1)

Pentru această s ursă se efectuează codarea Huffman, pl asând întâi mesaje le sursei restrânse
pe pozițiile cele mai jos posibile în listă și apoi pe pozițiile cele mai de sus posibile.

Fig. 1.2 Schema de codare

Fig. 1.3 Graful și cuvintele de cod

Pentru ac est cod, lungimea medie și dispersia s unt:
𝑙̅=0,2∙2+0,4∙1+0,2∙3+0,1∙3+0,1∙4=2,2 biți /mesaj
𝜎12= ∑(𝑙𝑖−𝑙̅)5
𝑖=1=0,22+1,22+0,82+1,82+1,82=8,6
Pentru cazul în care în codarea Huffman mesajele sursei restrânse se plasează pe po zițiile
cele mai de sus în listă, se o bține schema de codare din Fig. 1.4 și graful și cuvintel e de cod ca în
Fig. 1.5.

Fig. 1.4 Schema de codare

Fig. 1.5 Graf ul și cuvintele de cod

Pentru acest cod, lungimea medie este, evident, aceeași, în timp ce dispersia devine :
𝜎22=∑(𝑙𝑖−𝑙̅)2=0,22+0,22+0,22+0,82+0,82=1,45
𝑖=1
Deși din punct de vedere informațional, cele două coduri sunt identice, în practică se
preferă f olosirea celor de dispersie minimă, din motive de transm isie.
De exemplu, dacă se dorește să s e transmită mesaje ale sursei cu o viteză de 10.000
mesaje/sec., este necesar un canal cu capacitatea de 22.000 biți/sec. Deoarece viteza de generare a
biților oscilează în jurul valorii de 22.000 biți/sec., funcție de succesiunea de mesaje furnizate la
un moment dat, ieșirea sursei este încărcată într -un buffer. Dacă, de exemplu, sursa generează la
un moment dat șiruri de mesaje s4 și s5 mai multe secunde, pentr u primul cod se generează 40.000
biți/sec. și în fiecare s ecundă ar trebui un buffer de capacita te de 18.000 biți. Cu al doilea cod se
generează 30.000 biți /sec. și bufferul ar trebui să aibă capacitatea de 8.000 biți. Dacă se transmit
șiruri de mesaje s2 , cu primul cod se generează 10.000 biți/sec. și canalul n u e folosit la capacitatea
sa, rămânân d un deficit de 12.000 biți/sec., pe când cu al doilea cod se generează 20.000 biți/sec.,
deficitul existent în exploatarea canalului fiind numai de 2.000 biț i/sec. Așadar, din motive de
transmisie este mai rezonabil a se alege al doilea cod decât primul.

3.1.2. Procedeul de codare binară Shannon – Fano

Codarea Shannon -Fano se bazează pe ideea că pentru simboluri furnizate cu probabilități
echiprobabile se vor obține cuvinte de cod de lungime egală. Se descrie în continuare metoda
Shannon -Fano de obținere a codurilor instan tanee.

Acest procedeu se aplică de obicei în cazurile particulare în care probabilitățile de furnizare
ale m esajelor sunt puteri întregi pozitive ale lui (1/2), adică, de for ma:
(1.48 )

unde 𝑙𝑘 este un număr întreg pozitiv .
Dacă relația ( 1.48) este satisfăcută, mulțimea 𝑆={𝑠1,𝑠2,…,𝑠𝑁} a mesajelor sursei
discrete de informație ce urmează a fi codată poate fi partiționată în două submulțimi 𝑆0 și 𝑆1 ,
astfel încât suma probabilităților mesajelor incluse în 𝑆0 notată cu 𝑝(𝑆0), să fie egală cu suma
probabilităților mesajelo r incluse în 𝑆1 , notată cu 𝑝(𝑆0). Sursa S fiind totdeauna complet ă, se
poate scrie :

(1.49)

Submulțimile 𝑆0 și 𝑆1 se ot portiționa la rândul lo r în 𝑆00 și 𝑆01, respectiv în 𝑆10 și 𝑆11 ,
astfel încât suma probabilităților mesajelor incluse în cele patru submulțimi să fie aceeași, adică
se poate scrie relația:
(1.50)

Se procedează în mod analog până se obțin submulțimi care conțin un singur mesaj. Se
observă că fiecare submulțime are suma pr obabilităților mesajelor incluse egală cu o pute re
întreagă a lui (1/2). Puterea întreagă este egală cu numărul indicilor submulțimii respective Dacă
submulțimea conține un singur mesaj, 𝑠𝑘 și care un număr de indici egal cu 𝑙𝑘 , atunci s e poate
scrie:
𝑝(𝑠𝑘)=(1
2)𝑙𝑘=2−𝑙𝑘 (1.51)
de unde rezultă necesitatea ca sursa S ce urmează a fi codată să -și furnizeze mesajele cu
probabilități ega le cu 1/2 la o putere întreagă, pozitivă.

Sursa fiind c ompletă, se poate scrie: (1.52)
∑𝑝(𝑠𝑘)=1𝑁
𝑘=1

Înlocuind ( 1.51) în ( 1.52), rezultă: (1.53)
∑2−𝑙𝑘𝑁
𝑘=1=1
ceea ce înseamnă că inegalitatea lui Kraft devine în acest caz egalitate.
Cuvintele de cod se vor obține, atunci, astfel:
1. Se atribuie simbolul "0" su bmulțimii 𝑆0 și simb olul ”1” submulțimii 𝑆1 , (sau invers ) , astfel
că toate cuvintele corespunzătoare mesajelor incluse în 𝑆1 , vor începe cu ” 1” (sau invers );
2. Se alocă submulțimilor 𝑆00 și 𝑆10 ca al doilea mesaj ” 0” , iar submulțimil or 𝑆01 și 𝑆11 ca
al doilea mesaj ” 1” (sau in vers). În felul acesta, cuvintele de cod corespunzătoare mesajelor
incluse în 𝑆00 vor începe cu 00, cuvintele de cod corespunzătoare mesajelor incluse în 𝑆10
vor începe cu 10 și așa mai depart e, cuvintele de cod corespunzătoare mesajelor induse î n
𝑆11 vor începe cu 11 .
3. Operația se continuă în același mod, până când în fiecare submulțime rămâne un singur
mesaj, căruia îi va corespunde cuvântul de cod format din șirul de indici ai submulțimii
respective.
Deoarece la fiecare partiționare în dou ă submulțimi atribuirea mesajelor ”0” și ”1” este
arbitrară, rezultă că prin acest procedeu se pot obține o multitudine de coduri instantanee, dar toate
absolut optimale.
În principiu, procedeul de codare descris s -ar putea aplica în general, adică și atun ci când
relația ( 1.53) nu este satisfăcută. În acest caz, partiționările în submulțimi trebuie efectuate astfel
încât suma probabilităților mesajelor i ncluse în submulțimile respective să fie cât mai apropiate.
Atribuind simbolurile ”0” și ”1” ca în proced eul descris, se obțin totdeauna coduri instantanee.

Cu cât sumele probabilităților mesajelor componente ale submulțimilor respective vor fi
mai apropiate, cu atât lungimea medie a cuvintelor de cod va fi mai mică.

Exempl u 2
Se consideră surs a discretă de informație caracterizată de distribuția:
𝑆:(𝑠1 𝑠2
2−22−2 𝑠3 𝑠4 𝑠5
2−32−32−4 𝑠6 𝑠7 𝑠8
2−42−42−4)
Procedeul de codare binară Shannon – Fano este sintetizat în tabelul de m ai jos.

Graful arborescent atașat codului astfel obținut este reprezentat mai jos

3.1.3. Lungimea medie a cuvintelor de cod în cazul codului binar Huffman

Se știe că pentru un cod optimal
𝐻(𝑆)≤𝑙̅≤𝐻(𝑆)+1 (1.54)
Limita superioară din relația ( 1.54) nu este foarte precisă. 𝑝𝑚𝑎𝑥 este cea mai mare probabilitate
cu care este furnizat un mesaj, atunci pentru 𝑝𝑚𝑎𝑥 <0,5, limită superioară pentru codul Huffman
este 𝐻(𝑆)+𝑝𝑚𝑎𝑥 , în timp ce pentru 𝑝𝑚𝑎𝑥 ≥0,5 , limita superioară este 𝐻(𝑆)+𝑝𝑚𝑎𝑥 +0,086.
În aplicațiile în care numărul de mesaje ale sursei este mare, 𝑝𝑚𝑎𝑥 este relativ mic și
redundanța codului, care este diferența dintre lungimea medie și entropie, exprimată în procente
din entropie, este relativ mică. În cazul în care alfabetul sursei este mic și probabilitățile de apariție
ale diferitelor mesaje sunt neec hilibrate, valoarea probabilității 𝑝𝑚𝑎𝑥 poate fi relativ mare și codul
Huffman poate deveni ineficient, adică redundanța sa să reprezinte un procent semnificativ din
entropie.
Exemplu 3
Fie o sursă care furnizează mesajele 𝑆={𝑠1,𝑠2,𝑠3} cu probabilitățile 𝑝(𝑠1)=0,8;
𝑝(𝑠2)=0,02; 𝑝(𝑠3)=0,18. Entropia sursei este de 0,816 biți/mesaj.
Codul Huffman pentru această sursă este dat mai jos :

Lungimea medie pentru acest cod este 1,2 biți/simbol. Redundanța este 0,384 biți/simbol,
aproximativ 47% din H(S). Aceasta înseamnă că pent ru a coda această sursă sunt necesari cu 47%
mai mulți biți decât minimul necesar. Uneori , pentru micșorarea redundanței se realizează codarea
Huffman pe extensia sursei inițiale. Astfel, dacă se consideră extensia de ordinul 2 a sursei
precedente, se obți n 32=9 mesaje. Dacă se efectuează codarea Huffman a sursei extinse, se obțin
cuvintele de cod în următoru l table .

Pentru acest cod, lungimea medie este 𝑙̅𝑒=1,751 6 biți / mesaj.
Cum un mesaj al sursei extinse este format din două mesaje ale alfab etului original, rezultă
că lungimea medie, 𝑙̅ , exprimă în funcție de alfabetul original este 𝑙̅=0,8758 , redundanța este de
aproximativ 0,06 biți/simbol, adică aproximativ 7% din entropie.
Dacă pr obabilitățile mesajelor sunt mult neechilibrate, atunci ar putea fi necesară codarea
pe extensii de ordin superior, în scopul scăderii la valori acceptabile ale redundanței. Prin creșterea
ordinului extensiei, mărimea alfabetului sursei extinse crește expo nențial cu ordinul extensiei și
codarea Huffman poate d eveni ineficientă din punct de vedere al prețului de cost, caz în care se
folosește codarea aritmetică , care va fi discutată ulterior.

3.1.4. Procedeu l de codare Huffman generaliza

În acest caz, alfabetul codului conține mai mult de două simboluri. Procedeul de codare este
asemănător celui din cazul binar, parcurgându -se următoarele etape:
1. Se ordonează mesaje le sursei ce urmează a fi codată în ordinea descrescătoare a
probabilităților;
2. Dacă alfabetul codului conține M ≥ 3 simboluri, se reunesc ultimele M mesaje (de
probabilitățile cele mai mici) într -un singur mesaj, căruia i se alocă probabilitatea egal ă cu
suma probabilităților mesajelor componente. Se ordonează din nou mesajele în ordinea

descrescătoare a probabilităților, formându -se astfel prima sursă restrâ nsă 𝑅1. Procedându –
se în mod analog, se formează sursa restrânsă 𝑅2 din 𝑅1,𝑅3 din 𝑅2 și așa mai departe, până
când se obține o sursă restrânsă care conține M mesaje. Pentru ca ultima sursă restrânsă să
conțină M mesaje cărora să li se a loce arbitrar cele M mesaje din alfabetul codului, înainte
de a realiza restrângerile respective, se face următorul raționament:
– la formarea primei surse restrânse, reunindu -se M mesaje într-un singur mesaj, va rezulta
un număr de mesaje egal cu 𝑁−𝑀+1=𝑁−(𝑀−1);
– – a doua sursă restrânsă va conține, prin reunirea ultimelor M mesaje, un număr de mesaje
egal cu 𝑁−2𝑀+2=𝑁−2(𝑀−1);
– raționându -se în mod analog, după n restrângeri, ultima sursă restrânsă va conține un
număr de mesaje egal cu 𝑁−𝑛(𝑀−1), care trebuie să fie egal cu numărul M al mesajelor
din alfabetul codului, adică
𝑀=𝑁−𝑛(𝑀−1)⇒𝑛=𝑁−𝑀
(𝑀−1) (1.55)
Deoarece n (numărul de restrângeri) trebuie să fie un număr întreg pozitiv, se va considera:
𝑛1=[𝑁−𝑀
𝑀−1] (1.56)
unde [m] simbolizează cel mai mic număr întreg, mai mare sau egal decât m. Astfel, sursa va trebui
să aibă un număr de mesaje 𝑁1 , calculat cu rela ția
𝑁1=𝑀+𝑛1(𝑀−1) (1.57)
– Dacă sursa S ce urmează a fi codată are un număr N de mesaje care nu verifică relația
(1.57), se va adăuga la sursa respectivă un număr de mesaje, până când această relație este
satisfăcută. Mesajelor adăugate li se vor aloca probabilități nule, astfel că sursa inițială nu
va fi alterată, deoarece mesajele de probabilită ți nule nu vor fi furnizate niciodată.
3. La fiecare partiție în M submulțimi se alocă arbitrar cele M mesaje din alfabetul codului.
Deoarece alocarea celor M mesaje din alfabetul codului se face arbitrar, rezultă că prin
acest procedeu va rezulta o multitudi ne de coduri instantanee, toate cu aceeași lungime
medie a cuvintelor de cod, care nu mai poate fi micșorată prin nici un alt procedeu d e
codare, adică toate codurile astfel obținute vor fi instantanee și compacte.

Exemplu 4

Se presupune sursa discretă d e informație caracterizată de distribuția
𝑆:(𝑠1 𝑠2
0,10,2 𝑠3 𝑠4
0,30,15 𝑠5 𝑠6
0,05 0,2)
Dacă alfabetul codului este 𝑋={𝑥1,𝑥2,𝑥3} , să se realizeze o codare Huffman generalizată.
Înainte de a realiza codarea , se verifică dacă este satisfăcută relația (3.57) care, pentru cazul
particular considerat, devine : 𝑁1=2𝑛1+3 , unde 𝑛1=[6−3
3]=2 , deci 𝑁1=7. Va
trebui adăugat un nou mesaj, fie acesta 𝑠7, de pro babilitate nulă , adică 𝑝(𝑠7)=0.
Pentru realizarea codării, se procedează după cum se arată

Schema de codare pentru exemplu
Cuvintele de cod corespunzătoare mesajelor sursei sunt
𝑠1→𝑐1→𝑥1𝑥3𝑥1
𝑠2→𝑐2→𝑥3
𝑠3→𝑐3→𝑥2
𝑠4→𝑐4→𝑥1𝑥2
𝑠5→𝑐5→𝑥1𝑥3𝑥2
𝑠6→𝑐6→𝑥1𝑥1

Graful corespunzător codului este

Graful atașat codului

3.2. Codarea binară Huffman dinamic ă

Procedeul de codare binară Huffman descris în paragraful 3. 1 necesită cunoașterea probabilităților
cu care sursa își furnizează mesajele. În literatura de specialitate această situație este cunoscută și
sub denumirea de codare Huffman statică. În cazul în care probabilitățile de furnizare a mesajelor
nu sunt cunoscute, se folosește codarea Huffman dinamică sau adaptivă .
În descrierea cod ării Huffman dinamice sau adaptive se vor folosi următoarele notații și noțiuni :
– nodurile terminale sau externe din graful arborescent se vor numi frunze, corespunzând
mesajelor sursei;
– cuvântul de cod pentru un mesaj se obține parcurgând arborele de la rădăcină la frunza
corespunzătoare si mbolului. Prin convenție, zero se va aloca unei ramuri din stânga și unu,
unei ramuri din dreapta;
– nodurile de la extremitățile ramurilor care pleacă dintr -un nod reprezintă fiii sau copiii
nodului respectiv, numit nod părinte;
– ponderea unui nod extern este numărul de apariții a simbolului corespunzător frunzei
respective până la acel moment;
– ponderea unui nod intern este suma ponderilor fiilor nodului respectiv;
– Dacă sursa ce urmează a fi codat ă furnizează n mesaje, în graf există 2n+1 noduri inter ne
și externe, numerotate în continuare 𝑦1,… ,𝑦2𝑛+1 . Dacă 𝑥𝑗 este ponderea nodului cu
numărul 𝑦𝑗 , trebuie să existe relația 𝑥1≤𝑥2≤⋯ ≤𝑥2𝑛+1 ;

– nodurile 𝑦2𝑗−1 și 𝑦2𝑗 sunt fii ai aceluiași nod părinte, iar numărul de ordine al părintelui
este mai mare decât 𝑦2𝑗−1 și 𝑦2𝑗 .
Ultimele două caracteristici se numesc de fraternitate și orice arbore care are această proprietate
este un arbore Huffman .
În codarea Huffman dinamică, nici emițătorul, nici receptorul nu cunosc statistica sursei la
începerea transmisiei, astfel încât arborii de la transmisie și recepție constau dintr -un singur nod
corespunzător mesajelor încă netransmise, de pondere zero. P e parc ursul transmisiei, nodurile
corespunzătoare mesajelor transmise sunt adăugate arborelui, care este reconfigurat pe baza unui
procedeu de actualizare. Înaintea începerii transmiterii se stabilește un cod pentru fiecare mesaj,
după cum urmează:
Dacă su rsa furnizează mesajele 𝑠1,𝑠2,… ,𝑠𝑁 , se determină parametrii e și r, astfel încât
𝑁=2𝑒+𝑟,0≤𝑟<2𝑒 . Mesa jul 𝑠𝑘 este codat prin reprezentarea pe e +1 biți a lui k −1, dacă 1
2 ≤ k r ≤ , în caz contrar, 𝑠𝑘 este reprezentarea pe e biți a lui k – r – 1. De exemplu, pentru
𝑁=26→𝑟=10 și 𝑒=4→𝑠1=00000 , 𝑠2=00001 , … , 𝑠22=1011 .
Ideea principală în codarea Huffman adaptivă este aceea că arborele (graful) codului este
actualizat după fiecare mesaj codat, plecându -se inițial de la un singur nod rădăcină. Astfel, pentru
codarea mesajului cu numărul i din secvență se folosește un arbore de codare construit pe baza
celor i − 1 mesaje precedente din mesaj. După transmit erea mesajului i, arborele de codare se
actualizează, și noul arbore este folosit pentru codarea mesajului următor i + 1. Există mai multe
implementări ale algoritmului Huffman adaptiv, care diferă între ele prin modul de actualizare a
arborelui. În aceast ă lucrare se va prezenta metoda de actualizare propusă de Faller, Gallager și
Knuth (FGK).

3.2.1. Actualizarea arborelui

Algoritmul de actualizare necesită ca nodurile să fie numerotate într -o ordine stabilită. Cel
mai mare număr de nod este al rădăcinii. Cel mai mic se asignează nodului încă netransmis, care
este nod gol, (NG).
Mulțimea nodurilor cu aceeași pondere formează un bloc. Rolul algoritmului de actualizare
este de a păstra proprietatea de fraternitate în timpul modificării arborelui, pentru a reflecta ultima
estimare a frecvenței de furnizare a mesajului.

Pentru ca procedura de actualizare de la emițător și receptor să opereze cu aceeași
informație, arborele de la emițător este ac tualizat după codarea fiecărui mesaj, iar la recepție
arborele este actualizat după decodarea fiecărui mesaj.
Organigrama algoritmului de actualizare este prezentată în figura de mai jos :

Procedura de actualizare pentru algoritmul de codare dinamică Huffman

Procedura de actualizare este următoarea: după ce un mesaj a fost codat la emis ie sau
decodat la recepție, nodul extern corespunzător mesajului este examinat pentru a vedea dacă are
cel mai mare număr de nod din bloc. Dacă nodul extern nu are cel mai mare număr de nod, el este
interschimbat cu nodul care are cel mai mare număr din bl oc, cu condiția ca acesta să nu fie
părintele nodului ce urmează a fi actualizat. Ponderea nodului extern este apoi incrementată. Dacă
nu se interschimbă nodurile înaintea incrementării ponderii nodului, este posibil ca ordonarea
cerută de proprietățile de fraternitate să fie distrusă. Odată incrementată ponderea nodului, s -a
adaptat arborele Huffman la acel nivel.
Se trece apoi la nivelul următor, prin examinarea nodului părinte al nodului a cărui pondere
a fost incrementată, pentru a vedea dacă are cel mai mare număr din bloc. Dacă nu are, este

schimbat cu nodul cu cel mai mare număr din bloc. Din nou, face excepție nodul cu cel mai mare
număr, dacă acesta este părinte pentru nodul considerat. Odată ce s -a efectuat schimbarea (sau s -a
decis că nu est e necesară), ponderea nodului părinte este incrementată. Procesul se termină când
se ajunge la nodul rădăcină.
Când mesajul ce urmează a fi codat sau decodat apare pentru prima dată, acestuia i se
atribuie un nod extern și se atașează un nou nod NG în graf.
Atât nodul extern cât și nodul NG sunt fii al vechiului NG. Cum mesajul corespunzător
noului nod exte rn a apărut o singură dată, acestuia i se atribuie ponderea 1.
Cum vechiul nod NG este părinte pentru noul nod extern, ponderea sa se incrementează cu
1 și se continuă astfel până la rădăcină.

Exemplu 5
Se presupune că se dorește codarea Huffman adaptivă a secvenței [ 𝑎 𝑎 𝑟 𝑑 𝑣 𝑎] , care
conține 4 din 26 de mesaje posibile, reprezentate de literele mici ale unui alfabet. Pentru codarea
acestor mesaje se folosește codul prezentat în paragraful 3. 2.
Procesul de actualizare este arătat în Fig. 3. 13. Se începe cu nodul NG. Numărul total de
noduri este 2∙26+1=53, astfel încât se începe num ărătoarea invers ă, cu num ărul 53 asignat
nodului r ădăcină. Prima liter ă ce urmeaz ă a se transmite este 𝑎. Cum litera nu este în arbore, se
transmite 𝑎 și se adaugă aceasta în arbore. Nodul NG dă naștere unui nou nod NG și unui nod
terminal, corespunzător literei a. Ponderea nodului terminal va fi mai mare decât a nodului NG,
astfel încât se asignează numărul 51 nodului NG și 52 nodului terminal corespunzător literei 𝑎.
Următoarea literă de transmis este tot 𝑎. De această dată, codul transmis este 1, deoarece litera este
în graf. Nodul corespunzător lui 𝑎 are cel mai mare număr din bloc (dacă nu se consideră nodul
său părinte), așa încât nu este nevoie să schimbăm nodurile. Se incrementează ponderea nodului
extern și a nodului rădăcină. Următoarea literă de transmis este r. Cum litera nu are un nod
corespunză tor în arbore, se transmite cuvântul de cod pentru nodul NG, care este 0, urmat de
indexul lui r. Nodul NG dă naștere unui nou nod NG și unui nod extern corespunzător lui r. Din
nou, nu este necesară actualizarea arborelui, ci numai incrementarea corespunz ătoare a ponderilor
nodurilor. Următoarea literă este d, care, de asemenea, se transmite pentru prima dată. Se transmite
codul pentru nodul NG, care este 00, urmat de indexul pentru d. Nodul NG dă iar naștere la două
noduri. Încă nu este nevoie de a actual iza arborele. Acesta se schimbă cu transmiterea literei

următoare, 𝑣, care nu a mai fost întâlnită. S -a transmis codul frunzei goale, 000, urmat de codul
pentru litera 𝑣. În arbore se adaugă nodurile 45 și 46, cu 46 ca nod terminal pentru 𝑣. Se
incrementea ză ponderea nodului extern 46 și a vechiului NG. Se merge la nodul părinte al
vechiului NG, adică nodul 49 care nu are cel mai mare număr din bloc, așa că se schimbă cu 50,
care este cel mai mare număr din bloc și se incrementează ponderea acestuia. Se mer ge la rădăcina
nodului 50 care este 51 și care nu are cel mai mare număr din bloc, așa că se schimbă cu 52, a cărui
pondere se incrementează. Se merge la rădăcina nodului 52, adică nodul 53, care este nod rădăcină
și se incrementează ponderea acestuia. Urm ează mesajul 𝑎, care este în graf, așa încât se transmite
0. Deoarece numărul nodului extern corespunzător lui 𝑎 este maxim în bloc, se incrementează
ponderea acestuia și a părintelui, care este nod rădăcină.

Fig. 1 3. Arborele Huffman adaptiv ă, după ce s -a transmis secvența 𝑎 𝑎 𝑟 𝑑 𝑣 𝑎
a10r00d000v0

3.2.2. Algoritmul de codare

Diagrama pentru codare este prezentată în fig. inițial, arborii de la codare și decodare sunt formați
dintr -un singur nod NG. Prin urmare, cuvântul de cod corespunzător primului mesaj ce apare este
transm is în clar. După primul mesaj, de fiecare dată când trebuie codat un mesaj ce apare pentru
prima dată, se transmite întâi codul pentru nodul NG, care se obține prin parcurgerea arborelui
Huffman de la rădăcină la nodul NG.
Aceasta înștiințează receptorul că mesajul al cărui cod urmează nu are încă un nod în arborele
Huffman. Codul nodului NG este urmat de codul prestabilit pentru mesaj. Dacă mesajul ce
urmează a fi codat are un nod corespunzăt or în arbore, atunci este transmisă succesiunea de biți
obținută prin traversarea arborelui de la rădăcină la nodul extern corespunzător mesajului.

Fig. 14. Organigrama pentru codare

Algoritmul de compresie pentru codarea Huffman adaptivă presupune parcurgerea următorilor
pași:
1. Se iniț ializează arborele de codare cu un nod rădăcină.
2. Se transmite primul mesaj în clar (de ex. codul ASCII al unei litere).

3. Se construiesc încă două noduri (frunze) care pornesc din nodul rădăcină, unul la stânga,
care nu conține nici un simbol și căruia i se atașează ponderea nulă (frunză goală) și unul
la dreapta care conține simbolul apărut, ponderea acestuia devenind egală cu 1.
4. Se citește următorul mesaj din secvență:
➢ dacă mesajul este deja în arbore se transmite codul său din arbore. Codul mesajului se
formează citind simbolurile de ’0’ respectiv ’1’ atașate ramurilor, pornind de la nodul
rădăcină până la nodul în care se află mesajul. Apoi se trece direct la pasul 5;
➢ dacă mesajul nu este în arbore se transmite codul nodului terminal care nu conține nici un
simbol (frunză goală) urmat de codul în clar (de ex. ASCII) al mesajului. Codul nodului
fără nici o literă se formează ca și în cazul nodului care conține o literă.
5. Se actualizează arborele , dacă secvența s -a terminat, atunci codarea este terminată. În caz
contrar se reia procedeul începând cu pasul 4.

Exemplu 6

În Exemplul 5 s-a folosit un alfabet de 26 de litere. Pentru a obține codul prestabilit pentru mesaj
trebuie găsite valorile pentru e și r, astfel încât 2𝑒+𝑟=26 cu 0≤𝑟<2𝑒→𝑒=4,𝑟=10.
Primul mesaj de codat este a. Cum a este prima literă din alfabet, k=1. Deoarece
2∙𝑟=20>𝑘=1 , litere a va fi reprezenta rea pe e + 1 = 5 biți a numărului 𝑘−1=1−1=0,
adică 00000. Arborele este actualizat după diagrama din Fig. 3.13, nodul gol a dat naștere unui
nod extern corespunzător lui a și unui nou nod gol. Nodul extern corespunzător lui a are ponderea
1, iar nodul gol, 0. Nodul intern are ponderea 1 (suma ponderilor fiilor). Următorul mesaj este a.
Cum acesta există deja în arbore, cuvântul de cod corespunzător se obține prin traversarea grafului
de la rădăcină la nodul corespunzător, în cazul de față este 1.
După transmiterea codului pentru cel de -al doilea a, ponderea nodului extern corespunzător
acestuia este incrementată la 2, ca și ponderea părintelui.
Al treilea mesaj de tra nsmis este r. Cum acesta este la prima apariție, se transmite codul
nodului gol, adică 0, urmat de codul lui r. (r, fiind a optsprezecea literă din alfabetul de 26 de litere,
înseamnă că k = 18 ; deoar ece 18<2𝑟=20, litera r va fi reprezentarea binar ă pe
𝑘+1=4+1=5 biți a numărului 𝑘−1=18−1=17 , adică 10001 ). Arborele este
actualizat și se continuă cu mesajul d. Folosind același procedeu pentru d, se transmite codul

nodului gol, care este 00 urmat de indexul lui d, care este 00011 (d fiind a patra literă din alfabet
și deoarece 4 < 20, litera d va fi reprezentarea binară pe 𝑘+1=4+1=5 biți a numărului
𝑘−1=4−1=3, adică 00011). Următorul simbol, v , este al 22 -lea în alfabet și fiind mai mare
decât 20 se transmite codul pentru nodul gol, 000, urmat de reprezentarea binară pe 4 biți a lui
22-10-1=11, adică 1011. Următorul mesaj este a, pentru care se transmite 0.
Secvența transmisă este:
a 10 r 00 d 000 v 0, echivalentă cu
00000 1 0 1001 00 00011 000 1011 0
a a gol r gol d gol v a

3.2.3. Algoritmul de decodare

Organigrama pentru decodare este prezentată în Fig. 15.

Fig. 15. Organigrama pentru decodarea Huffman dinamică

Pe măsură ce este citită secvența binară recepționată, arborele se parcurge într -un mod identic cu
cel de la codare.
Odată identificat codul unei frunze din secvența recepționată, se decodează mesajul
corespunzător acelei frunze. Dacă frunza este frunză goală, se verifică următorii e biți pentru a
vedea dacă rezultă un număr mai mic decât r. Dacă este mai mic, se mai citește un bit pentru a
completa codul mesajului. Indexul mesajului se obține adăugând o unitate la numărul zecimal
corespunzăto r secvenței de e sau e+1 biți. Odată decodat mesajul, arborele este actualizat și
următorul bit recepționat este folosit pentru a porni o nouă parcurgere a arborelui.
Algoritmul de decompresie pentru codarea Huffman constă în parcurgerea următorilor
pași, prin care se reface pas cu pas arborele de la algoritmul de compresie:
1. Se inițializează ar borele de codare cu un nod rădăcină.
2. Se decodează primul mesaj transmis în clar (de ex. codul ASCII al literei).
3. Se construiesc încă două noduri care pornesc din nodul ră dăcină, unul la stânga, care nu
conține nici un mesaj și căruia i se atașează ponderea nulă, și unul la dreapta, care conține
mesajul recepționat, ponderea acestuia devenind egală cu 1.
4. Se citește codul recepționat, bit cu bit. Se parcurge arborele pornind din nodul rădăcină,
biții de ’0’ și ’1’ recepționați indicând ramurile care se aleg la parcurgere, până când se
ajunge la un nod frunză:
➢ dacă nodul frunză respectiv este nodul care nu conține nici un mesaj, se citește următorul
mesaj în clar, apoi se trece la pasul 5;
➢ dacă nodul frunză respectiv es te atașat unui mesaj, atunci acesta este mesajul decodat din
codul recepționat .
5. Se reactualizează arborele (vezi procedura mai jos). Dacă secvența recepționată s -a
terminat, atunci decodarea este terminată, iar în caz contrar se reia procedeul începând cu
pasul 4.

Exemplu 7

Să se decodeze secvența codată anterior, 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0.
Inițial arborele de la decodor constă numai dintr -un nod gol, așa că primul mesaj ce urmează a fi
decodat se obține din listă. Se citesc e=4 biți, 0000, care corespunde numărului zecimal 0.
Deoarece 0<𝑟=10, rezultă că se mai citește un bit, rezultând secvența 00000. Se decodează în
zecimal și se adaugă o unitate, astfel indexul simbolului recepționat este 1, care îi corespunde lui
a în listă, prin urmare, prima literă decodată este a.
Arborele este actualizat. Următorul bit recepționat este 1, care îi corespunde căii de la rădăcină la
nodul extern a, astfel încât al doi lea mesaj decodat este tot a.
Următorul bit este 0, care corespunde căii de la rădăcină la nodul gol. Următorii patru biți 1000
corespund numărului zecimal 8, care este mai mic decât 10, astfel încât se mai citește un bit pentru
a obține cuvântul 10001, al cărui echivalent zecimal plus o unitate este 18, care este indexul lui r.
Se decodează r și se actualizează arborele. Următorii doi biți 00 reprezintă parcurgerea grafului
până la frunza goală. Se citesc următorii 4 biți 0001, care corespund lui 1<10, deci se mai citește
un bit, adică secvența 00011. Pentru a obține indexul simbolulu i recepționat din listă, se adaugă o
unitate la valoarea zecimală a celor 5 biți. Valoarea indexului este 4, care corespunde simbolului
d. Continuând, se obține secvența decodată a a r d v a .

CAPITOLUL IV

Aplica ții ale codării H uffman

În continuare sunt prezentate câteva aplicații simple ale codării Huffman în compresie, această
codare fiind, de obicei, folosită în practică împreună cu alte tehnici de codare.

1.Compresia fără pierderi a imaginilor
Codarea Huffman poate fi folosită în compresia imaginilor digitale, când fiecare pixel poate lua
valori dintr -o mulțime finită. În cazul imaginilor monocrome, această mulțime constă din numere
întregi de la 0 la 225.
Rezultatele pentru patru imagini de t est pentru care s -a aplicat codarea Huffman sunt arătate în
Tabelul 1.

Tabelul 1 .

În reprezentarea imaginii originale (necompresate) se folosesc 8 biți/pixel. Imaginea constă
din 256 de rânduri a câte 256 de pixeli, deci reprezentarea necompresată folosește 65.536 biț i.
Din Tabelul 1. se observă că raportul de compresie diferă de la imagine la imagine,
obținându -se o reducere de numai aproximativ ½ până la 1bit/pixel, după compresie. Pentru unele
aplicații această reducere este acceptabilă. De exemplu, dacă într -o arhivă există sute de imagini,
o reducere de un bit pe pixel salvează mulți megabyți în spațiul discului. În codarea din exemplul
considerat nu s -a ținut cont de structura din date, dată de corelația dintre pixeli. Dintr -o inspecție

vizuală a imaginii, se poate observa că într -o imagin e pixelii sunt corelați cu vecinii lor. Un model
grosier pentru determinarea valorii unui pixel poate fi dat de relația 𝑥̂𝑛=𝑥𝑛−1, adică valoarea
estimată pentru un pixel este egală cu a valoarea pixelului precedent. Secvența reziduală va fi
diferența dintre pi xelii vecini. Dacă se consideră acest model și se folosește codul Huffman pentru
a coda secvența reziduală, rezultatele sunt cele din Tabelu 2. .

Tabelul 2.

După cum se observă, se obține o îmbunătățire a raportului de compresie față de cazul
precedent. Rezultatele din Tabelele 1. și 2. sunt obținute folosind un sistem în doi pași, în unul s –
a obținut statistica sursei, iar în al doilea s -a efectuat codarea Huffman. În loc să se folosească
sistemul în doi pași, se poate folosi un cod Huffman adaptiv. Rezultatele pentru acesta sunt
prezentate în Tabelul 3. .

Tabelul 3.

Se observă că diferențele dintre codul Huffman static și cel adaptiv sunt mici. Algoritmul
Huffman adaptiv este preferat în sistemele care lucrează on -line sau în timp real, când nu este

posibilă cunoașterea prealabilă a statisticii sursei. Acesta, însă, este mai dificil de implementat
decât cel static. Aplicația particulară va determina care din cele două este mai convenabil.

2.Compre sia textelor
În compresia textelor se folosește frecvent codarea Huffman, deoarece în texte, se folosește
un alfabet discret care, într -un domeniu dat, are probabilități relativ staționare. De exemplu,
modelul de probabilitate pentru un roman nu va diferi semnificativ de modelul de probabilitate
pentru alt roman. Similar, modelul de probabilitate pentru un set de programe C nu va diferi prea
mult de modelul de probabilitate pentru un alt set de programe C.
O îmbunătățire a compresie se poate obține, dacă mai întâi se îndepărtează redundanța din
date, materializată în corelația între mesajele din fișier, care este semnificativă în textele literare.
De exemplu, în capitolul de față, Huf este întotdeauna urmat de fman .

3.Compresia audio

Altă clasă de date care se pretează foarte bine pentru compresie este clasa de date audio de
pe compact discuri (CD). Semnalul audio pentru fiecare canal stereo este eșantionat la 44,1 kHz și
fiecare eșantion este reprezentat pe 16 biți, ceea ce conduce la o cantitate enormă de date stocate
pe CD care, pentru a fi transmise, ar necesita un canal cu capacitate semnificativă. Compresia este
cu siguranță utilă în acest caz. În Tabelul 4. se arată, pe ntru diverse tipuri de surse audio, mărimea
fișierului, entropia, mărimea estimată a fișierului compresat cu codarea Huffman și raportul de
compresie rezultat .

Tabelul 4. Codarea Huffman pe 16 biți a semnalului audio

Ca și la alte aplicații, se poate obține o creștere a compresiei, dacă mai întâi este îndepărtată
corelația din date. Datele audio pot fi modelate numeric. Se folosește modelul foarte simplu care
a fost folosit în exemplul codării imaginii: valoarea estimată a unui eșantion este aceeași cu
valoarea eșantionului anterior. Folosind acest model se obține o secvență reziduală. Entropia
acestei secvențe diferență este prezentată în Tabelul 5. .

Tabelul 5. Codarea Huffman pe 16 biți a secvenței reziduale audio

Se observă o reducere de aproximativ 60% a mărimii fișierului compresat față de fișierul original.

BIBLIOG RAFIE

[1] Berlekamp, E. R. Algebraic Coding Theory. New -York: McGraw -Hill Book Company, 1968.
[2] Borda M. E. Teoria transmisiunii informatiei, Partea I -a, Teoria informatiei si codarii
(fundamente si aplicatii), Universitatea Tehnica Cluj – Napoca, 1993.
[3] Gallager R. Information Theory and Reliable Communication. John Wiley and Sons, 1968.
[4] Istvan S. s.a. Teoria transmisiunii informatiei, Îndrumar de laborator, I. P. Bucuresti, 1983.
[5] Munteanu, V., Teoria transmiterii informatiei, E ditura "Gh. Asachi" Iasi, 2001.
[6] Munteanu V. Detectie si estimare, Editura "Gh. Asachi" Iasi, 1997.
[7] Murgan, A. T., Teoria transmisiunii informatiei – Probleme, Editura Didactica si Pedagogica,
Bucuresti, 1983.
[8] Murgan A. T. Principiile teoriei informatiei si ingineria informatiei si a comunicatiilor, Editura
Academiei Române, 1998.
[9] Peterson, W. W. Error -Correcting Codes. Cambridge, Mass: The M.I.T. Press, 1961.
[10] Spataru, Al., Teoria transmisiunii informatiei. Semnale si perturbatii, E ditura Tehnica,
Bucuresti, 1963.
[11] Spataru, Al., Teoria transmisiunii informatiei. Coduri si decizii statistice, Editura Tehnica,
Bucuresti, 1971.
[12] Spataru, Al., Teoria transmisiunii informatiei, Editura Didactica si Pedagogica, Bucuresti,
1983.
[13] Stoica V., Mihaescu A. Teoria transmisiunii informatiei Litografia I. P. Timisoara, 1990.