3. По каналу связи передаются сообщения, содержащие только восемь букв: Е, К, О, П, Р, С, Т, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: О — 10, П — 001, С — 0001, Т — 111. Для четырёх оставшихся букв Е, К, Р и Я кодовые слова неизвестны. Известно, что слово ПЕРЕКРЕСТОК было закодировано минимально возможным количеством двоичных знаков. Какое наименьшее суммарное количество двоичных знаков при этом было использовано для кодовых слов оставшихся букв Е, К, Р, Я? В ответе запишите суммарную длину кодовых слов букв Е, К, Р и Я.

Решение:

Даны кодовые слова для некоторых букв:

• О: 10 (длина 2)
• П: 001 (длина 3)
• С: 0001 (длина 4)
• Т: 111 (длина 3)

Слово для кодирования: ПЕРЕКРЕСТОК.

Состав слова: П (1), Е (2), Р (2), Е (1), К (1), Р (1), Е (1), С (1), Т (1), О (1), К (1).

Итого: П(1), Е(4), Р(3), К(2), С(1), Т(1), О(1).

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

• П: 001 (длина 3)
• С: 0001 (длина 4)
• Т: 111 (длина 3)
• О: 10 (длина 2)

Общая длина известных кодов для слова ПЕРЕКРЕСТОК:

1 * (длина П) + 1 * (длина С) + 1 * (длина Т) + 1 * (длина О) = 1 * 3 + 1 * 4 + 1 * 3 + 1 * 2 = 3 + 4 + 3 + 2 = 12.

Частоты букв в слове:

• Е: 4
• К: 2
• Р: 3
• П: 1
• С: 1
• Т: 1
• О: 1

Для минимизации общего количества двоичных знаков, буквы с наибольшей частотой должны иметь наименьшую длину кода. Неизвестные коды для Е, К, Р. У них наибольшие частоты: Е(4), Р(3), К(2).

Условие Фано означает, что ни один код не является префиксом другого. Чтобы минимизировать суммарную длину, мы должны назначить самые короткие доступные коды буквам с наибольшей частотой.

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

• О: 10 (2)
• Т: 111 (3)
• П: 001 (3)
• С: 0001 (4)

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

Коды, которые не являются префиксами других:

• 2-значные: 10 (используется О). Остальные 2-значные коды (00, 01, 11) являются префиксами для более длинных кодов, или не могут быть использованы, т.к. содержат префикс (например, 010 - префикс 01).
• 3-значные: 111 (используется Т), 001 (используется П).
• 4-значные: 0001 (используется С).

Учитывая условие Фано, оставшиеся буквы (Е, К, Р) должны получить коды. Нам нужно назначить самые короткие коды буквам с самой высокой частотой. Частоты: Е(4), Р(3), К(2).

Нам нужны коды для Е, К, Р. Наиболее вероятные следующие доступные короткие коды:

• Можем попробовать следующие варианты, исходя из свободных веток дерева кода:
• Для буквы с наибольшей частотой (Е, 4) — самый короткий доступный код.
• Для буквы со второй по частоте (Р, 3) — следующий короткий код.
• Для буквы с третьей по частоте (К, 2) — следующий короткий код.

Рассмотрим дерево кодов. У нас есть: 10, 001, 111, 0001.

Свободные ветки (не являющиеся префиксами):

• От 10: 100, 101 (длины 3).
• От 001: 0010, 0011 (длины 4).
• От 111: 1110, 1111 (длины 4).
• От 0001: 00010, 00011 (длины 5).

Самые короткие свободные коды: 100 (3), 101 (3). Следующие по краткости: 0010 (4), 0011 (4), 1110 (4), 1111 (4).

Наиболее короткие коды, которые мы можем дать: 100, 101, 0010.

Назначаем их по частоте:

• Е (частота 4): 100 (длина 3)
• Р (частота 3): 101 (длина 3)
• К (частота 2): 0010 (длина 4)

Теперь проверим, что все коды удовлетворяют условию Фано:

• О: 10
• Т: 111
• П: 001
• С: 0001
• Е: 100
• Р: 101
• К: 0010

Проверим префиксы:

• 100 не является префиксом для 10, 111, 001, 0001, 101, 0010.
• 101 не является префиксом для 10, 111, 001, 0001, 100, 0010.
• 0010 не является префиксом для 10, 111, 001, 0001, 100, 101.

Суммарная длина кодовых слов оставшихся букв Е, К, Р:

Длина(Е) + Длина(К) + Длина(Р) = 3 + 4 + 3 = 10.

Ответ: 10