Базовый уровень, время – 2 мин)
Тема: Кодирование и декодирование информации.
Что нужно знать:
· кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)
· обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход
· один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)
· кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование
· закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;
|
|
· закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;
· условие Фано – это достаточное, но не необходимое условие однозначного декодирования.
Пример задания
Р-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
Решение:
1) сначала выберем коды, в которых ни одно кодовое слово не совпадет с началом другого (такие коды называю префиксными)
2) для кода 2 условие «а» не выполняется, так как кодовое слово буквы В (01) начинается с кодового слова буквы А (0)
3) для кода 3 условие «а» не выполняется, так как кодовое слово буквы В (011) начинается с кодового слова буквы Б (01)
4) для кодов 1 и 4 условие выполняется, их рассматриваем дальше
5) считаем общее количество битов в сообщении для кода 1:
16∙1 + 8·2 + 4∙3 + 4∙3 = 56 битов
6) считаем общее количество битов в сообщении для кода 4:
16∙2 + 8·2 + 4∙2 + 4∙2 = 64 бита
7) код 1 даёт наименьшую длину сообщения, поэтому выбираем его
|
|
8) Ответ: 1.
Пример задания
Р-12. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
1) 7 2) 8 3) 9 4) 10
Решение (способ 1, исключение вариантов):
1) условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова
2) поскольку уже есть кодовое слово 0, ни одно другое кодовое слово не может начинаться с 0
3) поскольку есть код 110, запрещены кодовые слова 1, 11; кроме того, ни одно другое кодовое слово не может начинаться с 110
4) таким образом, нужно выбрать еще два кодовых слова, для которых выполняются эти ограничения
5) есть одно допустимое кодовое слово из двух символов: 10
6) если выбрать кодовое слово 10 для буквы В, то остаётся одно допустимое трёхсимвольное кодовое слово – 111, которое можно выбрать для буквы Г
7) таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов
8) если же не выбрать В – 10, то есть три допустимых трёхсимвольных кодовых слова: 100, 101 и 110; при выборе любых двух их них для букв В и Г получаем суммарную длину кодовых слов 10, что больше 9; поэтому выбираем вариант 3 (9 символов)
9) Ответ: 3.
Решение (способ 2, построение дерева):
1) условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков;
2) построим дерево для заданных кодовых слов А – 0 и Б – 110:
3) штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» листья для кодовых слов букв В (10) и Г (111)
4) таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов
5) Ответ: 3.