Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
т= 1
Наконец, так как р и Q являются произвольными в (5.6.13) и (5.6.14), наиболее точная граница получается после выборар и Q так, чтобы максимизировать Е0 (р, Q) — pR. Таким образом, мы приходим к определению показателя экспоненты случайного кодирования ЕТ (R):
Er(R) = max max [?0 (P. Q) — Р^Ь (5.6.16)
0<р<1 Q
где максимизация по Q производится по всем распределениям вероятностей Q == [Q (0), ..., Q (К — 1)]. Отсюда получаем следующее
следствие.
Следствие 1. Для ансамбля кодов с Q, которое максимизирует (5.6.16), имеем
Ре, rn< ехр [ — NEr (/?)], 1</л<ЛГ, (5.6.17)
Ре < ехр [—NEr (/?)]. (5.6.18)
На рис. 5.6.1 изображены показатели экспоненты случайного кодирования ЕГ (R) для нескольких каналов. Как будет показано в следующем параграфе, Ег (R) > 0 при всех R, 0 <; R < С, где С — пропускная способность канала в натуральных единицах. Следова-
155
тельно, при подходящем выборе кодов вероятность ошибки можно сделать экспоненциально стремящейся к нулю с ростом длины блока при любой скорости, меньшей пропускной способности.
Так как средняя по ансамблю кодов вероятность ошибки удовлетворяет (5.6.18), то ясно, что по крайней мере один код из ансамбля должен иметь вероятность ошибки столь же малую, как и эта вероятность. Это следствие не дает способа отыскания такого кода и было бы удивительно, если бы случайно выбранный код имел вероятность ошибки гораздо большую, чем средняя вероятность. В частности, используя неравенство Чебышева (5.4.6), получаем 1
Рг(Ре^аРе) при любом а>1. (5.6.19)
а
Этот результат очень важен при практическом использовании кодирования. Он говорит о том, что трудной является не проблема отыска-
Рис. 5.6.1. Показатель экспоненты случайного кодирования ET(R) для двух каналов:
а — типичное поведение; б—частный случай, в котором d*E0jdр2=0.
ния хороших кодов с большой длиной блока, а проблема отыскания интересных для практики методов кодирования и декодирования таких кодов.
Приведенные рассмотрения дают возможность лучше понять поведение Ре~^Рг{пг)Ре<тп для случайно выбранного кода. К сожа-
m
лению, вполне возможно (и в действительности высоко вероятно), что в таком случайно выбранном коде Ре m будет много больше, чем Р е для некоторых значений m и много меньше для других. Во многих системах передачи данных вероятности сообщений либо неизвестны, либо не имеют смысла. В таких ситуациях желательно обычно иметь код, для которого m равномерно мала при всех т. Приводимое ниже следствие устанавливает существование таких кодов с помощью первоначального случайного выбора хорошего кода и последующего удаления всех слов, для которых Р е, т слишком велико.
156
Следствие 2. Для любого дискретного канала без памяти, любого целого положительного N и любой положительной R существует (N, R)-блоковый код, для которого
Ре,т< 4 ехР [ — NEt (7?)], для всех т, = Г~еЛ'Я'“]. (5.6.20)
Доказательство. Выберем код с 2М. кодовыми словами, для которого при равновероятных сообщениях
2 М
2М
2 Ре,т-'
т — 1
: еХР
NE„
In 2 М
N
(5.6.21)
Удалим М кодовых слов из этого кода, устраняя, в частности, все слова, для которых
1п2Л-П
Ре,т> 2ехр
¦NEr
N
(5.6.22)
Не может быть больше чем М слов, удовлетворяющих (5.6.22) потому, что если бы М таких слов существовали, то (5.6.21) не имело бы места. При использовании декодирования по максимуму правдоподобия декодирующие подмножества, соответствующие оставшимся словам, не могут потерять какой-либо элемент и, таким образом, для каждого оставшегося слова получаем
( \п2М
— NEr
N
Используя (5.6.16) совместно с этим результатом, будем иметь
Ре,т<2ех р j —ЛгГ шах fmax ?0(р, Q) — р — Р
I Q N N ] )
2 ехр
¦N
_j_ max / max eq (p;
N 0<p^l\ Q
!)
= 4exp[ —JV?,(#)1-
Таким образом, это множество М кодовых слов удовлетворяет (5.6.20).
Свойства показателя экспоненты случайного кодирования Er(R)
Для того чтобы понять поведение Er (R), нужно вначале исследовать Е0 (р, Q) как функцию р. На рис. 5.6.2 изображена Е0 в зависимости от р, и следующая теорема показывает, что график Е0 всегда имеет такой общий вид. Средняя взаимная информация
Cf (Q; Р) = у Q (k)P (/ ] k) In P-(/|fe)-------¦ (5 .6.23)
