Шешімі: Минимальное кодирование слова
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 1, Н – 001. Для трёх оставшихся букв А, З и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАНТАТА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Шешімін қадамдап көрсету
5 қадамВ слове КАНТАТА буква К встречается 1 раз, Н — 1 раз, А — 3 раза, Т — 2 раза.
Кодовое слово $К=1$ означает, что кодовые слова остальных букв должны начинаться с $0$. С учётом слова $Н=001$ минимальный набор длин для трёх неизвестных кодов можно выбрать как $2$, $4$, $4$: например, $З=01$, $А=0000$, $Т=0001$.
Чтобы длина кодирования была минимальной, код минимальной длины назначаем букве А, которая встречается чаще всего. Тогда длины кодов можно распределить так: $|А|=2$, $|Т|=4$, $|З|=4$.
Суммарная длина кодирования слова равна $1\cdot|К|+3\cdot|А|+1\cdot|Н|+2\cdot|Т|$.
Подставляем длины кодов: $1\cdot1+3\cdot2+1\cdot3+2\cdot4=18$.
Где здесь ошибаются
Не учитывать, что буква А встречается в слове три раза, а буква Т — два раза.
Назначить короткое кодовое слово букве, которая встречается реже.
Нарушить условие Фано, выбрав кодовое слово, являющееся началом другого.