По каналу связи передаются сообщения, содержащие только буквы из набора {А, З, А, Н, И, Ч}. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано: никакое кодовое слово не является началом другого кодового слова.
Например, если кодовое слово буквы А — 1011, а кодовое слово буквы Б — 101, то прямое условие Фано нарушается, поскольку код буквы Б является началом кода буквы А.
Кодовые слова для некоторых букв известны:
- Н — 1111
- З — 110
Необходимо определить кодовые слова для букв А, К, Ч и найти минимально возможное количество двоичных знаков для кодирования слова «КАЗАЧКА».
Построение кодов
Для минимизации количества двоичных знаков, необходимо использовать наименьшие возможные кодовые слова для часто повторяющихся букв. В слове «КАЗАЧКА» буква А встречается трижды, а буква К дважды.
Построим коды, используя бинарное дерево. Так как ни один из существующих кодов не начинается с «0», для буквы А возьмем код «0» (один двоичный знак).
Далее построим дерево для кодов, начинающихся с «1». У нас уже есть коды для Н (1111) и З (110). Из-за прямого условия Фано, после 1111 (Н) и 110 (З) нельзя добавлять новые узлы ниже этих кодов. Используем код 10 (два двоичных знака) для К. Тогда для Ч останется код 1110 (четыре двоичных знака).
Подсчет двоичных знаков
Подсчитаем общее количество двоичных знаков для кодирования слова «КАЗАЧКА»:
- К — 10 (2 знака)
- А — 0 (1 знак)
- З — 110 (3 знака)
- А — 0 (1 знак)
- Ч — 1110 (4 знака)
- К — 10 (2 знака)
- А — 0 (1 знак)
Итого: 2 + 1 + 3 + 1 + 4 + 2 + 1 = 14 двоичных знаков.
Вывод
Минимально возможное количество двоичных знаков для кодирования слова «КАЗАЧКА» с учетом прямого условия Фано составляет 14.