Задание 5
ТЕМА 5
"Кодирование и декодирование информации"
Пример 1
Для кодирования некоторой последовательности, состоящей из букв С, К, А, Н, Е, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв С, К, А, Н использовали соответственно кодовые слова 000, 001, 111, 01. Для двух оставшихся букв – Е и Р – длины кодовых слов неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы Е, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Решение
Построим дерево для известных кодовых слов и увидим какие ветви не заблокированы по условию Фано:
С – 000; К – 001; А – 111; Н – 01.
Две ветви с кодами 10 и 110 можно использовать для кодирования букв Е и Р. По условию задачи нужно определить код для буквы Е с наименьшим числовым значением, тогда:
Ответ: 10
Пример 2
По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв Г, Д, Е используются такие кодовые слова: Г — 0, Д – 100, Е – 101. Какова наименьшая возможная суммарная длина всех кодовых слов?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.
Решение
Построим дерево для известных кодовых слов и увидим какие ветви не заблокированы по условию Фано:
Для дальнейшего кодирования можно использовать коды: 1100, 1101, 111. Также можно взять и другую последовательность с наименьшей возможной длиной кодов для букв А, Б и В: 110, 1110 и 1111.
В итоге получаем сумму длин кодов: 1 + 3 + 3 + 3 + 4 + 4 = 18.
Ответ: 18
Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу