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

Подписи к слайдам:

Кодирование и декодирование информации Задание 5 (базовый уровень, время – 2 мин)

Всё есть число.

Пифагор

Разработала Фоминова Елена Владимировна, учитель физики и информатики МБОУ СОШ № 23 МО Усть-Лабинский район Краснодарского края

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

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

а) процесс придания определенного смысла полученным сигналам;

б) процесс выявления первоначального

замысла, исходной идеи отправителя,

понимания смысла его сообщения.

Алфавит В основе каждого текста лежит алфавит – конечное множество символов. В основе русского языка лежит алфавит, называемый кириллицей, состоящий из 33 строчных и 33 заглавных букв. В основе английского языка лежит латиница – алфавит, состоящий из 26 строчных и 26 заглавных букв. Пусть задан алфавит Т, содержащий m символов: Т={t1, t2, … tm} Словом S в алфавите T называют любую последовательность символов алфавита: S =s1s2…sk, где si- это символы алфавита. Число символов в слове – k называют длиной слова. Мощность алфавита – это количество символов в нем. Алфавит .

При нажатии на клавиатурную клавишу компьютер получает сигнал в виде двоичного числа, расшифровку которого можно найти в кодовой таблице – внутреннем представлении знаков в ПК. Стандартом во всем мире считают таблицу ASCII.

Для хранения одного символа двоичного кода электронно-вычислительная машина выделяет 1 байт, то есть 8 бит. Эта ячейка может принимать только два значения: 0 и 1. Получается, что один байт позволяет зашифровать 256 разных символов, ведь именно такое количество комбинаций можно составить. Эти сочетания и являются ключевой частью таблицы ASCII.

Алфавит .

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

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

В двоичной системе счисления, которую активно используют компьютеры, встречаются лишь две цифры – 0 и 1.

Долгое время при работе с текстами, сохраняемыми в компьютере, используется код ASCII. Такой алфавит, содержащий 256 различных символов, мог включать латиницу и кириллицу, цифры, знаки операций, знаки препинания, скобки и другие символы. Но все-таки этого алфавита недостаточно, чтобы можно было хранить в памяти компьютера тексты на любых естественных языках.

Сегодня для хранения текстов используется кодировка из 2-х байтов, называемая UNICODE кодировкой, позволяющая словами из 16 битов кодировать алфавит, содержащий 216=65536 символов.

ASCII

UNICODE

Неоднозначное кодирование Пример. Пусть у нас есть алфавит из 3-х символов – А, М, П. Введем следующую кодировку: А-0, М-1, П-10. Рассмотрим закодированный текст: 1010. Этому тексту соответствует два слова – МАМА и ПП. Как видите, введенная кодировка не обеспечивает однозначное кодирование.

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

Условие Фано Условие Фано: никакое кодовое слово не совпадает с началом другого кодового слова. Коды, для которых выполняется условие Фано, называют префиксными (префикс слова — это его начальный фрагмент). Все сообщения, закодированные с помощью префиксных кодов, декодируются однозначно. Префиксные коды имеют важное практическое значение — они позволяют декодировать символы полученного сообщение по мере его получения, не дожидаясь, пока всё сообщение будет доставлено получателю. Нужно знать Прямое условие Фано Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо другого, более длинного кода.

А	В	С
10	11	001

А	В	С
10	11	00

А	В	С
100	110	010

D: 00

недопустимо:

C - 001

D – 00

Код D совпадает

с началом кода С

D: 11

недопустимо:

В - 11

D – 11

Код D совпадает

с кода В

D: 00

допустимо:

Прямое условие Фано выполнено.

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

А	В	С
10	11	001

А	В	С
10	11	00

А	В	С
100	110	010

D: 01

недопустимо:

C - 001

D – 01

Код D совпадает

с концом кода С

D: 11

недопустимо:

В - 11

D – 11

Код D совпадает

с кода В

D: 01

допустимо:

Обратное условие Фано выполнено.

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

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

Условия Фано

Задача 1

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приемной стороне канала связи. Использовали код: А-1, Б-000, В-001, Г-011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного кодирования.

Решение:

Проверяемый код буквы Д	Существующие коды букв А, Б, В, Г				Вывод
	А	Б	В	Г
	1	000	001	011
00	00 1 нет	00 000 есть	00 001 есть	00 011 нет	Код не пригоден
01	01 1 нет	01 000 нет	01 001 нет	01 011 есть	Код не пригоден
10	10 10 10 10 1 есть 000 нет 001нет 011нет				Код не пригоден
11	11 1 есть	11 000 нет	11 001нет	11 011нет	Код не пригоден
000	000 1 нет	000 000 есть	000 001 нет	000 011нет	Код не пригоден
001	001 1 нет	001 000 нет	001 001 есть	001 011нет	Код не пригоден
010	010 1 нет	010 000нет	010 001 нет	010 011нет	Код пригоден

Задача 2

Для кодирования последовательности символов, состоящей из букв К, И, Н, О, используется неравномерный код, удовлетворяющий условию Фано. При этом для буквы К использован код 0, а для буквы И – код 11. Требуется определить наименьшую возможную суммарную длину всех кодовых слов указанных букв.

Подсказка

Решение:

Для проверки на соответствие кодов условию Фано нужно попарно сравнить между собой коды по следующим правилам:

когда длина обоих сравнимых кодов совпадает, проверяется равенство этих кодов: если один код совпадает с другим, то такая пара кодов не удовлетворяет условию Фано;
когда длина сравнимых кодов различна, более короткий код записывается под более длинным с выравниванием обоих кодов по левому краю: если все знаки более короткого кода совпадают с соответствующими знаками в начале более длинного кода, то такая пара кодов не удовлетворяет условию Фано.

Код К	Код И	Код Н	Комментарий
0	11	1	Нельзя, так как совпадет с началом кода И.
		00	Нельзя – код К совпадает с началом кода Н
		01	Нельзя – код К совпадает с началом кода Н
		10	Допустимый код (не совпадает с кодом И, а код К не совпадает с его началом)

Задача 2

Итак, можно предположить, что первый код найден. Но посмотрим – удастся ли при этом найти код для буквы О. При этом можно отбросить те коды, которые не подошли для буквы Н, - ведь код буквы О должен удовлетворять тем же требованиям при сравнении с кодами К и И.

Код К	Код И	Код Н	Код О	Комментарий
0	11	10	11	Нельзя, так как совпадет с кодом И.
			000, 001, 010, 011	Нельзя – код К совпадает с началом кода О
			100, 101	Нельзя – код Н совпадает с началом кода О
			110, 111 и т.д.	Нельзя – код И совпадает с началом кода О
		100	101	Допустимый код (не совпадает с кодом Н, а код К и И не совпадает с его началом)

Код К	Код И	Код Н	Код О
0	11	100	101

Подсчитаем суммарную длину этих кодов: 1+2+3+3=9

Задача 3

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?

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

Подсказка

Задача 3

Решение:

На оставшуюся свободную ветку нужно «повесить» 4 кодовых слова (для букв В, Г, Д, Е)

суммарная длина кодовых слов будет в этом случае равна 1 + 2 + 3 + 4 + 2·5 = 20

(А-0, Б-10, В-110, Г-1110, Д-11110, Е-11111)

Задача 3

Решение:

суммарная длина кодовых слов будет в этом случае равна 1 + 2 + 4·4 = 19

(А-0, Б-10, В-1100, Г-1101, Д-1110, Е-1111)

Ответ: 19

Задача 4

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

суммарная длина кодовых слов будет в этом случае равна

1 + 3 +2 + 3 = 9

(А-0, Б-110, В-10, Г-111)

Ответ: 9

Нужно помнить

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

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

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

Кодирование может быть равномерное и неравномерное.

При равномерном кодировании все символы кодируются кодами равной длины.

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

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

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

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

Для трехбуквенного алфавита {А, М, П} используется кодировка А-01, М-10, П-001. Какой код минимальной длины следует задать для кодировки буквы Т, добавляемой в алфавит? Для трехбуквенного алфавита {А, М, П} используется кодировка А-01, М-10, П-001. Какой код минимальной длины следует задать для кодировки буквы Т, добавляемой в алфавит?

Задача 5

Ответ: 11

Решение:

Для нового символа, добавляемого в алфавит, нельзя использовать код, состоящий из одного символа, так как будет нарушено условие Фано. Для кода, состоящего из двух символов, возможен только один вариант, удовлетворяющий условию Фано, Т-11.

Задача 6

Ответ: П-00

Для четырехбуквенного алфавита {А, М, П, Т} используется кодировка А-01, М-10, П-001, Т-11. Можно ли уменьшить длину кода одного из символов, сохраняя однозначность декодирования? По каналу связи передаются сообщения, содержащие только 4 буквы: А, В, С, D. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв используются такие кодовые слова: А-111, В-0, D-110. По каналу связи передаются сообщения, содержащие только 4 буквы: А, В, С, D. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв используются такие кодовые слова: А-111, В-0, D-110. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Задача 7

Решение:

Коды 1 и 0 являются началом кода данных букв.

Коды 00 и 01 нельзя использовать, так как код буквы В является их началом. Следовательно, минимальный код для буквы C будет 10.

Ответ: 10

Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-100, Б-111, B-110, Г-0. Через канал связи передаётся сообщение: ВАБГАВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид. Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-100, Б-111, B-110, Г-0. Через канал связи передаётся сообщение: ВАБГАВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид.

Задача 8

Ответ: D3A6

Решение:

Закодируем сообщение ВАБГАВ – 1101001110100110.

Полученную двоичную последовательность переведем в шестнадцатеричный вид.

1101ӏ0011ӏ1010ӏ0110

D 3 A 6

По каналу связи передаются сообщения, содержащие только 3 буквы: А, В, С. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А и В используются такие кодовые слова: А: 11, В: 0. По каналу связи передаются сообщения, содержащие только 3 буквы: А, В, С. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А и В используются такие кодовые слова: А: 11, В: 0. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Задача 9

Решение:

Коды 1 и 0 являются началом кода данных букв.

Ответ: 10

Выполни самостоятельно

Задание 1. По каналу связи передаются сообщения, содержащие только 4 буквы: А, В, С, D; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, В, D используются такие кодовые слова: А: 0, В: 10, D: 110. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Задание 2. Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-00, Б-11, В-100, Г-011. Через канал связи передаётся сообщение: ГБВАГВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид.

Ответ: 111

Ответ: 7С1С

Задание 3. Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-00, Б-11, В-010, Г-011. Через канал связи передаётся сообщение: ГБВАВГ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность запишите в восьмеричной системе счисления.

Задание 4. Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-111, Б-110, В-10, Г-0. Через канал связи передаётся сообщение: ВАБГАВ. Закодируйте сообщение данным кодом. Полученную двоичную последовательность запишите в восьмеричной системе счисления.

Ответ: 75023

Ответ: 27636

Задание 5. По каналу связи передаются сообщения, содержащие только 3 буквы: А, В, С; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А и В используются такие кодовые слова: А: 10, В: 0. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Задание 6. По каналу связи передаются сообщения, содержащие только 4 буквы: А, В, С, D; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, В, D используются такие кодовые слова: А: 111, В: 0, D: 100. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Ответ: 11

Ответ: 101

Список использованной литературы

Биллинг В.А. Подготовка к ЕГЭ по информатике.
Богомолова О.Б. Информатика. Новый полный справочник для подготовки к ЕГЭ. –М.: АСТ Астрель, 2016.
Лещинер В.Р. ЕГЭ 2017. Информатика. 0 вариантов. –М.: Издательство «Экзамен», 2017 –М.: Национальный Открытый Университет «ИНТУИТ», 2016

Интернет-ресурсы Слайд 1 ЕГЭ http://bashgymn.ucoz.ru/muzi/may/a12183fc240047e94e1f82d423bb0dd0.jpg Слайд 2 https://rostovmama.ru/upload/000/u2/371/fb28decb.png Слайд 3 https://lh5.googleusercontent.com/B3xJ9aZD4N1SbjjtLHdY4qiQjr4412-TqkTBoBLVhz9gkCkArqDm42kas04VglU7ZitRhgmbaOETOuNY2WcYxJ71lEQmzDwKU94SDPMo2hb8kcckwVbU4EiSmLwZ7uvbkg Слайд 4,5,6,13 http://3.bp.blogspot.com/-_-2yo9G5IDQ/U2dLrlEs8hI/AAAAAAAAS2A/xmGQNen3WDU/s1600/000269.jpg Слайд 5 http://fb.ru/misc/i/gallery/38988/1040345.jpg Слайд 7 http://fb.ru/misc/i/gallery/38988/1040342.jpg Слайд 8 http://www.alfa-dominion.com/wp-content/uploads/2016/09/ar126593775101102-768x684.jpg Слайд 9, 28 http://kazan.czm.su/sites/default/files/vajno-znat.jpg https://begobike.com/wp-content/uploads/2016/07/Chitaem-pravila-gonol-na-begovelakh-1.jpg Слайд 10,11,12 http://wallsfield.com/wp-content/uploads/2014/12/binary-code.jpg Слайд 14, 15, 16, 17,18,19 http://www.yiliti.com/d/file/20160320/658-151111092Q4M9.jpg Слайд 14, 16 Человечек с книгой http://wealthinoptions.com/wp-content/uploads/2014/11/18853285_ml.jpg Слайд 20 http://til-lit.narod.ru/rekomend_K.jpg Слайд 21,22 ноль http://5dimensions.se/wp-content/uploads/2016/04/red-number-0.jpg Единица http://www.theintentionallife.com/wp-content/uploads/2014/12/1.jpg Слайд 23-27 http://wealthinoptions.com/wp-content/uploads/2014/11/18853285_ml.jpg

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

Подписи к слайдам:

Информатика - еще материалы к урокам:

Предметы

Похожие материалы