Podstawowe twierdzenie Shannona

Podstawowe twierdzenie Shannona dla kanałów bezszumowych (ang. the fundamental theorem for a noiseless channel) – twierdzenie sformułowane przez Claude'a E. Shannona w 1948 roku, a dotyczy ograniczenia na minimalną średnią długość słów kodowych w kodowaniu utworzonym do zapisu symboli generowanych przez pewne dyskretne źródło danych o określonej entropii (średniej liczbie bitów na symbol).

Przez dyskretne źródło danych rozumie się tutaj źródło danych opisywane przez dyskretną zmienną losową, tzn. na wyjściu z określonym prawdopodobieństwem pojawiają się symbole z pewnego skończonego alfabetu.

Twierdzenie Shannona brzmi:

Dane jest źródło o entropii $H$ (bitów na symbol) i kanał o przepustowości $C$ (bitów na sekundę). Możliwe jest znalezienie takiego kodu, przypisującego transmitowanym symbolom różne ciągi bitowe, żeby prędkość transmisji wynosiła $\frac{C}{H} - \epsilon$ dla dowolnie małego $\epsilon$. Ponadto nie można uzyskać średniej transmisji szybszej niż $\frac{C}{H}$ (symboli na sekundę).

Można je zapisać w nieco inny sposób – jeśli $L$ będzie oznaczało średnią długością słów kodowych (wartością oczekiwaną), wówczas twierdzenie Shannona nakłada na tę wartość dolne ograniczenie $H \leqslant L$. Innymi słowy nie można utworzyć jednoznacznie dekodowalnego kodu, który charakteryzowałoby się krótszą niż entropia źródła średnią długością słów kodowych.

Kodowanie Shannona

Shannon w dowodzie swojego twierdzenia pokazał, jak utworzyć kodowanie, które ma dodatkową zaletę – średnia długość kodu może być co najwyżej o jeden bit dłuższa od entropii:

$H \leqslant L < H + 1$

Co więcej, jeśli rozważy się nie pojedyncze symbole, ale metasymbole – ciągi złożone z $n$ kolejnych symboli – na mocy własności entropii układ nierówności przyjmuje postać:

$n \cdot H \leqslant L < n \cdot H + 1$

$H \leqslant \frac{L}{n} < H + \frac{1}{n}$

Przy zwiększaniu $n$ średnia długość kodów $\frac{L}{n}$ coraz bardziej zbliża się do minimum.

Efektywność kodowania

Dla kodowania podaje się efektywność, definiowaną jako iloraz $\frac{H}{L} \cdot 100\%$ – najlepsze kodowanie charakteryzuje się efektywnością 100%. Efektywność kodowania Shannona nie jest największa, poniższe metody tworzenia słów kodowych dają lepsze wyniki:

• kodowanie Shannona-Fano – opracowane przez Roberta M. Fano;
• kodowanie Huffmana – opracowane przez Davida Huffmana;
• kodowanie arytmetyczne

Bibliografia

• Claude E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, str. 379-423, 623-656, lipiec, październik, 1948 (str. 16 w podlinkowanym dokumencie PDF)