Question

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А—1, Б-000, В-001, Г—011.
Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

Answer 1

Вариантов кодового слова, которым может быть закодирована буква Д, много, поэтому проверим предложенные ответы, начиная с самых коротких:
1)   00 - является префиксом слова 000 (буква Б), отсюда, например, входящую последовательность    000000    можно    декодировать    двумя    различными    способами: 00 00 00 (ДДД) и 000 000 (ББ). Этот вариант ответа не подходит;
2)   01 - является префиксом слова 011 (буква Г). Входящую последовательность 011 можно декодировать двумя различными способами: 011 (Г) и 01 1 (ДА). Этот вариант ответа также не подходит;
3)   11 - не является префиксом ни одного из слов, но при этом кодовое слово 1 (А) является префиксом слова 11 (Д). Входящую последовательность 11 можно декодировать двумя различными способами: 11 (Д) и 1 1 (АА). Этот вариант ответа не подходит;
4)   010 - не является префиксом ни одного из слов и, при этом, ни одно из слов кода не является префиксом слова 010.