Подготовка к ЕГЭ : Задание 1

Задание 1

Задача 1.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1, Б–000,  В–001,  Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

1)  00              2)  01              3)  11             4)  010

            Решение. Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого).  Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным.

1)      00 – не подходит (является началом кодового слова 000 для буквы Б);

2)      01 – не подходит (является началом кодового слова 011 для буквы Г);

3)      11– не подходит (является продолжением(!) кодового слова 1 для буквы А);

4)      010 – подходит! (не является ничьим началом и никто не является его началом).

Ответ: 4.

Условие Фано является достаточным условием того, что код допускает однозначное декодирование, но не является необходимым. То есть код может допускать однозначное декодирование, но не удовлетворять условию Фано. Простейший пример таких кодов – т.н. постфиксные коды. Это такие коды, в которых никакое кодовое слово не является концом другого кодового слова. Для этих кодов расшифровка производится так же, как и для префиксных кодов, но двигаясь справа налево.

В рассмотренной задаче А достаточно найти один вариант, удовлетворяющий требованиям задачи. НЕ ТРЕБУЕТСЯ доказывать, что при остальных вариантах код не будет допускать однозначного декодирования. Однако, в данном случае это сделать несложно. А именно:

            1) Код Д: 00. Тогда 000000 допускает две расшифровки: ББ и ДДД.

            2) Код Д: 01. Тогда 011 допускает две расшифровки: Г и ДА.

            2) Код Д: 11. Тогда 11 допускает две расшифровки: АА и Д.

2. Задача

            Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова:  А–111, Б–110, В–100, Г–0.

Укажите, каким из приведенных ниже кодовых слов может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1) 00;   2) 001; 3) 10;   4) 101

            Решение. Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого).  Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным. Однако, в отличие от задачи из демо-варианта, здесь по условию более одного варианта может приводить к тому, что получится код, допускающий однозначное декодирование. Поэтому нужно перебирать варианты от более коротких к более длинных и, если вариант не приводит к префиксному коду, убеждаться, что этот вариант действительно дает код, не допускающий однозначного декодирования.

1) Код для Д: 00 – не допускает однозначного декодирования (00 допускает две расшифровки: ГГ и Д).

2) Код для Д: 10 – не допускает однозначного декодирования (100 допускает две расшифровки: В и ДГ).

3) Код для Д: 001 – не допускает однозначного декодирования (00100 допускает две расшифровки: ГГВ и ДГГ).

4) Код для Д: 101 – вместе с кодами для А, Б, В, Г образует префиксный код.

Правильный ответ: 4