Interpretação da entropia Shanon

Question

Freqüentemente tenho visto como uma explicação para a entropia de Shanon que ela representa " o número médio de perguntas sim / não necessárias para descobrir em qual estado um determinado sistema está " .

Isso funciona muito bem para um sistema com um número par de estados possíveis, mas se eu tentar fazer isso, digamos, 3 estados possíveis, todos equiprováveis, não acho que isso seja verdade. Na verdade, usando a entropia,$ H = \sum_{n = 1}^{3}\frac{1}{3}\log_2(\frac{1}{3}) = 1.58$Encontro um número médio de 1,58 perguntas sim / não. Se eu codificar o$1^{st}$estado como 0, o$2^{nd}$estado como 1e o$3^{rd}$como 00, o número médio de bits (perguntas) que preciso para caracterizar o sistema é$\frac{4}{3}=1.33$.

Cometi um erro em algum lugar ou significa que esta explicação com as perguntas sim / não é apenas uma forma de simplificar as coisas?

Answer 1

Primeiro, sua codificação proposta $A\to 0$, $B \to 1$, $C\to 00$atinge um comprimento de codificação abaixo da entropia, o que deveria ser impossível.

O problema é que sua codificação é praticamente inútil, porque não é "decodificável exclusivamente": se você receber $00$ você não pode saber se a entrada foi $AA$ ou $C$.

Então você precisa fazer algo como $A\to 0$, $B \to 10$, $C\to 11$ , que tem um comprimento de codificação médio de $5/3=1.666$ , acima da entropia ($H=1.585$) Isto é esperado.

E se você codificar cada valor isolado, então, sim, você não pode ter um desempenho melhor do que isso. Mas você pode codificar vários valores juntos (codificar "a extensão da fonte") e se aproximar da entropia.

Considere, por exemplo, um grupo de $n=5$valores. Existem$3^5=243$valores conjuntos igualmente prováveis. Porque$243 < 256 = 2^8$, você pode codificar isso com o grupo com $8$ perguntas sim-não.

Portanto, com este esquema simples, você precisa perguntar $8$ perguntas para descobrir $5$ valores, o que dá um comprimento de codificação $8/5=1.6$, perto da entropia.

O exposto acima não é o ideal (consulte a codificação de Huffman), mas essa é a idéia.

Answer 2

O comprimento de código esperado de um código Shannon-Fano é

$ \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.$

Observe que o limite tem um "+1" - isso está de acordo com seus cálculos

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

Observe que os códigos Shannon-Fano não são ideais, mas os códigos Huffman são. Para códigos Huffman, consulte

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