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 \}.$

Prawdopodobieństwa (a wraz z nimi symbole) są sortowane w porządku nierosnącym, tj. $p_{i}\geqslant p_{i+1}.$
Następnie dla tak uporządkowanych danych oblicza się niepełne prawdopodobieństwo kumulatywne: $P(x_{i})=p_{1}+p_{2}+\ldots +p_{i-1}$ – jest to suma prawdopodobieństw elementów od 1 do i-1.
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{,}{\color {blue}00}000_{2}$
$P_{2(b)}=0{,}{\color {blue}01}110_{2}$
$P_{3(c)}=0{,}{\color {blue}110}00_{2}$
$P_{4(d)}=0{,}{\color {blue}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\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 ${\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] .