Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
а)
?sp(*)
о-/ -
In 2 /?
-----О
-----1
?sp(K)
V2
'/2 г)
Рис. 5.8.1. Сравнение показателей экспонент сферической упаковки и случайного
кодирования.
max Е0 (р, Q)/p.
Q
При р ->¦ оо наклоны этих прямых линий стремятся к бесконечности и так как Esp (R) является выпуклой оболочкой этих функций, то Roo задается как предел концов отрезков, отсекаемых на оси R при р оо, т. е.
Е0 (р, Q)
lim max
р->оо Q
(5.8.5)
174
Отыскивая предел либо по правилу Лопиталя, либо с помощью разложения ?0 (р, Q) в ряд по степеням 1/(1 + р), получаем
Rcc = — In [min max 2 Q (k) Ф (/ \k% (5.8.6)
L Q i k
где
I 1 при P (/1 k) Ф 0,
при P(j\k) = 0. ^
Это значит, что для каждого выхода берется сумма вероятностей букв на входе, из которых этот выход может быть достигнут. Входные вероятности выбираются так, чтобы получить минимум наибольшей из этих сумм, и Ft,*, равно взятому со знаком минус логарифму этой минимаксной суммы. Отсюда можно увидеть, что Rx = 0, за исключением того случая, когда любой выход является недостижимым по крайней мере из одного входа.
Отметим теперь, что значение р, на котором достигается максимум
(5.8.2), убывает с ростом R. Более того, если максимизирующее значение р лежит между 0 и 1, то Ет (R) = Esp (R). Поэтому, если Ег (R) = Esp (R) для некоторого значения R, то равенство также сохраняется для всех больших значений R. Определим Rcr как такую наименьшую скорость R, т. е. как такое значение, для которого Esp (Ю — Er (R) тогда и только тогда, когда R ^ Rсг. Другими словами, для любого канала существует интервал скоростей Rcr ^ R ^ С, в котором показатели экспонент в верхней и нижней границах вероятности ошибки совпадают.
Функция надежности канала Е (R) определяется равенством
E(R)= lim sup--lnP^’ R) , (5.8.8)
N->oo N
где P e (N, R) — минимум P e по всем (N, R)-кодам при заданных N и R. Таким образом, надежность определяется как наибольший показатель экспоненты, с которым может убывать вероятность ошибки с ростом N. Показатели экспонент ЕТ (R) и Esp (R) являются нижней и верхней границами для Е (R) соответственно и, как было отмечено выше, функция Е (R) точно известна при Rcrs^. R ^ С. Конечно, удивительно то, что довольно грубые границы, которые были использованы в § 5.6, дают правильную функцию надежности канала в некотором интервале скоростей. Вместе с тем эти методы построения границ были выбраны с учетом того, что они дают функцию надежности. Имеется много других методов построения верхней границы вероятности ошибки, часто представляющиеся менее грубыми, которые дают, однако, более слабые результаты.
Может случиться (как в примерах (в) и (г) на рис. 5.8.1), что Rcr = = С. Это означает, что для значений R, сколь угодно близких к С, выражение [шах Е0 (p,Q) — рР1 не достигает максимума при р из интер-
Q
вала 0 р 1. Это, в свою очередь, означает, что координата точки пересечения оси R с кривой max Е0 (р, Q)/p больше или равна С при
Q
некотором р ^ 1, либо max Е0 (р, Q)/p стремится к С при р ->¦ оо.
Q
175
В любом случае, поскольку Е0 (р, Q) при фиксированном Q является выпуклой, то для некоторого Q должно быть Е0 (р, Q) = рС. Согласно теореме 5.6.3 это может произойти тогда и только тогда, когда (5.6.26а) удовлетворяется при этом Q. Используя подобное рассуждение, можно показать, что эти условия являются также необходимыми и достаточными для того, чтобы Rx = С. Подытоживая сказанное, отметим, что следующие три утверждения являются эквивалентными 1) Rcr = С; 2) RM = С; 3) равенство (5.6.26а) удовлетворяется при некотором Q, давая пропускную способность.
Теорема 5.8.2. (Прямолинейная граница.) Пусть задан произвольный дискретный канал без памяти, для которого Е ех (0) < оо, и пусть Esi (R) —линейная функция R^O, которая касается кривой Esp (R) и вместе с тем удовлетворяет условию Esi (0) = Еех (0). Пусть Ri является значением R, при котором Est (R) — Esp (R). Пусть
оз (N) и о4 (N) — функции, стремящиеся к нулю с ростом N и которые могут быть представлены в виде
Тогда при любом положительном целом N и любой R, о3 (N) ^ R ^ Rlt любой (N, R)-код имеет вероятность ошибки, которая удовлетворяет неравенству
Это утверждение является теоремой 4 в работе Шеннона, Галлаге-ра и Берлекэмпа (1967) и там же приведено ее доказательство. В формулировке теоремы 4 имеется небольшая ошибка, состоящая в том, что пропущено условие R > о3 (N). Однако приведенное там доказательство верно для сформулированной здесь теоремы. Прямолинейный отрезок показателя экспоненты Est (R) вместе с показателем экспоненты сферической упаковки дают верхнюю границу для надежности Е (R) при всех R, 0 < R < С, в пределе при больших N. Эти границы изображены на рис. 5.8.2 для тех же каналов, что и на рис. 5.8.1.
