9.2. ДИСКРЕТНЫЕ ИСТОЧНИКИ БЕЗ ПАМЯТИ И МЕРЫ ИСКАЖЕНИЯ ОТДЕЛЬНОЙ БУКВЫ

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

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

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

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

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

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

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

и среднее искажение

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

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

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

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

Так как теорема 4.4.3 утверждает, что выпуклая по то (9.2.5) можно далее ограничить сверху неравенством

которое представляет требуемый результат.

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

Далее определим как наименьшее для которого (рис. 9.2.1). Значение можно вычислить по формуле

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

Следовательно, минимум при условии достигается всегда при выборе определяемом из (9.2.7). Если для каждого имеется некоторое для которого то, очевидно,

Рис. 9.21. Вид типичной функции

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

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

является средним искажением на букву для этого совместного ансамбля. Тогда

Доказательство. Имеем

В равенстве (9.2.11) использовано то, что источник без памяти, а в (9.2.12) использованы соотношения (2.2.30) и (2.3.13). Подставляя (9.2.11) и (9.2.12) в (9.2.10), получаем

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

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

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

Следовательно, может быть эквивалентно определена для любого равенством

где минимизация проводится по при условии, что

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

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

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

а условная вероятность последовательности адресата при заданной последовательности источника и определяется равенством

Из теоремы 9.2.1 следует, что если среднее искажение на букву между последовательностями источника и последовательностями адресата для этого кода, то

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

Из этих соотношений получаем простое следствие теоремы 9.2.1.

Следствие. Для чтобы -код источника имел среднее искажение на букву необходимо, чтобы энтропия множества кодовых слов удовлетворяла неравенству

а М - неравенству

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

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

а) Если канал является каналом без памяти (с ограничениями или без ограничений на входе) и С — его пропускная способность (в натах) на одно использование, то

б) Если канал является каналом с конечным числом состояний и С — его верхняя пропускная способность (в натах) на одно использование, то в пределе при имеем

в) Если канал является каналом с конечным числом А состояний и С — его нижняя пропускная способность (в натах) на одно использование и если входной ансамбль канала не зависит от первоначального состояния то по крайней мере для одного значения

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

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

Согласно (7.2.12) для канала без ограничений на входе и согласно (7.3.5) для канала с ограничением на входе имеем

Сочетая (9.2.9), (9.2.21) и (9.2.22), имеем

Так как то отсюда получаем (9.2.18).

Утверждение Для заданного начального состояния и заданного утверждает, что

Из (4.6.15) и (4.6.21) имеем

Следовательно, независимо от начального состояния

Переходя к пределу при получаем и отсюда следует (9.2.19).

Утверждение в. Из (4.6.15) и (4.6.23) следует, что существует некоторое начальное состояние для которого

Согласно теореме 4.6.1

Сочетая (9.2.24), (9.2.27) и (9.2.28), получаем (9.2.20).

Предыдущая теорема несколько неестественна в том, что она относится только к двум классам каналов. Единственная трудность в установлении эквивалентной теоремы для других каналов лежит в нахождении подходящего определения для пропускной способности. Как показано в § 4.6, максимум средней взаимной информации на букву даже для канала с конечным числом состояний может существенно зависеть от начального состояния и от того, известно или нет это начальное состояние передатчику. Для наиболее интересных частных каналов, не входящих в эти классы, таких, как канал с аддитивным гауссовым шумом, изучавшийся в последней главе, сравнительно легко определить пропускную способность как максимум средней взаимной информации на единицу времени в пределе для больших интервалов времени. Как только пропускная способность будет определена и проблема, связанная с влиянием прошлой истории будет каким-то образом обойдена, то так же, как в последней теореме, можно будет найти, что где С — пропускная способность канала в натах в секунду.