Kodowanie Shannona

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Kodowanie Shannona – metoda kompresji bezstratnej, którą Claude E. Shannon przedstawił jako jeden z dowodów swojego podstawowego twierdzenia o kodowaniu.

Kodowanie Shannona nie tworzy optymalnych kodów, nieco lepsze wyniki daje modyfikacja znana jako kodowanie Shannona-Fano, zaś optymalny kod wyznacza kodowanie Huffmana.

Kodowanie Shannona[edytuj | edytuj kod]

Dane jest źródło i stowarzyszone z nimi prawdopodobieństwa

  1. Prawdopodobieństwa (a wraz z nimi symbole) są sortowane w porządku nierosnącym, tj.
  2. Następnie dla tak uporządkowanych danych oblicza się niepełne prawdopodobieństwo kumulatywne: – jest to suma prawdopodobieństw elementów od 1 do i-1.
  3. Kodowanie Shannona polega na wzięciu (długość Shannona) pierwszych bitów binarnego rozwinięcia liczby (brane są bity po przecinku).

Średnia długość kodów mieści się w przedziale gdzie to entropia źródła (średnia liczba bitów na symbol).

Przykład[edytuj | edytuj kod]

Niech (entropia ); prawdopodobieństwa są już podane nierosnąco.

Długości Shannona (długości kodów w bitach):

Prawdopodobieństwa kumulatywne:

I ich rozwinięcia binarne (wzięte 5 pierwszych bitów po przecinku, zaznaczono słowa kodowe):

Ostatecznie kody mają postać:

Średnia długość kodu Po podstawieniu do nierówności podanej w twierdzeniu: stwierdzamy, że otrzymany kod rzeczywiście ją spełnia.

Jednak, jak wspomniano, efektywność kodowania Shannona nie jest duża – dla danych z powyższego przykładu wynosi

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]