Interpretacja entropii Shanona

Question

Często widziałem jako wyjaśnienie entropii Shanona, że ​​reprezentuje ona „ średnią liczbę pytań tak / nie potrzebnych do ustalenia, w jakim stanie znajduje się dany system ”.

Działa to bardzo dobrze dla systemu mającego parzystą liczbę możliwych stanów, ale jeśli spróbuję to zrobić z, powiedzmy, 3 możliwymi stanami, wszystkie są równoważne, nie uważam tego za prawdę. Rzeczywiście, używając entropii,$ H = \sum_{n = 1}^{3}\frac{1}{3}\log_2(\frac{1}{3}) = 1.58$Znajduję średnio 1,58 pytań tak / nie. Jeśli zakoduję$1^{st}$Stan jak 0The$2^{nd}$stan jako 1i$3^{rd}$ponieważ 00średnia liczba bitów (pytań) potrzebnych do scharakteryzowania systemu wynosi$\frac{4}{3}=1.33$.

Czy gdzieś popełniłem błąd, czy to znaczy, że to wyjaśnienie z pytaniami tak / nie jest tylko sposobem na uproszczenie?

Answer 1

Najpierw proponowane kodowanie $A\to 0$, $B \to 1$, $C\to 00$osiąga długość kodowania poniżej entropii, co powinno być niemożliwe.

Problem polega na tym, że kodowanie jest praktycznie bezużyteczne, ponieważ nie jest „jednoznacznie dekodowalne”: jeśli otrzymasz $00$ nie możesz wiedzieć, czy dane wejściowe były $AA$ lub $C$.

Następnie musisz zrobić coś takiego $A\to 0$, $B \to 10$, $C\to 11$ , który ma średnią długość kodowania $5/3=1.666$ , powyżej entropii ($H=1.585$). Tego można było się spodziewać.

A jeśli zakodujesz każdą wartość osobno, to tak, nie możesz działać lepiej. Ale możesz zakodować kilka wartości razem (zakodować „rozszerzenie źródła”) i podejść do entropii.

Weźmy na przykład grupę plików $n=5$wartości. Tam są$3^5=243$równie prawdopodobne wspólne wartości. Dlatego$243 < 256 = 2^8$, możesz to zakodować za pomocą grupy $8$ Tak, żadnych pytań.

Dlatego w przypadku tego prostego schematu należałoby zapytać $8$ pytania do odkrycia $5$ wartości, co daje długość kodowania $8/5=1.6$, blisko entropii.

Powyższe nie jest optymalne (patrz kodowanie Huffmana), ale masz pomysł.

Answer 2

Oczekiwana długość kodu Shannon-Fano to

$ \mathbb {E} L=\sum _{i=1}^{n}p_{i}l_{i}\leq \sum _{i=1}^{n}p_{i}(-\log _{2}p_{i}+1)=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}+\sum _{i=1}^{n}p_{i}=H(X)+1.$

Zwróć uwagę, że powiązanie ma „+1” - jest to zgodne z Twoimi obliczeniami

http://en.wikipedia.org/wiki/Shannon%E2%80%93Fano_coding

Zauważ, że kody Shannon-Fano nie są optymalne, ale kody Huffmana są. Aby zapoznać się z kodami Huffmana, zobacz

https://en.wikipedia.org/wiki/Huffman_coding