Codarea binara Schannon - Fano

Codarea binara Schannon - Fano

Acest algoritm spune ca atunci cand probabilitatile asociate mesajelor sunt puteri intregi ale lui ½ atunci mesajele sursei primare pot fi impartite in 2 cantitati egale, astfel incat suma probabilitatilor mesajelor din fiecare submultime nou creata sa fie aceeasi. Algoritmul precizeaza ca noile submultimi pot fi divizate in continuare tot pe criteriul sumei probabilitatilor, pana cand se obtin submultimi cu un singur element. In acest caz inegalitatea lui Kraft devine egalitate. Se aloca apoi submultimilor astfel obtinute, arbitrar simboluri 0 respectiv 1 construind cuvintele de cod.

Ex: Fie o sursa ce contine 8 mesaje:

S: ( s s s s s s s s)

2 2 2 2 2 2 2 2

Pentru a demonstra ca succesiunile binare obtinute formeaza un cod se foloseste metoda grafurilor. Codul astfel obtinut are eficienta maxima.

In practica numarul probabilitatilor sunt puteri intrei ale lui ½. De aceea algoritmul se va aplica cautand metodele de construire a submultimii astfel incat sumele probabilitatilor pentru fiecare submultime sa fie cat mai apropiate posibile (codurile nu vor mai avea eficienta 1).

Prin def. un cod se numeste compact daca codifica mesajele individuale si nu pe grupe de mesaje. Un cod absolut optimal este si compact. Pt a obtine coduri compacte este necesar ca lungimile cuvintelor de cod sa descreasca odata cu cresterea probabilitatii.