Карточки
Тесты
Главная
Курсы
Подписка
4. Кодирование и декодирование информации: #291224
По каналу связи передаются сообщения, содержащие только буквы из набора: А, Б, К, Р, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений.
Кодовые слова для некоторых букв известны: К — $01$, Р — $001$. Для трёх оставшихся букв Б, Н и А кодовые слова неизвестны.
Какое количество двоичных знаков потребуется для кодирования слова БАРАБАН, если известно, что оно закодировано минимально возможным количеством двоичных знаков?
Известны кодовые слова:
- К — $01$;
- Р — $001$.
Одноразрядный код $0$ использовать нельзя, так как он является началом кодов $01$ и $001$. Код $1$ использовать можно, но тогда два других кодовых слова должны иметь длину не менее $4$: например, $0000$ и $0001$. Такой вариант не будет оптимальным.
Без одноразрядного кода можно использовать два свободных двухразрядных слова:
$10$ и $11$.
Для третьей буквы подходит код $000$. Получаем, например:
- А — $10$;
- Б — $11$;
- Н — $000$.
Все кодовые слова
$01$, $001$, $10$, $11$, $000$
удовлетворяют условию Фано.
В слове БАРАБАН:
- буква А встречается $3$ раза;
- буква Б — $2$ раза;
- буква Р — $1$ раз;
- буква Н — $1$ раз.
Количество двоичных знаков: $3\cdot2+2\cdot2+1\cdot3+1\cdot3=16$.
20
