Kodowanie Shannona – metoda kompresji bezstratnej, którą Claude E. Shannon przedstawił jako jeden z dowodów swojego podstawowego twierdzenia o kodowaniu.
Kodowanie Shannona nie tworzy optymalnych kodów, nieco lepsze wyniki daje modyfikacja znana jako kodowanie Shannona-Fano, zaś optymalny kod wyznacza kodowanie Huffmana.
Kodowanie Shannona
Dane jest źródło
i stowarzyszone z nimi prawdopodobieństwa
- Prawdopodobieństwa (a wraz z nimi symbole) są sortowane w porządku nierosnącym, tj.
![{\displaystyle p_{i}\geqslant p_{i+1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5dc2be367b1cb9079cff9c3da6204b26b3fd992c)
- Następnie dla tak uporządkowanych danych oblicza się niepełne prawdopodobieństwo kumulatywne:
– jest to suma prawdopodobieństw elementów od 1 do i-1. - Kodowanie Shannona polega na wzięciu
(długość Shannona) pierwszych bitów binarnego rozwinięcia liczby
(brane są bity po przecinku).
Średnia długość kodów mieści się w przedziale
gdzie
to entropia źródła (średnia liczba bitów na symbol).
Przykład
Niech
(entropia
); prawdopodobieństwa są już podane nierosnąco.
Długości Shannona (długości kodów w bitach):
![{\displaystyle l_{a}=\lceil -\log _{2}{0{,}45}\rceil =2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1c0fc884f06b17d6be21d998bb41e95388e13f2)
![{\displaystyle l_{b}=\lceil -\log _{2}{0{,}30}\rceil =2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8fde1fe24f08236b29be506e2c4b37971b95999)
![{\displaystyle l_{c}=\lceil -\log _{2}{0{,}20}\rceil =3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23561776d024a20ac7edd5ac6472e890d271cc09)
![{\displaystyle l_{d}=\lceil -\log _{2}{0{,}05}\rceil =5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e314f002e5b554cb7e9fff0af5c0b448b4712a1)
Prawdopodobieństwa kumulatywne:
![{\displaystyle P_{1(a)}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d6a3e4d11830a2b4bad31aaacc8c36aa24b20d6)
![{\displaystyle P_{2(b)}=p_{1}=0{,}45}](https://wikimedia.org/api/rest_v1/media/math/render/svg/95d5850ecc2e55229d18798343e797fb41b34adb)
![{\displaystyle P_{3(c)}=p_{1}+p_{2}=0{,}45+0{,}3=0{,}75}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93bc3dc15aef03fdbc7fbd3ef5dc64f903d62856)
![{\displaystyle P_{4(d)}=p_{1}+p_{2}+p_{3}=0{,}45+0{,}3+0{,}2=0{,}95}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6d52f90c344f27b816b20288badae989dbba106)
I ich rozwinięcia binarne (wzięte 5 pierwszych bitów po przecinku, zaznaczono słowa kodowe):
![{\displaystyle P_{1(a)}=0{,}{\color {blue}00}000_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c29b85ac05428735ec918b1b3ad14c84cc1ec40)
![{\displaystyle P_{2(b)}=0{,}{\color {blue}01}110_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5955053715bb0197cdcfa44eb4deebffdca71cdb)
![{\displaystyle P_{3(c)}=0{,}{\color {blue}110}00_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f75ee0fccc3c4c58ce21114c9686392d7a1dd7f4)
![{\displaystyle P_{4(d)}=0{,}{\color {blue}11110}_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e179620a2a08696d2dc5c08a064c3ed86338f1d1)
Ostatecznie kody mają postać:
![{\displaystyle kod(a)=00_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c1fb8b8e3958124badd1c849798dc444eb9a674)
![{\displaystyle kod(b)=01_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0ae944213b84eb398a7809373fe0a02013a83a8)
![{\displaystyle kod(c)=110_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1db7dd2e56a2ebf2c6192a537aa9f4b7601c16f6)
![{\displaystyle kod(d)=11110_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e91d89cd7935a83567f451556df45a8d11a8c308)
Średnia długość kodu
Po podstawieniu do nierówności podanej w twierdzeniu (średnia długość kodów):
stwierdzamy, że otrzymany kod rzeczywiście ją spełnia.
Jednak, jak wspomniano, efektywność kodowania Shannona nie jest duża – dla danych z powyższego przykładu wynosi
Zobacz też
Bibliografia
- Claude E. Shannon, A Mathematical Theory of Communication, reprint z poprawkami z „Bell System Technical Journal”, vol. 27, s. 379–423, 623–656, lipiec, październik 1948
Linki zewnętrzne
- MaurycyM. Gast MaurycyM., Kompresja danych - Przeczytaj - Kodowanie Shannona [online], Zintegrowana Platforma Edukacyjna [dostęp 2023-06-22] .