Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 81

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 75 76 77 78 79 80 < 81 > 82 83 84 85 86 87 .. 355 >> Следующая


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) могут быть нулевыми.
Предыдущая << 1 .. 75 76 77 78 79 80 < 81 > 82 83 84 85 86 87 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed