По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код,
Вопрос от пользователя
По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: О, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование.
Если таких кодов несколько, укажите код с наименьшим числовым значением
Ответ от эксперта
Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:
Легко заметить, что ближайшие от корня свободные листы (т.е. свободные коды с наименьшей длиной) — это 101 и 110. Наименьшее числовое значение имеет код 101.
Ответ: 101.
