теория 1.2 Кодирование информации (1)

1. Архитектура компьютеров

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

2.

Дискретное кодирование

3. Что такое кодирование?

Кодирование – это запись информации с
помощью некоторой знаковой системы (языка).
? Зачем кодируют информацию?
кодирование
Информация передается,
обрабатывается и хранится
данные (код)в виде кодов.
10101001010
передача
данные (код)
11111100010
борьба с помехами
(специальные способы
кодирования)
3
передача
обработка
хранение

4.

Кодирование — это представление информации в
форме, удобной для её хранения, передачи и
автоматической обработки.
Код — это правило, по которому сообщение
преобразуется в цепочку знаков.
Язык — это система знаков и правил,
используемая для записи и передачи
информации.
Формальный язык — это язык, в котором
однозначно определяется значение каждого
слова, а также правила построения
предложений и придания им смысла.
4

5. Языки

Язык – знаковая система, используемая для
хранения и передачи информации.
◼ естественные (русский, английский, …)
есть правила и исключения
◼ формальные (строгие правила)
E = mc
2
program qq;
begin
writeln("Привет!");
end.
16 = 1016 = 208 = 100002
Грамматика – правила по которым из символов алфавита
строятся слова.
Синтаксис – правила, по которым из слов строятся
предложения.
5

6. Знаковые системы

Знак — это «заменитель» объекта,
вызывает в сознании объект.
– пиктограмма
Символ — это знак, о значении которого
люди договорились.
§ – параграф
Знаковая система определяется
алфавитом (набором используемых
знаков) и правилами выполнения
операций с этими знаками.
010101
6

7. Цели и способы кодирования

Текст:
▪ в России: Привет, Вася!
▪ Windows-1251: CFF0E8E2E52C20C2E0F1FF21
▪ передача за рубеж (транслит): Privet, Vasya!
▪ стенография:
▪ шифрование: Рсйгжу-!Гбта”
Числа:
▪ для вычислений: 25
▪ прописью: двадцать пять
▪ римская система: XXV
7

8. Аналоговые сигналы и устройства

Аналоговый сигнал — это сигнал,
который в любой момент времени
может принимать любые
значения в заданном диапазоне.
Аналоговые компьютеры
▪ невозможно «очистить» сигнал от помех
▪ при измерении сигнала вносится ошибка
▪ при копировании аналоговая
информация искажается
8

9. Дискретные (цифровые) сигналы

U
U1
0
1
1
0
1
U0
0
T
2T
3T
4T
время
Свойства:
• сигнал изменяется только в отдельные
моменты времени (дискретность по времени);
• принимают только несколько возможных
значений (дискретность по уровню).
Дискретный сигнал — это последовательность
значений, каждое из которых принадлежит
некоторому конечному множеству.
9

10. Дискретность

Цель – максимально точно передавать
сообщения при сильных помехах.
Pacta sunt servanda.
•— —
•—
••
•—•—
01000011001
могут хранить и обрабатывать
! Компьютеры
только дискретную информацию!
… закодированную с помощью
конечного количества знаков
некоторого алфавита.
Все виды информации нужно
! перевести
в дискретный вид!
10

11. Дискретизация

Дискретизация — это представление
единого объекта в виде множества
отдельных элементов.
π
π
3,13
3,14
3,15
11

12. Дискретизация

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
время
дискретизация
! При дискретизации
есть потеря информации!
? Как уменьшить потери?
дискретная информация
12

13. Непрерывность и дискретность

—
! Дискретность
это не свойство
информации, а её
представления.
1
0
2
3
V
4
5
6
V
аналоговые
данные
дискретные
данные
13

14. Непрерывность и дискретность

увеличении точности дискретизации
! При
свойства аналоговой и дискретной
информации практически совпадают!
3,1415926
14

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

Равномерное и
неравномерное
кодирование

16. Вспомним известное

Алфавит — это набор знаков, который
используется в языке.
Мощность алфавита — это количество знаков в
алфавите.
Равномерный код — это код, в котором все
кодовые слова имеют одинаковую длину.
Неравномерный код — это код, в котором
кодовые слова имеют различную длину.
Двоичное кодирование — это кодирование с
помощью двух знаков.
1 бит — это одна двоичная цифра (один знак
сообщения, записанного в двоичном коде).
16

17. Равномерные коды

Равномерные коды – все кодовые слова (коды
отдельных букв) имеют одинаковую длину.
М
А
Ы
Л
У
пробел
000
001
010
011
100
101
МАМА МЫЛА ЛАМУ:
000 001 000 001 101 000 010 011 001 101 011 001
000 100
! Равномерные коды позволяют однозначно
декодировать сообщения!
сообщения получаются
длинными
17

18. Неравномерные коды

кодовые слова имеют разную длину
М
А
Ы
Л
У
пробел
01
00
1011
100
1010
11
0
0
1
А
М
0100010011011011100001110000011010
1
0
0
1
0
Л
У
1
1
Ы
М А М А
М
Ы
Л
А
Л
А М
Префиксный код – ни одно кодовое
слово не совпадает с началом
другого кодового слова
(условие Фано).
! Любой префиксный код позволяет
однозначно декодировать сообщения!
18
У

19. Количество возможных сообщений

Если алфавит языка состоит из M символов
(имеет мощность M), количество
различных сообщений длиной L знаков
равно
N=ML
Для двоичного кода: N = 2L
Сколько
• возможных 7-битовых двоичных кодов?
27
• возможных 5-буквеных слов в русском языке?
• возможных 3-буквеных слов в английском языке?
335
263
19

20. Двоичное кодирование

Двоичное кодирование – это кодирование всех видов
информации с помощью двух знаков (обычно 0 и 1).
Передача электрических сигналов:
сигнал с
помехами
U
U
сигнал с
помехами
5В
«1
»
1
полезный
сигнал
20
время
полезный
сигнал
0
1
«0
время
»

21. Двоичное кодирование

символы
рисунки
кодировщик
101011011101110110101
• в такой форме можно закодировать (почти) все
виды информации
• нужны только устройства с двумя состояниями
• почти нет ошибок при передаче данных
• компьютеру легче обрабатывать данные
человеку сложно воспринимать двоичные коды
? Можно ли использовать не «0» и «1», а другие
21
символы, например, «А» и «Б»?

22. Количество возможных сообщений

Сколько
• различных чисел можно закодировать в
8-битовой ячейке?
28
38
• различных чисел можно закодировать в
8-разрядной ячейке троичного компьютера
(-1, 0, 1)?
• сколько битов нужно выделить для
хранения номера спортсмена от 1 до 1000?
512 = 29 < 1000 210 = 1024
• сколько битов нужно выделить для
хранения температуры от –50 до 80 ?
128 = 27 < 131 28 = 256
10
8
22

23. Правило умножения

Если в сообщении длиной L на позиции i
может стоять один из Mi символов,
количество различных сообщений равно
N = M1 M2 … ML
Задача 1. Сколько существует различных
сообщений длины 5 в алфавите {A, B, C,
Х}, если буква «Х» может появляться
только на первом или на последнем
месте?
4 ∙ 3 ∙ 3 ∙ 3 ∙ 4 = 432
4 3 3 3 4
M1 M2 M3 M4 M5
23

24. Правило умножения

Задача 2. Сколько существует 5-значных
десятичных чисел, все цифры в которых
различны?
9
9
8
7
6
9 ∙ 9 ∙ 8 ∙ 7 ∙ 6 = 27216
M1 M2 M3 M4 M5
Не может быть
0!
24

25. Неравномерные коды

•можно уменьшить длину
закодированного сообщения
Равномерный код:
12 бит
А
00
Г
01
Р
10
А
0
Г
01
Р
10
ГАГАРА →
010001001000
9 бит
Неравномерный код:
ГАГАРА →
010010100
•не всегда однозначно декодируется
ГАГАРА
→
010010100
010010100
АРАРРА
→
25
010010100

26. Правило сложения

Задача 3. Сколько существует двоичных
кодов длиной от 2 до 5 битов?
L = 2:
L = 4:
N2 = 22 = 4 L = 3:
N4 = 24 = 16 L = 5:
N3 = 23 = 8
N5 = 25 = 32
N = 4 + 8 + 16 + 32 = 60
N = N2 + N3 + N4 + N5
! Правило сложения!
26

27. Правила умножения и сложения

Задача 4. Сколько существует различных
3-буквенных слов в алфавите {К, Р, О, Т}, в
которых буква К встречается ровно 1 раз?
К *
*
1
3
3
*
К
* 3 ∙ 1 ∙ 3 = 99 + 9 + 9 = 27
*
* К 3∙3∙1=9
1∙3∙3=9
27

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

Декодирование

29. Декодирование

Декодирование – это восстановление сообщения из
последовательности кодов.
М
А
Ы
Л
У
пробел
00
1
01
0
10
11
МАМА МЫЛА ЛАМУ → 00 1 00 1 11 00 01 0 1 11 0 1 00 10
Приняли сообщение:
0010011100010111010010 → ???
ЛЛАЛЛАААЛЛЛАЛАААЛАЛЛАЛ
! Не все коды допускают однозначное
декодирование!
29

30. Декодирование

Декодирование — это восстановление
сообщения из последовательности кодов.
•— — •— ••• •—•—
ВАСЯ
? Когда разделитель не нужен?
корень
А
Б
В
Г
Д
0
00 10 01 110 00
0
1
1
0
Все кодовые
слова
1
В
заканчиваются на 0
листьях дерева!
A
Д
1
1
0
1
0
Б
Г
30

31. Декодирование

корень
110 0000100110
1100000100110
Г
А В
Д Б
0
A
0
1
0
1
1
0
В
Д
1
0
Б
1
Г
Префиксный код — это код, в котором ни одно
кодовое слово не совпадает с началом другого
кодового слова (условие Фано). Сообщения
декодируются однозначно.
31

32. Постфиксные коды

Постфикс = окончание слова.
Постфиксный код – ни одно кодовое слово не
совпадает с концом другого кодового слова
(«обратное» условие Фано).
М
А
Ы
Л
У
пробел
10
00
1101
001
0101
11
! Любой постфиксный код позволяет
однозначно декодировать сообщения
(с конца)!
для декодирования нужно получить
всё сообщение целиком
32

33. Задачи на построение кода

Для передачи по каналу связи сообщения, состоящего только
из букв А, Б, В, Г, решили использовать неравномерный по
длине код:
А
Б
В
Г
1
000
001
?
Как нужно закодировать букву Г, чтобы длина кода была
минимальной и допускалось однозначное разбиение
кодированного сообщения на буквы?
1) 00
2) 01
3) 11
4) 010
Решение:
1) для букв А-Б-В выполнятся условие Фано
2) при Г=00 условие Фано нарушится (пары Г-Б, Г-В)
3) при Г=01 условие Фано выполняется
4) при Г=11 условие Фано нарушится (пара А-Г)
5) при Г=010 условие Фано выполняется (но длиннее 01)
33

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

А
01
Б
В
010 011
Г
11
Д
101
? Выполняются ли условия Фано?
Декодирование может быть неоднозначным…
010100111101
АБАГД
АБВГА
быть, что условия Фано
! Может
не выполнены, а декодирование
однозначно!
34

35. Комбинаторика

Задача 1. Сколько существует
четырёхзначных чисел, составленных из
чётных цифр?
4 5 5 5 = 500
4
5
2, 4, 6, 8 0, 2, 4, 6, 8
N = m1 m2 m3 m4
35
! Правило умножения!

36. Комбинаторика

Задача 2. Сколько существует
четырёхзначных чисел, составленных из
чётных цифр, в которых цифры не
повторяются?
4 4 3 2 = 96
4
5
2, 4, 6, 8
0, 2, 4, 6, 8
одна цифра уже
использована!
36

37. Комбинаторика

Задача 3. Сколько существует двоичных
кодов длиной 4 бита?
2 2 2 2 =24=16
N =M
2
! Правило умножения!
0, 1
N = M M M M
L
длина
сообщения
мощность
алфавита
37

38. Комбинаторика

Задача 4. Сколько существует двоичных
кодов длиной от 2 до 5 битов?
L = 2:
L = 4:
N2 = 22 = 4
N4 = 24 = 16
L = 3:
L = 5:
N2 = 23 = 8
N5 = 25 = 32
N = 4 + 8 + 16 + 32 = 60
N = N2 + N3 + N4 + N5
38
! Правило сложения!

39. Комбинаторика

Задача 5. В некоторой стране живут 1000
человек. Правительство решило присвоить
каждому собственный код, причем все коды
должны быть одинаковой длины и состоять
только из цифр 1, 2, 3 и 4. Определите
наименьшую длину таких кодов.
N = 4L ≥ 1000
L = 1:
L = 2:
L = 3:
39
41 = 4 < 1000
42 = 16 < 1000
43 = 64 < 1000
L = 4:
L = 5:
44 = 256 < 1000
45 = 1024 > 1000

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

Алфавитный подход к
измерению количества
информации

41. Алфавитный подход

Количество информации в битах определяется
длиной сообщения в двоичном коде.
10101100
8
битов
вперёд
назад
вправо
влево
00
01
10
11
? Сколько битов?
00 10 10 10 01 01 11
14 битов
41

42. Другие единицы измерения

1 байт (bytе) = 8 бит
1 Кбайт (килобайт) = 1024 байта
1 Мбайт (мегабайт) = 1024 Кбайт
1 Гбайт (гигабайт)
= 1024 Мбайт
1 Тбайт (терабайт) = 1024 Гбайт
42

43. Алфавитный подход

1) определяем мощность алфавита M;
2) определяем количество битов информации i,
приходящихся на один символ, —
информационную ёмкость (объём) символа:
M, символов
2
4
8
16
32
64
128
256
512
1024
i, битов
информации
1
2
3
4
5
6
7
8
9
10
3) количество информации в сообщении:
I = L·i
где L – количество символов в сообщении.
43

44. Алфавитный подход

• каждый символ несёт одинаковое количество
информации
• частота появления разных символов (и
сочетаний символов) не учитывается
• количество информации определяется только
длиной сообщения и мощностью алфавита
• смысл сообщения не учитывается
44

45. Задача

Определить количество информации в 10
страницах текста (на каждой странице 32 строки
по 64 символа) при использовании алфавита из
256 символов.
1) информационная ёмкость символа:
256 = 28 i = 8 бит = 1 байт
2) количество символов на странице:
32·64 = 25 ·26 = 211
3) общее количество символов:
L = 10·211
4) информационный объём сообщения:
I = L·i = 10·211·1 байтов = 20 Кбайт
45

46. Задача

Пароль длиной не более 11 символов (цифры и
12 различных букв, как строчные, так и
прописные. Посимвольное равномерное
кодирование, для хранения пароля отводится
минимально возможное целое количество байт.
Сколько байт нужно для 60 паролей?
1) мощность алфавита M = 10 + 12 + 12 = 34
2) информационная ёмкость символа:
25 < 34 26 i = 6 бит
2) на один пароль:
округление
6 · 11 = 66 бит = 8,… → 9 байт
вверх
4) на 60 паролей:
I = 60 · 9 байтов = 540 байт
46

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

Кодирование текстов

48. Кодирование символов

48
Кодирование символов
Система Брайля:
1 0
0 0
0 0
100000
А
011101
1 1
1 1
0 0
111100
В
1 0
1 0
0 0
Б
0 1
1 1
0 1
101000
Г
Общий подход:
•нужно использовать N символов
•выберем число битов k на символ: 2k N
•сопоставим каждому символу код – число от 0 до 2k – 1
•переведем коды в двоичную систему

49. Кодирование чисел (двоичная система)

Алфавит: 0, 1
Основание (количество цифр): 2
10 → 2
19 2
18 9
1 8
1
2
4
4
0
2 → 10
4 3 2 1 0 разряды
19 = 100112
2
2
2
0
2
1
0
1
система
счисления
2
0
4 + 0·23 + 0·22 + 1·21 + 1·20
=
1·2
100112
= 16 + 2 + 1 = 19
49

50. Кодирование символов

50
Кодирование символов
Текстовый файл
• на экране (символы)
• в памяти – коды
10000012 10000102 10000112 10001002
65
66
67
68
! В файле хранятся не изображения символов, а
их числовые коды!
Файлы со шрифтами: *.fon, *.ttf, *.otf

51. Кодировка ASCII (7-битная)

51
Кодировка ASCII (7-битная)
ASCII = American Standard Code for Information
Interchange
Коды 0-127:
0-31
управляющие символы:
7 – звонок, 10 – новая строка,
13 – возврат каретки, 27 – Esc.
32 пробел
знаки препинания: . , : ; ! ?
специальные знаки: + - * / () {} []
48-57
цифры 0..9
65-90
заглавные латинские буквы A-Z
97-122 строчные латинские буквы a-z

52. 8-битные кодировки

52
8-битные кодировки
Кодовые страницы (расширения ASCII):
0
127
1
таблица ASCII
Для русского языка:
CP-866
CP-1251
КОI8-R
MacCyrillic
128
254
национальный
алфавит
для MS DOS
для Windows (Интернет)
для UNIX (Интернет)
для компьютеров Apple
Проблема:
Windows-1251
Привет, Вася!
рТЙЧЕФ, чБУС!
KOI8-R
оПХБЕР, бЮЯЪ!
Привет, Вася!
255

53. 8-битные кодировки

53
8-битные кодировки
▪ 1 байт на символ – файлы
небольшого размера!
▪ просто обрабатывать в программах
▪ нельзя использовать символы
разных кодовых страниц
одновременно (русские и
французские буквы, и т.п.)
▪ неясно, в какой кодировке текст
(перебор вариантов!)
▪ для каждой кодировки нужен свой
шрифт (изображения символов)

54. Стандарт UNICODE

! Идея: объединить все символы в
одну таблицу!
• 110 182 символа (2012)
• каждому символу присвоен код
кириллица:
А – 041016, Б – 041116, …
а – 043016, б – 043116, …
• коды 0..10FFFF16, всего 1 114 112
54

55. UNICODE в Windows (UTF-16)

• общеупотребительные символы
0..65535 = 216-1 (0..FFFF16)
• эти символы можно закодировать с
помощью 16 бит
• кодировка UTF-16 (почти все символы по 16 бит)
можно одновременно использовать
символы разных языков (Интернет)
размер файла увеличивается
55

56. UNICODE в Linux (кодировка UТF-8)

•символы ASCII – 1 байт на символ
•остальные символы от 2 до 4 байт
•более 50% сайтов используют UTF-8
• тексты, состоящие только из кодов ASCII
(коды 0 – 127) не увеличиваются в размере
• переменное число байтов на символ
• замедление работы программ
56

57. Стандарт UNICODE

57
Стандарт UNICODE
1 112 064 знаков, используются около 100 0
Windows: UTF-16
16 битов на распространённые символы,
32 бита на редко встречающиеся
Linux: UTF-8
8 битов на символ для ASCII,
от 16 до 48 бита на остальные
▪ совместимость с ASCII
▪ более экономична, чем UTF-16, если
много символов ASCII

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

Кодирование
графической информации

59. Два типа кодирования рисунков

•растровое кодирование
точечный рисунок, состоит из пикселей
фотографии, размытые изображения
•векторное кодирование
рисунок, состоит из отдельных геометрических фигур
чертежи, схемы, карты
59

60. Растровое кодирование

60
Растровое кодирование
растр
пиксель
дискретизация
Пиксель – это наименьший элемент рисунка, для
которого можно задать свой цвет.
Растровое изображение – это изображение, которое
кодируется как множество пикселей.

61. Растровое кодирование

Шаг 1. Дискретизация:
разбивка на пиксели.
61
Шаг 2. Для каждого
пикселя определяется
единый цвет.

62. Растровое кодирование (True Color)

Шаг 3. От цвета – к числам: модель
RGB цвет = R + G + B
red
green
красный зеленый
0..255
0..255
R = 218
G = 164
B = 32
blue
синий
0..255
R = 135
G = 206
B = 250
Шаг 4. Числа – в двоичную
систему.
256·256·256 = 16 777 216 (True Color)
R: 256=28 вариантов, нужно 8 бит = 1 байт
R G B: всего 3 байта
62

63. Растровое кодирование

63
Растровое кодирование
0
0
0
1
0
0
0
0
0
0
1
1
1
1
1
1
1A2642FF425A5A7E16
0
1
0
1
0
0
0
1
1
0
0
1
0
1
1
1
1
0
0
1
0
1
1
1
0
1
0
1
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
1
0
0
0
0
1A
26
42
FF
42
5A
5A
7E

64. Разрешение

64
Разрешение
Разрешение – это количество пикселей,
приходящихся на дюйм размера изображения.
ppi = pixels per inch, пикселей на дюйм
1 дюйм = 2,54 см
Разрешение: экран 96 ppi, печать 300-600 ppi, типография 1200 ppi
300 ppi
96 ppi
печать
экран
48 ppi
24 ppi

65. Разрешение

65
Разрешение
Задача 1. Какой размер в пикселях должен иметь
закодированный рисунок с разрешением 300 ppi,
чтобы с него можно было сделать отпечаток
размером 10×15 см?
10 см × 300 пикселей
1181 пиксель
высота
2,54 см
15 см × 300 пикселей
1771 пиксель
ширина
2,54 см

66. Разрешение

66
Разрешение
Задача 2. Закодированный рисунок имеет
размеры 5760 × 3840 пикселей и
разрешение 600 ppi. Какой размер будет у
изображения, отпечатанного на принтере?
ширина
высота
5760 пикселей × 2,54 см
600 пикселей
3840 пикселей × 2,54 см
600 пикселей
24,4 см
16,3 см

67. Кодирование цвета

67
Кодирование цвета
00 11 11 11 11 11 11 11
00 11 11 11 11 11 11 11
00 01 01 01 01 01 01 01
00 01 01 01 01 01 01 01
00 10 10 10 10 10 10 10
00 10 10 10 10 10 10 10
? Как выводить на монитор цвет с кодом 00?
? Как закодировать цвет в виде чисел?

68. Теория цвета Юнга-Гельмгольца

68
Теория цвета Юнга-Гельмгольца
чувствительность
три типа
«колбочек»
0
400
500
600
700
, нм
! Свет любой длины волны можно заменить на
красный, зелёный и синий лучи!

69. Цветовая модель RGB

69
Цветовая модель RGB
Д. Максвелл, 1860 цвет = ( R,
G,
B )
green blue
red
красныйзеленый синий
0..255 0..255 0..255
(0, 0, 0)
(0, 255, 0)
(255, 255, 255)
(255, 0, 0)
(255, 150, 150)
(255, 255, 0)
(0, 0, 255)
(100, 0, 0)
? Сколько разных цветов можно кодировать?
256·256·256 = 16 777 216 (True Color, «истинный цвет»)
RGB – цветовая модель для устройств,
! излучающих
свет (мониторов)!

70. Цветовая модель RGB

70
Цветовая модель RGB
(255, 255, 0) → #FFFF00
RGB
Веб-страница
(0, 0, 0)
#000000
(255,255,255)
#FFFFFF
(255, 0, 0)
#FF0000
(0, 255, 0)
#00FF00
(0, 0, 255)
#0000FF
(255, 255, 0)
#FFFF00
(204,204,204)
#CCCCCC

71. Глубина цвета

71
Глубина цвета
Глубина цвета — это количество битов, используемое
для кодирования цвета пикселя.
? Сколько памяти нужно для хранения цвета
1 пикселя в режиме True Color?
R (0..255)
256 = 28 вариантов
8 битов = 1 байт
R G B: 24 бита = 3 байта
Задача. Определите размер файла, в котором
закодирован растровый рисунок размером 20×30
пикселей в режиме истинного цвета (True Color)?
20 30 3 байта = 1800 байт

72. Кодирование с палитрой

72
Кодирование с палитрой
? Как уменьшить размер файла?
• уменьшить разрешение
• уменьшить глубину цвета
снижается
качество
Цветовая палитра – это таблица, в которой каждому
цвету, заданному в виде составляющих в модели
RGB, сопоставляется числовой код.

73. Кодирование с палитрой

73
Кодирование с палитрой
00 11 11 11 11 11 11 11
00 11 11 11 11 11 11 11
00 01 01 01 01 01 01 01
00 01 01 01 01 01 01 01
00 10 10 10 10 10 10 10
00 10 10 10 10 10 10 10
Палитра:
0
0
0
цвет 002
0
0 255 255 0
0
цвет 012
цвет 102
? Какая глубина цвета?
? Сколько занимает палитра?
255 255 255
цвет 112
2 бита на пиксель
3 4 = 12 байтов

74. Кодирование с палитрой

74
Кодирование с палитрой
Шаг 1. Выбрать количество цветов: 2, 4, … 256.
Шаг 2. Выбрать 256 цветов из палитры:
248 0 88
0 221 21
181 192 0
21 0 97
Шаг 3. Составить палитру (каждому цвету – номер 0..255)
палитра хранится в начале файла
0
248 0 88
1
0 221 21
254
181 192 0
…
255
21 0 97
Шаг 4. Код пикселя = номеру его цвета в палитре
2 45 65 14
…
12 23

75. Кодирование с палитрой

75
Кодирование с палитрой
Файл с палитрой:
палитра
коды пикселей
Количество цветов
Размер палитры
(байтов)
Глубина цвета
(битов на пиксель)
2
4
16
256
6
12
48
768
1
2
4
8

76. Растровые рисунки: форматы файлов

76
Растровые рисунки: форматы файлов
Формат
BMP
JPG
True Color
Палитра
✓
✓
✓
GIF
PNG
✓
✓
✓
Прозрачность
Анимация
✓
✓
✓

77. Кодирование цвета при печати (CMYK)

77
Кодирование цвета при печати (CMYK)
RG
B
R
G
B
G
B
Белый – красный = голубой
C = Cyan
Белый – зелёный = пурпурный
M = Magenta
Белый – синий = желтый
C
M
Y
0
0
0
Y = Yellow
Модель CMY
255255 0
255 0 255
0 255255
255255255
▪ меньший расход краски и
лучшее качество для
чёрного и серого цветов

78. RGB и CMYK

78
RGB и CMYK
видит человек
RGB
CMYK
• не все цвета, которые
показывает монитор (RGB),
можно напечатать (CMYK)
• при переводе кода цвета из
RGB в CMYK цвет искажается
RGB(0,255,0)
→CMYK(65,0,100,0)
→ RGB(104,175,35)

79. Цветовая модель HSB (HSV)

79
Цветовая модель HSB (HSV)
HSB = Hue (тон, оттенок)
Saturation (насыщенность)
Brightness (яркость) или Value (величи
0 /360
270
0
Тон (H)
100
Яркость (B)
90
100
0
180
насыщенность –
добавить белого
яркость –
добавить чёрного

80. Цветовая модель Lab

80
Цветовая модель Lab
Международный стандарт кодирования цвета,
независимого от устройства (1976 г.)
Основана на модели восприятия цвета человеком.
Lab = Lightness (светлота)
a, b (задают цветовой тон)
• для перевода между
цветовыми моделями:
RGB → Lab → CMYK
Светлота 25%
Светлота 75%
• для цветокоррекции
фотографий

81. Профили устройств

81
Профили устройств
? Какой цвет увидим?
RGB(255,0,0)
680нм
CMYK(0,100,100,0)
RGB(255,0,0)
как 680нм
профиль
монитора
RGB(225,10,2
профиль
сканера
профиль
принтера

82. Растровое кодирование: итоги

82
Растровое кодирование: итоги
•универсальный метод (можно закодировать
любое изображение)
•единственный метод для кодирования и
обработки размытых изображений, не
имеющих чётких границ (фотографий)
•есть потеря информации (почему?)
•при изменении размеров цвет и форма
объектов на рисунке искажается
•размер файла не зависит от сложности
рисунка (а от чего зависит?)

83. Векторное кодирование

83
Векторное кодирование
Рисунки из геометрических фигур:
•отрезки, ломаные, прямоугольники
•окружности, эллипсы, дуги
•сглаженные линии (кривые Безье)
Для каждой фигуры в памяти хранятся:
•размеры и координаты на рисунке
•цвет и стиль границы
•цвет и стиль заливки (для замкнутых фигур)

84. Векторное кодирование

84
Векторное кодирование
Кривые Безье:
А
В
Б
угловой узел
гладкий узел
Д
Г
Хранятся координаты узлов и концов «рычагов»
(3 точки для каждого узла, кривые 3-го порядка).

85. Векторное кодирование (итоги)

85
Векторное кодирование (итоги)
•лучший способ для хранения чертежей,
схем, карт
•при кодировании нет потери информации
•при изменении размера нет искажений
растровый
рисунок
векторный
рисунок
•меньше размер файла, зависит от
сложности рисунка
•неэффективно использовать для
фотографий и размытых изображений

86. Векторное кодирование: форматы файлов

• WMF (Windows Metafile)
• EMF (Windows Metafile)
• CDR (программа CorelDraw)
для вебстраниц
• SVG (Scalable Vector Graphics, масштабируемые
векторные изображения)
• AI (программа Adobe Illustrator)
86

87. Векторные рисунки: SVG

87
Векторные рисунки: SVG
<svg>
прямоугольник
размеры
<rect width="135" height="30"
конту
координаты
x="0" y="10"
р
stroke-width="1" stroke="rgb(0,0,0)"
fill="rgb(255,255,255)"/>
заливка
<rect width="135" height="30" x="0" y="40"
stroke-width="1" stroke="rgb(0,0,0)"
fill="rgb(0,0,255)"/>
<rect width="135" height="30" x="0" y="70"
stroke-width="1" stroke="rgb(0,0,0)"
fill="rgb(255,0,0)"/>
<line x1="0" y1="0"
x2="0" y2="150"
stroke-width="15" stroke="rgb(0,0,0)" />
</svg>

88. 3D-графика

88
3D-графика
Трёхмерная графика (3D-графика) – это раздел
компьютерной графики, который занимается
созданием моделей и изображений трёхмерных
объектов.
3D-модели: каждая точка имеет 3 координаты
проекции (на плоскость)
3D-модели
анимация
расчёты (на прочность и т.п.)
3D-печать

89. Построение каркаса (рёбер)

89
Построение каркаса (рёбер)
узлы
(вершины)
! Хранятся координаты
точек (x, y, z)!
? Растровая или векторная?
рёбра

90. Поверхность

90
Поверхность
треугольники
многоугольники
(полигоны)

91. Завершение модели

91
Завершение модели
сглаживание
установка света
материал
установка камеры
камера

92. Результат

92
Результат
рендеринг
3D-печать
Рендеринг (визуализация) — построение двухмерного
изображения по 3D-модели.

93. Фрактальная графика

93
Фрактальная графика
Фрактал — это фигура, обладающая самоподобием:
основная фигура состоит из нескольких таких же, только
меньшего размера.
Пифагорово дерево Множество Мандельброт
Задаётся математической формулой + алгоритмом
построения.

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

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

95. Оцифровка звука

95
Оцифровка звука
аналоговы
й сигнал
Оцифровка – это преобразование аналогового
сигнала в цифровой код (дискретизация).
T – интервал дискретизации
1
f = – частота дискретизации
T
(Гц, кГц)
T
Человек слышит
16 Гц … 20 кГц
t
8 кГц – минимальная частота для
распознавания речи
11 кГц, 22 кГц,
44,1 кГц – качество CD-дисков
48 кГц – фильмы на DVD
96 кГц, 192 кГц

96. Оцифровка звука: квантование

96
Оцифровка звука: квантование
Сколько битов нужно, чтобы записать число
?0,6?
Квантование (дискретизация по уровню) – это представление
числа в виде цифрового кода конечной длины.
АЦП = Аналого-Цифровой Преобразователь
3-битное кодирование:
7
6
5
4
3
2
1
0
8 битов = 256 уровней
16 битов = 65536 уровней
24 бита = 224 уровней
Разрядность кодирования —
это число битов, используемое
для хранения одного отсчёта.
T
t

97. Оцифровка звука

97
Оцифровка звука
Задача. Определите информационный объем данных,
полученных при оцифровке звука длительностью
1 минута с частотой 44 кГц с помощью 16-битной звуковой
карты. Запись выполнена в режиме «стерео».
За 1 сек каждый канал записывает 44000
значений,
каждое занимает 16 битов = 2 байта
всего 44000 2 байта = 88000 байтов
С учётом «стерео»
всего 88000 2 = 176000 байтов
За 1 минуту
176000 60 = 10560000 байтов
10313 Кбайт 10 Мбайт

98. Оцифровка звука

98
Оцифровка звука
Как восстановить сигнал?
ЦАП = Цифро-Аналоговый Преобразователь
аналоговые
устройства!
T
t
? Как улучшить качество?
? Что при этом ухудшится?
уменьшать T
размер файла

99. Оцифровка – итог

99
Оцифровка – итог
можно закодировать любой звук (в т.ч.
голос, свист, шорох, …)
•есть потеря информации
•большой объем файлов
? Какие свойства оцифрованного звука определяют
качество звучания?
Форматы файлов:
WAV (Waveform audio format), часто без сжатия (размер!)
MP3 (MPEG-1 Audio Layer 3, сжатие с учётом
восприятия человеком)
AAC (Advanced Audio Coding, 48 каналов, сжатие)
WMA (Windows Media Audio, потоковый звук, сжатие)
OGG (Ogg Vorbis, открытый формат, сжатие)

100. Инструментальное кодирование

100
Инструментальное кодирование
MIDI (Musical Instrument Digital Interface — цифровой
интерфейс музыкальных инструментов).
в файле .mid:
128 мелодических
и 47 ударных
• нота (высота, длительность)
• музыкальный инструмент
• параметры звука (громкость, тембр)
• до 1024 каналов
программа для
звуковой карты!
в памяти звуковой карты:
• образцы звуков (волновые таблицы)
MIDI-клавиатура:
▪ нет потери информации
при кодировании
инструментальной музыки
▪ небольшой размер файлов
невозможно закодировать
нестандартный звук,
голос

101. Трекерная музыка

101
Трекерная музыка
В файле (модуле):
• образцы звуков (сэмплы)
• нотная запись, трек (track) – дорожка
• музыкальный инструмент
• до 32 каналов
Форматы файлов:
MOD разработан для компьютеров Amiga
S3M оцифрованные каналы + синтезированный
звук, 99 инструментов
XM, STM, …
Использование: демосцены (важен размер
файла)

102. Кодирование видео

102
Кодирование видео
! Видео = изображения + звук Синхронность!
изображения:
• ≥ 25 кадров в секунду
• PAL: 720×576, 24 бита
за 1 с: 720×576×25×3 байта ≈ 30 Мб
за 1 мин: 60×32 Мбайта ≈ 1,73 Гб
• HDTV: 1280×720, 1920×1080.
• 4K: 4096×3072
• исходный кадр + изменения (10-15 с)
• сжатие (кодеки – алгоритмы сжатия)
• DivX, Xvid, H.264, WMV, Ogg Theora…
звук:
• 48 кГц, 16 бит
• сжатие (кодеки – MP3, AAC, WMA, …)

103. Форматы видеофайлов

103
Форматы видеофайлов
AVI
– Audio Video Interleave – чередующиеся звук
и видео; контейнер – могут использоваться
разные кодеки
MPEG – Motion Picture Expert Group
WMV – Windows Media Video, формат фирмы
Microsoft
MP4 – MPEG-4, сжатое видео и звук
MOV – Quick Time Movie, формат фирмы Apple
WebM – открытый формат, поддерживается
браузерами