Решение: Условие Фано для кодов
По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые слова $1$, $00$, $0100$, $0111$ соответственно.
Укажите минимальную сумму длин кодовых слов для букв Д и Е, при которых код будет удовлетворять условию Фано.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение по шагам
4 шагаКодовое слово $1$ запрещает использовать любые новые слова, начинающиеся с $1$, поскольку оно стало бы началом этих слов.
$$w_{Д}, w_{Е} \text{ начинаются с } 0$$Слово $00$ занимает всю ветвь $00$, поэтому новые кодовые слова не могут начинаться с $00$.
В ветви $01$ уже находятся слова $0100$ и $0111$. Слова $010$ и $011$ использовать нельзя, так как они являются началами существующих кодовых слов.
Минимальные свободные слова в этих ветвях имеют вид $0101$ и $0110$. Оба слова имеют длину $4$ и не являются началами друг друга или уже заданных слов.
$$|0101|+|0110|=4+4=8$$Где здесь ошибаются
Использовать кодовое слово, начинающееся с $1$, поскольку слово $1$ уже является его началом.
Выбрать слова $010$ или $011$, которые являются началами кодовых слов $0100$ и $0111$.
Считать длину одного из новых слов равной $3$, не проверив условие Фано.