сайт для подготовки к ЕГЭ - В9 Кодирование, декодирование
Суббота, 10.12.2016, 05:59
Хочу сдавать ЕГЭ!!!
Главная Регистрация Вход
Приветствую Вас, Гость · RSS
Ученикам 10-11 кл
Гостевая книга
Википедия
Полезные   ссылки 
  • Школьный    сайт             
  • Банк данных ЕГЭ по информатике
  • Сайт ФИПИ
  • Решу ЕГЭ (тесты on-line)
  • Решение Демо ЕГЭ
  • Каталог сайтов
  • Подготовка к ГИА
    Информатика 9 кл
    Информатика 8 кл
    Информатика 7 кл
    Архив записей
    Статистика

    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0


     В9 Кодирование, декодирование

    Решение задач   А9 на тему  «Кодирование и декодирование информации»

    Уровень сложности-базовый,  время выполнения 2 мин

    Видеоуроки on-line

    http://videouroki.net/view_post.php?id=149 (сайт Д. Тарасова)

    Справочный материал:

    Существует равномерное и неравномерное кодирование. При равномерном кодировании сообщение декодируется однозначно.

     При неравномерном кодировании для однозначного декодирования сообщения нужно, чтобы выполнялось прямое и обратное условие Фано (прямое: никакой код не должен быть началом другого кода, обратное: никакой код не должен быть концом другого кода)

     Понимать, что мы можем закодировать сообщение, даже если условие Фано не выполняется, но возможно не сможем его однозначно декодировать.

     Однозначно декодировать – получить один единственный точный вариант. 



    Примеры решения задач на выполнение условия Фано

    Пример 1 A9  Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв - из двух бит, для некоторых - из трех). Эти коды представлены в таблице: 

    a          b          c          d          e

    000      110      01        001      10

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

    1) baade      2) badde        3) bacde     4) bacdb

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

    Разобьём код слева направо по данным таблицы и переведём его в буквы:

    110 000 01 001 10 — b a c d e.

    Правильный ответ указан под номером 3.

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

    A         B         C         D         E         F

    00        100      10        011      11        101

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

    1) DEFBAC        2) ABDEFC     3) DECAFB     4) EFCABD

    Решение:.

    Мы видим, что условия Фано и обратное условие Фано не выполняются, значит код можно раскодировать неоднозначно.

    Будем пробовать разные варианты, отбрасывая те, в которых получаются повторяющиеся буквы:

    1) 011 11 100 0101100

    Первая буква определяется однозначно, её код 011: D.

    Вторая буква также определится однозначно  — E.

    Пусть третья буква B, тогда следующая начинается с кода 010, но таких букв в таблице нет, значит предположение не верно.

    2) 011 11 10 00 101 100

    Третья буква — С, потом — A. Мы хотим получить ещё две буквы, чтобы в сумме их было 6, тогда следующая буква — F, и последняя  — B.

    Окончательно получили ответ: DECAFB.

    Правильный ответ указан под номером 3.

    Пример 3 A9 Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111. 

    Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

     1) это невозможно          2) для буквы В – 000

    3) для буквы Б – 0            4) для буквы Г – 11

    Решение.

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

    Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.

    Вариант 3 не подходит, потому что 0 является началом кода 0001.

    Вариант 4 не подходит, потому что код 1 является началом кода 111.

    Вариант 2 подходит, так как не нарушает условия Фано.

    Правильный ответ указан под номером 2.

    Задачи А9     Кодирование+Системы счисления

    Для решения этих задач нужно знать алгоритм перевода из двоичной системы счисления в восьмеричную и шестнадцатеричную.

    Пример 1 A9  Для кодирования букв А, Б, В, Г используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов БГАВ и записать результат в восьмеричном коде, то получится:

    1) 175423    2) 115612  3) 62577     4) 12376

    Решение .

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

    1 001 101 110 001 010 — 1 1 5 6 1 2.

    Правильный ответ указан под номером 2.

    Пример 2 A9 Для кодирования букв А, В, С, D используются трехразрядные последовательные двоичные числа, начинающиеся с 1 (от 100 до 111 соответственно). Если таким способом закодировать последовательность символов CDAB и записать результат в шестнадцатеричном коде, то получится: 

    1) А52    2) 4С8          3) 15D    4) DE5

    Решение.

    Закодируем последовательность букв: CDAB — 110111100101. Теперь разобьём это представление на четвёрки справа налево и переведём полученный набор чисел сначала в десятичный код, затем в шестнадцатеричный:

    1101 1110 0101 — 13 14 5 — DE5.

    Правильный ответ указан под номером 4.


    Задачи А9   Найти правильное кодирование

    Пример 1  Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код: 

    A         B         C         D         E

    000      11        01        001      10

    Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

    1) 110000010011110                 2) 110000011011110

    3) 110001001001110                   4) 110000001011110

    Решение.

    Разобьём каждый ответ на посимвольный код и найдём нужное:

    Вариант 1: 11 000 001 001 11 10 (этот вариант уже подходит, но проверим и остальные).

    Вариант 2: 11 000 001 10 11 11 0 — последняя часть кода не может быть раскодирована.

    Вариант 3: 11 000 10 01 001 11 0 — аналогично.

    Вариант 4: 11 000 000 10 11 11 0 0 — аналогично.

    Правильный ответ указан под номером 1.

    Пример 2 A9 . Для кодирования сообщения, состоящего только из букв О, К, Л, М и Б, используется неравномерный по длине двоичный код: 

    О         К         Л         М        Б

    00        01        11        010      0110

    Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано:

    1) 110001001001110       2) 10000011000111010

    3) 110001001101001      4) 1000110001100010

    Решение:

    Разобьём каждый ответ на посимвольный код и найдём нужный  вариант:

    Вариант 1: 11 00 010 01 00 11 10 — при таком разбиении последняя часть кода может быть раскодирована, а если разбить по-другому 11 00 01 00 10011, то сообщение также недекодируемо.

    В вариантах 2 и 4 невозможно раскодировать начало кода.

    Вариант 3: 11 00 01 00 11 01 00 1  — при таком разбиении последняя часть кода может быть раскодирована. Разобьём по-другому: 11 00 01 00 11 010 01 — такой вариант разбиения может быть раскодирован.

     .Правильный ответ указан под номером 3.



    Задачи на кодирование буквы

    Пример 1 A9 . Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? 

    1) 0001      2) 000       3) 11      4) 101    

    Решение. .

    Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.

    Рассмотрим варианты для буквы Г, начиная с самого короткого.

    3) Г=11: код буквы A является началом этого кода, поэтому этот вариант не подходит.

    4) Код Г=101 не подходит по аналогичной причине.

    2) Код Г=000 не сопадает с началом ни одного кода,следовательно это и есть правильный ответ.

    Правильный ответ указан под номером 2.

    Другие задачи на кодирование

    Пример 1 A9 . По каналу связи передаются сообщения, содержащие только 4 буквы: E, H, O, T. Для кодирования букв E, H, O используются 5-битовые кодовые слова: E — 00000, H — 00111, O — 11011. 

    Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее чем в трех позициях.

    Это свойство важно для расшифровки сообщений при наличии помех. Какое из перечисленных ниже кодовых слов можно использовать для буквы T, чтобы указанное свойство выполнялось для всех четырёх кодовых слов?

    1) 11111        2) 11100        3) 00011           4) не подходт ни одно из указанных выше слов

    Решение   Пользуясь правилом "любые два слова из набора отличаются не менее чем в трех позициях" проверим все возможные варианты.

    Число 11111 отличается от кодового слова 00111 только в двух позициях.

    Число 11100 отличается от кодового слова 00000 — в трех позициях, от 00111 — в четырех позициях, 11011 — в трех позициях.

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

     

    Copyright MyCorp © 2016
    Сделать бесплатный сайт с uCoz