Минимальное кодирование слова
По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 1, Н – 001. Для трёх оставшихся букв А, З и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАНТАТА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Условие как в банке ФИПИ — открыть и сверить
| По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Н, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: К – 1, Н – 001. Для трёх оставшихся букв А, З и Т кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КАНТАТА, если известно, что оно закодировано минимально возможным количеством двоичных знаков? | |||
| |
Формат: өлшем бірліктері жоқ сан немесе сөз; бөлшек бөлігін үтірмен бөліңіз.
1Мягкая — с чего смотретьдеңгей 1 из 3
Постройте дерево кодов с уже занятыми кодовыми словами $1$ и $001$. Какие самые короткие свободные ветви можно использовать?
2Жетекші — қандай сандарды есептеудеңгей 2 из 3
Из-за кодового слова $К=1$ все остальные слова должны начинаться с $0$. Код $Н=001$ запрещает использовать его как начало другого кодового слова.
3Тікелей — іс жүзінде шешімдеңгей 3 из 3
Можно взять длины кодов для трёх неизвестных букв равными $2$, $4$ и $4$. Самое короткое слово назначьте букве А, которая встречается три раза, а длину $4$ — букве Т, встречающейся два раза.