Карточки
Тесты
Главная
Курсы
Подписка
4. Кодирование и декодирование информации: #291238
По каналу связи передаются сообщения, содержащие только буквы из набора: В, Д, К, Н, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Н — $0$, К — $1001$. Для четырёх оставшихся букв В, Д, О и Р кодовые слова неизвестны.
Какое количество двоичных знаков потребуется для кодирования слова КОНОВОД, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Буква Н имеет код $0$, поэтому все остальные кодовые слова должны начинаться с $1$.
Код $1$ использовать нельзя, так как он является началом кода буквы К — $1001$. Код $10$ также использовать нельзя, поскольку он является началом кода $1001$.
Единственное возможное кодовое слово длины $2$ — $11$. Его выгодно назначить букве О, поскольку она встречается в слове КОНОВОД $3$ раза.
Остальные буквы можно закодировать так:
| Буква | Кодовое слово |
|---|---|
| Н | $0$ |
| К | $1001$ |
| О | $11$ |
| В | $1000$ |
| Д | $1010$ |
| Р | $1011$ |
Все кодовые слова удовлетворяют условию Фано.
Сделать сумму длин кодов букв В и Д меньше $8$ нельзя. В ветви $10$ уже расположен код К — $1001$, и в ней необходимо разместить ещё три кодовых слова. Поэтому для двух букв В и Д минимальная суммарная длина равна $4+4=8$.
В слове КОНОВОД:
- К встречается $1$ раз;
- О — $3$ раза;
- Н — $1$ раз;
- В — $1$ раз;
- Д — $1$ раз.
Общая длина закодированного слова: $4+3\cdot2+1+4+4=19$.
20
