Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
R (d*) = Н (U) — Ж (d*) — d* ln (К — 1) (9.5.13)
Для
а* < (К - \)Qmin, (9.5.14)
где (9.5.14) вытекает из (9.5.12) и (9.5.7) и где Qmin — наименьшее значение Q (к). Из этого результата и теорем 9.2.2 и 9.3.1 получаем следующую теорему.
Теорема 9.5.1. Пусть задан дискретный источник без памяти с энтропией Н (U) нат, с алфавитом объема К и минимальной вероятностью буквы Qmin и пусть задано, что источник связан с адресатом дискретным каналом без памяти с пропускной способностью С (в натах на символ источника), тогда для любого d* ^ (К — 1 )Qmm вероятность ошибки на символ источника d* может быть всегда достигнута с помощью соответствующего кодирования, если
C>H(U) — Ж (d*) — d*ln (К— 1), (9.5.15)
и никакими способами не может быть достигнута, если
С С Н (U) — Ж (d*) — d* ln (К — 1). (9.5.16)
Для простоты в теореме рассматриваются лишь дискретные каналы без памяти. Она, очевидно, остается справедливой всегда, когда С может быть выражена как максимум средней взаимной информации и вместе с тем интерпретирована с помощью теоремы кодирования. Весьма примечательно, что этот минимум вероятности ошибки может быть однозначно определен с помощью столь малого числа параметров.
Теперь вычислим R (d*) для больших значений d*. Для простоты обозначений предположим, что вероятности букв упорядочены
Q(0)>Q(1)>... >Q(/C-1). (9.5.17)
Как из физических соображений, так и из рассмотрения выражения
(9.5.11) можно предположить, что если какая-либо из выходных вероятностей равна 0, то она должна относиться к тем буквам, которые соответствуют наименее вероятным входам. Таким образом, мы принимаем, что для некоторого т, которое будет выбрано позднее, со (k) = О при к т и со (к) > 0 при k ^ т — 1. Для k ^ т равенство (9.5.10) принимает вид
Q (к) — fk е_Р, к ^ т. (9.5.18)
482
Неравенство f3 + (2/;i ~fj)e~P < 1, задающее ограничение, должно удовлетворяться с равенством при j^m—1. Следовательно, все fi должны быть одни и те же, скажем f0, при / ^ т — 1 и fj ^ f0 при
/ ;> т. Находя выражение, задающее ограничение для / = 0, и исполь-
зуя (9.5.18), получаем
/о П + (т— 1) е-Р] + K^Q(k) = l, (9.5.19)
k—tn
fh /о -------^k^m-1, (9.5.20)
lh /0 1 + (m — 1) e—p
m— 1
где Sm--~- V Q(k). k = 0
Из (9.5.18) видим, что 1 ^2= ••• ^/к-1 и ограничение
fi /о имеет место для j ^ /п, если
Q(m)<—^е~Р. _р. (9.5.21)
1 + (м—1)е р
Вектор f, задаваемый (9.5.18) и (9.5.20), максимизирует выражение
2 Q (k) In fh, если все со (/г), определяемые (9.5.10), неотрицательны.
к
Так как со (т — 1) ^ со (т— 2) <^ ... ^ со (0), то это требует только, чтобы
Q{m-1)> S™e-P (9.5.22)
1 + (m— 1) е р
Следовательно, для области р, где (9.5.21). и (9.5.22) удовлетворяются, заданное f приводит к соотношению
т — 1 о
min R0 (р, Р) = H(U)+ 2Q(k)ln~—^——p + р Л = 0 1 + (/п —1)е р
+ *2 Q(A)ln[Q(A)eP], (9.5.23)
k = rn
Теперь, зная inin R0 (р, Р) в некоторой области р, определяем R (d*) р
в соответствующей области наклонов. Параметр р связан с d* соотношением
d, = (./ min А’о ;р, Р) = (т- 1)_е^_ 5 2
<Эр т 1 + (/п-1)е-р т К ’
Для р ad*, связанных (9.5.24), имеем
R (d*) — min R0 (р, Р) — рd*.
Р
После некоторых преобразований это выражение приводится к виду
R (d*) = [Н (Um)-3? (d)-d In (т— 1)], (9.5.25)
16* 483
!'Дй И (Um) — энтропий редуцированного ансамбля с вероятностями Q (0)/Sm, ..., Q (т — l)/Sm и d определяется равенством
(9.5.26)
¦Sm
Подставляя (9.5.24) в (9.5.21) и (9.5.22), находим, что это решение справедливо для заданного т, если
mQ (m) + ^ Q(k)^d*^(m—l)Q(m—1)4- ^Q{k). (9.5.27)
к = т^\~ 1 k — m
Заметим, что для т = К — 1 нижняя граница для d* совпадает с верхней границей для d* , если d* удовлетворяет (9.5.13). Также верхняя граница для d* при каком-либо значении т (отличном от К — 1) совпадает с нижней границей при соседнем значении, меньшем т.
