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

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

Кодирование (coding, encode) и криптографическая (cryptographic) защита информации является частью более широкого понятия – теория информации (information theory). Основы этой науки заложены К. Шенноном, который в 1948-1949 годах опубликовал две основные свои работы – «Математическая теория связи» и «Теория связи в секретных системах». Эти работы не только дали толчок развитию методов кодирования, но и заложили основы современной научной криптологии (сriptologic, с греческого kryptos – тайный, logos – слово) – науки, занимающейся проблемой защиты информации путем ее преобразования.

Криптология разделяется на два направления:

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

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

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

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

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

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

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

Исходя из цели можно поставить следующие задачи:

- раскрыть основные понятия;

- рассмотреть количественное оценивание информации;

- изучить основную теорему Шеннона для кодирования;

- рассмотреть типовую классификацию методов кодирования;

- изучить статистические методы сжатия данных без потерь;

- обозначить словарные методы оптимального кодирования;

- раскрыть арифметическое кодирование.

ГЛАВА 1. ИНФОРМАЦИЯ И ЕЕ КОЛИЧЕСТВЕННЫЕ ОЦЕНКИ

1.1 Основные понятия

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

Комитет по терминологии академии наук рекомендует следующее определение информации: информация – это сведения, которые являются объектом хранения, передачи и преобразования [5].

Необходимо различать понятия информации и сообщения (messages). Сообщение – это форма представления информации. Например, при телеграфической передачи сообщения есть текст телеграммы. Сообщение для его передачи по соответствующему адресу предварительно превращают в сигнал (signal). Под сигналом понимают физическую величину, которая изменяется и отражает содержание сообщения. Сигнал – это материальный носитель сообщения. В современной технике нашли применение электрические, электромагнитные, световые и другие сигналы. Все сообщения по характеру изменений по времени можно разделить на непрерывные (continuous) и дискретные (discrete). Непрерывные по времени сообщения отображаются непрерывной функцией времени. Дискретные по времени сообщения характеризуются тем, что поступают в определенные моменты времени и описываются дискретной функцией времени.

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

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

Дискретность по множеству и временем не связана друг с другом. Поэтому возможны такие типы сообщений [13].

Непрерывные по множеству и временем.
Непрерывные по множеству и дискретные по времени.
Дискретные по множеству и непрерывные по времени.
Дискретные по множеству и времени.

Графически эти четыре типа сообщений представлен на рис. 1.1.

Рисунок 1.1 – Различные типы сообщений

В широком смысле преобразования сообщения в сигнал называют кодированием сообщения. В узком смысле – кодирование – это отображения дискретных сообщений сигналами в виде определенных сочетаний символов. Устройство, которое выполняет кодирование, называется кодером (coder), а декодирование – декодер (decoder). Кодер и декодер образуют кодек (codec) [8].

1.2 Количественное оценивание информации

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

На основе этого количество информации, полученные в результате проведения опыта, определяется как

где H – априорноя энтропия, H_o – остаточная энтропия (неопределенность последствий) опыта.

В этом представлении количество информации, полученное в результате опыта, – это мера снятой неопределенности.

При передаче сообщений в каналах без помех H_o = 0 и I = H.

В приложении к системам связи термин «количество информации» ввел Ральф Хартли в 1928 году. Он предложил определять эту величину как

где p – вероятность появления одного из N возможных равновероятных последствий опыта.

Логарифмическая мера количества информации может быть обоснована такими соображениями:

1. Количество информации больше в опыте с большим числом равновероятных последствий:

2. Если опыт имеет один результат, N =1, то

3. Количество информации в опыте, состоящий из отдельных этапов, в которых имеют место взаимозависимы последствия N₁, N₂ ...

Тогда в общем случае количество информации определится как

Постоянные a и b устанавливают масштаб величины I. По Хартли a = 1,

b = 2. В том случае, если

Эта единица количества информации используется, как правило, в системах связи. Известны также аналогичные единицы измерения нат (b = e ≈ 2,73 ...) и дит (b = 10). В дальнейшем, если значение основы b = 2, оно в функции логарифма не указывается.

Различные способы оценки количества информации представлены в [16]. Наиболее простым является комбинаторный (combinatory) подход. Согласно этому подходу, если дискретный источник информации U в каждый конкретный момент времени может принять случайным образом одно состояние с конечным множеством возможных состояний N, то энтропия (entropy) источника равна:

Эта мера информации была предложена Хартли в 1928 году. Основа логарифма не имеет принципиального значения и определяет только масштаб и единицу неопределенности. Поскольку современная информационная техника базируется на двоичной системе счисления, то конечно основу логарифма выбирают равной двум. При этом единица неопределенности называется двоичной единицей или битом (binary digit – bit). Если основу логарифма выбрать равной десяти, то неопределенность получим в десятичных единицах на одно состояние – дитах (dit). Основным недостатком комбинаторного подхода является его ориентированность на системы с равновероятны состояниями, хотя реальными системы не являются такими.

Вероятностный (probabilistic) подход учитывает этот недостаток. В общем случае источник характеризуется совокупностью состояний (states) с вероятностями (probabilities) их появления (ансамблем).

Для источников информации по неравновероятными состояниями мера неопределенности была предложена американским ученым К. Шенноном. Согласно Шенноном:

где С – произвольное положительное число. Если основание логарифма равна двум, то С = 1, и

Предложенная мера названа Энтропией, поскольку совпадает с Энтропией физической системы, определенной ранее Больцманом.

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

Алгоритмический подход [11] находит применение, если данные характеризуются некоторыми закономерностями, т.е. могут быть описаны некоторыми формулами или порождающими (образующими) алгоритмами (algorithms). Тогда энтропия будет равна минимальному количеству информации для передачи этих формул или алгоритмов от источника к приемнику информации. Алгоритмический подход может применяться при уплотнении графической информации.

Взаимосвязь меры Шеннона и Хартли. Если в источнике может быть реализовано N равновероятных состояний, то вероятность каждого из них равна

1/N, тогда неопределенность по Хартли, приходящаяся на одно состояние источника определяется так [12]:

Будем считать вероятности состояний p_i разными, а неопределенность, приходится на одно состояние источника, по аналогии, характеризуется величиной:

Усреднив по всему ансамблю U состояний источника найдем неопределенность, которая приходится в среднем на одно состояние источника:

А это и есть мера Шеннона, то есть мера Шеннона является обобщением меры Хартли в случае источника с неравномерными состояниями. Она позволяет учесть статистические свойства источника информации [5].

Свойства энтропии

Энтропия – действительно неотъемлемая величина.
Энтропия – величина ограничена.
Энтропия – равна нулю, если вероятность одного из состояний равна 1, то есть состояние источника полностью определено.
Энтропия – максимальна, когда все состояния источника равно вероятны.
Энтропия источника с двумя состояниями u₁ и u₂ меняется от 0 до 1, достигая максимума при равенстве их вероятностей.
Энтропия – объединение нескольких статистически независимых источников информации равна сумме энтропии начальных источников. В объединении двух источников U и V понимают обобщенный источник информации, характеризующееся вероятностями p (u_i, v_j) всех возможных комбинаций состояний u_i источника U и состояний v_j источника V.