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

Сегодня на уроке мы вспомним:

· что такое кодирование и декодирование информации;

· чем отличается равномерный код от неравномерного;

· рассмотрим типовые задания по кодированию и декодированию информации, которые могут быть по ОГЭ по информатике.

Кодирование информации – процесс преобразования сигнала из формы, которая удобна для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической переработки.

Декодирование – процесс восстановления содержания закодированной информации.

При кодировании информация, представленная в одной знаковой системе, преобразуется в другую.

Каждый символ исходного алфавита представляется конечной последовательностью символов кодового алфавита. Эта последовательность называется кодовым словом, или кодом.

Кодом может быть последовательность букв, цифр, знаков и так далее.

Длина кода – это определённое количество знаков, из которых состоит код.

Один символ исходного сообщения при кодировании может быть заменён одним или несколькими символами нового кода, и наоборот.

Как мы помним, различают равномерное кодирование и неравномерное.

Равномерным называется код, у которого длина каждого слова одинаковая.

Неравномерным называется код, у которого хотя бы у двух кодовых слов длины различаются.

Код может или не может быть декодирован однозначно, то есть без вариантов, в зависимости от системы кодирования.

Равномерные коды всегда декодируются однозначно.

Чтобы однозначно декодировать неравномерный код, важно знать, имеются ли в нём кодовые слова, которые являются одновременно началом других, более длинных кодовых слов.

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

Неравномерный код, в котором ни одно слово не является началом другого кодового слова, более длинного слова, называется префиксным.

Кодовые слова в таком случае можно записывать друг за другом без разделительного символа между ними.

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

Неравномерный код, в котором ни одно слово не является окончанием другого кодового слова, называется постфиксным.

Постфиксные коды декодировать не так удобно, как префиксные, так как они декодируются с конца. В таком случае необходимо дождаться, пока сообщение придёт полностью, чтобы начать процесс декодирования.

Давайте рассмотрим решение некоторых заданий по кодированию и декодированию информации.

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

– • – • • – • • • – • –

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

Определите текст радиограммы, в нём должно получится конкретное слово, а не набор символов. В ответе укажите, сколько букв было в исходной радиограмме.

Мы видим, что в данной шифровке используется неравномерный код, так как длины кодовых слов разные. Условие Фано выполняется, так как никакое кодовое слово не является началом никакого другого кодового слова.

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

Ответом будет число 5.

Анфиса шифрует русские слова (последовательности букв), записывая вместо каждой буквы её код.

Некоторые цепочки можно расшифровать не одним способом. Например, эта последовательность символов 00010101 может означать не только СКА, но и СНК.

Даны три кодовые цепочки:

10111101

00011110

100111101

Необходимо найти среди них ту, которая имеет только одну расшифровку, и записать в ответе расшифрованное слово.

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

Условие Фано не выполняется, так как код символа Н является началом кода символа Д.

Обратное условие Фано также не выполняется, так как код символа А является концом кода символа К.

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

В ответе записываем расшифрованное слово из второй цепочки – это слово «сон».

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

Определите, сколько букв содержит следующее сообщение:10 12 122 10102.

В ответе запишите последовательность букв без запятых и других знаков препинания.

Мы видим, что здесь используется неравномерное кодирование, так как кодовые слова разной длины. Условие Фано не выполняется, так как код символа А является началом кода символа Г. Обратное условие Фано также не выполняется, так как код символа Д является концом кодов символов А и Б.

То, что в ответе набор символов, а не конкретное слово – это нормально, и не нужно этого пугаться. В заданиях могут быть ответы как с определённым словом, так и с некоторой последовательностью символов.

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

Определите, какое сообщение закодировано в строчке: *# #*# #*

В ответе запишите последовательность букв без запятых и других знаков препинания.

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

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

Условие Фано не выполняется, так как присутствует код, который является началом других кодов.

Обратное условие Фано также не выполняется, так как присутствует код, который является концом другого кода.

Вася шифрует русские слова, записывая вместо каждой буквы её номер в алфавите (без пробелов). Номера букв даны в таблице:

Некоторые шифровки можно расшифровать несколькими способами. Например, данная последовательность цифр 12112 может означать «АБАК», «КАК» или «АБААБ». Даны четыре шифровки:

20335

21120

31321

51201

Только одна из них расшифровывается единственным способом. Найдите её и расшифруйте. То, что получилось, запишите в качестве ответа.

В таком задании в ряде цепочек ищем те, у которых нет нолей.

Так как такую цепочку (в нашем примере это третья цепочка) можно расшифровать как минимум двумя способами: отдельно каждую цифру расшифровать и расшифровать комбинациями цифр. В цепочках, которые имеют нули, расшифровать каждую цифру по отдельности не получится, так в таблице нет расшифровки цифры ноль.

Итак, осталось три цепочки:

20335

21120

51201

Расшифруем по отдельности каждую.

В конце урока попробуйте ответить на следующие вопросы:

Что такое кодирование информации?

Как звучит условие Фано?

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

Внимательно посмотрев урок, вам не составит труда ответить на вопросы.