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

Август 12, 2022

Главная
Информатика
Кодирование и декодирование информации

Содержание

3. Кодирование — это преобразование информации из одной ее формы представления в другую, наиболее удобную для её
4. каждого текста лежит алфавит – конечное В основе множество алфавит, символов. В основе русского языка лежит
5. При нажатии на клавиатурную клавишу компьютер получает сигнал в виде двоичного числа, р.асшифровку которого можно найти
6. . Половина таблицы стандартов ASCII содержит коды цифр, управляющих символов и латинских букв. Другая ее часть
7. Пример. Пусть у нас есть алфавит из 3-х символов – А, М, П. Введем следующую кодировку:
8. Условие Фано: никакое кодовое слово не совпадает с началом другого кодового слова. Все сообщения, закодированные с
10. Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо
11. D: 01 недопустимо: C - 001 D – 01 Код D совпадает с концом кода С
12. Для однозначности декодирования последовательности кодов достаточно выполнения хотя вышеуказанных условий Фано: - при выполнении прямого бы
13. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный
14. Решение: 0 1 А 0 1 Б На оставшуюся свободную ветку нужно «повесить» 4 кодовых слова
15. Решение: 0 1 А 0 1 Б 0 1 0 1 В Г 0 1 Д
16. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код,
18. Кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в
19. При равномерном кодировании все символы кодируются кодами равной длины. При неравномерном кодировании разные символы могут кодироваться
20. Для трехбуквенного алфавита {А, М, П} используется кодировка А-01, М-10, П-001. Какой код минимальной длины буквы
21. Ответ: П-00 Для четырехбуквенного алфавита {А, М, П, Т} используется кодировка А-01, М-10, П-001, Т-11. Можно
22. По каналу связи передаются сообщения, содержащие только 4 буквы: А, В, С, D. Для передачи используется
23. Ответ: D3A6 Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и
24. По каналу связи передаются сообщения, содержащие только 3 буквы: А, В, С. Для передачи используется двоичный
26. Задание 1. По каналу связи передаются сообщения, содержащие только 4 буквы: А, В, С, D; для
27. системе счисления. Задание 3. Для передачи по каналу связи сообщения, состоящего только из символов А, Б,
29. Скачать презентацию

Слайд 2

Слайд 3

Кодирование — это преобразование информации из одной ее формы представления в

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

Слайд 4

каждого текста лежит алфавит – конечное
В основе множество алфавит,
символов. В основе русского языка лежит
называемый кириллицей, состоящий из 33
строчных и 33 заглавных букв. В основе английского

языка лежит латиница – алфавит, состоящий из 26 строчных и 26 заглавных букв. Пусть задан алфавит Т, содержащий m

символов:
Словом S в

Т={t1, t2, … tm}
алфавите T называют любую

последовательность символов алфавита:
S =s1s2…sk,
где si- это символы алфавита. Число символов в слове – k называют длиной слова.
Мощность алфавита – это количество символов в нем.

Слайд 5

При нажатии на клавиатурную клавишу компьютер получает сигнал в виде двоичного

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

Получается, зашифровать

что один байт позволяет
256 разных

символов, ведь

именно такое количество комбинаций можно составить. Эти сочетания и являются ключевой частью таблицы ASCII.

Слайд 6

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

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

Долгое время

при работе с текстами, сохраняемыми в

компьютере, используется код ASCII.

Такой алфавит,

содержащий 256 различных символов, мог включать латиницу

и кириллицу, цифры, знаки

операций,

знаки

препинания,

все-таки

этого

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

было хранить в

алфавита памяти

компьютера тексты на любых естественных языках.
Сегодня для хранения текстов используется кодировка из 2-х

байтов, называемая UNICODE кодировкой,
словами из 16 битов

кодировать алфавит,

позволяющая
содержащий

216=65536 символов.

ASCII

UNICODE

Слайд 7

Пример.
Пусть у нас есть алфавит из 3-х символов – А, М,

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

Слайд 8

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

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

Слайд 9

Слайд 10

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

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

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

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

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

Слайд 11

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

кода С

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

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

Слайд 12

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

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

Слайд 13

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г,

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

Слайд 14

Решение:
0
1
А
0
1
Б
На оставшуюся свободную ветку нужно «повесить» 4 кодовых слова (для букв

В, Г, Д, Е)

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

Слайд 15

Решение:
0
1
А
0
1
Б
0
1
0
1
В Г
0
1
Д
Е
суммарная длина кодовых слов будет в этом случае равна 1 + 2

+ 4·4 = 19
(А-0, Б-10, В-1100, Г-1101, Д-1110, Е-1111)

Ответ: 19

Слайд 16

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

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

четырёх кодовых слов?

1
0

суммарная длина

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

Ответ: 9

Слайд 17

Слайд 18

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

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

Слайд 19

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

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

никакое кодовое кодового слова; закодированное

слово не является началом другого
сообщение можно однозначно

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

Слайд 20

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

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

Слайд 21

Ответ: П-00
Для четырехбуквенного алфавита {А, М, П, Т} используется кодировка А-01,

М-10, П-001, Т-11. Можно ли уменьшить длину кода одного из символов, сохраняя однозначность декодирования?

Слайд 22

По каналу связи передаются сообщения, содержащие только 4 буквы: А, В,

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

буквы C будет 10.

Ответ: 10

Слайд 23

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

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

переведем в

Полученную двоичную последовательность шестнадцатеричный вид.
1101ӏ0011ӏ1010ӏ0110 D 3 A 6

Слайд 24

По каналу связи передаются сообщения, содержащие только 3 буквы: А, В,

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

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

Слайд 25

Слайд 26

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

кодовые слова: А: 0, В: 10, D: 110. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Ответ: 111 Задание 2. Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-00, Б-11, В-100, Г-011. Через канал связи передаётся сообщение: ГБВАГВ.

Ответ: 7С1С

Слайд 27

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

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

Ответ: 27636

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

Содержание

Кодирование — это преобразование информации из одной ее формы представления в

При нажатии на клавиатурную клавишу компьютер получает сигнал в виде двоичного

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

Пример.Пусть у нас есть алфавит из 3-х символов – А, М,

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

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

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г,

Решение:01А01БНа оставшуюся свободную ветку нужно «повесить» 4 кодовых слова (для букв

Решение:01А01Б0101В Г01ДЕсуммарная длина кодовых слов будет в этом случае равна 1 + 2

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