Файл: Методы кодирования данных (Краткая история кодирования ).pdf

К примеру, кодировка символов русского языка, известная под названием Windows-1251, была введена со стороны – компанией Microsoft, но, принимая во внимание массовое распространение операционных систем и иных продуктов этой компании в России, она всерьез укрепилась и нашла широкое распространение (рисунок 2). Эта кодировка применяется на большинстве локальных компьютеров, работающих на платформе Windows:

Рисунок 2. Кодировка Windows

Еще одна достаточно распространенная кодировка называется КОИ-8 (код обмена информа­цией, 8-значный) – ее возникновение относится ко временам действия Совета Экономической Взаимопомощи государств Восточной Европы. На сегодняшний день кодировка КОИ-8 широко распространена в компьютерных сетях на территории России и в российском секторе Интернета.

Международный стандарт, предусматривающий кодировку символов русского алфавита, называется кодировкой ISO (International Standard Organization – Между­народный институт стандартизации). Однако в практике эта кодировка применяется очень редко.

Для компьютеров, которые работают с операционными системами MS-DOS, могут применяться еще 2 кодировки (кодировка ГОСТ и кодировка ГОСТ-альтернативная). Первая считалась устаревшей уже в первые годы появления персональных компьютеров, а вторая используется и в наше время.

Вследствие изобилия систем кодирования текстовых данных, действующих в России, появилась задача межсистемного преобразования данных – это одна из самых распространенных задач информатики.

1.3 Универсальная система кодирования текстовых данных

Рассматривая организационные трудности, которые связаны с созданием единой системы кодирования текстовых данных, можно сделать вывод, что они вызваны недостаточным набором кодов (256). При этом очевидно, что если, к примеру, кодировать символы не 8-разрядными двоичными числами, а числами с большим числом разрядов, то и охват допустимых значений кодов будет намного больше. Система, основанная на 16-разрядном кодировании символов, называется универсальной – UNICODE. 16 разрядов предоставляют уникальные коды для 65 536 разных символов – этого поля достаточно для расположения в одной таблице символов большей части языков мира.

Невзирая на банальную ясность такого подхода, простой механический переход на такую систему кодирования длительное время затягивался из-за ограниченных ресурсов средств вычислительной техники (в системе UNICODE все текстовые документы автоматически становятся в 2 раза длиннее). Во второй половине 90-х годов технические средства приобрели нужный уровень оснащенности ресурсами, и в наше время отмечается поэтапный перевод документов и программных средств на универсальную систему кодирования. Частным пользователям добавилось проблем по согласованию документов, которые были выполнены в различных системах кодирования, с программными средствами.

1.3 Кодирование графических данных

Если разглядывать черно-белое графическое изображение, напечатанное в газете или книге, при помощи увеличительного стекла, можно увидеть, что оно складывается из крошечных точек, которые образуют характерный узор, который называют растром.

Поскольку линейные координаты и индивидуальные свойства каждой точки можно выразить при помощи целых чисел, то можно сказать, что растровое кодиро­вание дает возможность использовать двоичный код для представления графических данных. Общепризнанным на сегодня считается представление черно-белых иллюстраций в виде сочетания точек с 256 градациями серого цвета, и, следовательно, для кодирования яркости любой точки достаточно 8-разрядного двоичного числа.

Для кодирования цветных графических изображений используется принцип расщепления произвольного цвета на основные составляющие. В качестве таких состав­ляющих используют 3 основных цвета: красный (Red), зеленый (Green) и синий (Blue). На практике считается (однако теоретически это не совсем так), что любой цвет, который видит человеческий глаз, можно произвести путем смешивания этих 3 основных цветов. Такая система кодирования называется системой RGB по первым буквам названий основных цветов.

Если для кодирования яркости каждой из основных составляющих использовать по 256 значений (8 двоичных разрядов), как это принято для полутоновых черно-белых изображений, то на кодирование цвета одной точки надо затратить 24 разряда. При этом система кодирования обеспечивает однозначное определение 16,5 млн. разных цветов, что очень близко к чувствительности человеческого глаза. Режим представления цветной графики с применением 24 дво­ичных разрядов называется полноцветным (True Color).

Каждому из основных цветов можно сопоставить дополнительный цвет, то есть цвет, дополняющий основной цвет до белого. Просто заметить, что для любого из основных цветов дополнительным будет цвет, который образован суммой пары остальных основных цветов. То есть, дополнительными цветами являются: голубой (Cyan), пурпурный (Magenta) и желтый (Yellow). Принцип расщепления произвольного цвета на составляющие компоненты можно использовать не только для основных цветов, но и для дополнительных, а это значит, что любой цвет можно представить в виде суммы голубой, пурпурной и желтой составляющей. Такой метод кодирования цвета принят в полиграфии, но в полиграфии применяется еще и 4-ая краска – черная (Black). Поэтому такая система кодирования обозначается 4-мя буквами CMYK (черный цвет обозначен буквой К, так как буква В уже занята синим цветом), и для представления цветной графики в этой системе нужно иметь 32 двоичных разряда.

Если уменьшить число двоичных разрядов, применяемых для кодирования цвета каждой точки, то можно уменьшить объем данных, но при этом диапазон кодируемых цветов значительно уменьшается. Кодирование цветной графики 16-разрядными двоичными числами называют режимом High Color.

При кодировании информации о цвете с помощью 8 бит данных можно пере­дать только 256 цветовых оттенка. Этот метод кодирования цвета называют индексным. Смысл названия в том, что, поскольку 256 значений совершенно недостаточно, чтобы передать весь диапазон цветов, доступный человеческому глазу, код каждой точки растра выражает не цвет сам по себе, а только его номер (индекс) в некой справочной таблице, называемой палитрой. Само собой, эта палитра должна прикладываться к графическим данным – без нее невозможно будет воспользоваться методами воспроизведения информации на экране или бумаге.

1.4 Кодирование звуковой информации

Приемы и методы обработки звуковой информацией появились в вычислительной технике позже всего. Кроме того, в противовес числовым, текстовым и графическим данным, у звукозаписей не было столь длительной и проверенной истории кодирования. В итоге методы кодирования звуковой информации двоичным кодом далеки от стандартизации. Множество различных компаний разработали свои корпоративные стандарты, однако, говоря обобщенно, можно выделить 2 главных направления.

Метод FM (Frequency Modulation) основан на том, что в теории любой сложный звук можно разложить на последовательный ряд простейших гармонических сигналов разных частот, каждый из которых представляет собой правильную синусоиду, а следовательно, может быть описан числовыми параметрами, то есть кодом. В природе звуковые сигналы имеют непрерывный спектр, то есть являются аналоговыми. Их разложение в гармонические ряды и представление в виде дискретных цифровых сигналов выполняют специальные устройства – аналогово-цифровые преобразователи (АЦП). Обратное преобразование для воспроизведения звука, закодированного числовым кодом, выполняют цифро-аналоговые преобразователи (ЦАП). При таких преобразованиях не миновать потерь информации, связанных с методом коди­рования, поэтому качество звукозаписи обычно выходит не вполне удовлетворительным и соответствует качеству звучания простейших электромузыкальных инструментов с окрасом, характерным для электронной музыки.

Метод таблично-волнового (Wave-Table) синтеза больше соответствует современному уровню развития техники. Если говорить упрощенно, то можно сказать, что где-то в заранее подготовленных таблицах хранятся образцы звуков для множества различных музыкальных инструментов. В технике такие образцы называют сэмплами. Числовые коды выражают тип инструмента, номер его модели, высоту тона, продолжительность и интенсивность звука, динамику его изменения, некоторые параметры среды, в которой происходит звучание, а также прочие пара­метры, характеризующие особенности звука. Поскольку в качестве образцов используются «реальные» звуки, то качество звука, полученного в результате синтеза, получается очень высоким и приближается к качеству звучания реальных музыкальных инструментов.

Глава 2. Методы кодирования данных

2.1 Теория кодирования и теория информации

Теория кодирования и теория информации появились в начале 20 века. Начало развитию этих теорий как научных дисциплин положило появление в 1948 г. статей К. Шеннона, заложивших основу для последующих исследований в этой области.

Основной моделью, которую изучает теория информации, является модель системы передачи сигналов (рисунок 3).

Рисунок 3. Модель системы передачи сигналов

Начальным звеном в приведенной выше модели является источник информации. Здесь рассматриваются дискретные источники без памяти, в которых выходом является последовательность символов некоторого фиксированного алфавита. Множество всех различных символов, порождаемых некоторым источником, называется алфавитом источника, а количество символов в этом множестве – размером алфавита источника. Например, можно считать, что текст на русском языке порождается источником с алфавитом из 33 русских букв, пробела и знаков препинания.

Кодирование дискретного источника заключается в сопоставлении символов алфавита А источника символам некоторого другого алфавита В. К тому же, обычно символу исходного алфавита А ставится в соответствие не один, а группа символов алфавита В, которая называется кодовым словом. Кодовый алфавит – множество различных символов, используемых для записи кодовых слов. Кодом называется совокупность всех кодовых слов, применяемых для представления порождаемых источником символов.

Дадим строгое определение кодирования. Пусть даны алфавит источника , кодовый алфавит. Обозначим множество всевозможных последовательностей в алфавите А (В). Множество всех возможных сообщений в алфавите А обозначим S. Тогда отображение, которое преобразует множество сообщений в кодовые слова в алфавитеВ, называется кодированием. Если , то– кодовое слово. Обратное отображение(если оно существует) называется декодированием.

Задача кодирования сообщения ставится следующим образом. Требуется при заданных алфавитах А и В и множестве сообщений S найти кодирование F, обладающее определенными свойствами и оптимальное в некотором смысле. Свойства, которые требуются от кодирования, могут быть разными. Приведем некоторые из них:

• существование декодирования;
• помехоустойчивость или исправление ошибок при кодировании: декодирование обладает свойством , β~β′ (эквивалентно β′с ошибкой);
• обладает заданной трудоемкостью (время, объем памяти).

Известны 2 класса методов кодирования дискретного источника информации: равномерное и неравномерное кодирование. Под равномерным кодированием понимается применение кодов со словами постоянной длины. Для того чтобы декодирование равномерного кода стало возможным, разным символам алфавита источника нужно поставить в соответствие разные кодовые слова. При этом длина кодового слова должна быть не меньше символов, где m – размер исходного алфавита, n – размер кодового алфавита.

При неравномерном кодировании источника используются кодовые слова разной длины. Причем кодовые слова обычно строятся так, что часто встречающиеся символы кодируются более короткими кодовыми словами, а редкие символы – более длинными (за счет этого достигается «сжатие» данных).

Под сжатием данных понимается компактное представление данных, которое достигается за счет избыточности информации, содержащейся в сообщениях. Большое значение для практического использования имеет неискажающее сжатие, позволяющее полностью восстановить исходное сообщение. При неискажающем сжатии происходит кодирование сообщения перед началом передачи или хранения, а после окончания процесса сообщение однозначно декодируется (это соответствует модели канала без шума (помех)).