Fano-Bedingung

Die Fano-Bedingung (nach Robert Fano) bezeichnet in der Kodierungstheorie der Informatik die Eigenschaft einer Sprache, präfix-frei zu sein. In einer Sprache, die der Fano-Bedingung genügt, gibt es kein Wort, das Präfix eines anderen Wortes ist. Informell ausgedrückt: In der Sprache existiert kein Wort welches identisch mit dem Anfang eines weiteren Wortes ist. Präfix-freie Sprachen vereinfachen die Worterkennung, da nach jedem erkannten Wort sofort zum nächsten übergegangen werden kann. Eine weitere Vorausschau ist aufgrund der Präfixfreiheit nicht nötig. Die Anwendung der Shannon-Fano-Kodierung bzw. des Huffman-Codes führen zu Kodierungen, die die Fano-Bedingung erfüllen. Ein Code, der die Fano-Bedingung erfüllt, wird Präfixcode genannt.

Beispiele

• Die Sprache L = {0, 10, 110, 1110, 11110} (z.B. als Kodierung der Werte 0,1,2,3,4) ist präfixfrei und genügt damit der Fano-Bedingung.
• Die deutsche Sprache hingegen genügt nicht der Fano-Bedingung, weil "bei" ein Wort der deutschen Sprache ist und zugleich Präfix von "Beispiel".
• Auch der Morsecode erfüllt die Fano-Bedingung nicht, deshalb benötigt man zum Dekodieren ein weiteres "Zeichen", die Pause zwischen zwei Codewörtern (Morsezeichen).

Formale Definition

Sei$\mathbf{\mathit{L}}$eine Sprache und $\epsilon$ das leere Wort.

$\forall u,v,w \in \mathbf{\mathit{L}}, (w = uv \implies v = \epsilon)$

Automat

Ein deterministischer Kellerautomat, der mit leerem Keller akzeptiert, erfüllt genau die Fano-Bedingung.