Решение: Кодирование по условию Фано
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали кодовые слова 000, 001, 10, 11 соответственно. Для двух оставшихся букв — Д и Е — кодовые слова неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение по шагам
3 шагаКодовые слова 000 и 001 занимают две ветви, начинающиеся с 00, а слова 10 и 11 — обе ветви, начинающиеся с 1.
Единственная свободная ветвь минимальной длины — 01. Однако если присвоить 01 букве Д, то любое кодовое слово для Е, начинающееся с 01, будет иметь 01 своим началом, что нарушит условие Фано.
Поэтому ветвь 01 нужно разделить на два кодовых слова одинаковой длины: 010 и 011. Букве Д выбирают слово с наибольшим числовым значением.
$$011 > 010$$Где здесь ошибаются
Выбрать 01, не учитывая необходимость кодового слова для второй оставшейся буквы.
Считать допустимым код, являющийся началом другого кодового слова.
Выбрать 010 вместо 011, не применив условие о наибольшем числовом значении.