Представление текстовой информации в компьютере (Неравномерный код. Условие Фано)

Прямое условие Фано:
Никакое кодовое слово (буква)
не может быть началом другого кодового слова (буквы)

Обратное условие Фано:
Никакое кодовое слово (буква)
не может быть окончанием другого кодового слова (буквы)

Для однозначного декодирования достаточно выполнение одного из условий.

А теперь на пальцах… 😉

Другим выходом из данной ситуации про ЗИМУ будет использование неравномерного  кода. Правда придется воспользоваться условием Фа́но[1] см.выше. Рассмотрим следующую задачу:

 ЗАДАЧА:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В используются такие кодовые слова:

А – 010, Б – 1, В – 011.

Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

 РЕШЕНИЕ:

Давайте разберем подробнее, что такое условие Фа́но:

 Никакое кодовое слово (буква)
не может быть началом другого кодового слова(буквы)

Это значит:

  1. Если буквы имею одинаковое количество разрядов, то они не должны быть одинаковыми. В самом деле, а = 10 и в = 10 не допускаются
  2. Если же буквы имеют разное количество разрядов, то буква с меньшим количеством разрядов не должна быть началом буквы с бо́льшим количеством разрядов

Например:

А – 01,
Б – 011 – так быть не может, потому что буква А является началом
буквы Б

 А вот так может:

А — 01,
Б — 001

Решим нашу задачу графически. Проще всего ее решать с помощью графов, а точнее частного случая графа – дерева.

Код букв может начинаться как с нуля, так и с единицы. По условию задачи буква Б – 1. Значит, код остальных букв будет начинаться с нуля. В противном случае буква Б будет являться началом для других букв.

Код буквы А, В, Г начинается с нуля. Второй символ у букв А, В по условию начинается с единицы, значит для буквы Г можно использовать ноль.

Графически описание этой задачи выглядит понятнее

ЗЕ ЭНД 🙂

[1]Ро́берт Ма́рио Фа́но (Robert Mario Fano, 11 ноября 1917, Турин, Италия — 13 июля 2016, Нейплс, Флорида, США) — итальяно-американский учёный в области информатики, профессор-эмерит факультетов электротехники и компьютерных наук в Массачусетском технологическом институте, действительный член Национальной академии наук США и ряда других национальных академий. Фано известен по работам в области теории информации, он независимо от Клода Шеннона изобрел ранний алгоритм сжатия информации и вывел неравенство Фано. /Источник: https://ru.wikipedia.org/wiki/Фано,_Роберт/