Конспект урока на тему «Декодирование»
план-конспект урока по информатике и икт (10 класс)

Конспект урока на тему «Декодирование»

Цель  урока: сформировать умение решать задания на кодирование и декодирование информацию.

Задачи:

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

Ход урока:

1.Организационный момент  

2.  Проверка домашнего задания

3. Изучение нового материала

4. Итоги урока.

5. Домашнее задание

Декодирование — это восстановление информационного сообщения из последовательности кодов.

Например, закодированное сообщение

•        • • — • — •        •        

можно восстановить, используя код Морзе «в обратную сторону»: в этой строке закодирована фамилия «Петров».

В некоторых случаях даже при использовании неравномерного кода не требуется вводить символ-разделитель. Для этого достаточно выполнение условия Фано: ни одно кодовое слово не совпадает с началом другого кодового слова. Такой код называют префиксным.

Пример 1. Пусть для кодирования первых 5 букв русского алфавита используется таблица:

Это неравномерный код, поскольку в нём есть двух- и трёхсимвольные кодовые слова. Построим для этой кодовой таблицы дерево, в котором от каждого узла (кроме листьев) отходят два ребра, помеченные цифрами 0 и 1. Чтобы найти код символа, нужно пройти по стрелкам от корня дерева к нужному листу, выписывая метки стрелок, по которым мы переходим (рис. 2.3). Заметим, что ни один символ не лежит на пути от корня к другому символу. Это значит, что условие Фано выполняется и любую правильную кодовую последовательность можно однозначно декодировать. Например, рассмотрим цепочку 1100000100110.

Следующий (единственно возможный) код — 000, это буква А:

Здесь условие Фано не выполняется, поскольку код буквы Б

является началом кода буквы Г (011), а код буквы Д (100) начинается с кода буквы В (10). Дерево для этой кодовой таблицы выглядит так (рис. 2.4)

Тем не менее можно заметить, что выполнено «обратное» условие Фано: ни одно кодовое слово не совпадает с окончанием другого кодового слова (такой код называют постфиксным). Поэтому закодированное сообщение можно однозначно декодировать с конца. Например, рассмотрим цепочку 011000110110. Последней буквой в этом сообщении может быть только В (код 10).

В общем случае (если код не является ни префиксным, ни постфиксным) декодировать сообщение удаётся только перебором вариантов.

Пример 3. Декодируем сообщение 010100111101, закодированное с помощью кодовой таблицы:

Здесь не выполняется ни «прямое», ни «обратное» условие Фано, поэтому декодировать сообщение однозначно, возможно, не удастся. На первом месте может быть буква А или буква Б. Сначала предположим, что это буква А:

А0100111101

Тогда второй буквой также может быть буква А:

АА00111101

Дальше декодировать не получается, потому что в таблице нет кодов 0, 00 и 001. Поэтому проверяем второй вариант: вторая буква — Б:

АБ0111101.

Третьей буквой может быть А:

АБА11101,

Тогда четвёртая и пятая буквы определяются однозначно — это буквы Г и Д. Таким образом, один из подходящих вариантов — АБАГД.

Посмотрим, есть ли другие варианты. После сочетания АБ может стоять буква В:

АБВ1101,

тогда оставшиеся буквы — это ГА, а полное сообщение — АБВГА. Этот вариант тоже подходит.

Кроме того, на первом месте может стоять буква Б:

Б100111101,

но дальше декодировать не удаётся, потому что в таблице нет кодов 1, 10 и 100. Таким образом, сообщение может быть декодировано двумя способами: АБАГД и АБВГА.

Пример 4. Существуют коды, для которых условия Фано не выполняются, но все сообщения однозначно декодируются. В кодовой таблице

код буквы А совпадает как с началом, так и с окончанием кода буквы В, т. е. этот код не является ни префиксным, ни постфиксным.

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

{Л, 1}. Граф, построенный с помощью приведённого выше алгоритма, содержит два узла и одну петлю (рис. 2.17).

В этом графе нет цикла, содержащего вершину Л, поэтому любое сообщение, записанное с помощью такого кода, декодируется однозначно. Это можно показать и простыми рассуждениями:

1. все цепочки 11 в сообщении — это коды букв Б, иначе они не могут образоваться;
2. все цепочки 010 — это коды букв В;
3. остальные символы сообщения могут быть только нулями — это коды букв А.

Иногда при кодировании и декодировании происходит искажение сообщения. Например, известно, что перевод художественных текстов (особенно стихов) на другой язык и затем обратный перевод могут изменить их до неузнаваемости.