Задание 5

Теория

Для успешного решения этого задания необходимо помнить условие Фано.

Условие Фано: для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, достаточно, чтобы никакой код не был началом другого (более длинного) кода.

Обратное условие Фано также является достаточным условием однозначного декодирования неравномерного кода. В нём требуется, чтобы никакой код не был окончанием другого (более длинного) кода.

Для возможности однозначного декодирования досточно выполнения одного из условий — или прямого, или обратного.

Пример задания

Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.

Воспользуемся ускорителем

в о д о п а д

01 00 10 00 11 100 10

Полученное число разобьем на тройки:

010 010 001 110 010

2 2 1 6 2

получаем 22162₈.

Ответ 22172.

Пример задания.

Вспомним условия, указанные в теории, получаем, что С не может быть равно 1, так как 11 может быть расшифровано как А и как СС. Следующее - 00 также не подходит (00 ВВ или С). Далее 10. Так как оно подходит под условия, это и будет кодом для С.

Ответ 10.

Пример задания.

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:

a b c d e

000 110 01 001 10

Какой набор букв закодирован двоичной строкой 1100000100110?

Разкодирование лучше начать сначала:

110 000 01 001 10

b a с d е

Ответ bacde.