Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
115
ний статистически зависит от входной последовательности. Таким образом, для этого класса каналов не только не выполняется равенство
(4.2.1), т. е.
-Му|х) = ПР(г/пК)
П
не имеет места, но также вероятности, входящие в это выражение, не определяются только через понятия, описывающие канал.
Будем называть каналы, такие, как на рис. 4.6.1, где 7 (sn | Хп, sn_i) не зависит от хп, каналами без межсимвольной интерференции, а каналы, такие, как на рис. 4.6.2, где q (sn | хп, s„_ i) принимает только значения 1 и 0 и зависит от хп, каналами, в которых имеется только память, связанная с межсимвольной интерференцией. В первом случае память возникает лишь из-за шума, а во втором случае — только из-за предыдущих входов. В общем ККЧС, конечно, присутствуют оба эффекта.
В силу того, что PN (у | х) не определена в общем случае для ККЧС, в основном мы будем иметь дело с PN (у, sn | х, s0) — вероятностью заданных выходной последовательности у = (уъ ..., yN) и окончательного состояния sN в момент N при условии, что заданы входная последовательность х = (л^, ..., xN) и начальное состояние s0 в момент 0. Эта вероятность может быть найдена по индукции из равенства
Pn (у, sjv|x, s0) =
~ 2 P{Un, sn\xn, Sn— i)Pn— i (Jn— u Sw—i|xjv—ь so)> (4.6.1)
SN— 1
ГДе XN- 1 (¦*!> •’ XN— l) И Jn- 1 ~ (y^' ¦¦¦’ У N — l)‘
Можно просуммировать это выражение по окончательному состоянию и получить
^iv(y|x, s0) = 2ftv(y, %|х, s0). (4.6.2)
SN
Пропускную способность ККЧС можно с достаточными основаниями определить несколькими различными способами. Дадим здесь два определения (которые при вычислениях в общем случае приводят к различным числовым значениям) и затем покажем на некоторых примерах смысл каждого из этих определений. Определим нижнюю пропускную способность ККЧС, С, как
С = lim Сдг, (4.6.3)
N—»¦ 00
где
Cn = -7- max min Iq (XN't Yw | s0), (4.6 4)
— N qn So \ v I
7q(X" Yw I s0) —
-110» (X) P„ (y 1 x, s,) log ¦ (4-6-5»
116
Подобно этому верхняя пропускная способность ККЧС С определяется следующим образом:
(4.6.6)
(4.6.7)
С = lim СN,
jV-*oo
где
CN~ — max max/Q(XAf; Yw|s0).
N Qn s0
Следующая теорема, доказательство которой проведено в прило жении 4А, устанавливает существование этих пределов.
Теорема 4.6.1. В канале с конечным числом А состояний
log Л
lim CN = sup
N —>оо N
lime» = inf
cN-
N
CN + ^i N
(4.6.8)
(4.6.9)
Из определений (4.6.4) и (4.6.7) очевидно следует, что
С^< CN для всех 1N. (4.6.10)
Отсюда прямым следствием теоремы является то, что для любого N
log А
с^<с<с<с^+ 1о§д
, -------. (4.6.11)
N ‘ -N N т N • v '
Это соотношение полезно при отыскании С и С, в особенности в случае, когда С = С, так как оно дает верхнюю и нижнюю границы для пределов, которые стремятся друг к другу при возрастании N.
В_ качестве первого примера, который позволит понять смысл С и С, рассмотрим рис. 4.6.3.
Х„ Р(уп\хп Srr-7-О) Уп Хг? Р(уп\ХП Sn-f = 0 Уп
п Q 1 0
и ¦ " ¦ --- / 1 - i
/ 2 - / 2
z---- 3 3- / Л
з---
Рис. 4.6.3. ККЧС; пример канала, пропускная способность которого не определена.
Если начальным состоянием является s0 = 0, то нетрудно заметить (рассматривая канал как пару параллельных каналов, как в за-
117
даче 4.1, с одним каналом для каждого состояния), что средняя взаимная информация максимизируется при выборе статистически независимых входов и при Q (0) = Q (1) = Q (2) + Q (3) = 73 для первого и всех входов в нечетные моменты, и при Q (0) + Q (1) = Q (2) = = Q (3) = г/3 для второго и всех входов в четные моменты. Для этих распределения на входе и начального состояния /q (Xw; Yw | s0) = = N log 3. Точно так же, если s0 = 1, то средняя взаимная информация максимизируется при перемене мест двух указанных одномерных распределений входных букв. Следовательно, Сд> = log 3 при всех N. Можно заметить, однако, что при использовании соответствующего