Codificare Shannon-Fano
Codificarea Shannon-Fano este un algoritm care permite obținerea unui cod bazat pe frecvența simbolului sursă. Ideea principală, ca și în cazul altor coduri, este de a crea cuvinte de cod mai scurte pentru simbolurile care apar cel mai frecvent. Dezvoltat de Claude Shannon și Robert M. Fano , a dat baza de la care va începe David A. Huffman și apoi își va dezvolta algoritmul de compresie ( codare Huffman ). Un cod Shannon-Fano corect obținut are caracteristica descifrabilității univoce, care este indispensabilă pentru ca decodorul să recunoască corect șirurile simbolurilor codificate.
Algoritm
- Simbolurile sursă sunt ordonate în ordinea descrescătoare a probabilității de emisie;
- Pentru fiecare pas al codificării, se formează două seturi pentru care suma probabilităților de emisie este cât se poate de similară;
- Un „1” sau un „0” este atribuit arbitrar fiecăreia dintre cele două părți;
- Pentru fiecare subset pe care îl obțin de la fiecare pas, pașii 2 și 3 se efectuează până când obținem subseturi ale unui singur element;
- Codul pentru fiecare simbol va fi obținut prin secvențierea „0” și „1” începând de la primul pas până la ultimul.
Exemplu
Avem un vocabular sursă L = {A, B, C, D, E}. Probabilitățile de emisie pentru fiecare simbol sunt P (A) = 1/10, P (B) = 1/10, P (C) = 2/10, P (D) = 2/10, P (E) = 4 / 10.
L i P i 1 2 3 ȘI 4/10 0 0 - D. 2/10 1 - C. 2/10 1 0 - B. 1/10 1 0 LA 1/10 1
Prima trecere formează două seturi, una cu probabilitatea 6/10 conținând simbolurile E și D și cea cu probabilitatea 4/10 cu simbolurile C, B și A. Singura altă alegere ar fi fost formarea unui set cu probabilitate 4/10 (doar simbolul E) și 6/10 (simbolurile D, C, B, A): codul final în acest caz ar fi diferit, dar performanțele ar fi identice.
La al doilea pas pentru setul de mai sus nu există alternative, pentru cel de sub două seturi pot fi create cu o probabilitate totală identică egală cu 2/10.
În cele din urmă, în al treilea pas, nu mai rămâne decât să împărțiți ultimele două simboluri.
Cuvintele de cod corespunzătoare fiecărui simbol pot fi citite de la pasul 1 până la pasul 3:
Simbol Cod LA 111 B. 110 C. 10 D. 01 ȘI 00
Este ușor de văzut că cele mai frecvente simboluri au un cod mai scurt asociat.
Bibliografie
- Bruce Carlson , Sisteme de comunicații , MCGRAW-HILL COLLEGE
