Задание 8. Тип заданий 5: кодирование информации.
- Задание:
По каналу связи передаются сообщения, содержащие пять букв: М, Я, Ч, И, К. Для передачи используется неравномерный двоичный код, допускающий однозначное кодирование. Для букв М, Я, Ч, И используются такие кодовые слова: М: 0, Я: 100, Ч: 110, И: 101.
Укажите кратчайшее кодовое слово для буквы К, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
- Решение:
Неравномерный двоичный код удовлетворяет условию Фано: "В неравномерном двоичном префиксном коде ни одно кодовое слово не может быть началом другого слова". Проще говоря, если у нас буква Я имеет код 100, это значит, что никакая другая буква не может иметь код 1 или 10, так как в этом случае код этой буквы будет началом кода буквы Я. Рассмотрим данные коды: М: 0 Я: 100 Ч: 110 И: 101 Сразу отметим, что код буквы К не может начинаться с 0, так как в этом случае буква М будет началом кода буквы К. Также нам не подходят коды 1, 10, 11, так как это начала кодов других букв. Рассмотрим трёхзначные коды. 100, 101 и 110 уже заняты, остаётся код 111. Ответ: 111
|
Комментарии ()
Нет комментариев. Ваш будет первым!