§ 5.1. Критерии качества. Постановка задачи кодирования с заданным критерием качества

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

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

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

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

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

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

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

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

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

Пример 5.1.1. Пусть два дискретных множества, состоящие из одного и того же набора элементов. Положим

Математическое ожидание с. в. на ансамбле

и

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

Предположим, что и на множестве задано равномерное распределение вероятностей. Предположим также, что аппроксимирующее множество состоит из двух последовательностей и . В соответствии с (5.1.1) и (5.1.6) величина равна относительному числу символов, в которых последовательности х и у не совпадают. Например,

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

Таблица 5.1.1 (см. скан)

Нетрудно найти, что средняя ошибка Каждая из аппроксимирующих последовательностей появляется с вероятностью 1/2 и, следовательно, энтропия ансамбля аппроксимирующих последовательностей равна 1. Это значит, что существует однозначно декодируемый двоичный код из двух слов, для которого требуется один двоичный символ на аппроксимирующую последовательность или один двоичный символ на три сообщения источника. При этом сообщения источника будут восстанавливаться со средней ошибкой 1/4.

Приведенный расчет показывает, что введение критерия качества и восстановление сообщений источника не точно, а с заданным уровнем ошибок, понижает по крайней мере в этом примере скорость кодирования. Заметим, что при точном восстановлении скорость равна 1 бит на сообщение, тогда как в рассматриваемом примере она равна V бит на сообщение.

Пример 5.1.2. Предположим, что множество X выбрано, как в предыдущем примере, а множество совпадает с X, но содержит дополнительный элемент; обозначим его через Пусть

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

Пример 5.1.3. Пусть числовые оси и сообщения источника представляют собой действительные случайные величины. Положим

Такой критерий качества приемлем, если при аппроксимации особенно нежелательны большие ошибки. Математическое ожидание

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

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

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

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

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

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

Определение 5.1.1. Кодом для кодирования с заданным критерием качества последовательностей сообщений длины называется произвольное множество аппроксимирующих последовательностей. Кодированием для кода называется произвольное отображение и множества на множество кодовых слов Число

называется средней ошибкой кодирования относительно критерия качества Число

называется скоростью кода

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

Кодирование, определяемое соотношением (5.1.13), будем называть оптимальным для данного кода и данного критерия качества

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

На рис. 5.1.1 показана структура кодера источника, на выходе которого появляется в среднем двоичных символов на сообщение. На выходе источника последовательно появляются сообщения из множества Эти сообщения разбиваются на блоки длины и каждый блок подвергается кодированию независимо от остальных блоков. Устройство, обозначенное на рисунке буквой А (аппроксиматор), каждому блоку поданному на

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

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

Рис. 5.1.1. Структура кодера.

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

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

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

1. Для любого найдется и код со скоростью кодирующий последовательности сообщений длины для которого средняя ошибка относительно критерия качества не превосходит (прямая теорема кодирования).

2. Для любого для всех и для всех кодов со скоростью средняя ошибка относительно критерия качества превышает (обратная теорема кодирования).

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