Теоремы кодирования при заданной мере искажения отдельной буквы

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

Сначала докажем следующую лемму.

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

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

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

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

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

Так как совместный процесс эргодичен, то можно применить

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

Точно так же с вероятностью, не меньшей будем иметь неравенство

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

Суммируя эти неравенства по всем получаем

Если то, как показано выше, и неравенство может быть приведено к следующему виду:

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

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

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

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

Рис. 4.

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

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

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

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

Теорема 2. Пусть заданы эргодический источник, мера искажения и скорость зависящая от искажения и (и вычисленная на основе заданных частот отдельных букв); заданы Тогда для любого достаточно большого существует множество А, содержащее М слов длины из алфавита со следующими свойствами:

2) среднее искажение между -словом длины и ближайшим наименее искаженным к нему словом из множества Л меньше или равно

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

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

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

В ансамбле кодов с кодовыми словами длины соотнесем всевозможными способами слова длины целым числам от 1 до М. Каждому целому числу соотнесено некоторое слово, скажем

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

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

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

то (используя знакопеременность и монотонное убывание членов разложения логарифма) получаем

Если взять М (число точек) равным по величине если это не целое число, равным наименьшему целому, превосходящему эту величину), то выражение, приведенное выше, будет равно Следовательно, при таком выборе М получаем оценку для среднего искажения

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

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

Следствие. Теорема 2 остается справедливой, если в утверждении заменить на 0. Она также остается справедливой, если в утверждении 1) сохранить а в утверждении 2) заменить его на

0, при условии что в этом случае т. е. наименьшего для которого определена функция

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

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

т. e. такое, что и используем теорему 2 для аппроксимации этой точки кривой.

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

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

Таким образом, можно достигнуть желаемого уровня искажения (большего, чем и в то же время приблизиться к использованию канала для передачи со скоростью, соответствующей Это можно сделать, подобно тому как это сделано в следствии к теореме 2, аппроксимируя кривую в точке левее скажем, в Такой код будет иметь слов, где может быть сделано как угодно малым при помощи выбора достаточно большого Код для канала образуется из М слов длины где — наибольшее целое число, удовлетворяющее условию Выбирая достаточно большим, можно сделать вероятность ошибки как угодно близкой к нулю, так как это соответствует скорости передачи, меньшей пропускной способности канала. Комбинация этих двух кодов приводит к общему коду со средним искажением, не превышающим