Podstawowe twierdzenie Shannona

Podstawowe twierdzenie Shannona dla kanałów bezszumowych^[1][2] (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 ${\displaystyle H}$ (bitów na symbol) i kanał o przepustowości ${\displaystyle 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 ${\displaystyle {\frac {C}{H}}-\varepsilon }$ dla dowolnie małego ${\displaystyle \varepsilon .}$ Ponadto nie można uzyskać średniej transmisji szybszej niż ${\displaystyle {\frac {C}{H}}}$ (symboli na sekundę).

Można je zapisać w nieco inny sposób – jeśli ${\displaystyle 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 ${\displaystyle 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

 Osobny artykuł: 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:

${\displaystyle H\leqslant L<H+1.}$

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

${\displaystyle n\cdot H\leqslant L<n\cdot H+1,}$

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

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

Efektywność kodowania

Dla kodowania podaje się efektywność, definiowaną jako iloraz ${\displaystyle {\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.

Przypisy

1. W polskiej literaturze to twierdzenie nazywane jest podstawowym tw. Shannona, pierwszym tw. Shannona, podstawowym tw. Shannona o dyskretnym kodowaniu beszumowym (A. Drozdek).
2. W modelu matematycznym zakłada się, że transmisja nie może zostać w żaden sposób zakłócona – to, co zostanie przesłane przez nadajnik, zawsze dotrze w tej samej postaci do odbiornika.

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