Źródło → Kanał: Dwustopniowe Kodowanie
Rozdział 10 Hamminga zaczyna się od modelu komunikacji Shannon'a, który odnosi się do każdego systemu przekazywania informacji: rozmowy telefoniczne, radio, dyski twarde, replikacja DNA, pamięć komputera.
Architektura dwustopniowa
Etap 1: Kodowanie źródła (kompresja). Przekształcając wiadomość źródłową w kompaktową reprezentację. Cel: usunięcie nadmiarowości naturalnej dla źródła. Kod Morse'a to przykład: częste litery otrzymują krótkie oznaczenia, rzadkie litery długie.
Etap 2: Kodowanie kanału (ochrona przed błędami). Dodawanie kontrolowanej nadmiarowości dostosowanej do cech charakterystycznych szumu kanału. Linia telefoniczna szumowa potrzebuje więcej nadmiarowości niż kabiel kablownia światłowodowa. Dwa etapy oddzielają się: optymalizuj każdy niezależnie dla własnej zadania.
Powszechny interfejs między dwoma etapami - standardowy strumień bitów - oznacza, że każde źródło może być połączone z każdym kanałem. Ta modułowość jest kluczowym odkryciem architektonicznym Shannon'a.
Przechowywanie 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. Zestawka do odtwarzania jest kanałem szumowym w czasie.
Rola szumu
Model Shannon'a zakłada radykalnie, że szum jest nieunikniony. Każdy kanał, każde medium magazynowania, każdy obwód przełączający wprowadza pewien procent błędów. Pytanie nie brzmi: "Jak eliminować szum?" ale "Jak odzyskać pierwotną wiadomość pomimo szumu?"
To kontrastuje z klasyczną fizyką, gdzie szum pojawia się jako przemyślenie drugie (względność). Shannon traktuje szum jako warunek podstawowy - wszelka teoria rozwija się na jego bazie.
Na razie, rozdział 10 koncentruje się na przypadku niemrawym: kodowanie źródła bez błędów. Problem korekty błędów (kodowanie kanału) czeka na późniejsze rozdziały.
Kiedy możesz jednoznacznie zdekodować?
Aby kod zmiennej długości był użyteczny, odbiornik musi jednoznacznie zdekodować strumień bitów. Hamming ilustruje to przy 4-symbolowym kodzie, który nie spełnia tego testu, a następnie wprowadza poprawkę: kody przednikowe.
Warunek przednikowy
Kod jest przednikowy (lub natychmiastowy) jeśli żaden słowa kodowego nie jest prefiksem innego słowa kodowego. Otrzymując strumień bitów, wiesz, że symbol zakończył się, gdy osiągniesz liść w drzewie dekodowania - nie wymaga się patrzenia w przód.
Przykładowy kod przednikowy dla {s1, s2, s3, s4}: s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Sprawdź: 0 nie jest prefiksem 10, 110 lub 111. 10 nie jest prefiksem 110 lub 111 (10 z kolejnymi bitami daje 100... lub 101..., żadne z nich nie zaczyna się od 110 lub 111). Kod spełnia warunek.
Procedura dekodowania: śledź drzewo, rozgałększ się na każdym przychodzącym bit, wydaj symbol, gdy dosięgniesz liścia, wróć do korzenia.
Nierówność Krafta
Dla dowolnej przednikowej binarnej kody z długościami kodów l_1, l_2, ..., l_n:
Σ 2^(−l_i) ≤ 1
Równość obowiązuje dla kompletnej kody (liście pokrywają całe drzewo binarne bez przeszkód). To warunek konieczny: żadna przednikowa kod nie może go naruszyć. Z drugiej strony, dla dowolnej grupy długości spełniającej nierówność Krafta, istnieje przednikowa kod.
Zastosowanie nierówności Krafta
Sprawdź Kraft dla podanych długości kodów: Σ 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 w kodzie zmienną długości: L = Σ p_i · l_i, gdzie p_i to prawdopodobieństwo symbolu s_i oraz l_i to jego długość kodu.
Jak krótki może być L? Odpowiedź Shannon'a: nie niższy niż entropia ź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ą prawie równie prawdopodobne (maksymalne nieprzewidywalność). Niska entropia oznacza, że niektóre symbole dominują (wysoka przewidywalność, większa kompresja).
Twierdzenie Kodowania Bezszumowego
Dla każdego kodu przedrostkowego: H(źródło) ≤ L ≤ H(źródło) + 1.
Nie można pokonać entropii. Kodowanie Huffman'a (następne rozdział) osiąga górny limit: L < H + 1. Dla kodów blokowych nad n symboli, granica sięścięża: H ≤ L/n < H + 1/n.
Entropia jest również limitem kompresji teoretycznej: nie można skompresować źródła poniżej H bitów na symbol bez straty 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
I Huffman kod {0, 10, 110, 111} osiąga L = 1,75 = H dokładnie.
Dlaczego Entropia Jest Dolną Granicą
Niższa granica niestrosującego twierdzenia kodowania nie jest tylko formułą - odbija coś głębokiego o informacji: nie można skompresować tego, co już jest maksymalnie nieprzewidywalne.
Gdy wszyscy symbole są równie prawdopodobni (jednorodne rozkład), entropia H = log₂(n) dla n symboli. Kod blokowy o długości log₂(n) bitów osiąga dokładnie H. Nie ma kodu, któryby mógł lepiej.
Gdy jeden symbol dominuje (np. p(A) = 0,99, p(B) = 0,01), H jest mały - bliski 0. Kod zmiennych długości może przypisać A bardzo krótki kod, efektywnie kodując strumień.
Praktyczne wnioski: duże zyski kompresji istnieją tylko wtedy, gdy prawdopodobieństwa symboli się znacznie różnią. Jeśli źródło jest już 'jednorodne' (losowe), kodowanie Huffman'a nie uzyskuje niczego.