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



Дата19.04.2020
өлшемі2,68 Mb.
#63052
түріЗадача

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

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

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

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

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

Языки

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

Азбука Морзе

  • Задача 1. Закодируйте свое имя с помощью азбуки Морзе.
  • ВАСЯ
  • Код неравномерный, нужен разделитель!
  • !

Кодовые таблицы

  • Задача 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
  • В
  • А
  • С
  • Я
  • Код равномерный, разделитель НЕ нужен!
  • !

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

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

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

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

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

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

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

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

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

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

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

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

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

  • М
  • А
  • Ы
  • Л
  • У
  • пробел
  • 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
    • 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 (Интернет)

8-битные кодировки (1 байт на символ)

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

Стандарт UNICODE

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

UNICODE в Windows (UTF-16)

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

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

  • символы ASCII – 1 байт на символ
  • остальные символы от 2 до 4 байт
  • более 50% сайтов используют UTF-8
  • тексты, состоящие только из кодов 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-клавиатура:
  • нет потери информации при кодировании инструментальной музыки
  • небольшой размер файлов
  • невозможно закодировать
  • нестандартный звук, голос
  • программа для звуковой карты!
  • 128 мелодических и 47 ударных

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

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

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

  • Синхронность!
  • Видео = изображения + звук
  • !
  • изображения:
    • ≥ 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, …

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

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

Конец фильма

  • ПОЛЯКОВ Константин Юрьевич
  • д.т.н., учитель информатики высшей категории,
  • ГОУ СОШ № 163, г. Санкт-Петербург
  • kpolyakov@mail.ru


Достарыңызбен бөлісу:




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет