Всем привет! Сегодня разбираем задачу на условие Фано, которое гласит, что ни одно кодовое слово не может являться началом другого кодового слова.
Погнали!
Для начала, вот условие:
По каналу связи передаются сообщения, содержащие только заглавные русские буквы. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 000, Б — 01, В — 1101, Г — 111, Д — 0010, Е — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОКОС?
Теперь начнём решать задачу, и первое с чего мы начнём это выписывание всего, что нам известно и что нам предстоит найти:
Далее рисуем граф, в котором начинаем отмечать все кодовые слова, которые нам уже известны:
Теперь переместим всё, что связано со словом КОКОС поближе к графу. Далее, зная, что у нас две буквы "К", стараемся подобрать к ним наиболее короткое кодовое слово (100). Так как букв "О" у нас тоже две, то пробуем подобрать другое кратчайшее кодовое слово (1100). Остается свободной ветка 0011, но, к сожалению, букву "С" мы туда поставить не можем, так как в условии сказано, что кодируется весь алфавит, а значит необходимо оставить для него место. Потребуется разделить эту ветку пополам и записать на одну из получившихся ветвей букву "С" (00111).
После чего нам не составит труда посчитать длину слова КОКОС (3+3+4+4+5=19)
Все эти этапы представлены на картинке ниже:
Ответ: 19
На этом у меня всё, не забудьте поставить лайки и подписаться!