Algoritmul de Compresie Huffman

1.1 Noţiuni introductive

1.1.1 Terminologie

Pentru a evita eventualele neînţelegeri ce ar putea rezulta din utilizarea unor termeni care sunt folosiţi în literatură cu mai multe accepţiuni este necesar să se facă unele precizări asupra sensului în care aceşti termeni sunt utilizaţi în această lucrare.

Informaţie. Pentru a introduce noţiunea de informaţie, se presupune că într-o situaţie oarecare pot avea loc N evenimente diferite, egal probabile, probabilitatea unui eveniment fiind p= . Prin realizarea unui eveniment din cele N posibile se obţine o informaţie. Aceasta este cu atât mai mare cu cât evenimentul realizat este mai imprevizibil, respectiv cu cât probabilitatea lui este mai mică. Prin definiţie, informaţia obţinută în acest caz este:

Se spune că se transmite o informaţie ori de câte ori se face o comunicare sau se transmite un mesaj care înlătură o anumită nedeterminare.

Semnal se numeşte o manifestare fizică (undă electromagnetică, undă sonoră, etc.) capabilă a se propaga printr-un mediu dat. Aceasta este cea mai largă accepţiune dată noţiunii de semnal. Denumirea de semnal este utilizată într-un sens mai restrâns excluzând acele semnale care dăunează procesului de transmisiune şi care se numesc perturbaţii.

Perturbaţie se numeşte un semnal care modifică semnalul aleator util care transmite informaţia, micşorând cantitatea de informaţie transmisă.

Mesaj se numeşte un semnal ce corespunde unei realizări particulare din ansamblul de idei, imagini, date, care trebuie transmise unui corespondent.

În orice proces în care se pune în evidenţă informaţia, trebuie incluse 3 elemente: 1) sursa de informaţie, 2) canalul de transmisie, 3) receptorul.

Canal (cale) de transmisiuni se numeşte totalitatea mijloacelor destinate transmisiunii mesajului, prin “mijloace” înţelegându-se atât aparatura cât şi mediul prin care se face transmisiunea şi include toate sursele de perturbaţii. În această categorie intră şi mediile fizice pe care se poate stoca (memora) informaţia, cum ar fi: benzile magnetice, discurile, etc. În general canalele de transmisiuni sunt afectate de perturbaţii, adică de semnale nedorite, care suprapunându-se pe semnalele purtătoare de informaţie le deteriorează.

Codare se numeşte prelucrarea discretă, efectuată cu scopul principal de a mări eficienţa transmisiei.

Decodare se numeşte operaţia inversă codării.

1.1.2 Modelul unui sistem de transmisie a informaţiei

Schema bloc este următoarea:

S = sursa de informaţii P = perturbaţii

E = emiţător R = receptor

G = generator de purtătoare D = destinatar

C = canal de transmisiuni

În general, prin sursă de informaţii se va înţelege mecanismul prin care se alege într-un mod imprevizibil de destinatar, un anumit mesaj ce urmează a fi transmis. Aceasta înseamnă că sursa de informaţii potenţial poate livra o mulţime de mesaje, dar la un moment dat ea va alege un anumit mesaj pe care-l va transmite, destinatarul necunoscând ce mesaj a ales sursa şi l-a transmis.

ieşirea sursei = m (mesaj)

În scopul transmiterii mesajelor la distanţă este necesar un emiţător care în cazul cel mai general realizează trei operaţii:

traducerea

codarea

modularea

Deoarece natura fizică a mesajelor limitate de sursă este foarte diversă, în general este necesară transformarea acestor mesaje, cu ajutorul unor traductoare, în semnale electrice, sau în semnale uşor de prelucrat ulterior. În scopul măririi eficienţei transmisiunii şi protejării informaţiei transmise împotriva perturbaţiilor semnalele de la ieşirea traductoarelor sunt transformate în semnale elementare aşa numita informaţie de codare. Pentru asigurarea posibilităţii de propagare la distanţă a semnalului tradus şi codat, se generează un semnal de înaltă frecvenţă (purtătoare) care este modulat de informaţia mesajului prelucrat anterior.

Prin canal de transmisiuni - se înţelege în general, orice mediu fizic prin care se poate propaga informaţia (cablul telefonic, cablu telegrafic, cablu coaxial, canal radio, canal TV). Canalele de transmisiuni sunt perturbate de anumite zgomote astfel încât semnalul de la ieşirea canalului r, este o sumă în general, dintre semnalul transmis de emiţător s şi zgomotul n ce apare inevitabil pe orice cale de transmisiuni.

Receptorul R realizează trei operaţii, în cazul cel mai general.

demodularea

decodarea

traducerea (adică operaţii inverse faţă de emiţător)

Receptorul R trebuie astfel sintetizat, ca din semnalul recepţionat r şi pe baza cunoaşterii statisticii a zgomotului ce poate apare pe canal, să estimeze după un anumit criteriu de fidelitate ce mesaj a transmis sursa. Motiv pentru care ieşirea receptorului său notat cu ^m = estimatorul mesajului transmis. Între m şi ^m există o anumită diferenţă, numită eroare de estimare. Scopul sintezei receptorului fiind acela de a realiza o eroare de estimare cât mai mică. Destinatarul este ca urmare orice maşină, beneficiarul mesajului transmis de sursă.