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}}-\varepsilon$ dla dowolnie małego $\varepsilon .$ 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, natomiast 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, s. 379–423, 623–656, lipiec, październik, 1948 (s. 16 w podlinkowanym dokumencie PDF).