9.3. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ ИСТОЧНИКОВ ПРИ ЗАДАННОМ КРИТЕРИИ ВЕРНОСТИ

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

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

где кодовое слово, в которое отображается в

Рис. 9.3.1. Код источника с двумя кодовыми словами и длиной блока 3 (линии указывают отображение

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

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

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

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

В этих выражениях — вероятности источника и тест-канала соответственно. Взаимная информация равна

где

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

Лемма 9.3.1. Пусть для заданных источника, меры искажения и тест-канала вероятность в указанном выше ансамбле кодов с кодовыми словами длины того, что (т. е. искажение между и кодовым словом, в которое оно отображается), превосходит заданное число Тогда

где произвольное положительное число; А — множество последовательностей, задаваемое соотношением

вероятность А в ансамбле тест-канала.

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

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

Доказательство. Применим лемму к тест-каналу, для которого достигается при заданном выбирая равным равным Среднее искажение на букву по ансамблю кодов леммы удовлетворяет соотношению

Это соотношение вытекает из того, что искажение на букву ограничивается сверху величиной когда и величиной вдругих случаях. Для имеем

Таким образом, (9.3.7) принимает вид

В соответствии с определением А

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

где дисперсия и — дисперсия для источника, порождающего одну букву, и вероятностей тест-канала. Отсюда

Из этого неравенства видно, что последнее выражение в (9.3.10) стремится к 0 с возрастанием для любого Следовательно, для достаточно больших

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

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

Доказательство леммы. Вероятность можно представить в виде

Для заданного и определим Ли как множество для которых пара содержится в А:

Отметим, что для заданного и имеем только тогда, когда при всех и, следовательно, только тогда, когда при всех Так как выбраны независимо то

где сумма берется по всем из дополнения Для имеем

Теперь потребуются следующие неравенства:

Равенство (9.3.23), очевидно, удовлетворяется при и так как левая часть выпукла по х, а правая часть линейна по х, то оно

удовлетворяется при Применяя эти неравенства к (9.3.21) и полагая х равным сумме по выводим

Подставляя это выражение в (9.3.16), получаем

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

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

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

Доказательство. Применим лемму к тест-каналу, на котором достигается выбирая равным равным Для ансамбля с {кодовыми словами, как и в (9.3.14), имеем

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

(страница пропущена)

Подставляя это выражение в (9.3.11) и (9.3.10), получаем

Выбирая находим, что сходится к с возрастанием как сходится к таким же образом.

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

Используя более тонкие методы, Пилк (1967) установил существование кодов со скоростью для которых искажение сходится к с возрастанием длины блока, как