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

Można je zapisać w nieco inny sposób – jeśli L {\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 H ⩽ L . {\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:

H ⩽ L < H + 1. {\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 n {\displaystyle n} kolejnych symboli – na mocy własności entropii układ nierówności przyjmuje postać:

n ⋅ H ⩽ L < n ⋅ H + 1 , {\displaystyle n\cdot H\leqslant L<n\cdot H+1,}
H ⩽ L n < H + 1 n . {\displaystyle H\leqslant {\frac {L}{n}}<H+{\frac {1}{n}}.}

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

Efektywność kodowania

Dla kodowania podaje się efektywność, definiowaną jako iloraz H L ⋅ 100 % {\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).