4.9. Обратная теорема кодирования для дис­кретного постоянного источника при за­данном критерии качества

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

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

Итак, имеется множествоX^п последовательностей длины n, на выхо­де источника без памяти, выбираемых в соответствии с заданным на нем распределением вероятностей . Кодовая книга или код со скоростьюR для этого источника определен как мно­жество изM = 2^Rn последовательностей из аппроксимирующего мно­жестваY^п. При построении кода мы стремимся минимизировать вели­чину средних искаженийD =M[d_n(x, у)], где мера искажения d_n(x,у) удовлетворяет ограничениям, сформулированным в начале главы , т.е. неотрицательна и

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

Теорема. Пусть заданы дискретный алфавит постоянного ис­точника X = {x}, аппроксимирующий алфавит X = {x} и мера ис­кажения . Для любого кода со скоростью R и средней ошибкой D имеет место неравенство R>H(D)

Доказательство. Следующая цепочка преобразований доказывает тео­рему

Переход (а) справедлив, поскольку энтропия кодовой книги не превы­шает логарифма числа кодовых слов, (b) имеет место, поскольку вычи­таемое неотрицательно. Далее, (с) и (d) - хорошо известные свойства взаимной информации, равенство (е) использует отсутствие зависимо­сти букв источника. В (f) мы неравенство, опустив некоторые условия в вычитаемом, отчего вычитаемое могло только увеличиться. В (g) и (h) использованы определения взаимной информации и затем функции скорость-искажение как минимума взаимной информации при ограниченной ошибке, причем через обозначена средняя ошибка аппроксимации значениями из . Неравенство (i) основано но выпуклости функции скорость-искажение, равенство (j) - на определении средней меры искажения для последовательностей длины n.

4.10. Прямая теорема кодирования с задан­ным критерием качества

Прямая теорема кодирования устанавливает существование кодов источника, для которых скорость R при заданном допустимом среднем искажении D может быть сделана сколь угодно близкой к соответствующему значению функции скорость-искажение H(D). Один из способов доказательства этого утверждения могло быть указание конкретного способа кодирования и декодирования, как это было сделано в случае кодирова­ния без потерь. Такое доказательство мы назвали бы конструктивным. К сожалению такое конструктивное решение задачи возможно только для некоторых вырожденных ситуаций (например, приD = 0). Чтобы доказать существование хороших кодов для произвольных источников без памяти, придется воспользоваться уже знакомой нам техникой слу­чайного кодирования.

Итак, метод доказательства состоит в том, что среднее искажение оценивается для кода, слова которого получены случайным независимым выбором кодовых слов. При подсчете ошибки кодирования усреднение выполняется как по множеству последовательностей источника, так и по множеству кодов. Если среднее значение искажений окажется равным D, то мы сможем утверждать что найдется хотя бы один код, для которого среднее искажение не больше D.

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

функция скорость-искажение дискретного постоянного источника.

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

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

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

Существенным подспорьем в практическом применении теории коди­рования для источников с заданной мерой точности является численный алгоритм Блэйхута, позволяющий построить функциюH(D) по дискрет­ной модели или по ее оценке, полученной по реализации последовательности данных на выходе источника.