лекции по ОТИ. Введение. Понятие информации. Информация и данные
 Скачать 376.35 Kb.
|
|
Тема: Кодирование символьной и числовой информации. Одна и та же информация может быть представлена (закодирована) в нескольких формах. C появлением компьютеров возникла необходимость кодирования всех видов информации, с которыми имеет дело и отдельный человек, и человечество в целом. Но решать задачу кодирования информации человечество начало задолго до появления компьютеров. Грандиозные достижения человечества - письменность и арифметика - есть не что иное, как система кодирования речи и числовой информации. Информация никогда не появляется в чистом виде, она всегда как-то представлена, как-то закодирована. Двоичное кодирование – один из распространенных способов представления информации. В вычислительных машинах, в роботах и станках с числовым программным управлением, как правило, вся информация, с которой имеет дело устройство, кодируется в виде слов двоичного алфавита. Кодирование символьной (текстовой) информации. Основная операция, производимая над отдельными символами текста - сравнение символов. При сравнении символов наиболее важными аспектами являются уникальность кода для каждого символа и длина этого кода, а сам выбор принципа кодирования практически не имеет значения. Для кодирования текстов используются различные таблицы перекодировки. Важно, чтобы при кодировании и декодировании одного и того же текста использовалась одна и та же таблица. Таблица перекодировки - таблица, содержащая упорядоченный некоторым образом перечень кодируемых символов, в соответствии с которой происходит преобразование символа в его двоичный код и обратно. Наиболее популярные таблицы перекодировки: ДКОИ-8, ASCII, CP1251, Unicode. Исторически сложилось, что в качестве длины кода для кодирования символов было выбрано 8 бит или 1 байт. Поэтому чаще всего одному символу текста, хранимому в компьютере, соответствует один байт памяти. Различных комбинаций из 0 и 1 при длине кода 8 бит может быть 28 = 256, поэтому с помощью одной таблицы перекодировки можно закодировать не более 256 символов. При длине кода в 2 байта (16 бит) можно закодировать 65536 символов. Кодирование числовой информации. Сходство в кодировании числовой и текстовой информации состоит в следующем: чтобы можно было сравнивать данные этого типа, у разных чисел (как и у разных символов) должен быть различный код. Основное отличие числовых данных от символьных заключается в том, что над числами кроме операции сравнения производятся разнообразные математические операции: сложение, умножение, извлечение корня, вычисление логарифма и пр. Правила выполнения этих операций в математике подробно разработаны для чисел, представленных в позиционной системе счисления. Основной системой счисления для представления чисел в компьютере является двоичная позиционная система счисления. Кодирование текстовой информации В настоящее время, большая часть пользователей, при помощи компьютера обрабатывает текстовую информацию, которая состоит из символов: букв, цифр, знаков препинания и др. Подсчитаем, сколько всего символов и какое количество бит нам нужно. 10 цифр, 12 знаков препинания, 15 знаков арифметических действий, буквы русского и латинского алфавита, ВСЕГО: 155 символов, что соответствует 8 бит информации. Суть кодирования заключается в том, что каждому символу ставят в соответствие двоичный код от 00000000 до 11111111 или соответствующий ему десятичный код от 0 до 255. Необходимо помнить, что в настоящее время для кодировки русских букв используют пять различных кодовых таблиц (КОИ - 8, СР1251, СР866, Мас, ISO), причем тексты, закодированные при помощи одной таблицы не будут правильно отображаться в другой Основным отображением кодирования символов является код ASCII - American Standard Code for Information Interchange- американский стандартный код обмена информацией, который представляет из себя таблицу 16 на 16, где символы закодированы в шестнадцатеричной системе счисления. Контрольные вопросы: Как происходит кодирование символьной информации? Как происходит кодирование числовой информации? Как происходит кодирование (текстовой) информации? Тема: Кодирование графической информации. Важным этапом кодирования графического изображения является разбиение его на дискретные элементы (дискретизация). Основными способами представления графики для ее хранения и обработки с помощью компьютера являются растровые и векторные изображения Векторное изображение представляет собой графический объект, состоящий из элементарных геометрических фигур (чаще всего отрезков и дуг). Положение этих элементарных отрезков определяется координатами точек и величиной радиуса. Для каждой линии указывается двоичные коды типа линии (сплошная, пунктирная, штрихпунктирная), толщины и цвета. Растровое изображение представляет собой совокупность точек (пикселей), полученных в результате дискретизации изображения в соответствии с матричным принципом. Матричный принцип кодирования графических изображений заключается в том, что изображение разбивается на заданное количество строк и столбцов. Затем каждый элемент полученной сетки кодируется по выбранному правилу. Pixel (picture element - элемент рисунка) - минимальная единица изображения, цвет и яркость которой можно задать независимо от остального изображения. В соответствии с матричным принципом строятся изображения, выводимые на принтер, отображаемые на экране дисплея, получаемые с помощью сканера. Качество изображения будет тем выше, чем "плотнее" расположены пиксели, то есть чем больше разрешающая способность устройства, и чем точнее закодирован цвет каждого из них. Для черно-белого изображения код цвета каждого пикселя задается одним битом. Если рисунок цветной, то для каждой точки задается двоичный код ее цвета. Поскольку и цвета кодируются в двоичном коде, то если, например, вы хотите использовать 16-цветный рисунок, то для кодирования каждого пикселя вам потребуется 4 бита (16=24), а если есть возможность использовать 16 бит (2 байта) для кодирования цвета одного пикселя, то вы можете передать тогда 216 = 65536 различных цветов. Использование трех байтов (24 битов) для кодирования цвета одной точки позволяет отразить 16777216 (или около 17 миллионов) различных оттенков цвета - так называемый режим “истинного цвета” (True Color). Заметим, что это используемые в настоящее время, но далеко не предельные возможности современных компьютеров. Контрольные вопросы: Что такое дискретизация? Что такое растровое изображение? Что такое векторное изображение? Что называется пикселем? В чем заключается матричный принцип кодирования графических изображений? Тема: Кодирование звуковой информации. Кодирование видеоинформации 1. Кодирование звуковой информации. Человек выражает свои мысли в виде предложений, составленных из слов. Они являются алфавитным представлением информации. Основу любого языка составляет алфавит - конечный набор различных знаков (символов) любой природы, из которых складывается сообщение. Для представления информации могут использоваться разные коды и, соответственно, надо знать определенные правила - законы записи этих кодов, т.е. уметь кодировать. Код - набор условных обозначений для представления информации. Кодирование - процесс представления информации в виде кода. Всем известно, что для общения друг с другом мы используем код - русский язык. При разговоре этот код передается звуками, при письме - буквами. Водитель передает сигнал с помощью гудка или миганием фар. Вы встречаетесь с кодированием информации при переходе дороги в виде сигналов светофора. Таким образом, кодирование сводиться к использованию совокупности символов по строго определенным правилам. Нельзя не сказать о том, что одно из основных достоинств компьютера связано с тем, что это удивительно универсальная машина. Каждый, кто хоть когда-нибудь с ним сталкивался, знает, что занятие арифметическими подсчетами составляет совсем не главный метод использования компьютера. Компьютеры прекрасно воспроизводят музыку и видеофильмы, с их помощью можно организовывать речевые и видеоконференции в Интернет, создавать и обрабатывать графические изображения, а возможность использования компьютера в сфере компьютерных игр на первый взгляд выглядит совершенно несовместимой с образом суперарифмометра, перемалывающего сотни миллионов цифр в секунду. Итак, кодирование информации – это процесс формирования определенного представления информации. В более узком смысле под термином «кодирование» часто понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки. Интересен тот факт, что с начала 90-х годов персональные компьютеры получили возможность работать со звуковой информацией. Каждый компьютер, имеющий звуковую плату, микрофон и колонки, может записывать, сохранять и воспроизводить звуковую информацию. Звук представляет собой звуковую волну с непрерывно меняющейся амплитудой и частотой. Чем больше амплитуда, тем он громче для человека, чем больше частота сигнала, тем выше тон. Программное обеспечение компьютера в настоящее время позволяет непрерывный звуковой сигнал преобразовывать в последовательность электрических импульсов, которые можно представить в двоичной форме, а именно по такой схеме: Процесс преобразования звуковых волн в двоичный код в памяти компьютера:  Процесс воспроизведения звуковой информации, сохраненной в памяти ЭВМ:  Описанный способ кодирования звуковой информации достаточно универсален, он позволяет представить любой звук и преобразовывать его самыми разными способами. Но бывают случаи, когда выгодней действовать по-иному. Издавна используется довольно компактный способ представления музыки – нотная запись. В ней специальными символами указывается, какой высоты звук, на каком инструменте и как сыграть. Фактически, ее можно считать алгоритмом для музыканта, записанным на особом формальном языке. В 1983 ведущие производители компьютеров и музыкальных синтезаторов разработали стандарт, определивший такую систему кодов. Он получил название MIDI. Конечно, такая система кодирования позволяет записать далеко не всякий звук, она годится только для инструментальной музыки. Но есть у нее и неоспоримые преимущества: чрезвычайно компактная запись, естественность для музыканта (практически любой MIDI-редактор позволяет работать с музыкой в виде обычных нот), легкость замены инструментов, изменения темпа и тональности мелодии. Есть и другие, чисто компьютерные, форматы записи музыки. Среди них – формат MP3, позволяющий с очень большим качеством и степенью сжатия кодировать музыку, при этом вместо 18–20 музыкальных композиций на стандартном компакт-диске (CDROM) помещается около 200. Одна песня занимает, примерно, 3,5 Mбайт, что позволяет пользователям сети Интернет легко обмениваться музыкальными композициями. 2. Кодирование видеоинформации. Особое внимание также уделяют кодированию видеоинформации. Чтобы хранить и обрабатывать видео на компьютере, необходимо закодировать его особым образом. Изображение в видео состоит из отдельных кадров, которые меняются с определенной частотой. Кадр кодируется как обычное растровое изображение, то есть разбивается на множество пикселей. Закодировав отдельные кадры и собрав их вместе, мы сможем описать все видео. Отметим то, что видеоданные характеризуются частотой кадров и экранным разрешением. Скорость воспроизведения видеосигнала составляет 30 или 25 кадров в секунду, в зависимости от телевизионного стандарта. Наиболее известными из таких стандартов являются: SECAM, принятый в России и Франции, PAL, используемый в Европе, и NTSC, распространенный в Северной Америке и Японии. Разрешение для стандарта NTSC составляет 768 на 484 точек, а для PAL и SECAM – 768 на 576 точек. Но не все пиксели используются для хранения видеоинформации. Так, при стандартном разрешении 768 на 576 пикселей, на экране телевизора отображается всего 704 на 540 пикселей. Поэтому для хранения видеоинформации в компьютере или цифровой видеокамере, размер кадра может отличаться от телевизионного. Например, в формате Digital Video или, как его еще называют DV, размер кадра составляет 720 на 576 пикселей. Такое же разрешение имеет кадр стандарта DVD Video. Размер кадра формата Video-CD составляет 352 на 288 пикселей. Если представить каждый кадр изображения как отдельный рисунок, то видеоизображение будет занимать очень большой объем, например, одна секунда записи в системе PAL будет занимать 25 Мбайт, а одна минута – уже 1,5 Гбайт. Поэтому на практике используются различные алгоритмы сжатия для уменьшения скорости и объема потока видеоинформации. Кодирование видеоинформации еще более сложная проблема, чем кодирование звуковой информации, так как нужно позаботиться не только о дискретизации непрерывных движений, но и о синхронизации изображения со звуковым сопровождением. В настоящее время для этого используется формат, которой называется AVI (Audio-Video Interleaved — чередующееся аудио и видео). Основные мультимедийные форматы AVI и WAV очень требовательны к памяти. Поэтому на практике применяются различные способы компрессии, то есть сжатия звуковых и видеокодов. В настоящее время стандартными стали способы сжатия, предложенные MPEG (Moving Pictures Experts Group — группа экспертов по движущимся изображениям). В частности, стандарт MPEG-1 описывает несколько популярных в настоящее время форматов записи звука. Так, например, при записи в формате МР-3 при практически том же качестве звука требуется в десять раз меньше памяти, чем при использовании формата WAV. Существуют специальные программы, которые преобразуют записи звука из формата WAV в формат МР-3. Стандарт MPEG-2 описывает методы сжатия видеозаписей, которые обеспечивают телевизионное качество изображения и стереозвуковое сопровождение и имеют приемлемые требования к памяти. Совсем недавно был разработан стандарт MPEG-4, применение которого позволяет записать полнометражный цветной фильм со звуковым сопровождением на компакт-диск обычных размеров и качества. Контрольные вопросы: Что такое код? Что понимают под кодированием? Как происходит кодирование звуковой информации? Как происходит кодирование графической информации? Какие стандарты кодирования видеоинформации существуют? Тема: Сжатие графической и видеоинформации. Методы сжатия. Обзор подходов к сжатию информации Как уже было сказано, дискретная форма представления информации является наиболее общей и универсальной. В виде совокупности символов, принадлежащих к ограниченному алфавиту, можно представить как текст или массивы чисел, так и оцифрованные звук и изображение. С учетом этого очевидно, что должны существовать универсальные методы сжатия данных (цифровой информации), применимые ко всем ее разновидностям. В силу своей универсальности эти методы должны исключать потерю информации (такая потеря может быть допустима при передаче, например мелкой детали изображения, но неприемлема, когда речь идет, скажем, о коде программы). С другой стороны, в ряде приложений общие методы наверняка не будут наиболее эффективными. Например, в силу особенностей зрительного и слухового восприятия, некоторое «огрубление» изображения или звука может оказаться малозаметным, при этом выигрыш в объеме передаваемых данных окажется значительным. В этих случаях уместно использовать специальные методы сжатия с потерями (рис.5.1). При кодировании со сжатием без потерь выделяются две разновидности методов: Первая основана на раздельном кодировании символов. Основная идея состоит в том, что символы разных типов встречаются неодинаково части и если кодировать их неравномерно, - так, чтобы короткие битовые последовательности соответствовали часто встречающимся символам, - то в среднем объем, кода будет меньше. Такой подход, именуемый, статистическим кодированием, реализован, в частности, в широко распространенном коде Хаффмана, о котором мы расскажем подробно ниже. Очевидно, что посимвольное кодирование не использует такого важного резерва сжатия данных, как учет повторяемости последовательностей (цепочек) символов. Простейший вариант учета цепочек – так называемое «кодирование повторов» или код RLE, когда последовательность одинаковых символов заменяется парой – "код символа + количество его повторов в цепочке". В большинстве случаев цепочки одинаковых символов встречаются нечасто. Однако, например, при кодировании черно-белых растровых изображений, каждая строка которых состоит из последовательных черных или белых точек, такой подход оказывается весьма эффективным (он широко применяется при факсимильной передаче документов). Кроме того, кодирование повторов нередко используется как составной элемент более сложных алгоритмов сжатия. Гораздо более универсальным является алгоритм, позволяющий эффективно кодировать повторяющиеся цепочки разных символов, имеющие при этом произвольную длину. Такой алгоритм был разработан Лемпелем и Зивом и применяется в разных версиях в большинстве современных программ-архиваторов. Идея алгоритма состоит в том, что цепочка символов, уже встречавшаяся в передаваемом сообщении, кодируется ссылкой на боле раннюю (при этом указываются «адрес» начала такой цепочки в «словаре» сообщения и ее длина). Ниже мы обсудим особенности алгоритма Лемпеля-Зива. Специализированные методы сжатия с потерями информации, естественно принципиально различаются для графики и звука. К методам сжатия изображений относятся «блочный» алгоритм JPEG основанный на независимом «огрублении» небольших фрагментов изображений (квадраты 8х8 пикселей). Здесь с ростом степени сжатия проявляется мозаичность изображения. Блочный метод JPEG (разработанный специальной группой международного комитета по стандартизации) получил сейчас повсеместное распространение и ниже мы рассмотрим его подробнее. Достигается степень сжатия – в среднем в десятки раз. При волновом сжатии в отличие от блочного изображение как бы «размывается» (чем выше степень сжатия, тем более нечетки границы и детали). При передаче данных получаемое изображение постепенно «проявляется» в деталях. Это позволяет получателю самому выбирать необходимый компромисс между качеством и скоростью получения изображения, что очень удобно, например в Интернет. К тому же «размытость» не столь резко воспринимается глазом как потеря качества по сравнению с «мозаичностью». Так что при субъективно близком уровне качества волновой метод дает большую степень сжатия по сравнению с «блочным». Именно такой подход реализован в новом стандарте JPEG 2000. Наконец, фрактальное сжатие основывается на том, что в изображении можно выделить фрагменты, повороты и масштабирование которых позволяет многократно использовать их при построении всей «картинки». Выделение и построение математического описания таких элементов-фракталов – трудоемкая в вычислительном отношении задача. Зато высокая степень сжатия (в сотни раз) и быстрота построения изображения по его фрактальному описанию делают метод очень удобным, когда не требуется быстрота компрессии. Например, этот метод удобно использовать при записи изображений на CD-ROM. Наконец, методы сжатия звука существенно различаются в зависимости от того, насколько хорошо известны специфические особенности его источника. Примерами источников, чьи особенности решающим образом влияют на характер звука, являются человеческий речевой аппарат и музыкальные инструменты. Для них эффективным способом сжатия звуковой информации является моделирование, когда передаются не характеристика звука, а параметры модели его источника. Что касается методов сжатия звука от произвольного источника, мы рассмотрим их ниже. |