Kodowanie Shannona

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Kodowanie Shannona, to metoda kodowania źródłowego, którą Claude E. Shannon przedstawił jako jeden z dowodów swojego twierdzenia o dyskretnym kodowaniu w kanałach bezszumowych, które brzmi:

Dla źródła sygnału

S

można znaleźć takie kody prefiksowe dla słów złożonych z

k

symboli źródłowych, żeby zachodziło:

$H(S) \le \frac{L_k}{k} < H(S) + \frac{1}{k}$

gdzie

H (S)

to entropia źródła, a

L k

- średnia długość kodów.

Kodowanie Shannona nie tworzy optymalnych kodów; nieco lepsze wyniki daje modyfikacja znana jako kodowanie Shannona-Fano. Znacznie lepszą efektywnością charakteryzują się kodowanie Huffmana oraz kodowanie arytmetyczne.

[edytuj] Kodowanie Shannona

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

Prawdopodobieństwa (a wraz z nimi symbole) są sortowane w porządku niemalejącym, tj. $p_i \ge p_{i+1}$ .
Następnie dla tak uporządkowanych danych oblicza się niepełne prawdopodobieństwo komulatywne: $P(x_i) = p_1 + p_2 + \ldots + p_{i-1}$ - jest to suma wszystkich prawdopodobieństw od 1. do i-1 elementu.
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).

[edytuj] 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 niemalejąco.

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):

$P 1(a) = 0.00000 2$
$P 2(b) = 0.01110 2$
$P 3(c) = 0.11000 2$
$P 4(d) = 0.11110 2$

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$

Ostatecznie kody mają postać:

$k o d (a) = 00 2$
$k o d (b) = 01 2$
$k o d (c) = 110 2$
$k o d (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: $1.72 \le 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 tego przykładu wynosi $\frac{H(S)}{L_k} \cdot 100\% = 73.2\%$ .

[edytuj] Kodowanie Shannona-Fano

Robert Fano zaproponował algorytm, który daje trochę lepsze wyniki kodowania - kody mogą być krótsze o 1 bit niż kody tworzony metodą Shannona, także rozkład bitów może się różnić.

Kodowanie Shannona-Fano przedstawia się następująco:

s - ciąg symboli ze zbioru $S$ posortowanych wg prawdopodobieństw $p i$
Shanon-Fano(s):
- Jeśli s zawiera dwa symbole do słowa kodu pierwszej litery dodaj 1, do słowa kodu drugiej litery - 0.
- W przeciwnym razie jeśli s zawiera więcej niż dwa symbole, podziel go na dwa podciągi s1 i s2 tak, żeby różnica między sumą prawdopodobieństw liter z s1 i s2 była najmniejsza. Do słów kodu symboli z s1 dodaj 1, do kodów symboli z s2 - 0. Wywołaj rekurencyjnie funkcje: Shannon-Fano(s1) oraz Shannon-Fano(s2).

[edytuj] Przykład

Niech $S = {a, b, c, d}$ , $p = {0.45,0.3,0.2,0.05}$ .

Początkowo ciąg $s = a b c d$ (porządek według malejącego prawdopodobieństwa).

Składa się z więcej niż 2 liter, zatem trzeba go podzielić. Możliwe są następujące sytuacje: 1) $s 1 = a$ , $s 2 = b$ (różnica prawdopodobieństw 0.1), 2) $s 1 = a b$ , $s 2 = c d$ (różnica prawdopodobieństw 0.5) oraz 3) $s 1 = a b c$ , $s 2 = d$ (różnica prawdopodobieństw 0.9) - wybierany jest ta para, dla której różnica prawdopodobieństw jest najmniejsza, a więc pierwszą parę. Do słów kodu liter z $s 1 = a$ dopisywane są 0, do słów kodu liter z $s 2 = b c d$ - 1:

a = 0
b = 1
c = 1
d = 1

Teraz wywoływana jest funkcja Shannon-Fano( $s 1$ ) - ten ciąg ma długość 1 i nie jest już dalej przetwarzany. Następnie wykonywane jest Shannon-Fano( $s 2$ ) - $s 2$ jest dłuższy niż 2 i musi zostać podzielony.

Sytuacja jest podobna jak w poprzednim kroku, bo $s 12 = b$ i $s 22 = c d$ . Do słów kodu liter z $s 12 = b$ dopisywane są 0, do słów kodu liter z $s 22 = c d$ - 1:

a = 0
b = 10
c = 11
d = 11

Wywoływana jest funkcja Shannon-Fano( $s 12$ ) - ten ciąg ma długość 1, nie jest już dalej przetwarzany. Następnie wykonywane jest Shannon-Fano( $s 22$ ) - $s 22$ ma długość 2, więc tutaj kodowanie kończy się - do słowa kodu pierwszego symbolu ( $c$ ) dopisywane jest 0, a do słowa kodu drugiego kodu ( $d$ ) - 1:

a = 0
b = 10
c = 110
d = 111

Średnia długość kodu $L_k = 1 \cdot 0.45 + 2 \cdot 03 + 3 \cdot 0.1 + 3 \cdot 0.05 = 1.8$ . W tym przypadku efektywność kodowania wynosi $\frac{H(S)}{L_k} \cdot 100\% = \frac{1.72}{1.80} \cdot 100\% = 95\%$ , jest więc znacznie lepsza niż kodowania Shannona.