Что такое декодирование в информатике 10 класс

Информатика. 10 класс

Конспект урока

Информатика, 10 класс. Урок № 14.

Тема — Кодирование текстовой информации

Цели и задачи урока:

— познакомиться со способами кодирования и декодирования текстовой информации с помощью кодовых таблиц и компьютера;

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

— познакомиться с алгоритмом Хаффмана.

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

Формула Хартли определяет количество информации в зависимости от количества возможных вариантов:

N — это количество вариантов,

i — это количество бит, не обходимых для кодирования.

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

i — кол-во бит, потребуемых для кодирования

Итак, если в нашем алфавите будет присутствовать только 32 символа, то каждый из них займет только 5 бит.

И тогда каждому символу мы дадим уникальный двоичный код. Такую таблицу мы будем назвать кодировочной.

Первая широко используемая кодировочная таблица была создана в США и называлась ASCII, что в переводе означало American standard code for information interchange. Как вы видите, в таблице присутствуют не только латинские буквы, но и цифры, и даже действия. Каждому символу отводится 7 бит, а значит, всего было закодировано 128 символов.

Но так как этого количества было недостаточно, стали создаваться другие таблицы, в которых можно было закодировать и другие символы. Например, таблица Windows-1251, которая, по сути, являлась изменением таблицы ASCII, в которую добавили буквы кириллицы. Таких таблиц было создано множество: MS-DOS, КОИ-8, ISO, Mac и другие:

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

Поэтому была разработана международная таблица кодировки Unicode, включающая в себя как символы английского, русского, немецкого, арабского и других языков. На каждый символ в такой таблице отводится 16 бит, то есть она позволяет кодировать 65536 символов. Однако использование такой таблицы сильно «утяжеляет» текст. Поэтому существуют различные алгоритмы неравномерной кодировки текста, например, алгоритм Хаффмана.

Идея алгоритма Хаффмана основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает новый очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код.

Пусть нам дано сообщение aaabcbeeffaabfffedbac.

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

Подсчитайте и внесите в таблицу частоту появления каждого символа в сообщении:

У вас должно получиться:

Расположите буквы в порядке возрастания их частоты.

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

Символы d и c превращаются в ветку дерева:

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

Итак, сортируем таблицу:

Объединяем символ e и символ cd в ветку дерева:

Получился префиксный код. Теперь осталось расставить 1 и 0. Пусть каждая правая ветвь обозначает 1, а левая — 0.

Составляем код буквы, идя по ветке дерева от буквы к основанию дерева.

Тогда код для каждой буквы будет:

Закодируйте ASCII кодом слово MOSCOW.

Составим таблицу и поместим туда слово MOSCOW. Используя таблицу ASCII кодов, закодируем все буквы слова:

Источник

Содержание урока

§5. Язык и алфавит

§6. Кодирование

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

§6. Кодирование

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

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

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

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

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

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

Заметим, что ни один символ не лежит на пути от корня к другому символу. Это значит, что условие Фано выполняется и любую правильную кодовую последовательность можно однозначно декодировать. Например, рассмотрим цепочку 1100000100110. Букв с кодами 1 и 11 в таблице нет, поэтому сообщение начинается с буквы Г — она имеет код 110:

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

Аналогично декодируем всё сообщение:

Пример 2. Рассмотрим другую кодовую таблицу:

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

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

Вторая буква с конца — Б (код 01):

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

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

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

А0100111101

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

АА00111101.

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

АБ0111101.

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

АБА11101,

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

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

АБВ1101,

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

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

Б100111101,

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

Пример 3 показывает, что неоднозначное декодирование возможно тогда, когда начало кода одной буквы совпадает с концом кода другой и можно переместить границу между кодами букв в сообщении. Например, последовательность 01011 может быть декодирована как АВ (01011) и БГ (01011). Следовательно, нужно обратить внимание на те цепочки, которые встречаются как в начале, так и в конце кодовых слов.

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

1. Определим все последовательности., которые совпадают с началом какого-то кодового слова и одновременно с концом какого-то кодового слова; в данном случае это две последовательности:

0 (начало кода буквы А и конец кода буквы Б)
1 (начало кода буквы Г и конец кода буквы Д)
10 (начало кода буквы Д и конец кода буквы Б).

2. Добавим к этому множеству <0, 1, 10>пустую строку, которую обычно обозначают буквой Λ (прописная греческая буква «лямбда»); элементы полученного множества <Λ, 0, 1>становятся узлами графа (рис. 2.5).

3. Соединим узлы дугами (направленными рёбрами) по такому правилу: два узла X и Y соединяются дугой, если последовательная запись кода узла X, кода некоторой буквы (или нескольких букв) и кода узла Y даёт код ещё одной буквы (рис. 2.6).

Например, последовательная запись пустой строки (Λ), кода буквы А (01) и цепочки 0 даёт цепочку 010, которая совпадает с кодом буквы Б; поэтому рисуем дугу из вершины Λ в вершину 0; у этой дуги пишем А → Б, и т. д. Поскольку код буквы Г можно записать как 11 = 1Λ1, у вершины 1 появляется петля Λ → Г.

Любое сообщение декодируется однозначно тогда и только тогда, когда в полученном таким образом графе нет циклов, включающих вершину «Λ».

В нашем графе есть несколько таких циклов, например:

• цикл «Λ0Λ», соответствующий сообщению ΛА0ГΛ = 01011; это сообщение может быть расшифровано как АВ и как БГ;
• цикл «Λ1Λ», соответствующий сообщению ΛА1АΛ = 01101; это сообщение может быть расшифровано как АД и как ВА;
• цикл «Λ01Λ», соответствующий сообщению ΛА01АΛ = 01010Lj это сообщение может быть расшифровано как АДА и как БД;
• цикл «Λ0101Λ», соответствующий сообщению ΛА0101АΛ = 01010101; это сообщение может быть расшифровано как АБД и как БДА.

Кроме того, из-за петли у вершины 1 неоднозначно декодируется любая последовательность вида 01. 101, где многоточие обозначает любое количество единиц. Например, сообщение 0111101 может быть декодировано как АГД или ВГА (см. пример 3).

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

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

Проверим, можно ли однозначно декодировать сообщения, построенные с помощью такого кода. Множество последовательностей, которые совпадают с началом и концом кодовых слов, состоит из пустой строки и единицы: <А, 1>. Граф, построенный с помощью приведённого выше алгоритма, содержит два узла и одну петлю (рис. 2.7).

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

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

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

Следующая страница Вопросы и задания

Cкачать материалы урока

Источник

Что такое декодирование в информатике 10 класс

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

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

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

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

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

Кодирование может быть равномерным и неравномерным. При равномерном кодировании все символы заменяются кодами равной длины; при неравномерном кодировании разные символы могут кодироваться кодами разной длины (это затрудняет декодирование). Неравномерный код называют еще кодом переменной длины.

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

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

Коды Морзе для некоторых букв.

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

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

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

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

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

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

Неравномерные коды, для которых выполняется условие Фано, называются префиксными. Префиксный код — такой неравномерный код, в котором ни одно кодовое слово не является началом другого, более длинного слова. В таком случае кодовые слова можно записывать друг за другом без разделительного символа между ними.

Например, код Морзе не является префиксным — для него не выполняется условие Фано. Поэтому в кодовый алфавит Морзе, кроме точки и тире, входит также символ–разделитель — пауза длиной в тире. Без разделителя однозначно декодировать код Морзе в общем случае нельзя.

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

Источник

Кодирование и декодирование. Условие ФАНО

Содержимое разработки

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

Декодирование – это восстановление сообщения из последовательности кодов.

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

При кодировании используют

равномерные и неравномерные коды.

Равномерные коды – все кодовые слова (коды отдельных букв)

имеют одинаковую длину.

МАМА МЫЛА ЛАМУ: 000 001 000 001 101 000 010 011 001 101 011 001 000 100

Равномерные коды позволяют однозначно декодировать сообщения.

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

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

Прямое условие Фано. Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом какого-либо другого, более длинного кода. Такой код называют «префиксным».

Обратное условие Фано. Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с окончанием какого-либо другого, более длинного кода. Такой код называют «постфиксным».

Почему необходимо соблюдение условия Фано

при неравномерном кодировании?

Исходный алфавит – алфавит русских букв, строчные и прописные буквы не различаются. Размер алфавита – 33 символа.

Применяется побуквенное кодирование по следующему правилу:

буква кодируется ее номером в алфавите: код буквы А – 1; буквы Я – 33 и т.д.

Тогда код слова АББА – это 1221.

Последовательность 1221 может означать не только АББА,

но и КУ (К – 12-я буква в алфавите, а У – 21-я буква).

Префиксный код – ни одно кодовое слово не совпадает

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

Любой префиксный код позволяет

однозначно декодировать сообщения.

Постфикс = окончание слова.

Постфиксный код – ни одно кодовое слово не совпадает

с концом другого кодового слова

10 00 10 00 11 10 1101 001 00 11 001 00 10 0101

М А М А М Ы Л А Л А М У

Любой постфиксный код позволяет однозначно декодировать сообщения (с конца).

Для однозначного декодирования достаточно выполнения хотя бы одного из двух условий Фано:

– при выполнении прямого условия Фано последовательность кодов однозначно декодируется с начала;

– при выполнении обратного условия Фано последовательность кодов однозначно декодируется с конца.

ПОСТРОЕНИЕ ДЕРЕВА ФАНО

Дерево Фано – это удобный и наглядный способ решения задач, связанных с подбором неравномерных двоичных кодов.

Основные принципы построения дерева Фано:

обеспечивается тогда, когда все

кодовые слова заканчиваются на

Для букв Т, Е, П используются такие кодовые слова: Т: 111, Е: 0, П: 100.

Кодовые слова для некоторых букв известны: А — 001, И — 01, С — 10.

Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОЛОБОК?

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

Для буквы И используется кодовое слово 1; для буквы О используется кодовое слово 01.

Какова минимальная общая длина кодовых слов для всех пяти букв?

Какое кодовое слово соответствует букве Н?

Определите, какое число передавалось по каналу в виде 01100010100100100110.

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

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

то есть остаток от деления суммы бит на 2; тогда

3) пятый бит в каждой пятерке можно отбросить!

4) разобьем последовательность на группы по 5 бит в каждой: 01010, 10010, 01111, 00011.

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

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

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

Источник