kodowanie Shannona

W dziedzinie kompresji danych kodowanie Shannona , nazwane na cześć jego twórcy, Claude'a Shannona , to bezstratna technika kompresji danych służąca do konstruowania kodu prefiksu na podstawie zestawu symboli i ich prawdopodobieństw (szacowanych lub mierzonych). Jest nieoptymalny w tym sensie, że nie osiąga najniższej możliwej oczekiwanej długości słowa kodowego, jak kodowanie Huffmana , i nigdy nie jest lepszy niż, ale czasami równy kodowaniu Shannona-Fano .

Metoda była pierwszą tego typu, technika została wykorzystana do udowodnienia twierdzenia Shannona o bezgłośnym kodowaniu w jego artykule „Mathematical Theory of Communication” z 1948 r. I dlatego jest centralnym punktem ery informacji.

Ta metoda kodowania dała początek dziedzinie teorii informacji i bez jej wkładu świat nie miałby żadnego z wielu następców; na przykład kodowanie Shannona-Fano, kodowanie Huffmana lub kodowanie arytmetyczne . Dane cyfrowe mają znaczący wpływ na wiele z naszego codziennego życia , a nie byłoby to możliwe bez kodowania Shannon i ciągłej ewolucji jego metod.

W kodowaniu Shannona symbole są ułożone w kolejności od najbardziej prawdopodobnego do najmniej prawdopodobnego, a słowa kodowe są przypisywane na podstawie pierwszego ${\ Displaystyle l_ {i} = \ lewo \ lceil - \ log _{2}p_{i}\right\rceil }$ bitów z rozwinięć binarnych skumulowanych prawdopodobieństw ${\ Displaystyle \ suma \ limity _ {k = 1} ^ {i-1} p_ {k}.}$ Tutaj ${\ Displaystyle \ lceil x \ rceil}$ oznacza funkcję sufitu (która $zaokrągla$ górę do następnej wartości całkowitej).

Przykład

W poniższej tabeli znajduje się przykład tworzenia schematu kodu dla symboli od a ₁ do a ₆ . Wartość l _i podaje liczbę bitów używanych do reprezentacji _symbolu ai . Ostatnia kolumna to kod bitowy każdego symbolu.

I	p ja	l ja	${\ Displaystyle \ suma _ {n = 0} ^ {i-1} p_ {n}}$	Poprzednia wartość w formacie binarnym	Słowo kodowe dla i
1	0,36	2	0,0	0,0000	00
2	0,18	3	0,36	0,0101...	010
3	0,18	3	0,54	0,1000...	100
4	0,12	4	0,72	0,1011...	1011
5	0,09	4	0,84	0,1101...	1101
6	0,07	4	0,93	0,1110...	1110

Shannon, Claude Elwood. "Matematyczna teoria komunikacji." Przegląd mobilnego przetwarzania i komunikacji ACM SIGMOBILE 5.1 ​​(2001): 3-55.