4.3. ОБРАЩЕНИЕ ТЕОРЕМЫ КОДИРОВАНИЯ

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

Рассмотрим вначале последовательность и из букв дискретного источника, изображенного на рис. 4.3.1. Энтропия на букву для последовательности из букв определяется равенством

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

Рис. 4.3.1. Система связи.

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

Целью системы связи является получение последовательности воспроизводящей последовательность и. Если то считается, что произошла ошибка в 1-й переданном символе. Вероятность такой ошибки определяется совместным ансамблем Средняя вероятность ошибки в последовательности из символов определяется следующим образом:

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

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

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

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

Тогда

где

Рис. 4.3.2. Интерпретация теоремы 4.3.1.

Обсуждение. Функция изображена на рис. 4.3.2. Теорема утверждает, что, если принимает заданное значение, отложенное на оси ординат на рис. 4.3.2, то должно быть не меньше соответствующей абсциссы. Так как то теорема ограничивает с помощью выражения, представляющего собой превышение энтропии источника над средней взаимной информацией. Легко эвристически установить справедливость (4.3.4). Средняя неопределенность и при заданном сможет быть разбита на два члена: первый, представляющий неопределенность, относящуюся к тому, была совершена ошибка или нет при заданном и; и второй, представляющий неопределенность переданной входной буквы в случаях, когда была сделана ошибка. Первый член ограничен сверху значением а второй член — значением, равным умноженным на максимальную неопределенность при условии, что произошла ошибка. Так как неопределенность при условии, что произошла ошибка, состоит в выборе между альтернативами, то второй член ограничен сверху значением

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

и и другое, содержащее пары для которых :

Согласно (4.3.3) разность между выражениями, стоящими в разных частях (4.3.4), равна

С помощью неравенства приходим к тому, что правая часть (4.3.7) меньше или равна выражению

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

Доказательство. Используя цепное правило для совместного ансамбля [см. равенство (2.2.30)], имеем

Неравенство (4.3.13) следует из общего неравенства [см. неравенство (2.3.13)].

Применяя теорему 4.3.1 к каждому слагаемому в (4.3.13), получаем

Чтобы завершить доказательство теоремы, следует показать, что

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

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

По определению будем считать, что последовательность источника связана с адресатом при N-кратном использовании канала, если совместный ансамбль [соответствующий выходу источника и, входу канала выходу канала и декодированному выходу (сообщению на выходе) обладает тем свойством, что у не зависит от и при условии, что задано не зависит от и их при условии, что задано у.

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

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

Теорема 4.3.3. (Теорема переработки информации.) Пусть последовательность источника связана с адресатом каналом, используемым N раз. Тогда

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

выходной последовательностью является средней взаимной информацией при Л-кратиом использовании канала.

Доказательство. Первое условие приведенного выше определения совместно с теоремой 2.3.3 дает: Из (2.3.19) теперь получим

Второе условие определения дает используя вновь (2.3.19), имеем

Объединяя (4.3.18) и (4.3.19), получаем (4.3.17).

Из доказанных двух теорем следует, что

где

Если канал является то будем иметь отсюда получаем

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

Теорема 4.3.4. (Обращение теоремы кодирования.) Пусть дискретный стационарный источник с алфавитом объема имеет энтропию и производит буквы со скоростью одна буква за секунд. Пусть дискретный канал без памяти имеет пропускную способность С и передача по нему ведется со скоростью одна буква за секунд. Пусть последовательность источника длины связана с адресатом каналом, используемым N раз, где

Тогда для любого вероятность ошибки на букву источника удовлетворяет неравенству

Доказательство. Согласно теореме и (4.3.22) является непосредственным следствием (4.3.21).

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

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

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

В частном случае канала без шума с буквами во входном и выходном алфавитах условие (4.3.22) является просто обращением теоремы кодирования для источника. Оно отличается от (3.1.20) тем, что ограничивает снизу вероятность ошибки на символ, а не вероятность ошибки в блоке.

Можно заметить, что граница, задаваемая (4.3.22), довольно слабая при большом объеме алфавита источника. Для того чтобы показать, что эта слабость границы неизбежна, построим источник, для которого произвольно велика, а произвольно мала даже при Пусть источник без памяти и его алфавит составляют буквы Пусть сколь угодно малое положительное число и пусть ей при Тогда, если декодер декодирует каждый символ в букву то ошибки появляются только тогда, когда источник вырабатывает буквы, отличные от Таким образом, вероятность ошибки равна Вместе с тем

При любом можно сделать сколь угодно большим, выбирая достаточно большое Можно заметить, что эта «система связи» удовлетворяет условию (4.3.22) с равенством, если