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

1.

Язык и кодирование

2.

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

3.

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

4.

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

5.

Кодирование звука и видео

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

1. Язык и кодирование

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

3

Кодирование – это запись информации с помощью

некоторой знаковой системы (языка).

Зачем кодируют информацию?

Зачем кодируют информацию?

?

кодирование

10101001010

данные (код)

обработка

11111100010

данные (код)

хранение

борьба с помехами

(специальные способы

кодирования)

борьба с помехами

(специальные способы

кодирования)

передача

передача

Информация передается,

обрабатывается и хранится

в виде кодов.

Информация передается,

обрабатывается и хранится

в виде кодов.

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

4

Язык – знаковая система, используемая для хранения и

передачи информации.



естественные (русский, английский, …)

есть правила и исключения



формальные (строгие правила)

Грамматика – правила по которым из символов алфавита строятся

слова.

Синтаксис – правила, по которым из слов строятся предложения.

2

mc

E



program qq;

begin

writeln("Привет!");

end.

program qq;

begin

writeln("Привет!");

end.

2

8

16

10000

20

10

16







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

Задача 1. Закодируйте свое имя с помощью азбуки

Морзе.

ВАСЯ

Код неравномерный, нужен разделитель!

Код неравномерный, нужен разделитель!

!

5

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

Задача 2. Закодируйте свое имя с помощью кодовой

таблицы (Windows-1251):

0

1

2

3

4

5

6

7

8

9

A

B C D E

F

C А

Б

В

Г

Д Е Ж З

И Й К Л М Н О П

D Р

С

Т

У

Ф Х Ц Ч Ш Щ Ъ Ы Ь

Э Ю Я

ВАСЯ

С2 С0 D1 DF

В

А

С

Я

Код равномерный, разделитель НЕ нужен!

Код равномерный, разделитель НЕ нужен!

!

6

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

Текст:



в России: Привет, Вася!



Windows-1251: CFF0E8E2E52C20C2E0F1FF21



передача за рубеж (транслит): Privet, Vasya!



стенография:



шифрование: Рсйгжу-!Гбта”

Информация (смысл сообщения) может

быть закодирована разными способами!

Информация (смысл сообщения) может

быть закодирована разными способами!

!

Числа:



для вычислений: 25



прописью: двадцать пять



римская система: XXV

Как зашифровано?

Как зашифровано?

?

7

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

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

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

9

Двоичное кодирование – это кодирование всех видов

информации с помощью двух знаков (обычно 0 и 1).

Передача электрических сигналов:

сигнал с помехами

сигнал с помехами

время

U

«1»

«0»

полезный

сигнал

полезный

сигнал

сигнал с помехами

сигнал с помехами

5 В

U

1 0 1

время

полезный

сигнал

полезный

сигнал

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

10

•

в такой форме можно закодировать (почти) все

виды информации

•

нужны только устройства с двумя состояниями

•

почти нет ошибок при передаче данных

•

компьютеру легче обрабатывать данные

человеку сложно воспринимать двоичные коды

Можно ли использовать не «0» и «1», а другие

символы, например, «А» и «Б»?

Можно ли использовать не «0» и «1», а другие

символы, например, «А» и «Б»?

?

кодировщик

кодировщик

ч

ис

л

а

ч

ис

л

а

символы

символы

рисунки

рисунки

з

в

у

к

з

в

у

к

101011011101110110101

101011011101110110101

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

11

Декодирование – это восстановление сообщения из

последовательности кодов.

М

А

Ы

Л

У

пробел

00

1

01

0

10

11

МАМА МЫЛА ЛАМУ → 00 1 00 1 11 00 01 0 1 11 0 1 00 10

0010011100010111010010



???

ЛЛАЛЛАААЛЛЛАЛАААЛАЛЛАЛ

Не все коды допускают однозначное

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

Не все коды допускают однозначное

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

!

Почему?

Почему?

?

Приняли сообщение:

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

12

Равномерные коды – все кодовые слова (коды

отдельных букв) имеют одинаковую длину.

М

А

Ы

Л

У

пробел

000

001

010

011

100

101

МАМА МЫЛА ЛАМУ:

000 001 000 001 101 000 010 011 001 101 011 001 000

100

Равномерные коды позволяют однозначно

декодировать сообщения!

Равномерные коды позволяют однозначно

декодировать сообщения!

!

сообщения получаются длинными

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

13

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

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

длине код:

Как нужно закодировать букву Г, чтобы длина кода была

минимальной и допускалось однозначное разбиение

кодированного сообщения на буквы?

1) 00

2) 01

3) 11

4) 010

А

Б

В

Г

1

000

001

?

Решение:

1)

для букв А-Б-В выполнятся условие Фано

2)

при Г=00 условие Фано нарушится (пары Г-Б, Г-В)

3)

при Г=01 условие Фано выполняется

4)

при Г=11 условие Фано нарушится (пара А-Г)

5)

при Г=010 условие Фано выполняется (но длиннее 01)

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

Кодирование чисел и

символов

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

15

Алфавит: 0, 1

Основание (количество цифр): 2

10



2

10



2

2



10

2



10

19

2

9

18

1

1

2

4

8

1

1

2

2

4

0

0

2

1

2

0

0

2

0

0

1

1

19 = 10011

2

система

счисления

система

счисления

10011

2

4 3 2 1 0

разряды

= 1·2

4

+

0·2

3

+

0·2

2

+

1·2

1

+

1·2

0

= 16 + 2 + 1 = 19

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

16

Текстовый файл

•

на экране (символы)

•

в памяти – двоичные

коды

1000001

2

1000010

2

1000011

2

1000100

2

В файле хранятся не изображения символов, а

их числовые коды в двоичной системе!

!

65

66

67

68

А где же хранятся изображения?

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

17

1.

Сколько символов надо использовать

одновременно? или 65536 (UNICODE)

2.

Сколько места надо выделить на символ:

3.

Выбрать 256 любых символов (или 65536) -

алфавит.

4.

Каждому символу – уникальный код 0..255

(или 0..65535). Таблица символов:

5.

Коды – в двоичную систему.

256

256

256 = 2

8

8 бит на символ

256 = 2

8

8 бит на символ

65

66

67

68

…

A

B

C

D

…

коды

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

0

1

254

255

127

128

таблица ASCII

(международная)

расширение

(национальный алфавит)

ASCII = American Standard Code for Information Interchange

0-31

управляющие символы:

7 – звонок, 10 – новая строка, 13 – возврат каретки, 27 –

Esc.

32

пробел

знаки препинания:

. , : ; ! ?

специальные знаки:

+ - * / () {} []

48-57

цифры 0..9

65-90

заглавные латинские буквы A-Z

97-122 строчные латинские буквы a-z

Кодовая страница (расширенная таблица ASCII)

для русского языка:

CP-866 для системы MS DOS

CP-1251 для системы Windows (Интернет)

КОИ8-Р для системы UNIX (Интернет)

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

•

1 байт на символ – файлы небольшого

размера!

•

просто обрабатывать в программах

•

нельзя использовать символы разных

кодовых страниц одновременно (русские

и французские буквы, и т.п.)

•

неясно, в какой кодировке текст

(перебор вариантов!)

•

для каждой кодировки нужен свой

шрифт (изображения символов)

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

20

•

110 182 символа (2012)

•

каждому символу присвоен код

кириллица:

А – 0410

16

,

Б – 0411

16

, …

а – 0430

16

,

б – 0431

16

, …

•

коды 0..10FFFF

16

, всего 1 114 112

Идея: объединить все символы в

одну таблицу!

!

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

можно одновременно использовать

символы разных языков (Интернет)

размер файла увеличивается

•

общеупотребительные символы

0..65535 = 2

16

-1 (0..FFFF

16

)

•

эти символы можно закодировать с

помощью 16 бит

•

кодировка UTF-16

(почти все символы по 16 бит)

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

22

•

символы ASCII – 1 байт на символ

•

остальные символы от 2 до 4 байт

•

более 50% сайтов используют UTF-8

•

тексты, состоящие только из кодов ASCII

(коды 0 – 127) не увеличиваются в размере

•

переменное число байтов на символ

•

замедление работы программ

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

3. Кодирование рисунков

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

24

•

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

точечный рисунок, состоит из пикселей

фотографии, размытые изображения

•

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

рисунок, состоит из отдельных геометрических фигур

чертежи, схемы, карты

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

25

Шаг 1. Дискретизация:

разбивка на пиксели.

Шаг 2. Для каждого пикселя

определяется

единый цвет.

Пиксель – это наименьший

элемент рисунка, для

которого можно независимо

установить цвет.

Пиксель – это наименьший

элемент рисунка, для

которого можно независимо

установить цвет.

Есть потеря информации!

•

почему?

•

как ее уменьшить?

!

Разрешение: число пикселей на дюйм, pixels per inch (ppi)

экран 96 ppi, печать 300-600 ppi, типография 1200 ppi

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

26

Шаг 3. От цвета – к числам: модель RGB

цвет = R + G + B

red

красный

0..255

blue

синий

0..255

green

зеленый

0..255

R = 218

G = 164

B = 32

R = 135

G = 206

B = 250

Шаг 4. Числа – в двоичную систему.

Сколько памяти нужно для хранения цвета 1 пикселя?

?

Сколько разных цветов можно кодировать?

?

256·256·256 = 16 777 216 (True Color)

R: 256=2

8

вариантов, нужно 8 бит = 1 байт

R G B: всего 3 байта

Глубина

цвета

Глубина

цвета

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

27

Шаг 1. Выбрать количество цветов: 2, 4, … 256.

Шаг 2. Выбрать 256 цветов из палитры:

248 0 88

0 221 21

181 192 0

21 0 97

Шаг 3. Составить палитру (каждому цвету – номер 0..255)

палитра хранится в начале файла

248 0 88

0 221 21

…

181 192

0

…

21 0

97

… 161 12 20

19 23 90

0

1

254

255

45

65

Шаг 4. Код пикселя = номеру его цвета в палитре

65

1

45 14

…

12 23

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

28

Сколько занимает палитра и основная часть?

?

Файл с палитрой:

палитра

коды пикселей

256 = 2

8

цветов:

палитра

256·3 = 768 байт

рисунок

8 бит на пиксель

16 цветов:

палитра

16·3 = 48 байт

рисунок

4 бита на пиксель

2 цвета:

палитра

2·3 = 6 байт

рисунок

1 бит на пиксель

Один цвет в палитре: 3 байта (RGB)

Глубина

цвета

Глубина

цвета

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

29

Формат

True Color

Палитра

Прозрачност

ь

BMP





JPG



GIF





PNG







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

G

R

B

G

B

G

R

B

30

Белый – красный = голубой

C = Cyan

Белый – зелёный = пурпурный

M = Magenta

Белый – синий = желтый

Y = Yellow

Модель CMY

C

M

Y

0

0

0

255 255

0

255

0

255

0

255 255

255 255 255

Модель CMYK: + Key color

Меньший расход краски и лучшее качество

для чёрного и серого цветов.

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

31

•

лучший способ для хранения

фотографий и изображений без четких

границ

•

спецэффекты (тени, ореолы, и т.д.)

•

есть потеря информации (почему?)

•

при изменении размеров рисунка он

искажается

•

размер файла не зависит от сложности

рисунка (а от чего зависит?)

Какие свойства цифрового рисунка

определяют его качество?

?

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

32

Строятся из геометрических фигур:

•

отрезки, ломаные, прямоугольники

•

окружности, эллипсы, дуги

•

сглаженные линии (кривые Безье)

Для каждой фигуры в памяти хранятся:

•

размеры и координаты на рисунке

•

цвет и стиль границы

•

цвет и стиль заливки (для замкнутых фигур)

Форматы файлов:

•

WMF (Windows Metafile)

•

CDR (CorelDraw)

•

AI (Adobe Illustrator)

•

SVG

(Inkscape)

для Web

для Web

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

33

<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>

<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>

прямоугольник

прямоугольник

размеры

размеры

координаты

координаты

конту

р

конту

р

заливка

заливка

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

34

•

лучший способ для хранения чертежей,

схем, карт;

•

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

•

при изменении размера нет искажений;

•

меньше размер файла, зависит от

сложности рисунка;

•

неэффективно использовать для

фотографий и размытых изображений

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

5. Кодирование звука

и видео

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

36

аналоговый

сигнал

Оцифровка – это преобразование аналогового сигнала

в цифровой код (дискретизация).

Оцифровка – это преобразование аналогового сигнала

в цифровой код (дискретизация).

T

t

– интервал дискретизации (с)

T

T

f

1



– частота дискретизации

(Гц, кГц)

8 кГц – минимальная частота для

распознавания речи

11 кГц, 22 кГц,

44,1 кГц – качество CD-дисков

48 кГц – фильмы на DVD

96 кГц, 192 кГц

Человек слышит

16 Гц … 20 кГц

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

37

Сколько битов нужно, чтобы записать число 0,6?

Сколько битов нужно, чтобы записать число 0,6?

?

T

t

0

1

2

3

4

5

7

6

3-битное кодирование:

8 битов = 256 уровней

16 битов = 65536 уровней

24 бита = 2

24

уровней

АЦП = Аналого-Цифровой Преобразователь

Квантование (дискретизация по уровню) – это представление

числа в виде цифрового кода конечной длины.

Квантование (дискретизация по уровню) – это представление

числа в виде цифрового кода конечной длины.

Разрядность кодирования —

это число битов, используемое

для хранения одного отсчёта.

Разрядность кодирования —

это число битов, используемое

для хранения одного отсчёта.

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

38

Задача. Определите информационный объем данных,

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

1 минута с частотой 44 кГц с помощью 16-битной

звуковой карты. Запись выполнена в режиме «стерео».

За 1 сек каждый канал записывает 44000 значений,

каждое занимает 16 битов = 2 байта

всего 44000



2 байта = 88000 байтов

С учётом «стерео»

всего 88000



2 = 176000 байтов

За 1 минуту

176000



60 = 1056000 байтов



10313 Кбайт



10 Мбайт

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

39

Как восстановить сигнал?

T

t

без

сглаживани

я

без

сглаживани

я

после

сглаживани

я

после

сглаживани

я

Какой улучшить качество?

Какой улучшить качество?

?

уменьшать

T

Что при этом ухудшится?

Что при этом ухудшится?

?



размер файла

аналоговые

устройства!

ЦАП = Цифро-Аналоговый Преобразователь

было до

оцифровки

было до

оцифровки

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

40

можно закодировать любой звук (в т.ч. голос, свист,

шорох, …)

•

есть потеря информации

•

большой объем файлов

Какие свойства оцифрованного звука определяют

качество звучания?

Какие свойства оцифрованного звука определяют

качество звучания?

?

Форматы файлов:

WAV

(Waveform audio format), часто без сжатия (размер!)

MP3

(MPEG-1 Audio Layer 3, сжатие с учётом

восприятия человеком)

AAC

(Advanced Audio Coding, 48 каналов, сжатие)

WMA

(Windows Media Audio, потоковый звук, сжатие)

OGG

(Ogg Vorbis, открытый формат, сжатие)

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

41

MIDI (Musical Instrument Digital Interface — цифровой

интерфейс музыкальных инструментов).

в файле

.mid

:

•

нота (высота, длительность)

•

музыкальный инструмент

•

параметры звука (громкость, тембр)

•

до 1024 каналов

в памяти звуковой карты:

•

образцы звуков (волновые таблицы)

MIDI-клавиатура:



нет потери информации при

кодировании инструментальной

музыки



небольшой размер файлов

невозможно закодировать

нестандартный звук, голос

программа для

звуковой карты!

программа для

звуковой карты!

128

мелодических и

47 ударных

128

мелодических и

47 ударных

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

42

В файле (модуле):

•

образцы звуков (сэмплы)

•

нотная запись, трек (track) – дорожка

•

музыкальный инструмент

•

до 32 каналов

Использование: демосцены (важен размер файла)

Форматы файлов:

MOD

разработан для компьютеров Amiga

S3M

оцифрованные каналы + синтезированный

звук, 99 инструментов

XM, STM, …

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

43

Синхронность!

Видео = изображения + звук

Видео = изображения + звук

!

изображения:

•

≥ 25 кадров в секунду

•

PAL: 768×576, 24 бита

за 1 с: 768×576×3 байта ≈ 32 Мб

за 1 мин: 60×32 Мбайта ≈ 1,85 Гб

•

HDTV: 1280×720, 1920×1080.

•

исходный кадр + изменения (10-15 с)

•

сжатие (кодеки – алгоритмы сжатия)

•

DivX, Xvid, H.264, WMV, Ogg Theora…

звук:

•

48 кГц, 16 бит

•

сжатие (кодеки – алгоритмы сжатия)

•

MP3, AAC, WMA, …

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

44

AVI

– Audio Video Interleave – чередующиеся звук и

видео; контейнер – могут использоваться

разные кодеки

MPEG – Motion Picture Expert Group

WMV

– Windows Media Video, формат фирмы

Microsoft

MP4

– MPEG-4, сжатое видео и звук

MOV

– Quick Time Movie, формат фирмы Apple

WebM

– открытый формат, поддерживается

браузерами