Равномерные коды позволяют однозначно декодировать сообщения!
!
сообщения получаются длинными
Неравномерные коды
М
А
Ы
Л
У
пробел
01
00
1011
100
1010
11
кодовые слова имеют разную длину
У
Ы
Л
А
М
0
0
0
0
0
1
1
1
1
1
0100010011011011100001110000011010
М
А
М
А
М
Ы
Л
А
А
Л
М
У
Префиксный код – ни одно кодовое слово не совпадает с началом другого кодового слова (условие Фано).
Любой префиксный код позволяет однозначно декодировать сообщения!
!
Постфиксные коды
Постфикс = окончание слова.
Постфиксный код – ни одно кодовое слово не совпадает с концом другого кодового слова («обратное»условие Фано).
М
А
Ы
Л
У
пробел
10
00
1101
001
0101
11
Любой постфиксный код позволяет однозначно декодировать сообщения (с конца)!
!
для декодирования нужно получить всё сообщение целиком
Задачи на построение кода
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код:
Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
1) 00 2) 01 3) 11 4) 010
А
Б
В
Г
1
000
001
?
Решение:
для букв А-Б-В выполнятся условие Фано
при Г=00 условие Фано нарушится (пары Г-Б, Г-В)
при Г=01 условие Фано выполняется
при Г=11 условие Фано нарушится (пара А-Г)
при Г=010 условие Фано выполняется (но длиннее 01)
Комбинаторика
Задача 1. Сколько существует четырёхзначных чисел, составленных из чётных цифр?
4
5
5
5
0, 2, 4, 6, 8
5
4
2, 4, 6, 8
= 500
Правило умножения!
!
Комбинаторика
Задача 2. Сколько существует четырёхзначных чисел, составленных из чётных цифр, в которых цифры не повторяются?
4
4
3
2
0, 2, 4, 6, 8
5
4
2, 4, 6, 8
= 96
одна цифра уже использована!
Комбинаторика
Задача 3. Сколько существует двоичных кодов длиной 4 бита?
2
2
2
2
0, 1
2
=24=16
Правило умножения!
!
длина сообщения
мощность алфавита
Комбинаторика
Задача 4. Сколько существует двоичных кодов длиной от 2 до 5 битов?
L = 2: N2 = 22 = 4
Правило сложения!
!
L = 3: N2 = 23 = 8
L = 4: N4 = 24 = 16
L = 5: N5 = 25 = 32
N = N2 + N3 + N4 + N5
N = 4 + 8 + 16 + 32 = 60
Комбинаторика
Задача 5. В некоторой стране живут 1000 человек. Правительство решило присвоить каждому собственный код, причем все коды должны быть одинаковой длины и состоять только из цифр 1, 2, 3 и 4. Определите наименьшую длину таких кодов.
N= 4L
≥ 1000
L = 1: 41 = 4 < 1000
L = 2: 42 = 16 < 1000
L = 3: 43 = 64 < 1000
L = 4: 44 = 256 < 1000
L = 5: 45 = 1024 >1000
Кодирование информации
Тема 2. Кодирование чисел и символов
Кодирование чисел (двоичная система)
Алфавит: 0, 1 Основание (количество цифр): 2
10 2
2 10
19
2
9
18
1
2
4
8
1
2
2
4
0
2
1
2
0
2
0
0
1
19 = 100112
система счисления
100112
4 3 2 1 0
разряды
= 1·24 +0·23+0·22+1·21+1·20
= 16 + 2 + 1 = 19
Кодирование символов
Текстовый файл
на экране (символы)
в памяти – двоичные коды
10000012
10000102
10000112
10001002
В файле хранятся не изображения символов, а их числовые коды в двоичной системе!
!
65
66
67
68
А где же хранятся изображения?
Кодирование символов
Сколько символов надо использовать одновременно? или 65536 (UNICODE)
Сколько места надо выделить на символ:
Выбрать 256 любых символов (или 65536) - алфавит.
Каждому символу – уникальный код 0..255 (или 0..65535). Таблица символов:
Коды – в двоичную систему.
256
256 = 28 8 бит на символ
65
66
67
68
…
A
B
C
D
…
коды
8-битные кодировки (1 байт на символ)
0
1
254
255
127
128
таблица ASCII
(международная)
расширение
(национальный алфавит)
ASCII = American Standard Code for Information Interchange
тексты, состоящие только из кодов ASCII (коды 0 – 127) не увеличиваются в размере
переменное число байтов на символ
замедление работы программ
Кодирование информации
Тема 4. Кодирование рисунков
Два типа кодирования рисунков
растровое кодирование точечный рисунок, состоит из пикселей
фотографии, размытые изображения
векторное кодирование рисунок, состоит из отдельных геометрических фигур
чертежи, схемы, карты
Растровое кодирование
Шаг 1. Дискретизация: разбивка на пиксели.
Шаг 2. Для каждого пикселя определяется единый цвет.
Пиксель – это наименьший элемент рисунка, для которого можно независимо установить цвет.
Есть потеря информации!
почему?
как ее уменьшить?
!
Разрешение: число пикселей на дюйм, pixels per inch (ppi)
экран 96 ppi, печать 300-600 ppi, типография 1200 ppi
Растровое кодирование (True Color)
Шаг 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=28 вариантов, нужно 8 бит = 1 байт R G B: всего 3 байта
Глубина цвета
Растровое кодирование с палитрой
Шаг 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
Растровое кодирование с палитрой
Сколько занимает палитра и основная часть?
?
Файл с палитрой:
палитра
коды пикселей
256 = 28 цветов: палитра 256·3 = 768 байт
рисунок 8 бит на пиксель
16 цветов: палитра 16·3 = 48 байт
рисунок 4 бита на пиксель
2 цвета: палитра 2·3 = 6 байт
рисунок 1 бит на пиксель
Один цвет в палитре: 3 байта (RGB)
Глубина цвета
Форматы файлов (растровые рисунки)
Формат
True Color
Палитра
Прозрачность
BMP
JPG
GIF
PNG
Кодирование цвета при печати
G
R
B
G
B
G
R
B
Белый – красный = голубой 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
Меньший расход краски и лучшее качество для чёрного и серого цветов.
Растровые рисунки
лучший способ для хранения фотографий и изображений без четких границ
спецэффекты (тени, ореолы, и т.д.)
есть потеря информации (почему?)
при изменении размеров рисунка он искажается
размер файла не зависит от сложности рисунка (а от чего зависит?)
Какие свойства цифрового рисунка определяют его качество?
?
Векторные рисунки
Строятся из геометрических фигур:
отрезки, ломаные, прямоугольники
окружности, эллипсы, дуги
сглаженные линии (кривые Безье)
Для каждой фигуры в памяти хранятся:
размеры и координаты на рисунке
цвет и стиль границы
цвет и стиль заливки (для замкнутых фигур)
Форматы файлов:
WMF (Windows Metafile)
CDR(CorelDraw)
AI (Adobe Illustrator)
SVG (Inkscape)
для Web
Векторные рисунки
x="0" y="10"
stroke-width="1" stroke="rgb(0,0,0)"
fill="rgb(255,255,255)"/>
stroke-width="1" stroke="rgb(0,0,0)"
fill="rgb(0,0,255)"/>
stroke-width="1" stroke="rgb(0,0,0)"
fill="rgb(255,0,0)"/>
x2="0" y2="150"
stroke-width="15" stroke="rgb(0,0,0)" />
прямоугольник
размеры
координаты
контур
заливка
Векторные рисунки
лучший способ для хранения чертежей, схем, карт;
при кодировании нет потери информации;
при изменении размера нет искажений;
меньше размер файла, зависит от сложности рисунка;
неэффективно использовать для фотографий и размытых изображений
Кодирование информации
Тема 5. Кодирование звука и видео
Оцифровка звука
аналоговый сигнал
Оцифровка – это преобразование аналогового сигнала в цифровой код (дискретизация).
T
t
– интервал дискретизации (с)
– частота дискретизации (Гц, кГц)
8 кГц – минимальная частота для распознавания речи
11 кГц, 22 кГц,
44,1 кГц – качество CD-дисков
48 кГц – фильмы на DVD
96 кГц, 192 кГц
Человек слышит
16 Гц … 20 кГц
Оцифровка звука: квантование
Сколько битов нужно, чтобы записать число 0,6?
?
T
t
0
1
2
3
4
5
7
6
3-битное кодирование:
8 битов = 256 уровней
16 битов = 65536 уровней
24 бита = 224 уровней
АЦП = Аналого-Цифровой Преобразователь
Квантование (дискретизация по уровню) – это представление числа в виде цифрового кода конечной длины.
Разрядность кодирования — это число битов, используемое
для хранения одного отсчёта.
Оцифровка звука
Задача. Определите информационный объем данных, полученных при оцифровке звука длительностью 1 минута с частотой 44 кГц с помощью 16-битной звуковой карты. Запись выполнена в режиме «стерео».
За 1 сек каждый канал записывает 44000 значений, каждое занимает 16 битов = 2 байта
всего 44000 2 байта = 88000 байтов
С учётом «стерео»
всего 88000 2 = 176000 байтов
За 1 минуту
176000 60 = 1056000 байтов
10313 Кбайт 10 Мбайт
Оцифровка звука
Как восстановить сигнал?
T
t
без сглаживания
после сглаживания
Какой улучшить качество?
?
уменьшать T
Что при этом ухудшится?
?
размер файла
аналоговые устройства!
ЦАП = Цифро-Аналоговый Преобразователь
было до оцифровки
Оцифровка – итог
можно закодировать любой звук (в т.ч. голос, свист, шорох, …)
есть потеря информации
большой объем файлов
Какие свойства оцифрованного звука определяют качество звучания?
?
Форматы файлов:
WAV (Waveform audio format), часто без сжатия (размер!)
MP3 (MPEG-1 Audio Layer 3, сжатие с учётом восприятия человеком)
AAC (Advanced Audio Coding, 48 каналов, сжатие)
WMA (Windows Media Audio, потоковый звук, сжатие)
OGG (Ogg Vorbis, открытый формат, сжатие)
Инструментальное кодирование
MIDI (Musical Instrument Digital Interface — цифровой интерфейс музыкальных инструментов).
в файле .mid:
нота (высота, длительность)
музыкальный инструмент
параметры звука (громкость, тембр)
до 1024 каналов
в памяти звуковой карты:
образцы звуков (волновые таблицы)
MIDI-клавиатура:
нет потери информации при кодировании инструментальной музыки
