Źródło → Kanał: Kodowanie dwustopniowe
Rozdział 10 Hamminga otwiera się modelem komunikacji Shannon'a, który ma zastosowanie w każdym systemie przesyłającym informacje: rozmowy telefoniczne, radio, dyski twarde, replikacja DNA, pamięć komputerowa.
Architektura dwustopniowa
Etap 1: Kodowanie źródła (kompresja). Przekonwertuj wiadomość źródłową na zwartą reprezentację. Cel: usuń nadmiarowość naturalną dla źródła. Kod Morse'a robi to: częste litery otrzymują krótkie kody, rzadkie litery otrzymują długie.
Etap 2: Kodowanie kanału (ochrona przed błędami). Dodaj kontrolowaną nadmiarowość dostosowaną do charakterystyk szumu kanału. Hałaśliwa linia telefoniczna wymaga więcej nadmiarowości niż światłowód. Dwa etapy się rozdzielają: zoptymalizuj każdy niezależnie dla jego własnego zadania.
Wspólny interfejs między dwoma etapami — standaryzowany strumień bitów — oznacza, że każde źródło może łączyć się z każdym kanałem. Ta modularność to kluczowy wgląd architektoniczny Shannon'a.
Pamięć jako komunikacja. Hamming zauważa, że wysyłanie wiadomości przez przestrzeń (transmisja) i wysyłanie jej przez czas (przechowywanie) używa tego samego modelu. Dysk kopii zapasowej to szumny kanał w czasie.
Rola szumu
Model Shannon'a wysuwia radykalne założenie: szum jest nieunikniony. Każdy kanał, każdy nośnik pamięci, każdy obwód przełączający wprowadza pewne prawdopodobieństwo błędu. Pytanie nie brzmi 'jak wyeliminować szum?' ale 'jak odzyskać oryginalną wiadomość pomimo szumu?'
To kontrastuje z fizyką klasyczną, gdzie szum pojawia się jako uzupełnienie (zasada nieoznaczoności). Shannon traktuje szum jako warunek fundamentalny — cała teoria opiera się na nim.
Na razie rozdział 10 skupia się na przypadku bez szumów: kodowanie źródła bez błędów. Problem kodowania kanału (korekta błędów) czeka na później rozdziały.
Kiedy możesz dekodować jednoznacznie?
Aby kod o zmiennej długości był przydatny, odbiornik musi jednoznacznie dekodować strumień bitów. Hamming ilustruje to kodem czterech symboli, który nie przechodzi tego testu, a następnie wprowadza rozwiązanie: kody wolne od prefiksów.
Warunek wolności od prefiksów
Kod jest wolny od prefiksów (lub natychmiastowy), jeśli żaden słowo kodowe nie jest prefiksem żadnego innego słowa kodowego. Po otrzymaniu strumienia bitów, wiesz, że symbol się skończył w momencie, gdy dotrzesz do liścia w drzewie dekodowania — nie potrzebna jest lookahead.
Przykład kodu wolnego od prefiksów dla {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Weryfikacja: 0 nie jest prefiksem 10, 110 ani 111. 10 nie jest prefiksem 110 ani 111 (10 po większej liczbie bitów daje 100... lub 101..., ani jedno ani drugie nie zaczyna się od 110 ani 111). Kod kwalifikuje się.
Procedura dekodowania: podążaj za drzewem, rozgałęź się na każdym wchodzącym bicie, wyślij symbol po dotarciu do liścia, wróć do korzenia.
Nierówność Krafta
Dla każdego kodu binarnego wolnego od prefiksów o długościach słów kodowych l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
Równość zachodzi gdy kod jest kompletny (liście wypełniają całe drzewo binarne bez przerw). To jest warunek konieczny: żaden kod wolny od prefiksów go nie naruszy. Odwrotnie, dla każdego zestawu długości spełniającego nierówność Krafta, istnieje kod wolny od prefiksów.
Zastosowanie nierówności Krafta
Mając długości słów kodowych, weryfikuj Krafta: Σ 2^(−l_i) ≤ 1.
Dla {s1=0, s2=10, s3=110, s4=111}: długości to 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
Entropia Shannon'a
Średnia długość kodu zmienno-długościowego: L = Σ p_i · l_i, gdzie p_i to prawdopodobieństwo symbolu s_i, a l_i to długość jego słowa kodowego.
Jak krótko może być L? Odpowiedź Shannon'a: nie poniżej entropii źródła.
Entropia Shannon'a: H = −Σ p_i · log₂(p_i) (jednostki: bity/symbol)
Entropia mierzy średnią informację na symbol. Wysoka entropia oznacza, że symbole są mniej więcej równie prawdopodobne (maksymalna nieprzewidywalność). Niska entropia oznacza, że niektóre symbole dominują (wysoka przewidywalność, bardziej kompresowalne).
Twierdzenie o kodowaniu bez szumów
Dla każdego kodu wolnego od prefiksów, H(źródło) ≤ L ≤ H(źródło) + 1.
Żaden kod nie może pokonać entropii. Kodowanie Huffmana (następny rozdział) osiąga górną granicę: L < H + 1. Dla kodów blokowych dla n symboli, granica się zacieśnia: H ≤ L/n < H + 1/n.
Entropia to też teoretyczna granica kompresji: nie możesz skompresować źródła poniżej H bitów na symbol bez utraty informacji.
Obliczanie entropii
Przykład: 4 symbole z prawdopodobieństwami p = [1/2, 1/4, 1/8, 1/8].
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bitów/symbol
A kod Huffmana {0, 10, 110, 111} osiąga L = 1.75 = H dokładnie.
Dlaczego entropia jest dolnym ograniczeniem
Dolne ograniczenie twierdzenia o kodowaniu bez szumów nie jest tylko formułą — odzwierciedla coś głębokie o informacji: nie możesz skompresować to, co jest już maksymalnie nieprzewidywalne.
Gdy wszystkie symbole są równie prawdopodobne (rozkład jednostajny), entropia H = log₂(n) dla n symboli. Kod blokowy długości log₂(n) bitów osiąga dokładnie H. Żaden kod nie może zrobić lepiej.
Gdy jeden symbol dominuje (powiedzmy, p(A) = 0.99, p(B) = 0.01), H jest małe — blisko 0. Kod zmienno-długościowy może przypisać A bardzo krótki kod, kodując strumień bardzo wydajnie.
Praktyczne wnioski: duże zyski kompresji istnieją tylko gdy prawdopodobieństwa symboli znacznie się różnią. Jeśli źródło jest już 'jednostajne' (losowo wyglądające), kodowanie Huffmana nic nie zyska.