Fano-Bedingung - LinkFang.de





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. Mit Hilfe der Shannon-Fano-Kodierung oder der Huffman-Kodierung lassen sich Kodierungen konstruieren, 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 Telefonnummern eines Telefonbuchs eines Vorwahlbereichs genügen ebenfalls der Fano-Bedingung. Dies ist notwendig, weil einige Telefone sofort wählen und beim ersten „Treffer“ verbinden.
  • Die deutsche Sprache hingegen genügt nicht der Fano-Bedingung, weil „bei“ ein Wort der deutschen Sprache ist und zugleich Präfix von „beide“ ist.
  • Der Morsecode erfüllt die Fano-Bedingung, wenn die längere Pause zwischen zwei Zeichen als drittes Symbol der Sprache betrachtet wird. Eine Folge der beiden Symbole kurzes Signal und langes Signal würde die Fano-Bedingung nicht erfüllen.

Formale Definition

Sei [math]\mathbf{\mathit{L}}[/math] eine Sprache und [math]\varepsilon[/math] das leere Wort. [math]\mathbf{\mathit{L}}[/math] erfüllt die Fanobedingung, ist also präfixfrei genau dann, wenn ein Gefüge [math] uv[/math] von zwei Wörtern der Sprache nur dann ein Wort sein kann, wenn einer der Bestandteile das leere Wort ist:

[math]\forall u,v,w \in \mathbf{\mathit{L}}: (w = uv \implies u = \varepsilon \lor v = \varepsilon)[/math]

Automat

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

Literatur

  • Rainer Malaka, Andreas Butz, Heinrich Hußmann: Medieninformatik: Eine Einführung. Pearson Studium, München 2009, ISBN 978-3-8273-7353-3, S. 74–77.

Kategorien: Kodierungstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Fano-Bedingung (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.