Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Подставляя (5.8.65) и (5.8.70) в (5.8.64), будем иметь
(5.8.69)
(5.8.70)
¦ А
' Л^е2
ехр [уу (С + е) М
В силу того, что это справедливо для всех (N, М)-кодов, имеем
A ехр |W (С+ е)]
Pe(N, M)^l-
jVe2
M
Наконец, для заданной R > С, выбирая е = (R — С)/2 и используя равенство М—\ tNR |, получаем (5.8.59), что завершает доказательство теоремы. |
Некоторые обобщения этой теоремы рассматриваются в задачах 5.34—5.36. В частности, если в (5.8.67) использовать границу Чернова, а не неравенство Чебышева, то можно показать, что при фиксированной R > С значение Ре стремится к 1 экспоненциально с ростом N. Точно так же, если заменить неравенство Чебышева центральной предельной теоремой, то можно получить более сильные результаты для R, близких к С.
190
5.9. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КАНАЛОВ С КОНЕЧНЫМ ЧИСЛОМ
СОСТОЯНИЙ
В § 4.6 были описаны каналы с конечным числом состояний с помощью условной вероятностной меры Р (уп, sn|;cn, Эта вероят-
ностная мера определяет вероятность PN( у] х, s0) любой последовательности на выходе у = (ylt ..., Уп) при условии, то задана последовательность на входе х = (хх, ..., л:^) и задано начальное состояние s0. Вместе с тем теорема 5.6.1 является теоремой кодирования, которая справедлива для любого распределения вероятности для канала Pn (У \х) (т- е- теорема 5.6.1 справедлива не только для каналов без памяти). Единственная трудность для прямого применения здесь этого результата состоит в том, что не ясно, как поступить с начальным состоянием. Нашей целью здесь является доказательство теоремы кодирования, которая может быть применена независимо от начального состояния. Главным результатом будет следующее утверждение: для любой скорости кода R и любом е > 0 существуют коды с достаточно большой длиной блока, такие, что независимо от сообщения и начального состояния Р е< ехр{—N[Er (R) — е]}, где Er (R) — положительна при R < С. Как было показано в § 4.6, Р е нельзя сделать сколь угодно малой (независимо от начального состояния) при R > С.
В каналах, которые не являются неразложимыми, вероятность ошибки, достижимая при использовании кодирования (особенно при Скоростях между С и С), в общем случае сильно зависит как от начального состояния, так и от знания передатчиком этого начального состояния. Мы не будем подробно рассматривать какие-либо детали этой последней задачи, так как обычно она поддается изучению при малом изменении модели. Например, если «панический» канал, изображенный на рис. 4.6.5, имеет начальное состояние s0 = 0, то можно просто пренебречь панической буквой (буквой 2) и не использовать ее на входе канала, рассматривая канал как двоичный канал без шума. Аналогично, если известно начальное состояние в канале с переменной фазой, изображенном на рис. 4.6.3, то его модель может быть переделана так, чтобы получилась пара параллельных каналов без памяти.
Пр и доказательстве теоремы кодирования, не зависящей от начального состояния, возникает задача, которая формально совпадает с аналогичной задачей для составного канала. Составным каналом называется канал, который описывается множеством различных переходных распределений вероятностей Р$ (у | х), где частное значение i неизвестно передатчику и приемнику. Задача состоит в том, чтобы найти код, который хорошо работает при всех значениях г. В нашем случае получается канал с конечным числом А состояний,и, следовательно, имеются А различных переходных распределений вероятностей, каждое из которых соответствует одному из возможных значений начального состояния s0. Развитый здесь подход (который применим только, когда А конечно) для простоты использует предположение, что начальные состояния имеют равные вероятности. При этом предположении получаем
191
Pn (у I x) = 2 4-p" (У I x, s0).
s„ Л
Теперь можно применить теорему 5.6.1, выбирая М кодовых слов не зависимо с распределением вероятности QN (х); в результате получим
Ре,т < (М- 1)р 2 {2 Qw (X) [S-J Р* (У I X, s0)]1/(I+P)j1+P, (5.9.1)
при любом р, 0 р ^ 1. Ясно, что наиболее точная граница в (5.9.1) может быть получена с помощью минимизации по всем распределениям вероятности на входе QN (х).
Используя такие же рассуждения, как и в обсуждении, следующем за теоремой 5.6.2, можно показать, что средняя вероятность ошибки по крайней мере для одного кода из ансамбля, удовлетворяет указанной выше границе и существует также код с данными N и М, для которого Ре< т, при любом т, ограничена сверху умноженной на четыре правой частью (5.9.1). Наконец, в силу того, что вероятность ошибки для такого кода является средним по А равновероятным состоянием, вероятность ошибки, при условии, что задано какое-либо начальное состояние, может не больше чем в А раз превышать среднее значение. Это дает границу для вероятности ошибки, которая в равной степени справедлива для любого начального состояния и, следовательно, больше не зависит от предположения о равновероятности состояний. Декодер, который рассматривается при выводе этой границы, декодирует сообщение т, для которого максимально значение
