7. Вероятность ошибки для ансамбля кодов

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

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

Теорема для двустороннего канала является обобщением теоремы 1 (из работы, цитированной на стр. 630), в которой устанавливается граница для в случае одностороннего канала. Доказательство ее является обобщением доказательства для двустороннего канала.

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

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

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

Будем использовать множества 5 и для того, чтобы определить процесс декодирования и при отыскании верхних границ для вероятностей ошибок. Этот процесс определяется следующим образом. Для любой частной пары кодов из случайного ансамбля предположим, что поступило сообщение и оно отображается в слово на входе. Пусть есть слово, соответствующее блоку из букв, полученное на конце 1. Рассмотрим подмножество слов из Могут встретиться следующие случаи. 1) Не имеется ни одного сообщения отображаемого в подмножество для рассматриваемой пары кодов. В этом случае декодируются, по условию, как сообщение номер один. 2) Имеется в точности одно сообщение, отображаемое в это подмножество. В этом случае оно декодируется в это сообщение. 3) Имеется более чем одно такое сообщение. В этом случае оно декодируется в то из таких сообщений, которое имеет наименьший номер.

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

Заметим сначала, что если принадлежит множеству то по определению этого множества

Просуммировав полученные неравенства по множеству значений принадлежащих получим

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

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

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

Здесь было использовано неравенство соотношение (19) и, наконец, тот факт, что

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

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

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

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

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

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

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

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

Тогда существует объект для которого

Вообще, для любого множества чисел таких, что существует объект для которого

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

Общая вероятность объектов, для которых нарушается какое-либо из наших условий, меньше или равна сумме всех частных так что

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

Предположим, например, нам известно, что в комнате находится некоторое число людей, средний возраст которых составляет 40 лет, а средний рост 5 футов. Здесь , используя более простую формулировку теоремы, можно утверждать, что в комнате имеется некто не старше 80 лет и не выше 10 футов, даже если в комнате находятся пожилые карлики и молодые баскетболисты. Полагая можно утверждать, что присутствует человек не выше 8 футов и не старше лет.

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

Этим заканчивается доказательство теоремы 1.

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

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

Тогда для данного существует некоторая пара кодов для всех достаточно больших длин блоков со скоростями передачи по обоим направлениям большими, чем соответственно и вероятностями ошибок

где - есть некоторое положительное число, не зависящее от

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