Wenn du dir mal das Beispiel 7.4 anguckst (Kapitel 7, S.8 ), dann wird klar, wieso man die unmöglichen Nachrichten braucht.Kami hat geschrieben:Was hat es mit den unmöglichen Nachrichten bei der Huffman-Codierung auf sich? Wozu sind die gut?
Mit unmöglichen Nachrichten erhält man eine mittlere Nachrichtenlänge von 1,875. Ohne unmögliche Nachrichten ist die mittlere Nachrichtenläge 2.
Die Anzahl der benötigten unmöglichen Nachrichten kann man berechnen, indem man q und u =|Q| in die Ungleichung
[tex]q+\lambda\cdot(q-1)\geq u[/tex]
einsetzt.
In Beispiel 7.4 bedeutet das:
[tex]4+\lambda\cdot 3 \geq 8[/tex]
[tex]\Rightarrow \lambda = 2[/tex]
Da sich u(0), also die Menge der Ausgangszeichen dann mit
[tex]u(0) := q+\lambda(q-1) = 4+2\cdot 3 = 10[/tex]
ergibt, müssen zu den acht vorhandenen Nachrichten noch zwei weitere hinzugefügt werden, um auf die geforderten zehn zu kommen.
Besonders wichtig ist dabei, daß im letzten Schritt noch q Nachrichten übrig bleiben, d.h.
[tex]u(\lambda) = q+(\lambda - \lambda)(q-1) = q[/tex]
Das ist ohne die unmöglichen Nachrichten nicht der Fall (im Beispiel würden in [tex]Q_2[/tex] nur zwei Nachrichten übrig bleiben), was die höhere Nachrichtenlänge erklärt.
Für q=2 ist das allerdings alles überflüssig, was die Codierung natürlich stark vereinfacht. Da ist nämlich gerade
[tex]\lambda = u-q[/tex]
und somit
[tex]u(0) = q + \lambda (q-1) = 2 + (u-2)\cdot 1 = u[/tex].
So... Gute Nacht!
