Пример задания
Р-13. По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:
а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);
б) общая длина закодированного сообщения должна быть как можно меньше.
Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?
1) А:0, Б:10, В:110, Г:111
2) А:0, Б:10, В:01, Г:11
3) А:1, Б:01, В:011, Г:001
4) А:00, Б:01, В:10, Г:11
Решение:
сначала выберем коды, в которых ни одно кодовое слово не совпадет с началом другого (такие коды называю префиксными)
для кода 2 условие «а» не выполняется, так как кодовое слово буквы В (01) начинается с кодового слова буквы А (0)
для кода 3 условие «а» не выполняется, так как кодовое слово буквы В (011) начинается с кодового слова буквы Б (01)
для кодов 1 и 4 условие выполняется, их рассматриваем дальше
считаем общее количество битов в сообщении для кода 1:
16∙1 + 8·2 + 4∙3 + 4∙3 = 56 битов
считаем общее количество битов в сообщении для кода 4:
16∙2 + 8·2 + 4∙2 + 4∙2 = 64 бита
код 1 даёт наименьшую длину сообщения, поэтому выбираем его
Ответ: 1.
Ещё пример задания
Р-12. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
1) 7 2) 8 3) 9 4) 10
Решение (способ 1, исключение вариантов):
условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова
поскольку уже есть кодовое слово 0, ни одно другое кодовое слово не может начинаться с 0
поскольку есть код 110, запрещены кодовые слова 1, 11; кроме того, ни одно другое кодовое слово не может начинаться с 110
таким образом, нужно выбрать еще два кодовых слова, для которых выполняются эти ограничения
есть одно допустимое кодовое слово из двух символов: 10
если выбрать кодовое слово 10 для буквы В, то остаётся одно допустимое трёхсимвольное кодовое слово – 111, которое можно выбрать для буквы Г
таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов
если же не выбрать В – 10, то есть три допустимых трёхсимвольных кодовых слова: 100, 101 и 110; при выборе любых двух их них для букв В и Г получаем суммарную длину кодовых слов 10, что больше 9; поэтому выбираем вариант 3 (9 символов)
Ответ: 3.
Решение (способ 2, построение дерева):
условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков;
построим дерево для заданных кодовых слов А – 0 и Б – 110:
штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» листья для кодовых слов букв В (10) и Г (111)
Задачи
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти коды представлены в таблице:
a b c d e
000 110 01 001 10
Определите, какой набор букв закодирован двоичной строкой 1100000100110
1) baade 2) badde 3) bacde 4) bacdb
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А - 001, Б - 010, В - 000, Г - 011.
Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д.
Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.
1) 00 2) 01 3) 0000 4) 101
Бонус:
