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

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

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 (średnia długość kodów):   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

Bibliografia

edytuj

Linki zewnętrzne

edytuj