Interpretation der Shanon-Entropie

Question

Ich habe oft als Erklärung für die Shanon-Entropie gesehen, dass sie " die durchschnittliche Anzahl von Ja / Nein-Fragen darstellt, die erforderlich sind, um herauszufinden, in welchem ​​Zustand sich ein bestimmtes System befindet ".

Dies funktioniert sehr gut für ein System mit einer geraden Anzahl möglicher Zustände, aber wenn ich dies mit beispielsweise 3 möglichen Zuständen versuche, die alle gleich wahrscheinlich sind, finde ich dies nicht wahr. In der Tat, unter Verwendung der Entropie,$ H = \sum_{n = 1}^{3}\frac{1}{3}\log_2(\frac{1}{3}) = 1.58$Ich finde durchschnittlich 1,58 Ja / Nein-Fragen. Wenn ich das verschlüssele$1^{st}$Zustand als 0, die$2^{nd}$Zustand als 1und die$3^{rd}$als 00die durchschnittliche Anzahl von Bits (Fragen) , die ich brauche das System zu charakterisieren , ist$\frac{4}{3}=1.33$.

Habe ich irgendwo einen Fehler gemacht oder bedeutet dies, dass diese Erklärung mit den Ja / Nein-Fragen nur eine Möglichkeit ist, die Dinge zu vereinfachen?

Answer 1

Zunächst Ihre vorgeschlagene Codierung $A\to 0$, $B \to 1$, $C\to 00$erreicht eine Codierungslänge unterhalb der Entropie, die unmöglich sein sollte.

Das Problem ist, dass Ihre Codierung praktisch nutzlos ist, weil sie nicht "eindeutig decodierbar" ist: wenn Sie empfangen $00$ Sie können nicht wissen, ob die Eingabe war $AA$ oder $C$.

Dann müssen Sie so etwas tun $A\to 0$, $B \to 10$, $C\to 11$ , die eine durchschnittliche Codierungslänge von hat $5/3=1.666$ über der Entropie ($H=1.585$). Dies ist zu erwarten.

Und wenn Sie jeden isolierten Wert codieren, können Sie keine bessere Leistung erzielen. Sie können jedoch mehrere Werte zusammen codieren (Code "die Erweiterung der Quelle") und sich der Entropie nähern.

Betrachten Sie zum Beispiel eine Gruppe von $n=5$Werte. Es gibt$3^5=243$gleich wahrscheinliche Gelenkwerte. weil$243 < 256 = 2^8$können Sie dies mit group with codieren $8$ ja, keine Fragen.

Daher müssten Sie mit diesem einfachen Schema fragen $8$ Fragen zu entdecken $5$ Werte, die eine Codierungslänge ergibt $8/5=1.6$in der Nähe der Entropie.

Das Obige ist nicht optimal (siehe Huffman-Codierung), aber Sie bekommen die Idee.

Answer 2

Die erwartete Codelänge eines Shannon-Fano-Codes beträgt

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

Beachten Sie, dass die Grenze eine "+1" hat - dies stimmt mit Ihren Berechnungen überein

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

Beachten Sie, dass Shannon-Fano-Codes nicht optimal sind, Huffman-Codes jedoch. Informationen zu Huffman-Codes finden Sie unter

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