Czym jest informacja?
Przed Shannonem "informacja" nie miała matematycznej definicji. Inżynierowie wiedzieli, że przesyłanie wiadomości przez zaszumioną linię telefoniczną jest zawodne, ale nie mieli precyzyjnego sposobu, by określić, co jest przesyłane ani co jest tracone. Fundamentalna intuicja Shannona była radykalna: informacja nie dotyczy znaczenia, semantyki ani ważności. Dotyczy zaskoczenia — stopnia, w jakim wiadomość redukuje niepewność.
Formalnie, zawartość informacyjna zdarzenia o prawdopodobieństwie p wynosi I = −log₂(p) bitów. Wybór podstawy 2 daje jednostki bitów (cyfr binarnych). Zdarzenie o prawdopodobieństwie 1/2 (rzut uczciwą monetą) niesie dokładnie 1 bit informacji. Zdarzenie o prawdopodobieństwie 1/4 niesie 2 bity. Zdarzenie o prawdopodobieństwie 1/8 niesie 3 bity. Zdarzenie pewne (p = 1) niesie 0 bitów — nie mówi ci niczego, czego już nie wiedziałeś. Ta definicja jest jedyną spójną z trzema naturalnymi wymaganiami: informacja jest addytywna dla zdarzeń niezależnych, jest funkcją ciągłą prawdopodobieństwa i jest maksymalna dla rozkładów jednostajnych.
Entropia Shannona
Dla źródła, które generuje symbole z alfabetu o prawdopodobieństwach p₁, p₂, ..., pₙ, entropia Shannona wynosi: H = −Σᵢ pᵢ log₂(pᵢ) bitów na symbol. Mierzy to średnią zawartość informacyjną na symbol — równoważnie, średnią niepewność przed zaobserwowaniem każdego symbolu.
Uczciwa moneta ma H = 1 bit. Moneta obciążona w stronę orła z prawdopodobieństwem 0,9 ma H ≈ 0,469 bita — znacznie mniej niepewności, a więc mniej informacji na rzut. Tekst angielski, z wysoce przewidywalnymi częstościami liter i strukturą gramatyczną, ma entropię rzędu 1,0–1,5 bita na znak (Shannon oszacował to poprzez eksperymenty z udziałem ludzi). Oznacza to, że tekst angielski ma ogromną redundancję — około 75% znaków jest przewidywalnych z kontekstu.
Entropia Shannona jest formalnie identyczna z entropią termodynamiczną we wzorze Boltzmanna, gdzie k zastępuje podstawa logarytmu. To nie przypadek: obie mierzą liczbę możliwych stanów (mikrostanów w fizyce, wiadomości w teorii komunikacji) zgodnych ze znanymi ograniczeniami makroskopowymi. Głęboki związek między teorią informacji a termodynamiką — badany przez Rolfa Landauera, Charlesa Bennetta i innych — pokazuje, że usunięcie informacji ma minimalny koszt termodynamiczny kT ln(2) dżuli na bit. Ta "zasada Landauera" łączy obliczenia, informację i fizykę na fundamentalnym poziomie.
Kompresja danych
Twierdzenie Shannona o kodowaniu źródłowym (1948) ustanawia fundamentalną granicę bezstratnej kompresji danych: żaden algorytm nie może skompresować danych poniżej H bitów na symbol średnio, gdzie H to entropia źródła. Powyżej H, doskonała bezstratna kompresja jest osiągalna (w zasadzie, dla wystarczająco długich wiadomości). Ta granica jest zarówno podłogą, poniżej której żaden algorytm nie może zejść, jak i celem, do którego dobre algorytmy się zbliżają.
Kodowanie Huffmana (1952) przypisuje symbolom binarne kody o zmiennej długości, z krótszymi kodami dla częstszych symboli — podobnie jak alfabet Morse'a nadaje literze "E" pojedynczą kropkę (najczęstsza litera angielska). Kodowanie Huffmana jest optymalne wśród kodów symbol po symbolu. Kodowanie arytmetyczne działa na całych wiadomościach i może zbliżyć się do granicy entropii dowolnie blisko. Algorytmy LZ77 i LZ78 (1977–78), używane w zip, gzip i PNG, wykorzystują powtarzające się wzorce w danych, a nie statystykę symboli, i stanowią podstawę większości nowoczesnych ogólnych kompresorów. Współczesne kompresory, takie jak Brotli (używany w przeglądarkach internetowych) i Zstandard, łączą modelowanie statystyczne z kodowaniem entropijnym, osiągając kompresję w granicach kilku procent od teoretycznej granicy.
Twierdzenie o zaszumionym kanale
Najbardziej zdumiewający wynik Shannona — twierdzenie o kodowaniu kanałowym z szumem — obalił to, co inżynierowie uważali za fundamentalne ograniczenie. Intuicja była taka: każdy prawdziwy kanał komunikacyjny dodaje szum, błędy uszkadzają wiadomości, a jedynym sposobem na zmniejszenie błędów jest wolniejsza transmisja. Shannon udowodnił, że ta intuicja jest błędna.
Dla dowolnego kanału o pojemności C = B · log₂(1 + S/N) bitów/sekundę (gdzie B to pasmo w Hz, a S/N to stosunek mocy sygnału do szumu), możliwe jest przesyłanie informacji z dowolną szybkością R < C z prawdopodobieństwem błędu zbliżającym się do zera wraz ze wzrostem długości wiadomości — po prostu przez wybór odpowiedniego kodu korekcyjnego. Transmisja z szybkościami powyżej C jest niemożliwa bez względu na kod. Pojemność kanału C jest fundamentalną granicą teoretyczno-informacyjną.
Dowód jest nieskonstruktywny: Shannon pokazał, że losowy kod zadziałałby z wysokim prawdopodobieństwem, ale nie powiedział, którego kodu użyć. Znalezienie praktycznych kodów zbliżających się do granicy Shannona zajęło inżynierom kolejne pięć dekad.
Odkryj algorytmy, które kodują, kompresują i przesyłają informacje w symulacji Kodowania Huffmana — zobacz, jak kody o zmiennej długości i kodowanie odnoszą się do teoretyczno-informacyjnych zasad odkrytych przez Shannona.
Kody korekcyjne
Richard Hamming, pracujący w Bell Labs w 1950 roku, opracował pierwsze kody korekcyjne błędów. Kody Hamminga dodają redundantne bity kontrolne do wiadomości w taki sposób, że każdy pojedynczy błąd bitu może być nie tylko wykryty, ale i skorygowany. Kod Hamminga (7,4) wysyła 7 bitów na każde 4 bity danych, umożliwiając korekcję dowolnego pojedynczego błędu bitowego. Schemat działa poprzez wybór słów kodowych maksymalnie oddalonych od siebie w "odległości Hamminga" (liczbie pozycji bitów, na których się różnią).
Kody Reeda-Solomona (1960), używane dziś w każdej płycie CD, DVD, kodzie QR i w komunikacji dalekiego kosmosu, traktują dane jako współczynniki wielomianu i przesyłają dodatkowe punkty ewaluacji. Pozwala to na korekcję błędów seryjnych — zarysowanie na płycie CD może uszkodzić wiele kolejnych bitów, a Reed-Solomon może zrekonstruować oryginalne dane, dopóki przetrwa wystarczająco dużo punktów ewaluacji. Kody turbo (1993) i kody kontroli parzystości o niskiej gęstości (LDPC) mogą osiągnąć szybkości transmisji w granicach ułamka procenta od granicy Shannona — wyczyn uważany przez dekady za praktycznie niemożliwy. Deep Space Network NASA używa kodów LDPC w sygnałach z sond Voyager, znajdujących się dziś ponad 20 miliardów kilometrów od Ziemi.
Teoria informacji w biologii i uczeniu maszynowym
DNA można analizować jako kanał informacyjny, w którym mutacje działają jak szum. Genom ludzki koduje około 6,4 miliarda par zasad, co odpowiada około 1,5 gigabajta surowej informacji — choć efektywna zawartość informacyjna jest niższa z powodu sekwencji powtarzalnych i redundantnych kodonów (kod genetyczny wykorzystuje 64 kodony dla 20 aminokwasów plus sygnały stopu). Analiza teoretyczno-informacyjna sekwencji genomowych pomaga identyfikować regiony funkcjonalne: regiony o niskiej entropii (silnie konserwowane sekwencje) często odpowiadają genom niezbędnym lub elementom regulatorowym.
W uczeniu maszynowym entropia Shannona pojawia się wszędzie. Funkcja straty cross-entropy — standardowy cel treningowy dla sieci klasyfikacyjnych — jest dokładnie entropią Shannona między prawdziwym rozkładem etykiet a rozkładem przewidywanym przez model. Minimalizacja cross-entropy jest równoważna estymacji największej wiarygodności. Informacja wzajemna I(X;Y) = H(X) − H(X|Y) mierzy, ile znajomość zmiennej Y redukuje niepewność co do X; jest wykorzystywana do selekcji cech, uczenia reprezentacji i w metodach information bottleneck, które kompresują reprezentacje, zachowując tylko informacje istotne dla zadania. Zasada minimalnej długości opisu (MDL), autorstwa Jormy Rissanena, ujmuje uczenie statystyczne jako problem kompresji: najlepszy model to ten, który najbardziej kompresuje dane, w naturalny sposób równoważąc dopasowanie z złożonością modelu.