Презентация - тест "Кодирование и декодирование информации"

КОДИРОВАНИЕ и ДЕКОДИРОВАНИЕ ИНФОРМАЦИИ ( 8 - 9 классы) Тест 1

Учебная презентация по информатике (8-9 класс)

Автор: Звездина Вера Алексеевна ,

учитель информатики

МБОУ г. Ивантеевка г.о. Пушкинский Московской обл.

«Образовательный центр №1»

Кодирование и декодирование информации, тест 1, задача 1

Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБАВ и записать результат в шестнадцатеричной системе счисления, то получится:

1) 132 16 2) D2 16 3) 3102 16 4) 2D 16

________________________________________________________

Решение :

Так как А = 00 2 , Б = 01 2 , В = 10 2 , Г = 11 2 ,

то ГБАВ = 11010010 2 = D2 16

Ответ: 2

Кодирование и декодирование информации, тест 1, задача 2

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

a b c d e

000 110 01 001 10

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

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

________________________________________________________

Решение на следующем слайде

Кодирование и декодирование информации, тест 1, задача 2

Решение :

Здесь применено неравномерное кодирование , при

котором нарушено обратное условие Фано (кодовое

слово 10 является концом кодового слова 1 10 и др.),

тогда декодировать выражение нужно сначала .

Получаем: 110 000 01 001 10 = bacde

Ответ : 3

Кодирование и декодирование информации, тест 1, задача 3

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

A B C D E

000 11 01 001 10

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

• 110000010011110 2) 110000011011110

3) 1100010010 01110 4) 110000001011110

________________________________________________________

Решение на следующем слайде

Кодирование и декодирование информации, тест 1, задача 3

Решение : A B C D E

000 11 01 001 10

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

1) 11 000 001 001 11 10

2) 11 000 001 10 11110

3) 11 000 10 0 10 01 110

4) 11 000 000 10 11  110

Таким об разом, только вариант 1 является верным.

Ответ : 1

Кодирование и декодирование информации, тест 1, задача 4

Для кодирования букв И, Д, Т, О, Х используются двоичные коды чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Если таким способом закодировать последовательность символов ТИХОХОД и записать результат в шестнадцатеричном коде, то получится:

1) CD89 2) 89CD 3) 3154542 4) 2043431

________________________________________________________

Решение на следующем слайде

Кодирование и декодирование информации, тест 1, задача 4

Решение :

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

И = 0 = 00 2 , Д =1 = 01 2 , Т = 2 = 10 2 , О = 3 =11 2 , Х = 4=100 2 , получаем

ТИХОХОД = 2043431 = 10 00 100 11 100 11 01 2 =

= 1000 1001 1100 1101 2 = 89CD 16

Но можно решить эту задачу просто путем рассуждений :

так как первая буква Т = 10 2 , то варианты ответов 1 и 3 отпадают. Вторая буква И = 00 2 , то получаем ТИ = 1000 2 = 8 16 , и вариант ответа – 2.

Ответ : 2

Кодирование и декодирование информации, тест 1, задача 5

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

A= 1 , Б= 000 , В= 001 .

Как нужно закодировать букву Г , чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?

1) 00 2) 01 3) 11 4) 010

_________________________________________________ _______

Решение на следующем слайде

Кодирование и декодирование информации, тест 1, задача 5

Решение :

Из условия получаем, что здесь нарушено обратное

условие Фано ( А = 1 является концом В = 00 1 ),

то при решении ищем кодовое слово, которое будет

самым коротким из возможных и не будет

началом другого кодового слова . Тогда ответом

будет вариант 2 (01) .

Ответ : 2

Кодирование и декодирование информации, тест 1, задача 6

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

А- 0 , И- 00 , К- 10 , О- 110 , Т- 111 .

Среди приведённых ниже слов укажите такое, код которого можно декодировать только одним способом. Если таких слов несколько, укажите первое по алфавиту.

1) КАА 2) ИКОТА 3) КОТ

4) ни одно из сообщений не подходит

_________________________________________________ _______

Решение на следующем слайде

Кодирование и декодирование информации, тест 1, задача 6

Решение :

1 ) КАА = 1000 = КИ – нет;

2) ИКОТА = 00… = ААКОТА - нет;

3) КОТ = 10110111 – да.

Можно решить задачу и без расшифровки : так как здесь кодовое слово А = 0 является и началом, и концом кодового слова И= 00 , то в слове не может быть сочетания АА , и остается слово КОТ .

Ответ : 3

Кодирование и декодирование информации, тест 1, задача 7

По каналу связи передаются сообщения, содержащие только 4 буквы: Л, Е,Т, О ;

для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, Л используются кодовые слова: Т – 101 , О – 01 , Л – 11 . Укажите кратчайшее кодовое слово для буквы Е , при котором код будет допускать однозначное декодирование.

_________________________________________________ _____

Решение на следующем слайде

Кодирование и декодирование информации, тест 1, задача 7

Решение :

В условии задачи нарушено обратное условие Фано

( О – 01 является концом Т – 1 01 ), то при решении

нельзя нарушать начальное условие .

Переберем все возможные варианты по возрастанию

длины кода:

- однозначные 0 и 1 – не могут быть;

• двузначные – 00 (подходит), 01 (О), 10 (начало

буквы Т- 10 1 ), 11 (Л).

Продолжение решения на следующем слайде

Кодирование и декодирование информации, тест 1, задача 7

Решение (продолжение)

Если построить дерево, то получим единственную

двузначную свободную ветку – 00 :

Ответ : 00

Кодирование и декодирование информации, тест 1, задача 8

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е , решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 00, 01, 110, 111 . Укажите кратчайшее возможное кодовое слово для буквы Д , при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание: условие Фано означает что ни одно кодовое слово не является началом другого кодового слова.

_________________________________________________ _______

Решение на следующем слайде

Кодирование и декодирование информации, тест 1, задача 8

Решение :

Из условия задачи видно, что здесь НЕ нарушено ни одно из условий

Фано , следовательно, при решении можно нарушить одно из них, но

нельзя нарушать другое. Также учтем, что хотя в ответе нужно привести

код одной буквы Д, но неизвестными по условию остаются два кодовых

слова - для букв Д и Е , поэтому в данной задаче ищем два доступных

кодовых слова, а в ответе выбираем из них код с меньшим числовым

значением .

Построим все возможные коды и вычеркнем из них

неудовлетворяющие сказанному выше, получим: 10 (станет началом

следующих кодов), 100, 101 и так далее. Тогда ответом будет меньшее

число – 100 .

Продолжение решения на следующем слайде

Кодирование и декодирование информации, тест 1, задача 8

Решение (продолжение)

При построении дерева заметим, что так как ветки 00 и 01 заняты,

то дерево от 0 в вершине строить нельзя. Тогда построим дерево от 1 ,

получим две свободные ветки – 100 и 101 , то в ответе будет код с

меньшим числовым значением – 100 .

Ответ : 100

Кодирование и декодирование информации, тест 1, задача 9

По каналу связи передаются сообщения, содержащие только пять букв: Р, А, Н, Е, Т . Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово 0 , для буквы Е используется кодовое слово 10 . Какова минимальная общая длина кодовых слов для всех пяти букв?

_________________________________________________ ___

Решение на следующем слайде

Кодирование и декодирование информации, тест 1, задача 9

Решение :

Из условия задачи видно, что здесь нарушено обратное условие

Фано , то при решении нельзя нарушить прямое условие. Также

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

и в ответе приводим суммарную минимальную длину их кодов.

Построим все возможные коды и вычеркнем из них

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

11 (нарушает начало следующих кодов), 110 (станет началом

следующих кодов), 111 , 1100, 1101 и так далее.

Берем первые три из найденных и считаем сумму длин всех кодов,

получаем 1 + 2 + 3 + 4 + 4 = 14 .

Продолжение решения на следующем слайде

Кодирование и декодирование информации, тест 1, задача 9

Решение (продолжение)

При построении дерева заметим, что дерево от 0 в вершине

строить нельзя (нарушится начальное условие Фано, а это

здесь недопустимо). Тогда построим дерево от 1 , получим:

Таким образом, свободны три ветки с

кодами 111, 1100 и 1110 , и сумма

длин всех кодов будет

1 + 2 + 3 + 4 + 4 = 14 .

Ответ : 14

Кодирование и декодирование информации, тест 1, задача 10

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г ; для передачи используется двоичный код, удовлетворяющий условию Фано.

Для букв А и Б используются такие кодовые слова: А – 1 ; Б – 011 .

Укажите сумму длин кратчайших кодовых слов для букв В и Г, при котором код будет допускать однозначное декодирование

_________________________________________________ ___

Решение на следующем слайде

Кодирование и декодирование информации, тест 1, задача 10

Решение :

Из условия задачи видно, что здесь нарушено обратное

условие Фано , то при решении нельзя нарушить прямое

условие. Также нужно учесть, в данной задаче ищем два

доступных кодовых слова, и в ответе приводим суммарную

минимальную длину их кодов.

Построим все возможные коды и вычеркнем из них

неудовлетворяющие сказанному выше, получим: 00 и 010

(дальнейшие коды не нужны!).

Тогда суммой длин кодов В и Г , получаем будет 2 + 3 = 5.

Продолжение решения на следующем слайде

Кодирование и декодирование информации, тест 1, задача 10

Решение ( продолжение)

При построении дерева заметим, что дерево от 1 в вершине строить нельзя (вершина закрыта, так как А = 1 ). Тогда построим дерево от 0 , получим:

Ответ : 5