Умова Фано англ Fano condition на честь Роберта Фано у теорії кодування необхідна умова побудови самотермінуючого коду у

Умова Фано (англ. Fano condition, на честь Роберта Фано) — у теорії кодування необхідна умова побудови самотермінуючого коду (у іншій термінології, префіксного коду). Звичайне формулювання цієї умови виглядає так:

Ніяке кодове слово не може бути початком іншого кодового слова.

Більш «математичне» формулювання:

Якщо в коді є слово а, то для будь-якого непорожнього рядка b слова ab у коді не існує.

Прикладом коду, що задовольняє умові Фано, є телефонні номери в традиційній телефонії. Якщо в мережі існує номер 101, то номер 1012345 не може бути виданий: набираючи три цифри, АТС припиняє розуміти подальший набір і сполучає з адресатом за номером 101. Проте, для набору із стільникового телефону це правило вже не діє, тому що потрібне явне завершення послідовності знаків відповідною кнопкою (зазвичай — із зображенням зеленої трубки), при цьому 101, 1010 і 1012345 можуть одночасно розумітися як різні адресати.

Див. також

Префіксний код

Література

Бауер Ф., Гооз Г. Інформатика. М., «Світ», 1990 г. — Т. 1.

Посилання

Код Хаффмана