Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
позициях и, как будет показано, отмеченного уменьшения показателя не возникает.
Рассмотрим теперь произвольный дискретный канал, в котором Pn (У Iх) является вероятностью получения последовательности у при условии, что была послана последовательность х. Как следует из (5.3.4), для двух заданных кодовых слов Xj и х2 вероятность ошибки при передаче какого-либо слова ограничена следующим образом:
Ре,т (*1. Х2) < 2 pN (у | ХХ)1 -s PN (у | X2)s,
У
т = 1,2; s—любое, О с s С 1. (5.5.2)
Если рассмотреть теперь ансамбль кодов, в котором кодовые слова выбираются независимо в соответствии с распределением вероятности Qn (х), то вероятность кода с некоторыми частными кодовыми словами Xj и х2 равна QN (xj) QN (х2). Следовательно, средняя вероятность ошибки по ансамблю имеет вид
Ре,т = 2 2 Qn (хх) Qn (х2) Ре,т (xlf хя) (5.5.3)
< 2 2 2 Qn (xjl) Qn (X2) Pn (y | Xj)1 —s PN (y | x2)s. (5.5.4)
Xi X2 у
'Po.m < 2 [2 Qn (Xi) Pw (у I Xi)1 - s 1| 2 Qw (x2) Pn (y | x2)s], у Ui Jl*i J
m= 1,2; s — любое, 0-< s< 1. (5.5.5)
Минимум (5.5.5) no s имеет место при s = V2. Для того чтобы показать это*’, заметим, что хх и х2 в (5.5.5) являются просто глухими индексами суммирования. Поэтому, если поменять местами s и 1 — s, то функция не изменится и, следовательно, она является симметричной относительно s = V2. Так же в силу того, что (как уже было показано) правая часть (5.5.2) является выпуклой ^ по s, то правая часть (5.5.5) также является выпуклой ^ по s. Из симметрии и выпуклости следует, что минимум должен быть в точке s = V2 и поэтому
^.m<2[2QA'(x)//Mi^)]2, т^\,2. (5.5.6)
Если канал является каналом без памяти, то
Рлг(у|х)= П Р (у п\ хп)«
П — 1
В этом случае (5.5.6) можно упростить, если положить
Qw(x)-- П Q(xn),
п = 1
*> Конечно, можно положить s= 1/а ву(5.5.5) независимо от того, минимизирует это выражение или нет. Таким образом, читатель может спокойно прене-бречь^этой и подобными последующими минимизациями по свободным параметрам, не беспокоясь о справедливости результата.
149
где Q (k) — произвольное распределение вероятности для буквы. Другими словами, рассматривается ансамбль, в котором каждая буква любого кодового слова выбирается независимо с распределением вероятности Q (к). При этом (5.5.6) можно представить в виде
N
п Q(xn)V~P(yn\Xn)Г- (5.5.7)
Ух у дД*. *Nn = 1 J
После раздельного суммирования по хп каждого сомножителя в произведении [аналогично тому, как это было в (5.3.5)]', получим
У1
N
П 2<Э(*„)г Р(Уп\*п)
1 хп
(5.5.8)
Изменяя порядок возведения в квадрат, умножения и суммирования по уп точно так же, как это было сделано для хп, долучаем
Ре,т< П 2 [? $(*»); (5.5.9)
п=\Уп" п J
Так как в (5.5.9) суммирование по хп производится по входному алфавиту (0, 1, ..., К— 1) и суммирование по уп производится по выходному алфавиту (0, ..., J — 1), то это дает
т = 1,2. (5.5.10)
(j =о \k =о J I
Это представляет собой границу сверху для средней вероятности ошибки по ансамблю кодов с двумя кодовыми словами длины N. Буквы кодовых слов выбираются независимо с вероятностями Q (k), и канал является дискретным каналом без памяти с переходными вероятностями Р (j\k). В двоичном симметричном канале, положив Q (0) = Q (1) = 1/2, из (5.5.10) получаем
Ре,ш < I V2 (J/6+ /Т=1)Т- (5.5.11)
Можно заметить, что граница в (5.5.11) отличается от границы в (5.5.1). На рис. 5.5.1 проиллюстрировано это отличие в зависимости от е.
Причина этого отличия может быть понята с наибольшей ясностью в пределе при стремлении г к 0. Вероятность ошибки для типичного кода с кодовыми словами, отличающимися в половине позиций, очевидно, стремится к нулю. Вместе с тем вероятность того, что в ансамбле кодов два выбранных кодовых слова будут совпадать) равна 2~N; это дает границу для Ре> т в (5.5.11). Другими словами, при малых е средняя вероятность ошибки Ре> т определяется не типичными^ кодами, а в высшей степени специфическими кодами, для которых Ре< т велика.
Приведенное рассуждение довольно просто, но оно часто используется в теории информации. Если требуется получить надежную передачу по каналу с шумами, то нужно сконцентрировать внимание
150
jia специфических событиях, которые вызывают ошибки, а не на типичных событиях, которые не вызывают ошибок. К сожалению, этим важным принципом часто пренебрегают при построении моделей физических каналов связи.
