По каналу связи передаются шифрованные сообщения, содержащие только прописные буквы русского алфавита. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 01, 10, 11 и 000 соответственно.
Укажите самое короткое кодовое слово для буквы Е, при котором код не будет удовлетворять условию Фано, при этом в записи самого этого слова должно использоваться более одного символа, а само слово не должно совпадать ни с одним из используемых слов для кодирования букв А, Б, В и Г. Если таких слов несколько, то укажите слово с минимальным числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Укажите самое короткое кодовое слово для буквы Е, при котором код не будет удовлетворять условию Фано, при этом в записи самого этого слова должно использоваться более одного символа, а само слово не должно совпадать ни с одним из используемых слов для кодирования букв А, Б, В и Г. Если таких слов несколько, то укажите слово с минимальным числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Подсказка 1. Запиши все известные кодовые слова и вычеркни те из них, которые являются началом другого кода.
Подсказка 2. Условие Фано: ни одно кодовое слово не начинается другого, поэтому допустимые слова ищут на дереве кодов среди свободных листьев.
Подсказка 3. Выбирай самое короткое слово, а при равной длине — с наименьшим двоичным значением. Ловушка: свободное слово может перекрыть оставшиеся буквы.
Разбор.
Решение.
Букву А кодируем кодовым словом 01, букву Б кодируем кодовым словом 10, букву В кодируем кодовым словом 11, букву Г кодируем кодовым словом 000. Для буквы Е нельзя использовать кодовые слова 1 и 0, так как кодовые слова должны быть длиннее одного символа. Также нельзя использовать кодовые слова 01, 10, 11 и 000, так как они заняты буквами А, Б, В и Г. Для буквы Е можно использовать код 00, так как он длиннее одного символа и не используется для кодирования других букв, при этом не удовлетворяет условию Фано.
Ответ: 00.
Примечание.
Заметьте, что код буквы Е по условию НЕ должен удовлетворять условию Фано.
Ответ.
00