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

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