Презентация на тему _Кодирование информации_. Кодирование информации Тема Язык и кодирование Что такое кодирование
 Скачать 2.73 Mb.
|
Кодирование информацииЯзык и кодирование Двоичное кодирование Кодирование чисел и символов Кодирование рисунков Кодирование звука и видео Кодирование информацииТема 1. Язык и кодирование Что такое кодирование?Кодирование – это запись информации с помощью некоторой знаковой системы (языка). Зачем кодируют информацию? ? кодирование 10101001010 данные (код) обработка 11111100010 данные (код) хранение борьба с помехами (специальные способы кодирования) передача передача Информация передается, обрабатывается и хранится в виде кодов. ЯзыкиЯзык – знаковая система, используемая для хранения и передачи информации.
формальные (строгие правила) Грамматика – правила по которым из символов алфавита строятся слова. Синтаксис – правила, по которым из слов строятся предложения. program qq; begin writeln("Привет!"); end. Азбука МорзеЗадача 1. Закодируйте свое имя с помощью азбуки Морзе. ВАСЯ Код неравномерный, нужен разделитель! ! Кодовые таблицыЗадача 2. Закодируйте свое имя с помощью кодовой таблицы (Windows-1251):
ВАСЯ С2 С0 D1 DF В А С Я Код равномерный, разделитель НЕ нужен! ! Цели и способы кодированияТекст:
Windows-1251: CFF0E8E2E52C20C2E0F1FF21 передача за рубеж (транслит): Privet, Vasya! стенография: шифрование: Рсйгжу-!Гбта” Информация (смысл сообщения) может быть закодирована разными способами! ! Числа:
прописью: двадцать пять римская система: XXV Как зашифровано? ? Кодирование информацииТема 2. Двоичное кодирование Двоичное кодированиеДвоичное кодирование – это кодирование всех видов информации с помощью двух знаков (обычно 0 и 1). Передача электрических сигналов: сигнал с помехами время U «1» «0» полезный сигнал сигнал с помехами 5 В U 1 0 1 время полезный сигнал Двоичное кодированиев такой форме можно закодировать (почти) все виды информации нужны только устройства с двумя состояниями почти нет ошибок при передаче данных компьютеру легче обрабатывать данные человеку сложно воспринимать двоичные коды Можно ли использовать не «0» и «1», а другие символы, например, «А» и «Б»? ? кодировщик числа символы рисунки звук 101011011101110110101 ДекодированиеДекодирование – это восстановление сообщения из последовательности кодов.
МАМА МЫЛА ЛАМУ → 00 1 00 1 11 00 01 0 1 11 0 1 00 10 0010011100010111010010 ??? ЛЛАЛЛАААЛЛЛАЛАААЛАЛЛАЛ Не все коды допускают однозначное декодирование! ! Почему? ? Приняли сообщение: Равномерные кодыРавномерные коды – все кодовые слова (коды отдельных букв) имеют одинаковую длину.
МАМА МЫЛА ЛАМУ: 000 001 000 001 101 000 010 011 001 101 011 001 000 100 Равномерные коды позволяют однозначно декодировать сообщения! ! сообщения получаются длинными Неравномерные коды
кодовые слова имеют разную длину У Ы Л А М 0 0 0 0 0 1 1 1 1 1 0100010011011011100001110000011010 М А М А М Ы Л А А Л М У Префиксный код – ни одно кодовое слово не совпадает с началом другого кодового слова (условие Фано). Любой префиксный код позволяет однозначно декодировать сообщения! ! Постфиксные кодыПостфикс = окончание слова. Постфиксный код – ни одно кодовое слово не совпадает с концом другого кодового слова («обратное» условие Фано).
Любой постфиксный код позволяет однозначно декодировать сообщения (с конца)! ! для декодирования нужно получить всё сообщение целиком Задачи на построение кодаДля передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? 1) 00 2) 01 3) 11 4) 010
Решение: для букв А-Б-В выполнятся условие Фано при Г=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 Кодирование символовТекстовый файл на экране (символы) в памяти – двоичные коды
В файле хранятся не изображения символов, а их числовые коды в двоичной системе! !
А где же хранятся изображения? Кодирование символовСколько символов надо использовать одновременно? или 65536 (UNICODE) Сколько места надо выделить на символ: Выбрать 256 любых символов (или 65536) - алфавит. Каждому символу – уникальный код 0..255 (или 0..65535). Таблица символов: Коды – в двоичную систему. 256 256 = 28 8 бит на символ
коды
таблица ASCII (международная) расширение (национальный алфавит) ASCII = American Standard Code for Information Interchange
32 пробел знаки препинания: . , : ; ! ? специальные знаки: + - * / () {} [] 48-57 цифры 0..9 65-90 заглавные латинские буквы A-Z 97-122 строчные латинские буквы a-z Кодовая страница (расширенная таблица ASCII) для русского языка: CP-866 для системы MS DOS CP-1251 для системы Windows (Интернет) КОИ8-Р для системы UNIX (Интернет) 1 байт на символ – файлы небольшого размера! просто обрабатывать в программах нельзя использовать символы разных кодовых страниц одновременно (русские и французские буквы, и т.п.) неясно, в какой кодировке текст (перебор вариантов!) для каждой кодировки нужен свой шрифт (изображения символов) Стандарт UNICODE110 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) палитра хранится в начале файла
0 1 254 255 45 65 Шаг 4. Код пикселя = номеру его цвета в палитре
Сколько занимает палитра и основная часть? ? Файл с палитрой:
256 = 28 цветов: палитра 256·3 = 768 байт рисунок 8 бит на пиксель 16 цветов: палитра 16·3 = 48 байт рисунок 4 бита на пиксель 2 цвета: палитра 2·3 = 6 байт рисунок 1 бит на пиксель Один цвет в палитре: 3 байта (RGB) Глубина цвета Форматы файлов (растровые рисунки)
Кодирование цвета при печати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 байтов С учётом «стерео»
За 1 минуту 176000 60 = 1056000 байтов 10313 Кбайт 10 Мбайт Оцифровка звукаКак восстановить сигнал? T t без сглаживания после сглаживания Какой улучшить качество? ? уменьшать T Что при этом ухудшится? ? размер файла аналоговые устройства! ЦАП = Цифро-Аналоговый Преобразователь было до оцифровки Оцифровка – итогможно закодировать любой звук (в т.ч. голос, свист, шорох, …) есть потеря информации большой объем файлов Какие свойства оцифрованного звука определяют качество звучания? ? Форматы файлов:
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 каналов Использование: демосцены (важен размер файла) Форматы файлов:
S3M оцифрованные каналы + синтезированный звук, 99 инструментов XM, STM, … Кодирование видеоСинхронность! Видео = изображения + звук ! изображения:
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, … Форматы видеофайлов
MPEG – Motion Picture Expert Group WMV – Windows Media Video, формат фирмы Microsoft MP4 – MPEG-4, сжатое видео и звук MOV – Quick Time Movie, формат фирмы Apple WebM – открытый формат, поддерживается браузерами Конец фильма |