Podręcznik

Transmisja cyfrowa wymaga zapisu przesyłanej informacji w postaci strumienia binarnego. Strumień binarny to ciąg wartości logicznych „0” i „1”. Celowo unikam tu słowa „bit”, gdyż nie zawsze liczba przesłanych wartości logicznych jest równa liczbie bitów informacji. Zetknęliśmy się już z tym problemem w p.3.3 Moduł2. Transmitując serię sygnałów binarnych pojawiających się z niejednakowym prawdopodobieństwem (sygnał s₁(t) reprezentował wartość logiczną „1” i pojawiał się z prawdopodobieństwem P₁,  a s0(t) reprezentował wartość logiczną „0” i pojawiał się z prawdopodobieństwem P₀=1-P₁) przekonaliśmy się, że przysyłamy mniej niż 1 bit informacji na sygnał. W istocie, gdy P₁=1, P₀=0 (lub odwrotnie) nie przesyłamy żadnej informacji, gdyż z góry wiemy, że otrzymamy zawsze ten sam sygnał. Gdy oba sygnały pojawiają się z prawdopodobieństwem P₁=P₀=1/2, wówczas dopiero przesyłamy jeden bit informacji na sygnał. 
Jeśli ilość informacji zawarta w strumieniu binarnym jest mniejsza niż liczba wartości logicznych, wówczas istnieje możliwość przeprowadzenia kompresji bezstratnej, tzn. przetworzenia ciągu wartości logicznych na inny ciąg  zawierający mniej elementów. Operacja taka jest bezstratna, tzn. możemy zawsze wrócić do pierwotnego ciągu wartości logicznych. 
Jaki jest cel stosowania kompresji? Chodzi o oszczędne wykorzystanie kanału. Im mniej symboli transmisji danych transmitujemy w jednostce czasu, tym węższe pasmo częstotliwości zajmujemy i możemy podzielić się kanałem z innymi użytkownikami. Jeżeli informacja ma być zapisana w pamięci, to dzięki kompresji zużywamy mniej pamięci dla przechowania tych samych danych. 
Nie wszystkie rodzaje danych mogą być poddane bezstratnej kompresji, jedynie takie, które dadzą się zapisać jako ciąg wartości logicznych. Dane tekstowe są najlepszym przykładem. Dźwięk, nawet spróbkowany – już nie, gdyż każda próbka jest liczbą rzeczywistą, więc nie może być przedstawiona jako ciąg binarny o skończonej długości. Tym niemniej mówi się o „bezstratnych” koderach dźwięku czy obrazu. Należy to rozumieć w ten sposób, że wstępnie dokonano przetworzenia analogowo-cyfrowego (A/C), otrzymując strumień binarny o dużej liczbie elementów. To przetworzenie A/C jest operacją stratną. Następnie przetwarzamy ten strumień binarny na inny strumień, mający mniejszą liczbę elementów. To już jest operacja bezstratna. W ten sposób postępujemy kodując obraz w systemie JPEG. 
Algorytmy bezstratnej kompresji nie są w zasadzie algorytmami przetwarzania sygnałów, nie poświęcimy im więc wiele miejsca. Warto jednak poznać granicę stosowania tych algorytmów. 
Załóżmy zatem, że źródło informacji może przekazać do transmisji M różnych wiadomości (np. liter alfabetu). Te wiadomości pojawiają się z prawdopodobieństwem odpowiednio $p_1,p_2,\ldots,p_M$  (np. litera „e” pojawia się częściej niż „q”). Jeśli pojawi się  i -ta wiadomość, to ilość informacji, jaką otrzymamy, będzie odwrotnie proporcjonalna do  $p_i$ . Co więcej, będzie ona proporcjonalna do  ${log}_2{(}\frac{1}{p_i})$.  Dlaczego wykorzystano tu logarytm? Gdy otrzymamy dwie wiadomości (np. słowo złożone z dwóch liter alfabetu), to prawdopodobieństwo takiego zdarzenia jest równe iloczynowi prawdopodobieństw dla poszczególnych liter. Pozyskana w ten sposób ilość informacji jest sumą ilości informacji obu wiadomości. Przetworzenie iloczynu w sumę zapewnia funkcja logarytmiczna:  $log({\frac{1}{p_1p_2})=}log({\frac{1}{p_1})+}log({\frac{1}{p_2})}$. Podstawa logarytmu równa 2 daje wynik w bitach informacji. 

Podstawowe znaczenie ma średnia ilość informacji, zwana entropią: 

C. Shannon udowodnił, że kodując informacje dostarczane przez źródło o entropii H  trzeba przeznaczyć (średnio) co najmniej H wartości logicznych (“0” i “1”) na wiadomość. Dokładniej, średnia długość słowa kodowego nie może być mniejsza niż entropia: $L_{min{\ }}=H$. Przeznaczając mniej niż H wartości logicznych na wiadomość, nie zdekodujemy poprawnie każdej z M możliwych wiadomości. Możemy jednak konstruować kody o średniej długości słowa L dowolnie bliskiej entropii:

Jak stworzyć taki kod? Optymalny algorytm podał D.Huffman [3]. Zapoznamy się z nim na przykładzie: Mamy 8 zdarzeń, pojawiających się z różnym prawdopodobieństwem (Tabela 1). 

Tabela 1 Kod Huffmana

Stosując zwykły kod binarny, mielibyśmy 8 słów o długości 3: 000, 001, 010,…, 111. Zastosujemy jednak kod o zmiennej długości słowa. Algorytm Huffmana składa się z kolejnych kroków i  polega na łączeniu dwóch zdarzeń o najmniejszym prawdopodobieństwie. 
W pierwszym kroku łączymy zdarzenia 7,8 i dodajemy ich prawdopodobieństwa (moglibyśmy zacząć od dowolnej pary wybranej z czterech ostatnich zdarzeń). W drugim kroku łączymy 5,6. Mamy teraz 6 zdarzeń, z których 4 mają najmniejsze prawdopodobieństwa równe 0.1. Łączymy dwa z nich, a potem dwa pozostałe. Mamy teraz 4 zdarzenia o prawdopodobieństwach 0.3, 0.3, 0.2, 0.2. Łączymy 2 ostatnie, potem 2 pierwsze. Ostatnim krokiem będzie połączenie dwóch zagregowanych zdarzeń i otrzymanie prawdopodobieństwa równego 1. Najczęściej zamiast tabeli tworzy się drzewo i właśnie dotarliśmy do jego korzenia. 
Teraz wychodząc z korzenia docieramy do kolejnych “liści”, czyli pierwotnych zdarzeń. Idąc w górę wpisujemy “1” do słowa kodowego, a idąc w dół wpisujemy “0” (można postąpić odwrotnie). Tak więc pierwszemu zdarzeniu przypisujemy kod 11, a ostatniemu 0000. 
Średnią długość słowa kodowego otrzymamy, mnożąc długości słów przez prawdopodobieństwa ich pojawienia się. W naszym przypadku 
L = 0.3x2 + 0.3x2 + 0.1x3 + 0.1x3 + 4 x (0.05x4) = 2.6 bit  <  3 bit
Otrzymaliśmy zatem bardziej efektywny kod niż zwykły kod binarny o długości słów równej 3. 
Zauważmy, że kod Huffmana może być dekodowany „na bieżąco”, gdyż żadne słowo kodowe nie jest początkiem innego słowa. Taki kod nazywa się kodem prefiksowym.
Obliczając entropię analizowanego źródła informacji wg. wzoru (1), otrzymujemy 2.57 bita informacji. Kod Huffmana ma średnią długość słowa równą 2.6. Zgodnie ze wzorem (2) istnieje możliwość bardziej efektywnego kodowania. Możemy to osiągnąć, kodując pary następujących po sobie zdarzeń. Dla 8 zdarzeń takich par będzie 64. 

Rozpatrzmy jednak prostszy przykład. Mamy 2 zdarzenia: E1 o prawdopodobieństwie p₁ = 0.1 i E2 o prawdopodobieństwie p₂ = 0.9. Entropia wynosi H = 0.469, ale kodując pojedyncze zdarzenia nie mamy wyboru: jednemu przypisujemy kod “1” a drugiemu “0”.  Długość kodu wynosi  L = 1. 
Kodując 4 pary zdarzeń i stosując algorytm Huffmana mamy:

Średnia długość słowa wynosi 0.01x3 + 0.09x3 + 0.09x2 + 0.81x1 = 1.29   na parę zdarzeń, a więc  0.645 wartości logicznych na zdarzenie. 
Kodując trójki sąsiednich zdarzeń, możemy jeszcze bardziej zbliżyć się do entropii. Takie postępowanie nazywa się rozszerzaniem źródła informacji. 
Istnieje wiele efektywnych algorytmów kompresji bezstratnej, zainteresowanych odsyłam do [3].