Файл: Теоретические основы кодирования данных.pdf

Введение

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

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

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

Обеспечение помехоустойчивости при передаче данных по каналам связи.

Сжатие информации в базах данных.

Цель данной работы – ознакомиться с понятием кодирования и изучить методы кодирования данных.

С учетом поставленной цели будут решены следующие задачи:

- рассмотрены теоретические основы кодирования: дано понятие, классификация;

- проанализированы методы кодирования данных и примеры их применения.

Курсовая работа состоит из введения, двух глав, заключения и библиографии.

Глава 1 Теоретические основы кодирования данных

1.1 Понятие кодирования данных

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

Термин «кодирование информации» можно рассматривать с разных точек зрения^[1].

С одной стороны, при любых видах работы с информацией всегда существует понятие о представлении данной информации, в виде конкретных символических структур. Наиболее распространенными являются одномерные представления информации, где сообщения имеют вид в виде последовательности символов. Таким образом информация представляется в письменных текстах, при передаче по каналам связи, в памяти вычислительной техники. Однако широко применяются и многомерные представления такой информации, причем под многомерностью понимается не только расположение составных частей информации на плоскости или в пространстве (в виде различных рисунков, или схем, или графов, или объемных макетов и т.п.), но и множественность признаков символов, которые используются. Так например, информацию могут нести не только значения букв и цифр, но и их цвет, размер, вид шрифта.  Всякое событие, всякое явление служит источником информации. Всякое событие, всякое явление может быть выражено по-разному, разным способом, разным «алфавитом», т. е. по-разному закодировано.

Кодирование данных – это процесс формирования определенного представления информационных данных.

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

В ЭВМ применяется двоичная система счисления, т.е. все числа в компьютере представляются с помощью нулей и единиц, поэтому компьютер может обрабатывать только информацию, представленную в цифровой форме.

Для преобразования числовой, текстовой, графической, звуковой информации в цифровую необходимо применить кодирование.

Итак, кодирование – это преобразование данных одного типа через данные другого типа. В ЭВМ применяется система двоичного кодирования, основанная на представлении данных последовательностью двух знаков: 1 и 0, которые называются двоичными цифрами (binary digit – сокращенно bit)^[2].

Целые числа кодируются двоичным кодом довольно просто (путем деления числа на два). Для кодирования нечисловой информации используется следующий алгоритм: все возможные значения кодируемой информации нумеруются и эти номера кодируются с помощью двоичного кода^[3].

Кодирование чисел

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

Кодирование целых чисел производится через их представление в двоичной системе счисления: именно в этом виде они и помещаются в ячейке. Один бит отводиться при этом для представления знака числа (нулем кодируется знак "плюс", единицей – "минус").

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

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

Кодирование текста

Для представления текстовой информации используется таблица нумерации символов или таблица кодировки символов, в которой каждому символу соответствует целое число (порядковый номер). Восемь двоичных разрядов могут закодировать 256 различных символов.

Существующий стандарт ASCII (сокращение от American Standard Code for Information Intercange – американский стандартный код для обмена информацией; 8 – разрядная система кодирования) содержит две таблицы кодирования – базовую и расширенную. Первая таблица содержит 128 основных символов, в ней размещены коды символов английского алфавита, а во второй таблице кодирования содержатся 128 расширенных символов.

Так как в этот стандарт не входят символы национальных алфавитов других стран, то в каждой стране 128 кодов расширенных символов заменяются символами национального алфавита. В настоящее время существует множество таблиц кодировки символов, в которых 128 кодов расширенных символов заменены символами национального алфавита.

Так, например, кодировка символов русского языка Widows – 1251 используется для компьютеров, работающих под ОС Windows. Другая кодировка для русского языка – это КОИ – 8, которая также широко используется в компьютерных сетях и российском секторе Интернет.

В настоящее время существует универсальная система UNICODE, основанная на 16 – разрядном кодировании символов. Эта 16 – разрядная система обеспечивает универсальные коды для 65536 различных символов, т.е. в этой таблице могут разместиться символы языков большинства стран мира.

Кодирование графической информации

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

Растровые изображения представляют собой однослойную сетку точек, называемых пикселями (pixel, от англ. picture element). Код пикселя содержит информации о его цвете.

Для описания черно-белых изображений используются оттенки серого цвета, то есть при кодировании учитывается только яркость. Она описывается одним числом, поэтому для кодирования одного пикселя требуется от 1 до 8 бит: чёрный цвет – 0, белый цвет – N = 2^k-l, где k – число разрядов, которые отводятся для кодирования цвета. Например, при длине ячейки в 8 бит это 256-1 = 255. Человеческий глаз в состоянии различить от 100 до 200 оттенков серого цвета, поэтому восьми разрядов для этого вполне хватает.

Цветные изображения воспринимаются нами как сумма трёх основных цветов – красного, зелёного и синего. Например, сиреневый = красный + синий; жёлтый = красный + зелёный; оранжевый = красный + зелёный, но в другой пропорции. Поэтому достаточно закодировать цвет тремя числами – яркостью его красной, зелёной и синей составляющих. Этот способ кодирования называется RGB (Red – Green – Blue). Его используют в устройствах, способных излучать свет (мониторы). При рисовании на бумаге действуют другие правила, так как краски сами по себе не испускают свет, а только поглощают некоторые цвета спектра. Если смешать красную и зелёную краски, то получится коричневый, а не жёлтый цвет. Поэтому при печати цветных изображений используют метод CMY (Cyan – Magenta – Yellow) – голубой, сиреневый, жёлтый цвета. При таком кодировании красный = сиреневый + жёлтый; зелёный = голубой + жёлтый.

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

Объекты векторного изображения, в отличие от растровой графики, могут изменять свои размеры без потери качества (при увеличении растрового изображения увеличивается зернистость).

Кодирование черно-белых изображений

Теперь - о цвете: как же его закодировать? Если говорить о чернобелой (монохроматической) гамме, то характеристика цвета сводится к яркости. Она описывается одним числом. Для кодирования яркости пикселов отводятся ячейки фиксированного размера, чаще всего от 1 до 8 бит. Черный цвет кодируется нулем, а белый - максимальным числом N, которое может быть записано в ячейку. Для одноразрядной ячейки N=1, для 8-разрядной - N=255. Для практического применения 8-разрядных ячеек вполне достаточно, потому что как раз не более 200 оттенков серого цвета способен различить человеческий глаз. Если же N=1, то оттенки серого цвета при достаточно маленьких размерах пикселов нетрудно имитировать. Здесь можно использовать частоту чередования черных и белых пикселов. Например, серый цвет можно получить, если из каждых двух соседних пикселов сделаем один белый, а другой черный. Глазу будет казаться, что эта часть картинки имеет серый цвет. Если количество черных пикселей в таком чередовании уменьшить, то получится серый цвет более светлого оттенка:

Кодирование цветных изображений

С цветными изображениями дело обстоит сложнее. Человеческий глаз различает огромное количество оттенков разных цветов. Здесь кодирование осуществляется так. Известно, что каждый цвет - это сумма 3-х основных цветов: красного, зеленого и синего. Поэтому цвет пикселя можно закодировать тремя числами: яркостью красной, зеленой и синей составляющих. Этот способ называется RGB (red - красный, green - зеленый, blue - синий).

При рисовании на бумаге действуют другие законы (краски не испускают света, а только поглощают некоторые цвета из падающего на них света). Если смешать красную и зеленую краски, то получится не желтый цвет, а коричневый. Поэтому на печатающих устройствах обычно используется в качестве основных голубой, сиреневый и желтый цвета (такой метод кодировки называется CМY). Эти способы просты в реализации, но неудобны работе. Поэтому все чаще используется другая схема кодирования: цветовой тон / насыщенность / яркость (HSV). При этом цвет каждого пикселя кодируется тремя числами, но их значения уже не те, что в методах кодирования RGB и CMY.

Кодирование звукового сигнала

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

Для этого существует устройство, которое называется аналого-цифровым преобразователем (АЦП). АЦП измеряет электрическое напряжение в определенном диапазоне и выдает ответ в виде многоразрядного двоичного числа. Например, 8-разрядный АЦП преобразует напряжения в диапазоне [-500мВ, 500мВ] в 8-битовые двоичные числа в диапазоне [-128, 127].

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

При работе со стереозвуком процесс дискретизации производится для левого и правого каналов отдельно и независимо. На качество воспроизведения закодированного звука влияют два параметра: частота дискретизации и ее разрешение - размер ячейки, отводимый под запись амплитуды. Например, при записи на СD-диски используются 16-разрядные значения, а частота дискретизации около 44 КГц. Отсюда превосходное качество звучания речи и музыки. Но во многих случаях качество CD не требуется: для записи и воспроизведения звуков речи достаточно частоты 8 КГц. Основным достоинством работы компьютера со звуком является то, что закодированный звук можно не только хранить, но и обрабатывать его. Чем сложнее обработка, тем, естественно, сложнее алгоритм обработки. Простой же алгоритм, например, нарастания звука, сделать очень нетрудно:

алг нарастание_звука

арг | в i запис. звук с частотой дискр. 22016 КГц

рез | в o запис. этот звук, плавно нараст. в 1-ю сек.

нач цел i,x

| начать чтение("in.xxx"); начать запись("out.xxx")

| i:=1

| нц пока не конец файла

| | ввод x