Основы теории информации. Кодирование информации

 

1.3 Классификация информации

 

Существует две системы классификации: иерархическая и фацетная. При иерархической классификации (рис. 1.) множество объектов последовательно разбиваются на соподчиненные подмножества.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 1. Классификация информации

 

1.4 Формы представления информации

 

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

Рассмотрим способы представления информации в ЭВМ.

Представление целых чисел.

Для эффективности использования памяти в ЭВМ используют разные методы представления целых чисел. При этом применяется формат с фиксированной запятой.

Для положительных (без знаковых) чисел все биты ячейки памяти участвуют в указании количественного значения числа. Например, 1 байт=8 битам дает возможность задать числа в диапазоне от 00000000 до 11111111 в двоичной системе (0-255 в десятичной системе). Если же используется для кодирования машинное слово (2 байта), то возможен числовой диапазон от 0 до 2^16-1=65535 в десятичной системе.

В случае если нужно указать число со знаком, старший бит в двоичной системе выделяется для указания знака. При этом одним байтом можно задать числа от -128 до +127, а 16 разрядное целое со знаком позволяет указать числовой диапазон от -32768 до +32767 в десятичной системе. Для замены операции вычитания операцией сложения, отрицательные числа в памяти компьютера хранятся в дополнительном коде. 
В компьютере операции над целым числами выполняются целочисленным процессорам по определенным правилам.

Представление вещественных чисел.

Для выполнения операций с большей точностью в компьютере используется формат представления чисел с плавающей запятой. При таком кодировании часть разрядов отводится для указания порядка, другая часть для указания мантиссы и один бит для указания знака. Например, при длине числа 32 бита (двойное машинное слово) 1 бит отводится для указания знака, 8 бит – указание порядка и 24 бита – для мантиссы. Это позволяет задать диапазон от 10^-38 до 10^38 .

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

Представление текстовой информации.

В случае текстовой информации, каждому символу сопоставляется двоичное  число, образуя таблицу кодировок символов. Существует различные стандарты кодировок: ASCII, UCS-2, UCS-4. Например,  в таблице ASCII одним байтом кодируются 256 символов (включая управляющие символы). Согласно этой кодировке букве b соответствует код 01100010, о – 01101111, k – 01101011. И слово book записывается четырьмя байтами 01100010 01101111 01101111 01101011.  

Представление графической информации.  

Для кодирования графической информации все изображение делиться на равные участки – пиксели. Чем больше пикселей, тем качественнее представление графического изображения. Каждый пиксель задается двоичным кодом цвета дискретизированной области. В основном применяют кодировки RGB (Red-Green-Blue) - для устройств, работающих по принципу излучения (мониторы), CMYK (Cyan-Yellow-Magenta-Black)  - для устройств, работающих по принципу отражения от белого (печать на бумагу).  
В системе RGB при глубине цвета 24 бита, состояние пикселя задается 24 битами, из которых 8 бит используется для задания интенсивности красного, 8 бит – интенсивности зеленого и последние 8 бит - интенсивности синего. Таким образом, три цвета, каждый из которых имеет 256 уровней интенсивности, смешиваются в разных соотношениях, и получается 224 различных цветов.

Не трудно подсчитать объем памяти необходимый для хранения изображения на экране монитора разрешением 800х600 точек при глубине цвета 24 бит.   

800*600*3байта=1440000 байт=1.44 Мбайт.

В таком виде сохраняется информация в графических файлах с расширением BMP. Но для уменьшения занимаемого объема применяются различные методы сжатия типа JPG, GIF и т. д.

Представление звуковой информации.

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

Обычно глубина кодирования (дискретизация по уровню) составляет 16 бит (65536 уровней), а частота дискретизации 24000 раз в секунду. Можно подсчитать поток информации при таком качестве звука 
16 бит*24000 с-1=2 байта*24000 с-1=48000 байт в секунду=48 Кбайт/с 
При воспроизведении звука цифровыми устройствами, поток чисел обратно представляются в аналоговый сигнал при помощи цифро-аналогового преобразователя.

Универсальный звуковой формат файла без сжатия это WAV. Наиболее распространенный формат со сжатием - MP3.

Представление видео - информации.

Видео представляет собой поток последовательно сменяющихся кадров изображений. Следовательно, представление видео в ЭВМ сводится к представлению потока графической информации. Телевизионный формат воспроизведения видео использует разрешение кадра 720*576 точек с 24 битовой глубиной цвета. Скорость воспроизведения составляет 25 кадров в секунду. Объем передаваемой при этом информации составляет: 
24бита*720*576*25=248832000 бит/с или приблизительно 30 Мбайт/с. 
Это составляет очень большой поток данных, поэтому при хранении и передачи видео используют разные методы сжатия (MPEG, AVI). В современных цифровых  видеокамерах запись видео выполняется в цифровой форме после предварительного сжатия.

 

1.5 Способы представления  информации

 

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

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

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

Непрерывное сообщение может быть представлено непрерывной функцией, заданной на некотором отрезке [а, Ь] (см. рис. 2). Непрерывное сообщение можно преобразовать в дискретное (такая процедура называется дискретизацией). Для этого из бесконечного множества значений этой функции (параметра сигнала) выбирается их определенное число, которое приближенно может характеризовать остальные значения. Один из способов такого выбора состоит в следующем. Область определения функции разбивается точками x1, x2,... хn, на отрезки равной длины и на каждом из этих отрезков значение функции принимается постоянным и равным, например, среднему значению на этом отрезке; полученная на этом этапе функция называется в математике ступенчатой. Следующий шаг – проецирование значений “ступенек” на ось значений функции (ось ординат). Полученная таким образом последовательность значений функции у1, у2, ... уn. является дискретным представлением непрерывной функции, точность которого можно неограниченно улучшать путем уменьшения длин отрезков разбиения области значений аргумента.

 

Рис. 1. Процедура дискретизации непрерывного сообщения

 

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

Таким образом, любое сообщение может быть представлено как дискретное, иначе говоря последовательностью знаков некоторого алфавита.

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

Единицы количества информации: вероятностный и объемный подходы

Определить понятие “количество информации” довольно сложно. В решении этой проблемы существуют два основных подхода. Исторически они возникли почти одновременно. В конце 40-х годов XX века один из основоположников кибернетики американский математик Клод Шеннон развил вероятностный подход к измерению количества информации, а работы по созданию ЭВМ привели к “объемному” подходу.

Вероятностный подход

Рассмотрим в качестве примера опыт, связанный с бросанием правильной игральной .кости, имеющей N граней (наиболее распространенным является случай шестигранной кости: N = 6). Результаты данного опыта могут быть следующие: выпадение грани с одним из следующих знаков: 1,2,... N.

Введем в рассмотрение численную величину, измеряющую неопределенность -энтропию (обозначим ее Н). Величины N и Н связаны между собой некоторой функциональной зависимостью:

 

H = f (N), (1.1)

 

а сама функция f является возрастающей, неотрицательной и определенной (в рассматриваемом нами примере) для N = 1, 2,... 6.

Рассмотрим процедуру бросания кости более подробно:

1) готовимся  бросить кость; исход опыта неизвестен, т.е. имеется некоторая неопределенность; обозначим ее H1;

2) кость брошена; информация об исходе данного  опыта получена; обозначим количество  этой информации через I;

3) обозначим  неопределенность данного опыта  после его осуществления через H2. За количество информации, которое получено в ходе осуществления опыта, примем разность неопределенностей “до” и “после” опыта:

 

I = H1 – H2 (1.2)

 

Очевидно, что в случае, когда получен конкретный результат, имевшаяся неопределенность снята (Н2 = 0), и, таким образом, количество полученной информации совпадает с первоначальной энтропией. Иначе говоря, неопределенность, заключенная в опыте, совпадает с информацией об исходе этого опыта. Заметим, что значение Н2 могло быть и не равным нулю, например, в случае, когда в ходе опыта следующей выпала грань со значением, большим “З”.

Следующим важным моментом является определение вида функции f в формуле (1.1). Если варьировать число граней N и число бросаний кости (обозначим эту величину через М), общее число исходов (векторов длины М, состоящих из знаков 1,2,.... N) будет равно N в степени М:

 

X=NM. (1.3)

 

Так, в случае двух бросаний кости с шестью гранями имеем: Х=62=36. Фактически каждый исход Х есть некоторая пара (X1, X2), где X1 и X2 – соответственно исходы первого и второго бросаний (общее число таких пар – X).

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

 

f(6M) = M ∙ f(6)

 

Данную формулу можно распространить и на случай любого N: