Entropia (teoria informacji)

Entropia w teorii informacji jest miarą niepewności, losowości lub średniej ilości informacji zawartej w źródle komunikacyjnym. Definicja została wprowadzona w 1948 roku przez amerykańskiego matematyka i inżyniera Claude’a Shannona i od tego czasu odgrywa kluczową rolę w takich dziedzinach jak kompresja danych, kodowanie, transmisja danych oraz kryptografia.

Definicja matematyczna

Niech X będzie dyskretną zmienną losową przyjmującą wartości x₁, x₂, …, xₙ z prawdopodobieństwami P(xᵢ). Entropia Shannona zmiennej X definiowana jest jako:

H(X) = -\sum_{i=1}^{n} P(x_i) \log_{2} P(x_i)
    

Jednostką entropii jest bit (logarytm o podstawie 2) lub nat (logarytm naturalny). Wartość H(X) opisuje średnią liczbę bitów potrzebnych do opisania symbolu generowanego przez źródło.

Właściwości entropii

• Nieujemność: H(X) ≥ 0. Entropia jest równa zero wtedy i tylko wtedy, gdy zmienna X jest deterministyczna (jedno prawdopodobieństwo = 1).
• Maxymalność: Dla zmiennej o n równoprawdopodobnych zdarzeniach, H(X) = \log_2 n. To jest maksymalna entropia dla danej liczby stanów.
• Podaddytywność (łańcuchowa): Dla dwóch zmiennych losowych X i Y, H(X,Y) = H(X) + H(Y|X), gdzie H(Y|X) jest entropią warunkową.
• Monotoniczność względem rozdrobnienia: Dodanie drobnych szczegółów (np. podział zdarzenia na mniejsze podzdarzenia) nie zmniejsza entropii.

Interpretacje i zastosowania

Komunikacja i kodowanie

Entropia określa teoretyczną granicę kompresji bezstratnej. Zgodnie z twierdzeniem Shannona, żaden algorytm nie może średnio kodować źródła z H(X) bitami na symbol, ale może zbliżyć się do tej granicy, stosując np. kodowanie Huffmana lub kodowanie arytmetyczne.

Transmisja przez szumy

W kanale komunikacyjnym, który wprowadza szum, entropia przydaje się do wyznaczania pojemności kanału – maksymalnej szybkości transmisji, przy której błąd transmisji może być asymptotycznie znikomy. Pojemność kanału C jest dana wzorem:

C = \max_{P(x)} I(X;Y)
    

gdzie I(X;Y) jest informacją wzajemną między wejściem X a wyjściem Y kanału.

Kryptografia i bezpieczeństwo

Entropia kluczy kryptograficznych jest miarą ich siły. Im wyższa entropia (np. losowość generowanego klucza), tym trudniej przeprowadzić atak typu brute‑force. Standardy takie jak NIST SP 800‑90 definiują minimalne wymagania dotyczące entropii generatorów liczb losowych.

Entropia w fizyce i innych dziedzinach

Mimo że pojęcie pochodzi z teorii informacji, istnieją analogie do entropii termodynamicznej. W kwantowej teorii informacji wprowadza się entropię von Neumanna, która jest odpowiednikiem entropii Shannona dla stanów kwantowych.

Rozszerzenia i odmiany

• Entropia warunkowa H(Y|X) – średnia niepewność Y przy znanej wartości X.
• Informacja wzajemna I(X;Y) – redukcja niepewności jednej zmiennej po obserwacji drugiej.
• Entropia względna (dywergencja Kullbacka‑Leiblera) – miara odległości między dwoma rozkładami prawdopodobieństwa.
• Entropia Renyi'ego – rodzina miar zależnych od parametru α, uogólniająca entropię Shannona.

Przykłady obliczeniowe

Rozważmy źródło generujące symbole A, B, C z prawdopodobieństwami 0,5; 0,3; 0,2. Entropia wynosi:

H = -(0,5·log₂0,5 + 0,3·log₂0,3 + 0,2·log₂0,2) ≈ 1,485 bitów
    

Oznacza to, że średnio potrzebujemy nieco ponad 1,4 bitu do zakodowania każdego symbolu.

Zobacz także

• Claude Shannon
• Teoria informacji
• Kod Huffmana
• Kod arytmetyczny
• Kwantowa informacja

Bibliografia

1. Claude E. Shannon, „A Mathematical Theory of Communication”, Bell System Technical Journal, 1948.
2. Thomas M. Cover, Joy A. Thomas, Elements of Information Theory, Wiley, 1991.
3. David J. C. MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003.
4. Markus Müller, Entropie w kryptografii i bezpieczeństwie, Warszawa: PWN, 2015.