Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) это невозможно
2) для буквы В – 000
3) для буквы Б – 0
4) для буквы Г – 11
Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.
Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.
Вариант 3 не подходит, потому что 0 является началом кода 0001.
Вариант 4 не подходит, потому что код 1 является началом кода 111.
Вариант 2 подходит, так как не нарушает условия Фано.
Правильный ответ указан под номером 2.
Здравствуйте! Решая задачу по вашему принципу, я столкнулась с проблемой. Приведу пример:
А - 1; Б - 000; В - 0101; Г - 001; Д - 011.
Ответы:
А) для буквы В - 010;
Б) это невозможно;
В) для буквы В - 101;
Г) для буквы Г - 01.
По условию Фано подходят варианты А) и Б).
Но, анализируя ответ В), получаем неоднозначность раскодирования: 1011 - (АД или ВА). По вашему условие Фано является достаточным для решения подобных задач. Как быть здесь?
В вашем примере верный ответ — А. Если для буквы В выбрать код 101, то 1 будет являться началом кода для буквы В, нарушится условие Фано.