Shannon-Fano-Kodierung

Shannon-Fano-Code (oder auch nur Fano-Code) ist eine Methode der Datenkompression, in der die Codewortlänge über eine Reihung von Zeichen nach deren geschätzter oder gemessener Verteilung gewählt wird.

Codierschema

1. Ordnen der Originalsymbole nach fallenden Auftrittswahrscheinlichkeiten
2. Aufteilen der Originalsymbole in zwei Gruppen (möglichst) gleicher Summenwahrscheinlichkeiten
3. Zuordnung eines Bits, so dass die erste Gruppe mit "0" und die zweite Gruppe mit "1" adressiert wird
4. Wiederholen der Schritte 2 und 3 mit den im vorangegangenen Codierschritt entstandenen Gruppen

Der Code ist eindeutig decodierbar, da kein Codewort linker Teil eines anderen Codewortes ist: Präfix-Freiheit.

Beispiel

$P(A_{i})$ ist unsere Wahrscheinlichkeit dass das Ereignis $A_{i}$ eintritt. Z.b. 1/6 bei einem sechsflächigen Würfel.

$A_{i}$	$P(A_{i})$				Shannon-Fano-Code
1 V	7/20	0	0		00
-1 V	6/20	0	1		01
0 V	4/20	1	0		10
2 V	2/20	1	1	0	110
-2 V	1/20	1	1	1	111

Siehe auch: Huffman-Code

Weblinks

• Schöne Erläuterung der Quellencodierung mit Shannon-Fano-Code