Нижняя граница для искажения при заданной пропускной способности канала

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

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

или, что равносильно, для любого кода где — функция, обратная

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

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

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

Прежде всего покажем, что Имеем (так как — есть функция а также Последнее следует из приведенного выше условия независимости. Действительно, так что Но так как X есть функция и по той же причине Упорядочивая приведенные соотношения, имеем

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

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

Здесь использован тот факт, что рассматривается канал без памяти, так что , следовательно, Наконец, последнее неравенство обусловлено тем, что С — наибольшее из возможных значений

Так как элементарное приращение величины ограничено значением С, то полное изменение после шагов ограничено величиной Следовательно, величина не меньше Отсюда

Теперь найдем верхнюю границу выраженную в терминах искажения Имеем

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

так как есть минимум взаимной информации при искажении Поэтому наше неравенство можно записать в виде

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

Но есть полное искажение системы, так что

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

Это и есть по существу утверждение, сформулированное в теореме 1.

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