Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
159
строго выпуклой w по R в этом диапазоне R. Заметим, что так как д2Ет (R, Q)/dR2 = 0 вне этого диапазона, то функция Ет (R, Q) является выпуклой w по R при всех R >• 0.
Показатель экспоненты случайного кодирования Er (R) можно теперь связать с Er (R, Q) следующим образом:
Er (R) = max ET(R, Q). (5.6.34)
Этот максимум берется по множеству функций, которые являются выпуклыми w и убывающими по R. Легко заметить (задача 4.12), что функция, на которой достигается максимум, также является выпуклой w и убывающей по R. Кроме того, при Q, на котором дости-
Рис. 5.6.3. Функция ET(R, Q) как огибающая сверху семейства линейных функций ?о(р> Q) — рR при р в качестве параметра.
гается пропускная способность канала, функция Ет (R, Q) является положительной при R<LCf (Q; Р) = С и, следовательно, Er (R) является положительной при R < С. Это доказывает следующую фундаментальную теорему.
Теорема 5.6.4. (Теорема кодирования для канала с шумами.) Для любого дискретного канала без памяти показатель экспоненты случайного кодирования Er (R) [см. (5.6.16) и (5.6.18)] является выпуклой w убывающей положительной функцией R при 0 ^ R < С.
Интересная геометрическая интерпретация процесса максимизации Е0 (р, Q) — р/? по р и Q может быть получена, если заметить, что при фиксированных р и Q функция Е0 (р, Q) — рR является линейной от R и имеет наклон —р. Таким образом, Er (R, Q), как показано на рис. 5.6.3, является огибающей сверху семейства прямых линий, порожденных различными значениями р, 0 ^ р ^ 1. Из этого построения видно, что Е0 (р, Q) является точкой пересечения оси ординате касательной к кривой Er (R, Q), имеющей наклон —р. Из этого построения также непосредственно следует выпуклость ^ функции ET(R, Q).
Для того чтобы максимизировать ?'0(р, Q)—р R аналитически как по р, так и по Q, целесообразно вначале провести максимизацию по Q
Er(R)= шах Г—pR + niax?'0(p, Q)l. (5.6.35)
СКр<1 [ q J
160
функция Е0 (р, Q) не является выпуклой ^ функцией Q, однако, к счастью, она оказывается равной взятому со знаком минус логарифму выпуклой ^ функции. Введем обозначение:
F (р> Q) = ехр [—Е0 (р, Q)] =¦ 1 Q(k)P(j\kym + P))l + P. (5.6.36)
/= о \* = о /
Значение Q, на котором достигается минимум F (р, Q), будет максимизировать Е0 (р, Q).
Теорема 5.6.5. При любом р ^ 0 функция F (р, Q), заданная
(5.6.36), является выпуклой ^ функцией Q в области, где Q является вектором вероятностей. Необходимыми и достаточными условиями того, что на векторе вероятностей Q достигается минимум F (р, Q) [или максимум Е0 (р, Q)], являются условия
2 Р (Л ?)1/( 1 + р) ai (Q)p > 2 aJ (Q)1 + p ПРИ Bcex ^ (5.6.37)
/ i
с равенством при всех k, для которых Q (k) >- 0. Функция aj (Q) задается равенством
%Q(k)P(j\k)lI(l+p). (5.6.38)
k
Доказательство. При р > 0 функция a.j (Q)1+p является выпуклой w функцией (Q) > 0, так как ее вторая производная неотрицательна. В силу того, что a j (Q) является линейной функцией Q, из определения выпуклости следует, что а^(0)'+р является выпуклой ^ функцией Q. Поэтому
F(р, Q) = 2«Л0), + Р j
является выпуклой ^ функцией Q.
Согласно теореме 4.4.1 необходимыми и достаточными условиями того, что вектор вероятностей Q минимизирует F (р, Q) являются условия
dI?dQ(^ ^ для всех с Равенством> если Q (k) > 0; А = const.
(5.6.39)
Отыскивая dF/dQ(k) и производя деление на (1 + р), получаем (5.6.37), Постоянная в правой части (5.6.37) вычисляется с помощью умножения каждого из соотношений на Q (k) и суммированием по k. [
Задача явного решения (5.6.37) и (5.6.38) для отыскания максимума Eq (р, Q) почти эквивалентна задаче отыскания пропускной способности. Для некоторых каналов Q, на котором достигается максимум, можно угадать и проверить с помощью (5.6.37). Для любого симметричного канала (определение см. в § 4.5.) легко проверить, что максимум Е0 (р, Q) достигается тогда, когда все Q (k) равны друг другу. Далее, если число входов равно числу выходов, то иногда возможно решить (5.6.37) как систему линейных уравнений относительно a j (Q)p 6 Зак. 210 161
и затем решить (5.6.38) относительно Q (k), Наконец, используя выпуклость F (р, Q), легко найти максимум^ (р, Q) на вычислительной машине.
Так же как при атыскании пропускной способности, решение
(5.6.37) и (5.6.38) относительно CLj (Q) является единственным, а решение относительно Q (k) не обязательно единственно. Если входной алфавит объема К больше, чем выходной алфавит объема У, то всегда можно отыскать максимум Е0 (р, Q) лишь на J ненулевых значениях Q (k). Единственным существенным отличием отыскания максимума / (Х\ Y) от отыскания максимума Е0 (р, Q) является то, что выходные вероятности для пропускной способности всегда строго положительны, в то время как некоторые a, (Q) могут быть нулевыми.