Podstawowe twierdzenie Shannona

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do 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 (bitów na symbol) i kanał o przepustowości (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 dla dowolnie małego Ponadto nie można uzyskać średniej transmisji szybszej niż (symboli na sekundę).

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

 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:

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

Przy zwiększaniu średnia długość kodów coraz bardziej zbliża się do minimum.

Efektywność kodowania[edytuj | edytuj kod]

Dla kodowania podaje się efektywność, definiowaną jako iloraz – 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:

Przypisy[edytuj | edytuj kod]

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

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