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 ${\displaystyle S=\{x_{1},x_{2},\dots \}}$ i stowarzyszone z nimi prawdopodobieństwa ${\displaystyle p=\{p_{1},p_{2},\dots \}.}$

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

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

Przykład

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

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

• ${\displaystyle l_{a}=\lceil -\log _{2}{0{,}45}\rceil =2}$
• ${\displaystyle l_{b}=\lceil -\log _{2}{0{,}30}\rceil =2}$
• ${\displaystyle l_{c}=\lceil -\log _{2}{0{,}20}\rceil =3}$
• ${\displaystyle l_{d}=\lceil -\log _{2}{0{,}05}\rceil =5}$

Prawdopodobieństwa kumulatywne:

• ${\displaystyle P_{1(a)}=0}$
• ${\displaystyle P_{2(b)}=p_{1}=0{,}45}$
• ${\displaystyle P_{3(c)}=p_{1}+p_{2}=0{,}45+0{,}3=0{,}75}$
• ${\displaystyle 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):

• ${\displaystyle P_{1(a)}=0{,}{\color {blue}00}000_{2}}$
• ${\displaystyle P_{2(b)}=0{,}{\color {blue}01}110_{2}}$
• ${\displaystyle P_{3(c)}=0{,}{\color {blue}110}00_{2}}$
• ${\displaystyle P_{4(d)}=0{,}{\color {blue}11110}_{2}}$

Ostatecznie kody mają postać:

• ${\displaystyle kod(a)=00_{2}}$
• ${\displaystyle kod(b)=01_{2}}$
• ${\displaystyle kod(c)=110_{2}}$
• ${\displaystyle kod(d)=11110_{2}}$

Średnia długość kodu ${\displaystyle L_{k}=2\cdot 0{,}45+2\cdot 0{,}3+3\cdot 0{,}2+5\cdot 0{,}05=2{,}35}$ ${\displaystyle (k=1).}$ Po podstawieniu do nierówności podanej w twierdzeniu (średnia długość kodów): ${\displaystyle 1{,}72\leqslant 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 ${\displaystyle {\frac {H(S)}{L_{k}}}\cdot 100\%=73{,}2\%.}$

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

• MaurycyM. Gast MaurycyM., Kompresja danych - Przeczytaj - Kodowanie Shannona [online], Zintegrowana Platforma Edukacyjna [dostęp 2023-06-22] .