Погода
Календарь
Март 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 123
45678910
11121314151617
18192021222324
25262728293031
Страницы сайта

Кодирование и декодирование информации.

  • Кодирование — это представление информации в форме, удобной для её хранения, передачи и обработки. Правило преобразования информации к такому представлению называется кодом.
  • Кодирование бывает равномерным и неравномерным:
  • при равномерном кодировании всем символам соответствуют коды одинаковой длины;
  • при неравномерном кодировании разным символам соответствуют коды разной длины, это затрудняет декодирование.

Пример: Зашифруем буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и посчитаем количество возможных сообщений:

двоичное кодирование

Таким образом, мы получили равномерный код, т. к. длина каждого кодового слова одинакова для всех кодов (2).

КОДИРОВАНИЕ И РАСШИФРОВКА СООБЩЕНИЙ

Декодирование (расшифровка) — это восстановление сообщения из последовательности кодов.

Для решения задач с декодированием, необходимо знать условие Фано:Условие Фано: ни одно кодовое слово не должно являться началом другого кодового слова (что обеспечивает однозначное декодирование сообщений с начала)Префиксный код — это код, в котором ни одно кодовое слово не совпадает с началом другого кодового слова. Сообщения при использовании такого кода декодируются однозначно.

  • если сообщение декодируется с конца, то его можно однозначно декодировать, если выполняется обратное условие Фано:
  • условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Однозначное декодирование обеспечивается:

Однозначное декодирование

Однозначное декодирование

Декодирование

Задание 1. Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится
1) 4B16                   2) 41116       3)BACD16  4) 102316 

Решение: Из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный. Последовательность БАВГ кодируется так: 01 00 10 11 = 1001011.

Разобьем  такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем  1001011 = 0100  10112 = 4B16  Ответ – 1.

Задание 2.  Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти  коды представлены в таблице:

Определить, какой набор букв закодирован двоичной строкой 0110100011000

1) EBCEA
2) BDDEA
3) BDCEA
4) EBAEA             

Решение:

1.Здесь используется неравномерное кодирование, при котором декодирование может быть неоднозначным, то есть, заданному коду может соответствовать несколько разных исходных сообщений

2.Попробуем декодировать с начала цепочки, первой буквой может быть B или E, эти случаи нужно рассматривать отдельно

3.Пусть первая буква – E с кодом 011, тогда остается цепочка 0100011000 для кода 0100011000 первой буквой может быть только B с кодом 01, тогда остается 00011000 (начало исходной цепочки – EB?)

для кода 00011000 первой буквой может быть только A с кодом 000, тогда остается 11000, а эта цепочка не может быть разложена на заданные коды букв

поэтому наше предположение о том, что первая буква – E, неверно

4.Пусть первая буква – B с кодом 01, тогда остается цепочка 10100011000

для кода 10100011000 первой буквой может быть только D с кодом 10, тогда остается 100011000  (можно полагать, что начало исходной цепочки – BD?)

для кода 100011000 первой буквой может быть только С с кодом 100, тогда остается 011000 (начало исходной цепочки – BDC?)

Несмотря на то, что среди ответов есть единственная цепочка, которая начинается с BDC, здесь нельзя останавливаться, потому что «хвост» цепочки может «не сойтись»

для кода 011000 на первом месте может быть B (код 01) или E (011); в первом случае «хвост» 1000 нельзя разбить на заданные коды букв, а во втором – остается код 000 (буква А), поэтому исходная цепочка может быть декодирована как BDCEA.  Ответ – 3

 Решение 2:

  1. для кода 0110100011000 последней буквой может быть только А (код 000),  тогда остается цепочка 0110100011
  2. для 0110100011 последней может быть только буква E (011),  тогда остается цепочка 0110100
  3. для 0110100 последней может быть только буква C (100),  тогда остается цепочка 0110
  4. для 0110 последней может быть только буква D (10),  тогда остается 01 – это код буквы B
  5. таким образом, получилась цепочка BDCEA. Ответ – 3

  Решение 3:

  1. в данном случае самое простое и надежное – просто закодировать все ответы, используя приведенную таблицу кодов, а затем сравнить результаты с заданной цепочкой
  2. получим

1) EBCEA – 01101100011000    2) BDDEA – 011010011000

3) BDCEA – 0110100011000     4) EBAEA – 01101000011000

  • сравнивая эти цепочки с заданной, находим, что правильный ответ – 3.

Задание 3.  Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 1              2) 1110                3) 111                  4) 11

Решение:

  1. рассмотрим все варианты в порядке увеличения длины кода буквы Г
  2. начнем с Г=1; при этом получается, что сообщение «10» может быть раскодировано двояко: как ГА или Б, поэтому этот вариант не подходит
  3. следующий по длине вариант – Г=11; в этом случае сообщение «110» может быть раскодировано как ГА или В, поэтому этот вариант тоже не подходит
  4. третий вариант, Г=111, дает однозначное раскодирование во всех сочетаниях букв, поэтому…правильный ответ – 3.

Задание 4: Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

    Решение:

1.Это задание удобнее решать с помощью дерева; условие Фано выполняется тогда, когда все выбранные кодовые слова заканчиваются в листьях дерева

2. Построим дерево по известным кодовым словам: А – 0, Б – 10:

3. На оставшуюся свободную ветку нужно «повесить» 4 кодовых слова (для букв В, Г, Д, Е)

4. Если выбрать один код длиной 3 (В – 110), то оставшиеся 3 кода нужно «повесить» на одну ветку, так, что на ней нужно делать две развилки:

5. Суммарная длина кодовых слов будет в этом случае равна
1 + 2 + 3 + 4 + 2·5 = 20

6. Попробуем другой вариант: оставшиеся 4 кода повесить на 4 ветки одинаковой длины:

7. Суммарная длина кодовых слов будет в этом случае меньше, чем в предыдущем случае: 1 + 2 + 4 · 4 = 19

Ответ: 19.

Задание 5. По каналу связи передаются сообщения, каждое из которых содержит 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 даёт наименьшую длину сообщения, поэтому выбираем его

Ответ: 1.

Задание 6.  Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
1) 7                 2) 8                  3) 9                       4) 10

     Решение:

  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 символов)

Ответ: 3.

      Решение 2:

1.Условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков;

2.Построим дерево для заданных кодовых слов А – 0 и Б – 110:

3. Штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» листья для кодовых слов букв В (10) и Г (111)

4. Таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов.
Ответ: 3.

        Задание 7. По каналу связи передаются сообщения, содержащие только 5 букв А, И, К, О, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами:
А — 0, И — 00, К — 10, О — 110, Т — 111.

Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.
1) КАА      2) ИКОТА     3) КОТ     4) ни одно из со­об­ще­ний не под­хо­дит

      Решение:

  1. прежде всего заметим, что для заданного кода не выполняется ни прямое, ни обратное условие Фано; «виновата» в этом пара А – И: код буквы А совпадает как с началом, так и с окончанием кода буквы И; больше ни для одной пары кодовых слов прямое условие Фано не нарушено
  2. это означает, что не все сообщения могут быть декодированы однозначно
  3. теперь нужно понять, какие последовательности могут быть декодированы неоднозначно; в данном случае очевидно, что сообщения АА и И кодируются одинаково: 00, поэтому все слова, где есть АА или И, не могут быть декодированы однозначно
  4. поэтому варианты 1 (КАА) и 2 (ИКОТА) отпадают
  5. на всякий случай проверим вариант 3: КОТ = 10110111; первой буквой может быть только К (по-другому сочетание 10 получить нельзя), аналогично вторая буква – только О, а третья – только Т.
    Ответ: 3.

       

        Задание 8: Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.

Для компактности результат записали в шестнадцатеричной системе счисления. Выберите правильную запись кода.

              1) BD9AA5        2) BDA9B5       3) BDA9D5        4) DB9DAB

      Решение:

1.«вытянем» растровое изображение в цепочку: сначала первая (верхняя) строка, потом – вторая, и т.д.:

2. в этой полоске 24 ячейки, черные заполним единицами, а белые – нулями:

3. поскольку каждая цифра в шестнадцатеричной системе раскладывается ровно в 4 двоичных цифры, разобьем полоску на тетрады – группы из четырех ячеек (в данном случае все равно, откуда начинать разбивку, поскольку в полоске целое число тетрад – 6):

4. переводя тетрады в шестнадцатеричную систему, получаем последовательно цифры B (11), D(13), A(10), 9, D(13) и 5, то есть, цепочку BDA9D5. Ответ – 3.

        Задание 9.  Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по каналу в виде 01010100100111100011?

    Решение:

1.сначала разберемся, как закодированы числа в примере; очевидно, что используется код равномерной длины; поскольку 2 знака кодируются 10 двоичными разрядами (битами), на каждую цифру отводится 5 бит, то есть

2 → 00101 и 3 → 00110

2. как следует из условия, четыре первых бита в каждой последовательности – это двоичный код цифры, а пятый бит (бит четности) используется для проверки и рассчитывается как «сумма по модулю два», то есть остаток от деления суммы битов на 2; тогда

2 = 00102, бит четности (0 + 0 + 1 + 0) mod 2 = 1        

3 = 00112, бит четности (0 + 0 + 1 + 1) mod 2 = 0    

3. но бит четности нам совсем не нужен, важно другое: пятый бит в каждой пятерке можно отбросить!

4. разобьем заданную последовательность на группы по 5 бит в каждой:

01010, 10010, 01111, 00011.

5. отбросим пятый (последний) бит в каждой группе:

0101, 1001, 0111, 0001.
это и есть двоичные коды передаваемых чисел:

01012 = 5, 10012 = 9, 01112 = 7, 00012 = 1.

6. таким образом, были переданы числа 5, 9, 7, 1 или число 5971.

Ответ: 5971.

Задание 10.  Для ко­ди­ро­ва­ния букв О, В, Д, П, А ре­ши­ли ис­поль­зо­вать дво­ич­ное пред­став­ле­ние чисел 0, 1, 2, 3 и 4 со­от­вет­ствен­но (с со­хра­не­ни­ем од­но­го не­зна­ча­ще­го нуля в слу­чае од­но­раз­ряд­но­го пред­став­ле­ния). За­ко­ди­руй­те по­сле­до­ва­тель­ность букв ВО­ДО­ПАД таким спо­со­бом и ре­зуль­тат за­пи­ши­те вось­ме­рич­ным кодом.

Решение:

Сна­ча­ла сле­ду­ет пред­ста­вить дан­ные в усло­вии числа в дво­ич­ном коде:

Затем за­ко­ди­ро­вать по­сле­до­ва­тель­ность букв: ВО­ДО­ПАД — 010010001110010. Те­перь разобьём это пред­став­ле­ние на трой­ки спра­ва на­ле­во и пе­ре­ведём по­лу­чен­ный набор чисел в де­ся­тич­ный код, затем в вось­ме­рич­ный (вось­ме­рич­ное представ­ле­ние сов­па­да­ет с де­ся­тич­ным при раз­би­е­нии трой­ка­ми)

 010 010 001 110 010 — 22162.

Задание 11. (Демонстрационный вариант ЕГЭ по информатике 2018 года). По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

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

Top