Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Теорема 5.7.1. Пусть задан произвольный дискретный канал без памяти, пусть N — любое положительное целое число и R — какое-либо положительное число. Тогда существуют (N, /?)-коды, для которых при всех т, 1 ^ т ^ I eNIi~],
Ех (Р, Q) = —pin 2 Q (k) Q d) [2 YP UI k) P и 10]1/P (5.7.12)
и максимум no Q в (5.7,11) берется по всем распределениям вероятностей для букв на входе канала.
Исследование свойств функции Еех (R'), которая называется показателем экспоненты для процедуры с выбрасыванием, проводится почти так же, как для показателя экспоненты случайного кодирования. Ее свойства зависят от Ех (р, Q) таким же образом, как свойства ЕТ (R) зависели от Е0 (р, Q).
Теорема 5.7.2. Пусть Q — распределение вероятности на входе дискретного канала без памяти с переходными вероятностями P(i\k)’> будем считать, что У (Q; Р) > 0 [см. (5.6.23)]. Тогда при любом р > 0 Ех (р, Q) является строго возрастающей и выпуклой г\ функцией р. Выпуклость будет строгой, за исключением случая, когда канал является каналом без шума, в том смысле, что для любой пары (г, к) используемых входов (т. е. таких входов, для которых Q (г) >0, Q (k) > 0) справедливо либо Р (/ \k) Р (у| г) = 0 для всех /, либо Р (/1 k) == Р (/1 г) для всех /.
Эта теорема доказана в приложении 5Б. Заметим, что согласно
(5.7.11) Eex(R) можно понимать как верхнюю грань значений множества линейных функций R: —p/? + max ^(р, Q)
(5.7.10)
где функция Еех задается равенствами
Еех (%') = SUP [—P-R' + max Ех (р, Q)],
(5.7.11)
р>1
Q
Q
Рис. 5.7.1.
Сравнение
EAR).
с наклоном —р при каждом р 1. Это изображено на рис. 5.7.1. Заметим, что при р = 1 можно изменить порядок суммирования по j с суммированием по i и k в определении Ех (р, Q) и после этого можно заметить, что Ех (1, Q) = (1. Q)-
Это показывает связь между Еех (R) и Er (R), проиллюстрированную на рис. 5.7.1. Поскольку Ех (р, Q)— строго возрастающая функция р, то указанная геометрическая интерпре-ECX(R) и тация доказывает, что (в общем случае) Е ех (R) > Er (R) для достаточно малых R. Однако в пределе при пере-очень большим шумом это разлйчие становится
ходе к каналу с
сколь угодно малым (см. задачу 5.31).
Заметим, что в любой области, где Е и поэтому
In 4
~лГ
¦/? + max?’je(l, Q)
Q
R
4 ехр / — N
(R) — Ег (R), имеем р = 1
(5.7.13)
что в точности совпадает с равномерной границей для Ре< т, заданной
(5.6.20). Граница для процедуры с выбрасыванием (5.7.10), таким образом, строго точнее, чем граница случайного кодирования в области, где [/? + (In 4)//V] строго меньше, чем наименьшая R, для которой Еех (R) = ЕТ (R).
Может случиться, что для достаточно малой R функция Еех (R) принимает бесконечные значения. Для того чтобы исследовать этот случай, заметим, что координата точки пересечения оси R линейной функцией —рR + Ех (р, Q) равна Ех (р, Q)/p. При р -> оо функция —рR + Ех (р, Q) имеет вертикальную асимптоту
R= lim Ех(р, Q)/p
Рт* 00
и Е ех (R) принимает бесконечные значения при
R< lim Ех (р, Q)/p.
Р'+СО
(Другими словами, для таких R функция —рR + Ех (р, Q) стремится к оо при р -> се.) Раскрывая этот предел по правилу Лопиталя, получаем
?*(p-^ = -ln[2Q(fc)Q(9<pA>,L
з U. i J
lim
р-»оо
fl при 2 Y P(j\k)P(j\i)4= °> Фа, 1=) 1
[ 0 в остальных случаях.
(5.7.14)
(5.7.15)
170
Пусть Rx,x обозначает максимальное значение (5.7.14) по Q, т. е.
Rx, оо = max-
Q
-In Q(k)Q(i) [k,i
Ф h,
(5.7.16)
Из сказанного следует, что Е ех (R) = се при R С RXiao.
Из (5.7.14). можно увидеть, что RX: «, = 0, если ipkii = I при всех k и (', и Rx,<x> > 0 в других случаях. Если <pfti г = 0 для некоторых k и i, то эти два входа не будут никогда перепутаны на приемном конце и по крайней мере один бит информации можно передать при одном использовании канала без каких-либо ошибок, используя лишь эти два входа. Если положить Q (k) = Q (г) = 1/2 для этой пары
Еех(Я)
RX ,оо ~1п2
ъ
/ --
6)
Рис. 5.7.2. Функция Eex(R) для каналов с Rx, со>0.
входов, то правая часть (5.7.14) будет равна In 2. Отсюда следует, что если Rxt жФ 0, то RXt ж должна быть по крайней мере равной In 2. Шеннон (1956) определил пропускную способность канала с нулевой ошибкой как наибольшую скорость, с которой данные могут быть переданы по каналу с нулевой вероятностью ошибки (в противоположность к сколь угодно малой вероятности ошибки). Так как Ре> т = = 0 при R < Rx,x, то получаем, что RXtCO является нижней границей для пропускной способности канала с нулевой ошибкой. На рис. 5.7.2 изображено поведение Е ех (R) для двух каналов с Rx х > 0. В задаче 5.25 выведено простое выражение для Rx,oа-
