Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код:
Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
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
Меньший расход краски и лучшее качество для чёрного и серого цветов.
Растровые рисунки
лучший способ для хранения фотографий и изображений без четких границ
спецэффекты (тени, ореолы, и т.д.)
есть потеря информации (почему?)
при изменении размеров рисунка он искажается
размер файла не зависит от сложности рисунка (а от чего зависит?)
Какие свойства цифрового рисунка определяют его качество?
?
Векторные рисунки
Строятся из геометрических фигур:
отрезки, ломаные, прямоугольники
окружности, эллипсы, дуги
сглаженные линии (кривые Безье)
Для каждой фигуры в памяти хранятся:
размеры и координаты на рисунке
цвет и стиль границы
цвет и стиль заливки (для замкнутых фигур)
Форматы файлов:
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, сжатие с учётом восприятия человеком)
