Podstawowe twierdzenie Shannona

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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 (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[edytuj | edytuj kod]

Information icon.svg 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 \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[edytuj | edytuj kod]

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:

Bibliografia[edytuj | edytuj kod]

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

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.