4. Энтропия в контексте защиты информации от помех при передаче по каналу связи

4.1. Меры искажения. Постановка задачи защиты информации от помех при передаче по каналу связи

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

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

Конечно, следует выбирать критерии так, чтобы уровень объектив­ного качества был монотонно связан с уровнем субъективного качества. Однако, в большинстве случаев "повергнуть алгебре язык гармоний" не удается. Приходится, как это часто бывает в теоретических исследовани­ях, накладывать на множестве мер искажений такие ограничения, кото­рые позволили бы с разумной сложностью найти аналитические решения интересующих нас задач.

Итак, рассмотрим некоторое множествоX = {x}, элементы которо­го - сообщения источника и второе множество,Y = {y}, которое будем называть аппроксимирующим. Мера искажения определяется как функция на множестве , удовле­творяющая следующим ограничениям:

- Для любыхx = (x₁,..., x_n), y = (y₁,..., y_n)

(4.17)

где - так называемая побуквенная мера искажения.

- для всех

Согласно этим условиям, при кодировании последовательностей со­общений источника, мы рассматриваем только такие меры искажения которые вычисляются как среднее значение побуквенной меры по всем сообщениям последовательностей, причем побуквенная мера обязательно неотрицательна. Оба ограничения вполне естественны. Первое нормиру­ет суммарную ошибку в последовательности сообщений по отношению к длине последовательности и позволяет объективно сравнивать кодеры, обрабатывающие последовательности разной длины. Второе ограничение тоже понятно, оно означает, что аппроксимация приводит к потере точности иd(x,y) указывает величину потери, связанной с заменой точного значения xего аппроксимирующим значением y. Приведем несколько примеров.

Пример. Вероятностная (Хэммингова) мера искажения. Пусть X = {0,..., M-1} - дискретное множество, иY = X. Положим

Соответствующая мера представляет собой долю "ошибок" при выдаче получателю y вместо истинной последовательности x. При большой длине последовательностиd_n(x,y) можно рассматривать как эмпи­рическую оценку вероятности ошибочного символа, отсюда - название "вероятностная мера"

Пример. Абсолютная мера искажения. Пусть Х – произвольное множество вещественных чисел и Y = X. Положим

Соответствующая мера представляет собой нормированную сумму модулей отклонения компонентy от компонент последовательностиx.

Пример. Квадратическая мера искажения. Пусть Х – произвольное множество вещественных чисел и Y = X. Положим

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

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

Рассмотрим теперь приведенную на рис.15 модель системы, осу­ществляющей кодирование при заданном критерии качества.

Рис. 4.1. Схема кодирования с заданным критерием качества

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

Декодер хранит точную копию кодаB и по полученному индексуmвоспроизводит аппроксимирующую последователь-ность y =b_m.

Поскольку для передачи индекса m достаточно logM бит (для сокращения записи мы считаем М степенью двойки), скоростью кода источника называется величина

бит / сообщение источника.

При фиксированном коде В и заданной вероятностной модели источника можно усреднением по всем подсчитать среднюю ошибку

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

Таким образом, основными характеристиками описанной системы кодирования являются два числа: скорость R и средняя ошибка D. Наша задача закодировать последовательность сообщений с наименьшей ско­ростью и с наименьшей ошибкой.

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

Более формально, функцией скорость искажение R(D) для заданной модели источника называется функция вида

где нижняя рань берется по длинам кодируемых последовательностей, а минимум – по таким кодам последовательностей длины n, которые удовлетворяют ограничению на допустимую ошибку D.

Аналогично можно определить функцию искажение-скорость D(R).

Очевидно, определение невозможно использовать для подсче­та функции скорость-искажение. Желательно (как это было сделано для кодирования источников без потерь и для каналов связи) научиться вы­числятьR(D) по модели канала без перебора по всевозможным кодам источника, аналогично тому, как для кодирования без потерь минималь­ная скорость кода определяется энтропией источника, а максимальная достижимая скорость передачи информации по каналу связи равна его пропускной способности.

Вернемся к схеме на рис. 4.1. Модель источника задана и тем самым задано распределение вероятностей на последовательностях из . Для определенности, будем считать источник непрерывным и описывать мо­дель источника плотностью распределения вероятностей .Заметим, что среднее количество информации об , доставляемой получателю декодером может быть подсчитано как взаимная информация . Соответственно, затраты в битах в расчете на одну букву ис­точника составляют бит. Все промежуточные блоки ОТ вхо­да до выхода схемы на рис. 4.1 можно описать в виде условного распреде­ления вероятностей Многообразие таких плотностей полностью включает в себя все мыслимые схемы кодирования, но нас интересуют только такие плотности, при которых выполняется требование к допу­стимой ошибке, которая в данном случае вычисляется как

Теоретической функцией скорость-искажение называется величина (4.19)

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

Эти утверждения мы сформулируем, как всегда в виде двух теорем кодирования - прямой и обратной. Но прежде, чем мы приступим к фор­мулировке и доказательству теорем кодирования, мы изучим свойства функции H(D)и рассмотрим несколько важных моделей источников и мер искажения, для которых H(D) может быть вычислена в явной форме как функция параметров модели.