5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано
5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано.
Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?
Примечание.
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Ответ: 19 ___________________________.
Решение:
1) Кодируем:
А 0
Б 10
В 110
Г 1110
Д 1111
Е 10000
итого:19 Ответ: 19
1. Еще одна задача
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А–111, Б–110, В–100, Г–0.
Укажите, каким из приведенных ниже кодовых слов может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
1) 00; 2) 001; 3) 10; 4) 101
Решение. Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого). Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным. Однако, в отличие от задачи из демо-варианта, здесь по условию более одного варианта может приводить к тому, что получится код, допускающий однозначное декодирование. Поэтому нужно перебирать варианты от более коротких к более длинных и, если вариант не приводит к префиксному коду, убеждаться, что этот вариант действительно дает код, не допускающий однозначного декодирования.
1) Код для Д: 00 – не допускает однозначного декодирования (00 допускает две расшифровки: ГГ и Д).
2) Код для Д: 10 – не допускает однозначного декодирования (100 допускает две расшифровки: В и ДГ).
3) Код для Д: 001 – не допускает однозначного декодирования (00100 допускает две расшифровки: ГГВ и ДГГ).
4) Код для Д: 101 – вместе с кодами для А, Б, В, Г образует префиксный код.
Правильный ответ: 4
Еще одна Задача 2.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–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. Условие Фано является достаточным условием того, что код допускает однозначное декодирование, но не является необходимым. То есть код может допускать однозначное декодирование, но не удовлетворять условию Фано. Простейший пример таких кодов – т.н. постфиксные коды. Это такие коды, в которых никакое кодовое слово не является концом другого кодового слова. Для этих кодов расшифровка производится так же, как и для префиксных кодов, но двигаясь справа налево.
Замечание 2. В рассмотренной задаче А достаточно найти один вариант, удовлетворяющий требованиям задачи. НЕ ТРЕБУЕТСЯ доказывать, что при остальных вариантах код не будет допускать однозначного декодирования. Однако, в данном случае это сделать несложно. А именно:
1) Код Д: 00. Тогда 000000 допускает две расшифровки: ББ и ДДД.
2) Код Д: 01. Тогда 011 допускает две расшифровки: Г и ДА.
2) Код Д: 11. Тогда 11 допускает две расшифровки: АА и Д.
| № | Наименование | Время | Стоимость | |
|---|---|---|---|---|
| 1 |
Дистанционный репетитор по информатике по Skype |
1 час | от 600 руб. |
Со студентами провожу занятия по высшей математике, математическому анализу, теории вероятности и математической статистике, линейной алгебре. Индивидуальные занятия в Москве в офисе на м.Китай-город.
Подготовку к ЕГЭ школьников по математике, физике и информатике,
занятия со студентами по высшей математике, физике.
Демоверсия ЕГЭ 2017 по математике. Профильный уровень.
Демоверсия ЕГЭ 2017 по физике.
Демоверсия ЕГЭ 2017 по информатике
Вот основные темы по высшей математике: пределы, последовательности, производные, интегрирование, дифференцирование, линейная алгебра, аналитическая геометрия, теория вероятности.
Решение задач:
На главную страницу: запись на занятие с репетитором по математике, физике и информатике
