6. Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, И использовали соответственно кодовые слова 00, 01, 100, 110. Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение:

Задача на построение префиксного кода (условие Фано). Нам даны кодовые слова для некоторых букв, и нужно найти кратчайшее возможное кодовое слово для буквы П, которое не будет являться началом или продолжением существующих кодов.

Известные кодовые слова:

• К: 00
• Л: 01
• М: 100
• Н: 110

Построение дерева кодов:

Начнем с корневого узла (пустое слово). От него отходят две ветки: 0 и 1.

1. 0: От ветки 0 отходят 0 и 1.
   - 00 (К) — это законченное кодовое слово. Дальнейшее ветвление от него невозможно (т.к. оно должно быть префиксным).
   - 01 (Л) — это законченное кодовое слово. Дальнейшее ветвление от него невозможно.
2. 1: От ветки 1 отходят 0 и 1.
   - 10: От ветки 10 отходят 0 и 1.
   - 100 (М) — законченное кодовое слово. Дальнейшее ветвление невозможно.
   - 101 — свободная ветка.
   - 11: От ветки 11 отходят 0 и 1.
   - 110 (Н) — законченное кодовое слово. Дальнейшее ветвление невозможно.
   - 111 — свободная ветка.

Поиск кратчайшего кода для П:

Теперь ищем кратчайшие свободные кодовые слова. Наша задача — найти такие кодовые слова для буквы П, которые не являются префиксами существующих кодов и для которых не существует существующих кодов в качестве префиксов.

Рассмотрим свободные ветки:

• 101: Это свободная ветка. Она короче, чем 111.
• 111: Это также свободная ветка.

Если мы назначим П = 101, то у нас остаются свободными ветки, которые начинаются с 101 (например, 1010, 1011) и ветка 111. Код 101 удовлетворяет условию префиксности.

Если мы назначим П = 111, то у нас остаются свободными ветки, которые начинаются с 111 (например, 1110, 1111) и ветка 101.

Среди свободных ветвей 101 и 111, наименьшим числовым значением обладает 101.

Таким образом, кратчайшим возможным кодовым словом для буквы П является 101.

Проверка:

Кодовые слова: К=00, Л=01, М=100, Н=110, П=101. Ни одно из этих слов не является началом другого. Например, 101 не является началом 100 или 110, и наоборот. 100 не является началом 101 или 110.