Fano condition

The Fano condition (after Robert Fano ) describes in the coding theory of computer science the property of a language to be prefix- free. In a language that meets the Fano condition, there is no word that is identical to the beginning of another word.

Prefix-free languages simplify word recognition, since after each recognized word you can immediately move on to the next. A further forecast is not necessary due to the freedom of prefixes.

With the help of the Shannon-Fano coding or the Huffman coding , codings can be constructed that meet the Fano condition. A code that meets the Fano condition is called a prefix code .

Examples

The language L = {0, 10, 110, 1110, 11110} (e.g. as coding of the values 0, 1, 2, 3, 4) does not have any prefixes and thus satisfies the Fano condition.
The phone numbers in a phone book of a prefix area also meet the Fano requirement. This is necessary because some telephones dial immediately and connect on the first "hit".
The German language, on the other hand, does not meet the Fano requirement because “bei” is a German word and is also the prefix of “both”.
The Morse code meets the Fano condition when the longer break between two characters is considered as the third symbol of the language. A sequence of the two symbols short signal and long signal would not meet the Fano condition.

Formal definition

Be a language and the empty word . fulfills the Fano condition, i.e. it is prefix-free if and only if a combination of two words of the language can only be a word if one of the components is the empty word: ${\ displaystyle \ mathbf {\ mathit {L}}}$ ${\ displaystyle \ varepsilon}$ ${\ displaystyle \ mathbf {\ mathit {L}}}$ ${\ displaystyle uv}$

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

Automat

A deterministic basement machine that accepts with an empty basement exactly fulfills the Fano condition.

literature

Rainer Malaka, Andreas Butz, Heinrich Hußmann: Medieninformatik: An introduction. Pearson Studium, Munich 2009, ISBN 978-3-8273-7353-3 , pp. 74-77.