9.5. МОДИФИКАЦИЯ ОБРАЩЕНИЯ ТЕОРЕМЫ КОДИРОВАНИЯ ДЛЯ КАНАЛА С ШУМАМИ

Как было уже отмечено, функция искажения

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

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

упрощаются для этой меры искажения и имеют вид

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

Используя это в нижней границе (9.4.10), получаем

Тогда для всех имеем

Правая часть максимизируется по в результате давая точную границу при удовлетворяющем равенству

Подставляя (9.5.7) в (9.5.5) и производя преобразования, выводим

где

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

Теперь найдем условия, при выполнении которых (9.5.8) удовлетворяется и переходит в равенство. Из теоремы 9.4.1 следует, что (9.5.4) удовлетворяется с равенством, если для (9.5.7) существует решение с которое для этой меры искажения принимает вид

Для

Все со неотрицательны, если

Следовательно, (9.5.4) удовлетворяется с равенством для всех достаточно больших Так как для каждого

имеет с кривой по крайней мере, одну общую точку, и так как эта точка задается (9.5.6) для всех удовлетворяющих (9.5.12), то имеем

для

где (9.5.14) вытекает из (9.5.12) и (9.5.7) и где наименьшее значение Из этого результата и теорем 9.2.2 и 9.3.1 получаем следующую теорему.

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

и никакими способами не может быть достигнута, если

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

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

Как из физических соображений, так и из рассмотрения выражения (9.5.11) можно предположить, что если какая-либо из выходных вероятностей равна 0, то она должна относиться к тем буквам, которые соответствуют наименее вероятным входам. Таким образом, мы принимаем, что для некоторого которое будет выбрано позднее, со при и при Для равенство (9.5.10) принимает вид

Неравенство задающее ограничение, должно удовлетворяться с равенством при —1. Следовательно, все должны быть одни и те же, скажем при при Находя выражение, задающее ограничение для и используя (9.5.18), получаем

где

Из (9 5.18) видим, что и ограничение имеет место для если

Вектор задаваемый (9 5 18) и (9.5 20), максимизирует выражение если все определяемые (9.5.10), неотрицательны. Так как то это требует только, чтобы

Следовательно, для области где (9 5 21) и (9.5 22) удовлетворяются, заданное приводит к соотношению

Теперь, зная в некоторой области определяем в соответствующей области наклонов Параметр связан с соотношением

Для , связанных (9.5.24), имеем

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

где энтропия редуцированного ансамбля с йераятйостймй определяется равенством

Подставляя (9.5.24) в (9.5.21) и (9.5.22), находим, что это решение справедливо для заданного если

Заметим, что для нижняя граница для совпадает с верхней границей для если удовлетворяет (9.5.13). Также верхняя граница для при каком-либо значении (отличном от К— 1) совпадает с нижней границей при соседнем значении, меньшем

Наконец, верхняя граница для при равна так что для любого большего чем то значение, для которого (9.5.13) задает определяет для которого (9.5.25) задает

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