§ 6.2. Кодирование источников с дополнительной информацией

6.2.1. Постановка задачи.

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

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

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

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

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

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

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

называются при этом скоростями кодирования источников соответственно.

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

Рис. 6.2.1. Область допустимых пар скоростей при кодировании источника с дополнительной информацией.

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

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

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

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

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

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

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

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

6.2.2. Функция T(d) и ее свойства.

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

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

тройках посредством следующих соотношений:

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

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

Лемма 6.2.1. Функция монотонно неубывающая, выпуклая вниз функция при всех

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

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

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

Множества можно рассматривать как дизъюнктные. Пусть для любого элемента положим

При этом определен ансамбль для которого

Таким образом, из (6.2.4) следует, что ансамбль принадлежит а из (6.2.5), произвольности и определения (6.2.2) следует неравенство (6.2.3). Лемма доказана.

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

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

Лемма 6.2.2. Для любого целого положительного и любого

Доказательство. Заметим, что при ансамбль где

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

Обозначим где ансамбли, соответствующие моменту времени Для любого ансамбля из имеют место два утверждения:

1) при любых фиксированных сообщениях ансамбли статистически независимы;

2) при любом фиксированном сообщении ансамбли статистически независимы.

Первое утверждение проверяется с помощью следующей цепочки соотношений:

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

Используя эти соотношения и свойства энтропии, можно записать

где последнее равенство — следствие указанной выше независимости (соотношение (6.2.8)).

Положим Тогда из (6.2.9) следует, что откуда с учетом (6.2.10) получим

где последнее неравенство следует из выпуклости функции и того, что

Так как а функция не убывает с ростом то

Лемма доказана.

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

Лемма 6.2.3. Пусть фиксированы множества и распределения вероятностей Если то найдется распределение такое, что

для всех и число элементов для которых превосходит

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

Если то эта [система имеет ненулевое решение Суммируя обе части (6.2.12) по всем получим, что и поэтому среди элементов имеется по крайней мере один отрицательный. Выберем таким образом, что для некоторого

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

Лемма 6.2.4. Пусть такое максимальное подмножество множества что, если то

Тогда

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

где

В соответствии с теоремой Куна-Таккера для нахождения значения функции при каждом фиксированном значении необходимо решить следующую задачу минимизации: найти

где X — величина, определяемая условиями Куна-Таккера по заданному значению Тогда ансамбль который доставляет минимум (6.2.14), будет доставлять минимум также и (6.2.13). Если изменяется в области своих значений, то X также изменяется некоторым образом и поэтому можно рассмаривать как функцию от В общем случае , если Если показать, что для любого и любого то минимум в (6.2.14) при любых будет для каждого достигаться на одном и том же подмножестве множеств Тем самым минимум в (6.2.13) также будет достигаться на подмножестве множеств Следовательно, для всех и лемма будет доказана. Покажем, что

Пусть для некоторого фиксированного X минимум в (6.2.14) достигается на ансамбле который задается распределениями Будем считать, что в функциях аргументы фиксированы и равны . В этом случае

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

для всех где — множитель Лагранжа, обусловленный ограничением Так как соотношение (6.2.16) не зависят от то минимум в правой части (6.2.15) достигается на любом распределении таком, что

В соответствии с леммой 6.2.3 найдется такое распределение при котором выполняется (6.2.17) и число элементов для которых не превосходит Отсюда очевидно следует, что Лемма доказана.

6.2.3. Обратная теорема кодирования.

Пусть совместно заданные дискретные источники без памяти и — совместный ансамбль сообщений. Пусть — множество всех ансамблей распределения вероятностей на которых удовлетворяют условиям (6.2.1) и Определим множество пар чисел следующим образом:

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

На плоскости множество имеет границу, определяемую функцией Действительно, энтропия не

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

и, наоборот, любая пара удовлетворяющая этому неравенству, принадлежит

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

Доказательство. Пусть некоторыйфиксированный код для кодирования источника с дополнительной информацией. Как и при доказательстве теоремы 6.1.1, имеем

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

Очевидно, что

Из этого соотношения следует, что

Так как неубывающая функция то

Нетрудно заметить, что ансамбль принадлежит множеству и поэтому, применяя определение (6.2.7), лемму 6.2.2 и последнее неравенство, получим

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

6.2.4. Прямая теорема кодирования.

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

В качестве первого шага докажем утверждение, являющееся по существу непосредственным следствием из прямой теоремы кодирования для пары зависимых источников (теоремы 6.1.2).

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

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

и кодом с длиной для кодирования источника дополнительной информацией, причем и вероятность ошибки где Лемма доказана.

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

Пусть фиксирован некоторый ансамбль степень ансамбля т. е.

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

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

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

Тогда имеют место следующие неравенства:

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

где черта означает дополнение.

Пусть

Обозначим через такое подмножество множества что для любой пары при выполняется неравенство Из этих определений и (6.2.19) следует, что

откуда получается, что

Пусть

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

откуда получается, что

Положим теперь

Так как то для множества неравенства К 5 утверждения леммы выполняются. Кроме того,

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

Поэтому при указанном выше выборе величин неравенства 7-9 утверждения леммы также выполняются. Лемма доказана.

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

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

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

где множество кодовых слов.

Кроме того, для любого кода, для которого и выполнены неравенства 1 и 2, число кодовых слов удовлетворяет условию

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

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

Так как то из последнего неравенства следует, что

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

Учитывая теперь, что получим

Таким образом, неравенство 2 также имеет место.

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

Кроме того, из условий 1 и 3 указанной леммы следует, что для любой пары

Предположим, что для построенного выше кода

Тогда из неравенства (6.2.22) вытекает, что по крайней мере для одного

Из и (6.2.24) и того, что получим

т. е. при Лемма доказана.

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

Доказательство. Как уже отмечалось ранее, для доказательства теоремы достаточно показать, что для любого ансамбля и любого найдется и отображение множества на множество для которого построения такого отображения воспользуемся кодом леммы 6.2.7. Положим если тогда из условия 3 этой леммы сразу получим

и, следовательно, для любого найдется такое, что —

Оценим теперь энтропию Положим

где слова кода леммы 6.2.7 и множества определены в лемме 6.2.6. Введем обозначения:

Тогда

Из определения множества утверждения 8 леммы 6.2.6 и из того, что имеем

Из утверждений 1 и 4 леммы 6.2.6 следует, что для всех

Из последнего неравенства нетрудно вывести, что

Подставляя (6.2.27), (6.2.28) в (6.2.26) и учитывая, что получим при достаточно большом

для всех . В случае можно использовать оценку

Так как то из (6.2.29) и (6.2.30) следует, что

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

Другими словами, если то при Полагая теперь для кода леммы 6.2.7 и учитывая неравенство 2 этой леммы, из (6.2.31) и (6.2.32) получим, что для любого найдется такое, что

Теорема доказана.