Карточки
Тесты
Главная
Курсы
Куратор
Подписка
4. Кодирование и декодирование информации: #291231
По каналу связи передаются сообщения, содержащие только буквы из набора: А, В, Д, К, Р, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Р — $1$, К — $0000$. Для четырёх оставшихся букв А, В, Д и Н кодовые слова неизвестны.
Какое количество двоичных знаков потребуется для кодирования слова КАРАВАН, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Код буквы Р равен $1$, поэтому все остальные кодовые слова должны начинаться с $0$.
Код $0$ использовать нельзя, так как он является началом кода К — $0000$. Кратчайший свободный код — $01$. Его выгодно отдать букве А, поскольку в слове КАРАВАН она встречается $3$ раза.
Для остальных букв можно выбрать, например, такие коды:
| Буква | Кодовое слово |
|---|---|
| Р | $1$ |
| К | $0000$ |
| А | $01$ |
| В | $001$ |
| Н | $00010$ |
| Д | $00011$ |
Код удовлетворяет условию Фано. Буква Д в слове КАРАВАН не встречается, поэтому ей можно назначить один из наиболее длинных кодов.
В слове КАРАВАН:
- К встречается $1$ раз;
- А — $3$ раза;
- Р — $1$ раз;
- В — $1$ раз;
- Н — $1$ раз.
Количество двоичных знаков: $4+3\cdot2+1+3+5=19$.
Меньше получить нельзя: после выбора кода $01$ для буквы А в ветви $00$ необходимо разместить код К — $0000$ и ещё три кодовых слова. Минимальные возможные длины этих трёх слов — $3$, $5$, $5$ или $4$, $4$, $4$, поэтому суммарная длина кодов букв В и Н не может быть меньше $8$.
20
