Kodowanie Shannona

Kodowanie Shannona – metoda kompresji bezstratnej, którą Claude E. Shannon przedstawił jako jeden z dowodów swojego podstawowego twierdzenia o kodowaniu.

Kodowanie Shannona nie tworzy optymalnych kodów, nieco lepsze wyniki daje modyfikacja znana jako kodowanie Shannona-Fano, zaś optymalny kod wyznacza kodowanie Huffmana.

Kodowanie Shannona

Dane jest źródło $S=\{x_1,x_2,\dots \}$ i stowarzyszone z nimi prawdopodobieństwa $p=\{p_1,p_2,\dots \}.$

1. Prawdopodobieństwa (a wraz z nimi symbole) są sortowane w porządku nierosnącym, tj. $p_i⩾p_{i+1}.$
2. Następnie dla tak uporządkowanych danych oblicza się niepełne prawdopodobieństwo kumulatywne: $P(x_i)=p_1+p_2+\dots +p_{i-1}$ – jest to suma prawdopodobieństw elementów od 1 do i-1.
3. Kodowanie Shannona polega na wzięciu $\lceil -{\log }_2{p}_i\rceil$ (długość Shannona) pierwszych bitów binarnego rozwinięcia liczby $P_i$ (brane są bity po przecinku).

Średnia długość kodów mieści się w przedziale $[H(S),H(S)+1),$ gdzie $H(S)$ to entropia źródła (średnia liczba bitów na symbol).

Przykład

Niech $S=\{a,b,c,d\},$ $p=\{0,45;0,3;0,2;0,05\}$ (entropia $H(S)=1,72$); prawdopodobieństwa są już podane nierosnąco.

Długości Shannona (długości kodów w bitach):

• $l_a=\lceil -{\log }_{2}0,45\rceil =2$
• $l_b=\lceil -{\log }_{2}0,30\rceil =2$
• $l_c=\lceil -{\log }_{2}0,20\rceil =3$
• $l_d=\lceil -{\log }_{2}0,05\rceil =5$

Prawdopodobieństwa kumulatywne:

• $P_{1(a)}=0$
• $P_{2(b)}=p_1=0,45$
• $P_{3(c)}=p_1+p_2=0,45+0,3=0,75$
• $P_{4(d)}=p_1+p_2+p_3=0,45+0,3+0,2=0,95$

I ich rozwinięcia binarne (wzięte 5 pierwszych bitów po przecinku, zaznaczono słowa kodowe):

• $P_{1(a)}=0,00000_2$
• $P_{2(b)}=0,01110_2$
• $P_{3(c)}=0,11000_2$
• $P_{4(d)}=0,{11110}_2$

Ostatecznie kody mają postać:

• $kod(a)=00_2$
• $kod(b)=01_2$
• $kod(c)=110_2$
• $kod(d)=11110_2$

Średnia długość kodu $L_k=2\cdot 0,45+2\cdot 0,3+3\cdot 0,2+5\cdot 0,05=2,35$ $(k=1).$ Po podstawieniu do nierówności podanej w twierdzeniu (średnia długość kodów): $1,72⩽2,35<1,72+1$ stwierdzamy, że otrzymany kod rzeczywiście ją spełnia.

Jednak, jak wspomniano, efektywność kodowania Shannona nie jest duża – dla danych z powyższego przykładu wynosi $\frac{H(S)}{L_k}\cdot 100\mathrm{\%}=73,2\mathrm{\%}.$

Zobacz też

• kodowanie arytmetyczne

Bibliografia

• Claude E. Shannon, A Mathematical Theory of Communication, reprint z poprawkami z „Bell System Technical Journal”, vol. 27, s. 379–423, 623–656, lipiec, październik 1948

Linki zewnętrzne

• Szablon:Cytuj