Co Shannon Nazwał Informacją
Shannon zdefiniował informację poprzez mierzenie zaskoczenia. Wiadomość z prawdopodobieństwem p nosi:
I = −log₂(p) bitów
Pewne zdarzenie (p = 1) nosi 0 bitów — brak zaskoczenia, brak informacji. Rzadkie zdarzenie (p = 1/1024) nosi 10 bitów.
Hamming natychmiast zwraca uwagę na problem: to jest formuła do mierzenia wielkości, nie definicja pojęcia. Mierzy zaskoczenie podobne do maszynowego, nie ludzkie znaczenie. Student, który już zna odpowiedź na pytanie, otrzymuje 0 bitów z odpowiedzi — niezależnie od tego, jak ważna jest odpowiedź dla innych.
Formuła dobrze sprawdza się w systemach telefonicznych, radiu, komputerach. Słabo sprawdza się w komunikacji ludzkiej, biologii lub znaczeniu. Ulubiona nazwa Hamminga: 'Teoria Komunikacji', a nie 'Teoria Informacji.'
Entropia
Dla alfabetu q symboli z prawdopodobieństwami p₁, p₂, ..., p_q, średnia informacja na symbol to entropia:
H = −Σᵢ pᵢ log₂(pᵢ)
H osiąga maksimum, gdy wszystkie prawdopodobieństwa są równe: H_max = log₂(q) bitów. Każdy rozkład nierównomierny ma mniejszą entropię.
Obliczanie Entropii
Entropia binarna: źródło z dwoma symbolami, P(0) = p, P(1) = 1−p.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H(p) = 0 dla p = 0 lub p = 1 (całkowicie przewidywalne). H(p) = 1 bit dla p = 0.5 (całkowicie nieprzewidywalne).
Nierówność Gibbsa a Kodowanie Bezszumowe
Nierówność Gibbsa: dla dowolnych dwóch rozkładów prawdopodobieństwa p = {pᵢ} i q = {qᵢ}:
−Σ pᵢ log₂(pᵢ) ≤ −Σ pᵢ log₂(qᵢ)
z równością tylko gdy p = q. To opiera się na podstawowym fakcie, że ln(x) ≤ x − 1 dla wszystkich x > 0, z równością przy x = 1.
Konsekwencja: entropia H(p) jest maksymalna, gdy wszystkie symbole są równoprawdopodobne. Dla q symboli: H_max = log₂(q).
Twierdzenie o kodowaniu bezszumowym: dla kodu jednoznacznie dekodowalnego nierówność Krafta wymaga Σ 2^(−lᵢ) ≤ 1, gdzie lᵢ to długość kodu symbolu i. Przez nierówność Gibbsa średnia długość kodu L = Σ pᵢ lᵢ spełnia:
L ≥ H(p) = −Σ pᵢ log₂(pᵢ)
Nie możesz zrobić lepiej niż entropia średnio. Kodowanie Huffmana osiąga L < H + 1.
Pojemność Kanału
Kanał binarny symetryczny (BSC) odwraca każdy bit niezależnie z prawdopodobieństwem błędu Q = 1 − P. Pojemność kanału — maksymalny niezawodny transfer informacji — to:
C = 1 + P log₂(P) + Q log₂(Q) = 1 − H(Q)
gdzie H(Q) = −Q log₂(Q) − (1−Q) log₂(1−Q) to entropia binarna wskaźnika błędów.
Przy Q = 0 (bez błędów): C = 1 bit/transmisja (kanał doskonały). Przy Q = 0,5 (losowe odwracanie): C = 0 (kanał nie nosi informacji). Przy Q = 1 (wszystkie bity się odwracają): C = 1 (dokładnie wiesz co nadawca wysłał, wystarczy odwrócić wszystko z powrotem).
C mierzy maksymalny transfer R, przy którym możesz przesyłać z dowolnie małym prawdopodobieństwem błędu. Jeśli R < C, takie kody istnieją. Jeśli R > C, nie istnieją — żaden kod nie może pokonać pojemności.
Obliczanie Pojemności Kanału
Z P = 0,9 (wskaźnik błędu 10%, Q = 0,1):
C = 1 + 0,9 log₂(0,9) + 0,1 log₂(0,1)
log₂(0,9) ≈ −0,152, log₂(0,1) ≈ −3,322
C ≈ 1 + 0,9×(−0,152) + 0,1×(−3,322) = 1 − 0,137 − 0,332 ≈ 0,531 bitów/transmisja
Co Twierdzenie Dowodzi
Fundamentalne twierdzenie Shannona: dla dowolnego transfer R < C istnieją kody długości bloku n (z n → ∞) osiągające prawdopodobieństwo błędu P_E → 0.
Dowód używa zaskakującego argumentu: kody losowe. Zamiast konstruować konkretny kod, Shannon uśrednił po wszystkich możliwych losowych kodach (kodowanie rzutem monety). Pokazał, że średni błąd po wszystkich kodach jest mały. Jeśli średnia jest mała, co najmniej jeden kod osiąga mały błąd.
Analiza oparta na sferach: nadawca wybiera wiadomość aᵢ → sfera promienia n(Q + ε₂) wokół aᵢ w n-wymiarowej przestrzeni binarnej. Dla dużych n, odbierana słowa bⱼ leży wewnątrz tej sfery z dużym prawdopodobieństwem. Odbiornik dekoduje do słowa kodowego, którego sfera zawiera bⱼ.
Cztery przypadki decydują o prawdopodobieństwie błędu P_E:
``
aᵢ w sferze inny aⱼ w sferze wynik
tak nie poprawnie (bez błędu)
tak tak wieloznaczne → błąd
nie tak złe odkodowanie → błąd
nie nie poza wszystkimi sferami → błąd
``
Ograniczenie na P_E wychodzi na: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) dla odpowiednio wybranych d i ε₂. Wybierając ε₂ tak aby H(Q+ε₂) < C czyni wykładnik ujemny. Dla dużych n, drugi składnik → 0.
Egzystencjalny Charakter Twierdzenia
Hamming był precyzyjny o tym, co twierdzenie robi i nie robi.
Co dowodzi: niezawodna komunikacja przy transfer R < C jest możliwa, w zasadzie, dla wystarczająco dużych n.
Co nie dostarcza: jawnej konstrukcji kodu. Kod losowy długości n wystarczająco dużych, aby zbliżyć się do pojemności, ma książkę kodową o rozmiarze M × n bitów, gdzie M i n są astronomicznie duże. Nie możesz jej przechowywać ani liczyć na niej.
Kody korekcji błędów vs. Shannon: kody korekcji błędów (Hamming, Reed-Solomon, turbo, LDPC) dostarczają jawne, obliczalne konstrukcje. Poświęcają pewną odległość od pojemności w zamian za praktyczne kodery & dekodery. Gdy n rośnie i więcej błędów jest korygowanych na blok, praktyczne kody mogą zbliżyć się do pojemności bliskim.
Przykład satelitów kosmicznych: Voyager i Pioneer używały potężnych kodów korekcji błędów do komunikacji przez miliardy mil na 5–20 watów mocy. Długie długości bloków pozwoliły korygować więcej błędów na blok, zbliżając się do pojemności mimo ogromnego szumu z odległości.
Ocena Krytyczna
Hamming zamknął Rozdział 13 szerzszą krytyką definicji w nauce. Formuła informacyjna Shannona mierzy zaskoczenie maszynowe, nie ludzkie znaczenie. Nazwa 'Teoria Informacji' obie obiecuje zbyt wiele. Analogia z sieciami rybackimi: rybak, który łowi tylko ryby większe niż oka sieci, wyciąga wniosek, że nie ma mniejszych ryb. Ograniczenia narzędzia stają się ograniczeniami widocznego świata.
Problem z Definicjami
Hamming użył teorii informacji, aby wskazać szerszy punkt metodologiczny: początkowe definicje określają co znajdziesz, bardziej niż większość ludzi zdaje sobie sprawę.
Shannon wybrał zdefiniować 'informację' jako zaskoczenie. Ta definicja była produktywna dla inżynierii komunikacji. Ale zaimportowała specyficzny zakres — systemy podobne do maszyn — w słowo ('informacja'), które sugeruje uniwersalną zastosowwalność.
Analogia z sieciami rybackimi: sieć z przejściem 6 cali łowi tylko duże ryby. Rybak wyciąga wniosek: minimalna wielkość ryby to 6 cali. Wniosek odzwierciedla narzędzie, nie świat.
IQ jako paralelny przykład: test zaprojektowany do mierzenia 'inteligencji', skalibrowany do wytwarzania rozkładu normalnego, następnie używany do definiowania inteligencji. Narzędzie kształtuje pojęcie.
Rekomendacja Hamminga: zawsze gdy napotkasz definicję, zapytaj (1) jak wiele zgadza się z twoją wcześniejszą intuicją? (2) ile zniekształca? (3) w jakich warunkach została sformułowana? (4) czy jest teraz stosowana w różnych warunkach?