5 codarea shannon-fano
DESCRIPTION
Codarea Shannon-FanoTRANSCRIPT
Platformă de e-learning și curriculă e-contentpentru învățământul superior tehnic
Transmisia datelor multimedia in retele de calculatoare
5. Codarea Shannon-Fano
Codarea Shannon-Fano• Are avantajul simplitatii• Suboptimal• Se bazeaza pe teoria Shannon
1. Codul este construit astfel: mesajele sursei s(i) si probabilitatileasociate p(i) sunt listate in ordine descrescatoare aprobabilitatilor
2. Lista este divizata pentru a forma doua grupuri de probabilitatiegale
3. Fiecare mesaj din primul grup receptioneaza (primeste) 0 caprim simbol al cuvantului de cod, iar mesajele din lista a douavor avea cuvintele de cod incepand cu 1
4. Fiecare din sub-listele obtinute sunt divizate dupa acelasicriteriu si se aloca (asigneaza) simboluri suplimentare
5. Procesul se continua pana cand se obtin sub-liste cu un singurmesaj
2
Codarea Shannon-Fano• Lungimea cuvantului de cod este
–log(p(x))daca este posibil sa se divizeze in subgrupuri de probabilitate egala
• Cand acest lucru nu este posibil, unele din cuvintele de cod vor avea lungimi de
(-log(p(x)) +1)• Codul Shannon-fano furnizeaza o lungime medie a
cuvintelor de cod ce satisface relatia :
3
1 H(S) l H(S)
4
Codarea Shannon-Fano
a b c d e f
9 8 6 5 4 2
a b
9 8
c d e f
6 5 4 2
0 1
00 11 11
5
Codarea Shannon-Fano
a b c d e f
9 8 6 5 4 2
a b
9 8
c d e f
6 5 4 2
0 1
0 1
00 11 11
6
Codarea Shannon-Fano
a b c d e f
9 8 6 5 4 2
a b
9 8
c d e f
6 5 4 2
0 1
0 1
0100 11 11
7
Codarea Shannon-Fano
a b c d e f
9 8 6 5 4 2
a b
9 8
0
0 1
c d e f
6 5 4 2
1
0 1
0100 11 11
8
Codarea Shannon-Fano
a b c d e f
9 8 6 5 4 2
a b
9 8
c d e f
6 5 4 2
0 1
0 1 0 1
0100 1010 1111
9Codarea Shannon-Fano
a b c d e f
9 8 6 5 4 2
a b
9 8
e f
4 2
0 1
0 1 1
0100 1010 1111
c d
6 5
0
0 1
10Codarea Shannon-Fano
a b c d e f
9 8 6 5 4 2
a b
9 8
e f
4 2
0 1
0 1 1
0100 101100 1111
c d
6 5
0
0 1
11
Codarea Shannon-Fano
a b c d e f
9 8 6 5 4 2
a b
9 8
0 1
0 1
0100 101100 1111
c d
6 5
0
0 1
1
e f
4 2
0 1
12
Codarea Shannon-Fano
a b c d e f
9 8 6 5 4 2
a b
9 8
0 1
0 1
0100 101100 111110
c d
6 5
0
0 1
1
e f
4 2
0 1