Similar presentations:
Кодирование информации
1. Кодирование информации
1Кодирование
информации
§ 4. Дискретное кодирование
§ 5. Равномерное и
неравномерное кодирование
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
2. Кодирование информации
2Кодирование
информации
§ 4. Дискретное кодирование
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
3. Вспомним известное
Кодирование информации, 10 класс3
Вспомним известное
Кодирование — это представление информации
в форме, удобной для её хранения, передачи и
автоматической обработки.
Код — это правило, по которому сообщение
преобразуется в цепочку знаков.
Язык — это система знаков и правил,
используемая для записи и передачи
информации.
Формальный язык — это язык, в котором
однозначно определяется значение каждого
слова, а также правила построения
предложений и придания им смысла.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
4. Знаковые системы
Кодирование информации, 10 класс4
Знаковые системы
Знак — это «заменитель» объекта, вызывает в
сознании объект.
– пиктограмма
Символ — это знак, о значении которого люди
договорились.
§ – параграф
– рубль
Знаковая система определяется алфавитом
(набором используемых знаков) и правилами
выполнения операций с этими знаками.
?
Знаковая система в компьютерах?
К.Ю. Поляков, Е.А. Ерёмин, 2018
010101
http://kpolyakov.spb.ru
5. Аналоговые сигналы и устройства
Кодирование информации, 10 класс5
Аналоговые сигналы и устройства
Аналоговый сигнал — это сигнал,
который в любой момент времени
может принимать любые значения в
заданном диапазоне.
Аналоговые компьютеры
невозможно «очистить» сигнал от помех
при измерении сигнала вносится ошибка
при копировании аналоговая информация
искажается
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
6. Дискретные (цифровые) сигналы
Кодирование информации, 10 класс6
Дискретные (цифровые) сигналы
U
U1
1
1
0
1
0
U0
0
T
2T
3T
4T
время
Свойства:
• сигнал изменяется только в отдельные моменты
времени (дискретность по времени);
• принимают только несколько возможных значений
(дискретность по уровню).
Дискретный сигнал — это последовательность
значений, каждое из которых принадлежит
некоторому конечному множеству.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
7. Дискретность
Кодирование информации, 10 класс7
Дискретность
Цель – максимально точно передавать
сообщения при сильных помехах.
Pacta sunt servanda.
•— —
•—
••
•—•—
01000011001
!
Компьютеры могут хранить и обрабатывать
только дискретную информацию!
… закодированную с помощью конечного
количества знаков некоторого алфавита.
!
Все виды информации нужно
перевести в дискретный вид!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
8. Дискретизация
Кодирование информации, 10 класс8
Дискретизация
Дискретизация — это представление единого
объекта в виде множества отдельных
элементов.
π
π
3,13
К.Ю. Поляков, Е.А. Ерёмин, 2018
3,14
3,15
http://kpolyakov.spb.ru
9. Дискретизация
Кодирование информации, 10 класс9
Дискретизация
t°
t°
36,8
36,8
36,6
36,6
36,4
36,4
6
9
12 15 18 21 24
время
аналоговая информация
6 ч.
9 ч.
12 ч.
15 ч.
18 ч.
21 ч.
24 ч.
36,7°
36,8°
36,9°
36,7°
36,5°
36,5°
36,6°
!
6
9
12 15 18 21 24
время
дискретизация
При дискретизации
есть потеря информации!
?
Как уменьшить потери?
дискретная информация
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
10. Непрерывность и дискретность
Кодирование информации, 10 класс10
Непрерывность и дискретность
!
1
0
2
3
V
4
Дискретность —
это свойство не
информации, а её
представления.
5
6
V
аналоговые
данные
К.Ю. Поляков, Е.А. Ерёмин, 2018
дискретные
данные
http://kpolyakov.spb.ru
11. Непрерывность и дискретность
Кодирование информации, 10 класс11
Непрерывность и дискретность
!
При увеличении точности дискретизации
свойства аналоговой и дискретной
информации практически совпадают!
3,1415926
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
12. Кодирование информации
12Кодирование
информации
§ 5. Равномерное и
неравномерное кодирование
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
13. Вспомним известное
Кодирование информации, 10 класс13
Вспомним известное
Алфавит — это набор знаков, который
используется в языке.
Мощность алфавита — это количество знаков в
алфавите.
Равномерный код — это код, в котором все
кодовые слова имеют одинаковую длину.
Неравномерный код — это код, в котором
кодовые слова имеют различную длину.
Двоичное кодирование — это кодирование с
помощью двух знаков.
1 бит — это одна двоичная цифра (один знак
сообщения, записанного в двоичном коде).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
14. Количество возможных сообщений
Кодирование информации, 10 класс14
Количество возможных сообщений
Если алфавит языка состоит из M символов
(имеет мощность M), количество различных
сообщений длиной L знаков равно
N=ML
Для двоичного кода: N = 2L
27
Сколько
• возможных 7-битовых двоичных кодов?
• возможных 5-буквеных слов в русском
335
языке?
• возможных 3-буквеных слов в английском
языке?
263
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
15. Количество возможных сообщений
Кодирование информации, 10 класс15
Количество возможных сообщений
Сколько
• различных чисел можно закодировать в
8-битовой ячейке?
28
• различных чисел можно закодировать в
8-разрядной ячейке троичного компьютера
(-1, 0, 1)?
38
10
• сколько битов нужно выделить для
хранения номера спортсмена от 1 до 1000?
512 = 29 < 1000 210 = 1024
8
• сколько битов нужно выделить для
хранения температуры от –50 до 80 ?
128 = 27 < 131 28 = 256
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
16. Правило умножения
Кодирование информации, 10 класс16
Правило умножения
Если в сообщении длиной L на позиции i может
стоять один из Mi символов, количество
различных сообщений равно
N = M1 M2 … ML
Задача 1. Сколько существует различных
сообщений длины 5 в алфавите {A, B, C, Х},
если буква «Х» может появляться только на
первом или на последнем месте?
4
3
3
3
4
4 ∙ 3 ∙ 3 ∙ 3 ∙ 4 = 432
M1 M2 M3 M4 M5
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
17. Правило умножения
Кодирование информации, 10 класс17
Правило умножения
Задача 2. Сколько существует 5-значных
десятичных чисел, все цифры в которых
различны?
9
9
8
7
6
9 ∙ 9 ∙ 8 ∙ 7 ∙ 6 = 27216
M1 M2 M3 M4 M5
Не может быть 0!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
18. Неравномерные коды
Кодирование информации, 10 класс18
Неравномерные коды
• можно уменьшить длину закодированного
сообщения
Равномерный код:
12 бит
А
00
Г
01
Р
10
ГАГАРА → 010001001000
Неравномерный код:
А
0
Г
01
Р
10
9 бит
ГАГАРА → 010010100
• не всегда однозначно декодируется
→ 010010100 ГАГАРА
010010100
→ 010010100 АРАРРА
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
19. Правило сложения
Кодирование информации, 10 класс19
Правило сложения
Задача 3. Сколько существует двоичных кодов
длиной от 2 до 5 битов?
L = 2:
L = 4:
N2 = 22 = 4
N4 = 24 = 16
L = 3:
L = 5:
N3 = 23 = 8
N5 = 25 = 32
N = 4 + 8 + 16 + 32 = 60
N = N2 + N3 + N4 + N5
К.Ю. Поляков, Е.А. Ерёмин, 2018
!
Правило сложения!
http://kpolyakov.spb.ru
20. Правила умножения и сложения
Кодирование информации, 10 класс20
Правила умножения и сложения
Задача 4. Сколько существует различных
3-буквенных слов в алфавите {К, Р, О, Т}, в
которых буква К встречается ровно 1 раз?
К
*
*
1
3
3
1∙3∙3=9
*
К
*
3∙1∙3=9
*
*
К
3∙3∙1=9
К.Ю. Поляков, Е.А. Ерёмин, 2018
9 + 9 + 9 = 27
http://kpolyakov.spb.ru
21. Кодирование информации
21Кодирование
информации
§ 6. Декодирование
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
22. Декодирование
Кодирование информации, 10 класс22
Декодирование
Декодирование — это восстановление сообщения из
последовательности кодов.
•— — •— ••• •—•—
ВАСЯ
?
А
000
Б
10
Когда разделитель не нужен?
В
01
Г
110
Все кодовые слова
заканчиваются на
0
листьях дерева!
A
К.Ю. Поляков, Е.А. Ерёмин, 2018
корень
Д
001
1
0
1
0
1
В
Д
1
0
Б
0
1
Г
http://kpolyakov.spb.ru
23. Декодирование
Кодирование информации, 10 класс23
Декодирование
корень
Г
А В
Д Б
1
0
0
A
1
0
1100000100110
1100000100110
1
0
В
Д
1
Б
0
1
Г
Префиксный код — это код, в котором ни одно
кодовое слово не совпадает с началом другого
кодового слова (условие Фано). Сообщения
декодируются однозначно.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
24. Задачи
Кодирование информации, 10 класс24
Задачи
1. Для передачи сообщения, состоящего только из букв
А, Б, В, Г, решили использовать неравномерный код:
A = 0, Б = 10, В = 110.
Как нужно закодировать букву Г, чтобы длина кода
была минимальной и допускалось однозначное
декодирование?
2. Для передачи сообщения, состоящего только из букв
А, Б, В, Г, решили использовать неравномерный код:
A = 0, Б = 100, В = 101.
Как нужно закодировать букву Г, чтобы длина кода
была минимальной и допускалось однозначное
декодирование?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
25. Постфиксные коды
Кодирование информации, 10 класс25
Постфиксные коды
Постфиксный код — это код, в котором ни одно
кодовое слово не совпадает с окончанием
другого кодового слова. Сообщения
декодируются однозначно (с конца!).
А
000
Б
01
В
10
Г
011
Д
100
011000110110
01
1000110110
Б Д
К.Ю. Поляков, Е.А. Ерёмин, 2018
Г Б В
http://kpolyakov.spb.ru
26. Неоднозначное декодирование
Кодирование информации, 10 класс26
Неоднозначное декодирование
А
01
?
Б
010
В
011
Г
11
Д
101
Выполняются ли условия Фано?
Декодирование может быть неоднозначным…
АБАГД
010100111101
!
АБВГА
Может быть, что условия Фано
не выполнены, а декодирование
однозначно (см. учебник)!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
27. Задачи для самостоятельного решения
27Задачи для
самостоятельного решения
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
28. Задачи
Кодирование информации, 10 класс28
Задачи
1. Сколько существует в коде Морзе различных
последовательностей из точек и тире, длина которых от 4 до 6
символов?
2. Сколько существует различных
3-буквенных слов в алфавите {Ж, И, Р, А, Ф}, в которых буква Р
встречается ровно 1 раз?
3. Сколько существует различных сообщений длины 4 в алфавите
{A, B, C, D, E}, если буква «C» может появляться только на
втором или на предпоследнем месте?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
29. Конец фильма
Кодирование информации, 10 класс29
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru
30. Источники иллюстраций
Кодирование информации, 10 класс30
Источники иллюстраций
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
http://overhealth.ru
https://ufhealth.org
http://wmposters.com
http://www.ulmart.ru
http://all-graphic.net
http://123rf.com
http://made-in-china.com
http://megamaster.biz
http://evrobass.ru
http://blendercontest.com
http://ru.wikipedia.org
авторские материалы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru