Для кодирования некоторой последовательности, состоящей из букв А, Б, В и Г, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.
Для букв А, Б и В использовали такие кодовые слова:
А – 0, Б – 10, В – 110.
Каким кодовым словом может быть закодирована буква Г?
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
Для того чтобы закодировать букву Г таким образом, чтобы двоичный код удовлетворял свойству однозначного декодирования, необходимо, чтобы никакое кодовое слово не было префиксом другого кодового слова. Это условие позволяет однозначно декодировать последовательность, не вызывая путаницы при разбиении на кодовые слова.
У нас уже есть следующие кодовые слова:
Рассмотрим возможные варианты для буквы Г:
Следовательно, нужно выбрать кодовое слово, которое не начинается с "0", "10" или "110", а также не является их префиксом.
Давайте проверим следующий вариант:
Таким образом, кратчайшее возможное кодовое слово для буквы Г, удовлетворяющее условию однозначного декодирования, будет "111".
Для того чтобы обеспечить однозначное декодирование, кодовое слово для буквы Г не должно быть префиксом для кодовых слов других букв. Таким образом, возможны следующие варианты:
При таком кодировании полученная двоичная последовательность будет однозначно декодирована, так как слова для каждой буквы не являются префиксами друг друга.
