Question

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный троичный код, позволяющий однозначно декодировать троичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А–11, Б–12, В–21, Г–22. Укажите, каким кодовым словом может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

Answer 1

Итак, нужно, чтобы любая троичная последовательность декодировалась однозначно. Смотрим на варианты:
0, 01, 02, 10
Если выбрать кодом 0, декодировка будет происходить однозначно (ни в одном из остальных кодов нуля нет). А если выбирать коды из двух цифр - опять-таки всё будет однозначно, т.к. все коды букв будут иметь одинаковую длину (например, для декодировки 1121222202 надо будет разбить строку на подстроки длины 2: 11 21 22 22 02, и расшифровать каждую подстроку). Без условия на длину слова подошли бы они все.

Нужен код наименьшей длины, поэтому в ответы пойдёт 0.

Answer 2

Для кодирования буквы Д необходимо использовать кодовое слово, которое не совпадает с кодовыми словами для других букв, чтобы обеспечить однозначное декодирование.

Так как кодовые слова для А, Б, В и Г состоят из двух цифр троичной системы счисления, то кодовое слово для буквы Д также должно состоять из двух цифр.

При этом необходимо выбрать кодовое слово, которое не повторяется среди уже использованных. Таким образом, мы можем использовать кодовое слово 20 или 02 для буквы Д.

Оба этих кодовых слова удовлетворяют свойству однозначного декодирования, так как они не совпадают с кодовыми словами для других букв. Однако, кратчайшим кодовым словом является 20, состоящее из двух цифр.