Решение: Условие Фано для кодов
По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова 0, 11, 1000, 1011 соответственно.
Укажите минимальную сумму длин кодовых слов для букв Д и Е, при котором код будет удовлетворять условию Фано.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение по шагам
4 шагаКодовое слово 0 является началом любого слова, начинающегося с 0, поэтому дополнительные кодовые слова не могут начинаться с 0.
В ветви 1 уже используются слова 11, 1000 и 1011. Чтобы не нарушить условие Фано, новые слова должны быть свободными листьями двоичного дерева.
Наименьшие свободные кодовые слова имеют длину 4: например, 1001 и 1010. Они не являются началами или окончаниями других заданных слов.
Сумма длин двух новых кодовых слов равна:
$$4+4=8$$Где здесь ошибаются
Используют кодовое слово 10, хотя оно является началом слов 1000 и 1011.
Выбирают слова, начинающиеся с 0, несмотря на наличие кодового слова 0.
Минимизируют длину только одного кодового слова, не проверяя условие Фано для второго.