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

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

Пусть задан дискретный УШК без памяти с входным алфавитом X, выходными алфавитами и переходными вероятностями причем вторая составляющая канала является ухудшенным вариантом первой, т. е. Пусть некоторое конечное множество, Зададим распределение вероятностей на четверках посредством соотношения (6.4.8), где некоторые выбранные произвольным образом распределения вероятностей на и X соответственно,

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

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

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

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

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

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

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

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

Таким образом, из (6.4.12) следует, что ансамбль принадлежит), а из (6.4.13), произвольности и определения (6.4.10) следует неравенство (6.4.11). Лемма доказана.

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

где

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

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

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

Заметим, что из (6.4.14) и следует статистическая независимость ансамблей при фиксированных через

обозначены ансамбли сообщений, соответствующие моменту времени Действительно,

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

т. e. имеет место указанная выше независимость. Отсюда имеем

Кроме того,

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

Положим теперь Тогда из (6.4.20) и (6.4.21) следует, что

Обозначим тогда Из (6.4.21) имеем

где последнее неравенство следует из выпуклости функции Предположим, что тогда и из неравенства (6.4.22) получим, что Поскольку монотонно невозрастающая функция то неравенство (6.4.24) дает

что и требовалось доказать.

Рассмотрим теперь некоторый код для дискретного УШК при передаче в ситуации Пусть

Выберем распределения вероятностей следующим образом:

где - множество кодовых слов кода Зададим на следующее распределение вероятностей:

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

Лемма 6.4.4. Пусть вероятности ошибок при декодировании первым и вторым декодерами кода для дискретного УШК без памяти. Для любого такого кода имеют место неравенства

Доказательство. Обозначим через множества решений первого и второго декодеров соответственно. Правило декодирования для кода и распределения (6.4.27) однозначно определяют распределение вероятностей на множестве Для этого распределения вероятностей выполняются следующие очевидные соотношения:

Заметим, что вероятность ошибки второго декодера а условная вероятность ошибки первого декодера при условии, что передавалось одно из кодовых слов Утверждение леммы следует из сделанного замечания, из (6.4.28), (6.4.29) и неравенства Фано. Лемма доказана.

Из доказанной леммы вытекает, что пара скоростей для передачи по УШК в ситуации не является допустимой в том случае, когда удовлетворяется хотя бы одно из неравенств

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

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

Лемма 6.4.5. Пусть является максимальным подмножеством множества таким, что если то Тогда

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

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

Таким образом, равенство (6.4.31), а следовательно и утверждение

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

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

Рис. 6.4.8. Типичный вид функции

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

где - переходные вероятности первой составляющей ШК а — второй, и

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

удовлетворять соотношениям (6.4.34) и, следовательно, максимизировать правую часть (6.4.33). Из (6.4.35) следует, что, если для всех

то распределение удовлетворяет соотношениям (6.4.34).

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

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

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

Поэтому наименьшее значение при котором есть . С другой стороны, для любого ансамбля из леммы 6.4.1 следует, что

поэтому

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

Теорема 6.4.1. (обратная теорема кодирования). Для произвольного дискретного УШК без памяти

где — области пропускной способности для передачи по УШК в ситуациях соответственно.