Embedded Files
(до 2021 года задание 5)
Теория
Для успешного решения этого задания необходимо помнить условие Фано.
Условие Фано: для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, достаточно, чтобы никакой код не был началом другого (более длинного) кода.
Обратное условие Фано также является достаточным условием однозначного декодирования неравномерного кода. В нём требуется, чтобы никакой код не был окончанием другого (более длинного) кода.
Для возможности однозначного декодирования досточно выполнения одного из условий — или прямого, или обратного.
Для решения этого задания стоит вспомнить теорию графов для подсчета количества вариантов.
Разберем сразу на примере:
Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв П и Р кодовые слова неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Итак, у нас есть точка отсчета - начальное положение. Обозначим его *, Все коды могут начится только с одного из двух вариантов: 0 или 1:
Старые типы
Пример задания
Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.
Воспользуемся ускорителем
в о д о п а д
01 00 10 00 11 100 10
Полученное число разобьем на тройки:
010 010 001 110 010
2 2 1 6 2
получаем 221628.
Ответ 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.
Google Sites
Report abuse