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

есть число.
Пифагор
Разработала Фоминова Елена

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

в другую, наиболее удобную для её хранения, передачи или обработки.

Кодирование

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

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

В основе русского языка лежит алфавит, называемый кириллицей, состоящий из

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

Алфавит

виде двоичного числа, расшифровку которого можно найти в кодовой таблице

– внутреннем представлении знаков в ПК. Стандартом во всем мире считают таблицу ASCII.

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

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

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

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

ASCII

UNICODE

А, М, П.
Введем следующую кодировку: А-0, М-1, П-10.
Рассмотрим закодированный

текст: 1010.
Этому тексту соответствует два слова – МАМА и ПП.
Как видите, введенная кодировка не обеспечивает однозначное кодирование.

Неоднозначное кодирование

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

кодового слова.
Коды, для которых выполняется условие Фано, называют префиксными

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

Условие Фано

не совпадает с началом (префиксом) какого-либо другого, более длинного кода.

Прямое

условие Фано

D: 00
недопустимо:
C - 001
D – 00
Код D совпадает
с началом кода С

D: 11
недопустимо:
В - 11
D – 11
Код D совпадает
с кода В

D: 00
допустимо:
Прямое условие Фано выполнено.

из кодов не совпадает с окончанием (постфиксом) какого-либо другого, более

длинного кода.

D: 01
недопустимо:
C - 001
D – 01
Код D совпадает
с концом кода С

D: 11
недопустимо:
В - 11
D – 11
Код D совпадает
с кода В

D: 01
допустимо:
Обратное условие Фано выполнено.

из двух вышеуказанных условий Фано:
при выполнении прямого условия Фано

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

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

Условия Фано

Б, В, Г и Д, решили использовать неравномерный двоичный код,

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

Решение:

Н, О, используется неравномерный код, удовлетворяющий условию Фано. При этом

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

Подсказка

Решение:

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

– удастся ли при этом найти код для буквы О.

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

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

В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий

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

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

Подсказка

(для букв В, Г, Д, Е)
0
1
В
0
1
Г
0
1
Д
Е
суммарная длина кодовых слов будет

в этом случае равна 1 + 2 + 3 + 4 + 2·5 = 20
(А-0, Б-10, В-110, Г-1110, Д-11110, Е-11111)

1 + 2 + 4·4 = 19
(А-0, Б-10, В-1100, Г-1101,

Д-1110, Е-1111)

Ответ: 19

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

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

0

1

А

0

1

0

1

Б

В

Г

суммарная длина кодовых слов будет в этом случае равна
1 + 3 +2 + 3 = 9
(А-0, Б-110, В-10, Г-111)

Ответ: 9

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

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

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

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

П-001. Какой код минимальной длины следует задать для кодировки буквы

Т, добавляемой в алфавит?

Задача 5

Ответ: 11

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

кодировка А-01, М-10, П-001, Т-11. Можно ли уменьшить длину кода

одного из символов, сохраняя однозначность декодирования?

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

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

Задача 7

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

Ответ: 10

А, Б, В и Г, используется неравномерный (по длине) код:

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

Задача 8

Ответ: D3A6

Решение:
Закодируем сообщение ВАБГАВ – 1101001110100110.
Полученную двоичную последовательность переведем в шестнадцатеричный вид.
1101ӏ0011ӏ1010ӏ0110
D 3 A 6

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

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

Задача 9

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

Ответ: 10

буквы: А, В, С, D; для передачи используется двоичный код,

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

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

Ответ: 111

Ответ: 7С1С

из символов А, Б, В и Г, используется неравномерный (по

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

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

Ответ: 75023

Ответ: 27636

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

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

Ответ: 11

Ответ: 101

полный справочник для подготовки к ЕГЭ. –М.: АСТ Астрель, 2016.
Лещинер

В.Р. ЕГЭ 2017. Информатика. 0 вариантов. –М.: Издательство «Экзамен», 2017 –М.: Национальный Открытый Университет «ИНТУИТ», 2016
© Поляков К. Подготовка к ЕГЭ, 2009-2016 http://kpolyakov.spb.ru

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

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

Интернет-ресурсы