По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В используются такие кодовые слова: А: 100110, Б: 110010, В: 001011. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение:

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

• А: 100110
• Б: 110010
• В: 001011

Ни один из кодов не является префиксом другого. Нам нужно найти кратчайшее кодовое слово для буквы Г, при котором код останется однозначно декодируемым. Рассмотрим возможные кратчайшие коды (1, 2, 3 бита):

• 1-битные коды: 0, 1. Если взять любой из них, то код '0' станет префиксом для '001011' (В), а код '1' станет префиксом для '100110' (А) и '110010' (Б). Поэтому 1-битные коды не подходят.
• 2-битные коды: 00, 01, 10, 11.
• Если взять 00 для Г: код 00 будет префиксом для В (001011). Не подходит.
• Если взять 01 для Г: код 01 не является префиксом для А, Б, В. Это возможно.
• Если взять 10 для Г: код 10 не является префиксом для А, Б, В. Это возможно.
• Если взять 11 для Г: код 11 будет префиксом для Б (110010). Не подходит.

У нас осталось два варианта: '01' и '10'. Оба они кратчайшие (2 бита) и не являются префиксами других кодов.

По условию, если таких кодов несколько, нужно указать код с наименьшим числовым значением. Числовое значение '01' равно 1, а '10' равно 2. Наименьшее значение у кода '01'.

Ответ: 01