un

guest
1 / ?
back to lessons

Co Shannon Nazwał Informacją

Shannon zdefiniował informację jako miarę zaskoczenia. Wiadomość o prawdopodobieństwie p zawiera:

I = −log₂(p) bitów

Określone zdarzenie (p = 1) zawiera 0 bitów - żaden niepokój, żadna informacja. Rzadkie zdarzenie (p = 1/1024) zawiera 10 bitów.

Hamming natychmiast zwraca uwagę na problem: to jest wzór na pomiar ilości, a nie definicja pojęcia. Mierzy on zaskoczenie maszynowe, a nie znaczenie ludzkie. Student, który już wie odpowiedź na pytanie, otrzymuje 0 bitów z odpowiedzi - niezależnie od tego, jak ważna jest odpowiedź dla innych.

Wzór ma zastosowanie w telefonii, radiu, komputerach. Zastosowanie ma słabo w komunikacji ludzkiej, biologii lub znaczeniu. Nazwa ulubionego 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 dochodzi do maksimum, gdy wszystkie prawdopodobieństwa są równe: H_max = log₂(q) bitów. Każde nierytualne rozkład ma niższą 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 (zupełnie przewidywalne). H(p) = 1 bit dla p = 0.5 (zupełnie nieprzewidywalne).

Entropia Binarna & Pojemność Kanału

Oblicz H(p) dla p = 0.25. Pokaż wzór z liczbami zastąpionymi, oblicz oba terminy i podaj wynik w bitach. Następnie interpretuj: co H(0.25) < H(0.5) mówi o zawartości informacji w rzucie kością zaniżoną w porównaniu z rzutem kością sprawiedliwą?

Nierówność Gibbsa & Kodowanie Bezszumowe

Nierówność Gibbsa: dla dowolnych dwóch dystrybucji prawdopodobieństwa p = {pᵢ} i q = {qᵢ}:

−Σ pᵢ log₂(pᵢ) ≤ −Σ pᵢ log₂(qᵢ)

z równością tylko wówczas, gdy p = q. To opiera się na podstawowej fakt, że ln(x) ≤ x − 1 dla wszystkich x > 0, z równością dla x = 1.

Skutek: entropia H(p) jest maksymalizowana, gdy wszystkie symbole są równie prawdopodobne. Dla q symboli: H_max = log₂(q).

Teorema kodowania bezszumowego: przy założeniu, że kod jest jednoznacznie odkodowywalny, nierówność Krafta wymaga, aby Σ 2^(−lᵢ) ≤ 1, gdzie lᵢ to długość kodu dla symbolu i. Na podstawie nierówności Gibbsa, średnia długość kodu L = Σ pᵢ lᵢ spełnia:

L ≥ H(p) = −Σ pᵢ log₂(pᵢ)

Nie można uzyskać lepszego wyniku niż entropia średnia. Kodowanie Huffman'a osiąga L < H + 1.

Nierówność Gibbsa mówi, że H(p) ≤ −Σ pᵢ log₂(qᵢ) dla dowolnej dystrybucji q. Gdy q jest równa uniformnej dystrybucji qᵢ = 1/q dla wszystkich i, strona prawna uproszcza się do log₂(q). Pokaż to uproszczenie algebraicznie, a następnie powiedz, co to implikuje w sprawie maksymalnej entropii alfabetu q-symboli.

Pojemność Kanału

Kanał binarny symetryczny (BSC) odwraca każdą bitów niezależnie z prawdopodobieństwem Q = 1 − P. Pojemność BSC - maksymalna szybkość przesyłu wiarygodnych 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 dla stopy błędów.

Gdy Q = 0 (brak błędów): C = 1 bit/transmisja (perfect channel). Gdy Q = 0,5 (losowe odwracanie): C = 0 (kanał nie przekazuje żadnych informacji). Gdy Q = 1 (wszystkie bity odwracają): C = 1 (wiesz dokładnie, co wysłał nadawca, tylko odwróć wszystko z powrotem).

C mierzy maksymalny wskaźnik przesyłowy R, przy którym możesz przesyłać z dowolnie małą błędowością. Jeśli R < C, takie kodexy istnieją. Jeśli R > C, nie istnieją - żaden kod nie może przewyższyć pojemności.

Entropia & Pojemność Kanału

Obliczanie Pojemności Kanału

Z P = 0,9 (10% stawka błędów, 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/transmisja

Kanał binarny symetryczny ma błędowość Q = 0,2 (P = 0,8). Oblicz pojemność kanału C = 1 + P log₂(P) + Q log₂(Q). Użyj log₂(0,8) ≈ −0,322 i log₂(0,2) ≈ −2,322. Pokaż swoje zastąpienie i arytmetykę, a następnie interpretuj: na tej pojemności, jaką część szybkości przetwarzania danych może przewozić informacje?

Co dowodzi Teoria

Podstawowa teoria Shannona: dla dowolnej stawki R < C, istnieją kodexy o długości bloku n (z n → ∞) osiągające błędowość P_E → 0.

Dowód używa zaskakującego argumentu: losowe kodexy. Zamiast konstruować konkretny kod, Shannon przecięcia nad wszystnymi możliwymi losowymi książkami kodowymi (rzucane monety). Pokazał, że średnia błędów nad wszystkimi książkami kodowymi jest mała. Jeśli średnia jest mała, przynajmniej jeden kod ma małą błędowość.

Analiza sferyczna: nadawca wybiera komunikat aᵢ → sferę o promieniu n(Q + ε₂) wokół aᵢ w przestrzeni binarnej o n wymiarach. Dla dużego n, odbiornik słowo otrzymane bⱼ znajduje się wewnątrz tej sfery z wysoką prawdopodobieństwem. Odbiornik dekoduje do słowa kodowego, którego sfera zawiera bⱼ.

Cztery przypadki określają prawdopodobieństwo błędu P_E:

`` aᵢ w sferze inne aⱼ w sferze wynik tak nie poprawny (brak błędu) tak tak niejednoznaczny → błąd nie tak błędne odczytywanie → błąd nie nie poza wszystkimi sferami → błąd ``

Geometria Informacyjna & Zakładanie Sfer

Wiązanie na P_E wynosi: P_E ≤ d + M × 2^(n × (H(Q+ε₂) − C)) dla odpowiednio dobranych d i ε₂. Wybór ε₂ tak, aby H(Q+ε₂) < C sprawia, że wykładnik jest ujemny. Dla dużego n, drugi człon → 0.

Przyrodnicza natura teoremu

Hamming był precyzyjny co do tego, co teoria dowodzi i co nie.

Co udowadnia: niezawodne komunikowanie się z szybkością R < C jest możliwe teoretycznie, dla wystarczająco dużych wartości n.

Co nie dostarcza: konstrukcji kodu wskazanej explicit. Losowy kod o długości n, dużym wystarczająco, aby zbliżyć się do pojemności, ma księgę kodów o wielkości M × n bitów, gdzie obie M i n są astronomicznie duże. Nie można z niego zapisać ani obliczyć.

Kody korekujące błędy vs. Shannon: kody korekujące błędy (Hamming, Reed-Solomon, turbo, LDPC) dostarczają konkretną, obliczalną konstrukcję. Związane są z pewnym odległością od pojemności w zamian za praktyczne dekodery. W miarę jak n rośnie, a korekty błędów na blokach stają się liczniejsze, praktyczne kody mogą zbliżyć się do pojemności bardzo blisko.

Przykład satelitów: Voyager i Pioneer używały potężnych kody korekujących błędy, aby komunikować się na odległość miliardów mil, korzystając z 5-20 watów energii. Długie długości bloków pozwalały na korektę większej liczby błędów na blok, zbliżając się do pojemności pomimo ogromnego szumu z odległości.

Krytyczna ocena

Hamming zakończył rozdział 13 krytyką definicji w naukach. Formuła Shannon'a mierzy maszynowy zaskoczenie, a nie znaczenie ludzkie. Nazwa 'Teoria Informacji' przesadza. Porównanie do sieci rybackiej: rybak, który łowi tylko ryby większe niż siatka siatki, stwierdza, że nie ma mniejszych rybek. Ograniczenia narzędzia stają się ograniczeniami świata.

Teoria Shannon'a dowodzi, że istnieją kody osiągające niemalże zera błędy przy szybkości R < C, ale dowód jest niestrukturalny: pokazuje istnienie przez średnią nad księgami kodów losowych, a nie przez budowę kodu. Wyjaśnij w swoich własnych słowach, dlaczego to ma znaczenie praktycznie, i opisz, co jest lukią między dowodem istnienia Shannon'a a prawdziwym kodem korekującym błędy, którego inżynierowie muszą rozwiązać.

Problem z Definicjami

Hamming użył teorii informacji, aby zrobić większy punkt metodologiczny: początkowe definicje determinują, co znajdujesz, częściej niż większość ludzi się domyśla.

Shannon wybrał, aby zdefiniować 'informację' jako zaskoczenie. Ta definicja była produktywna dla inżynierii komunikacji. Ale wprowadziła ona określony zakres - systemy podobne do maszyn - do słowa ('informacja') sugerującego uniwersalną zastosowalność.

Porównanie do sieci rybackiej: sieć o siatce o średnicy 6 cali łowi tylko duże ryby. Rybkarz kończy, że minimalna wielkość ryb to 6 cali. Wniosek odzwierciedla narzędzie, a nie świat.

IQ jako analogia: test zaprojektowany do pomiaru 'inteligencji', kalibrowany tak, aby wygenerować rozkład normalny, a następnie używany do definiowania inteligencji. Narzędzie kształtuje pojęcie.

Zalecenie Hamminga: gdy napotkasz definicję, zapytaj (1) jak bardzo zgadza się ona z twoim intuicją przedziałową? (2) jak bardzo ją zakłóca? (3) w jakich warunkach została opracowana? (4) czy jest obecnie stosowana w innych warunkach?

Zastosuj krytykę Hamminga czterema pytanimi do definicji Shannon'a informacji. Dla każdego z czterech pytań podaj konkretne odpowiedzi, które pokazują, że zetknąłeś się zarówno z definicją, jak i jej ograniczeniami.