Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
указанного выше распределения на входе, на передающем конце должно быть известным начальное состояние канала, и, таким образом, С в этом примере является максимальной средней взаимной информацией на букву, которую можно достичь, если передатчик имеет возможность выбора распределения на входе, согласованного с начальным состоянием.
Если начальное состояние не известно иа передающем конце, то правильным будет так выбрать входное распределение, чтобы получить большую среднюю взаимную информацию для каждого возможного начального состояния. Нижняя пропускная способность С представляет собой наибольшую среднюю взаимную информацию на букву, которую можно достичь при фиксированном входном распределении, независимо от начального состояния. В этом примере можно показать, что С = CN = 3/2 бит при любом N и что С достигается на статистически независимых и равновероятных входах.
Для рассмотренного здесь примера нет основания для утверждения, что С или С является действительной пропускной способностью канала. Они просто применимы в близких физических ситуациях: одна к случаю, когда возможно провести некоторое измерение для определения фазы последовательности состояний, и другая — в случае, когда такое измерение невозможно.
р (Уп^ п-i 1 Уп
Хп р(уП\хл>Г7-1^1) Уп
Рис. 4.6.4.
U8
На рис. 4.6.4 изображена задача Другого типа. Канал остается йсе время либо в состоянии 0 либо в состоянии 1. Пропускная способность канала, соответствующая состоянию 0, равна 1 бит, а пропускная способность канала, соответствующая состоянию 1, равна log2 3 бит. При этом С = log 3 бит. С помощью несложных вычислений можно показать, что С ж 0,965 бит достигается на независимых входах, используемых с вероятностями Q (0)0,391, Q (1) = Q (2) = Q (3) я» & 0,203. Отсюда видно, С меньше, чем пропускная способность каждого из отдельных каналов, что следует из того, что одно и то же входное распределение должно давать среднюю взаимную информацию на букву, не большую С для каждого состояния.
Рис. 4.6.5. «Панический» канал.
Наконец, на рис. 4.6.5 представлен «панический» канал. Входная буква 2 является панической буквой и ее использование выводит из строя канал во все будущие моменты времени. Очевидно, что С = 1 бит и С = 0 бит.
Предыдущие примеры были отчасти вырожденными в том смысле, что влияние начального состояния не уменьшалось с увеличением времени. Далее будет определен класс ККЧС, в котором влияние начального состояния убывает на нет со временем, и будет показано, что для этих каналов С = С. До того как приступить к этому, установим два обращения теоремы кодирования для ККЧС; одно, соответствующее С, и другое — С.
Так же как и в § 4.3, рассмотрим дискретный источник с алфавитом объема М, который производит буквы со скоростью одна буква за каждые ха секунд. Последовательность источника и после соответствующей обработки должна быть передана по ККЧС и воспроизведена как последовательность v для получателя у адресата. Пусть этот канал используется один раз каждые тс секунд; рассмотрим последовательности источника и — (ии ..., Ul) произвольной длины L и последовательности канала с длиной, которая равна наибольшему целому числу, меньшему Lxjxe:
N = \_LxJxc j.
(4.6.12)
119
Будем считать, что канал находится в некотором начальном состоянии s0 и что устройство обработки данных помещено между источником и каналом и между каналом и адресатом. Вероятности источника, пере^
ходные вероятности канала, начальное состояние и устройство обра^
ботки определяют теперь совместный ансамбль UL, XN, YN, \Lt Этот совместный ансамбль зависит от начального состояния s„, кото* рое в течение некоторого времени мы будем считать детерминированным. Предположим, как и в § 4.3, что последовательность источника связана с последовательностью, которая выдается адресату, с помощью iV-кратного использования канала, в том смысле, что для всех возможных и, х, у, v имеем
Pn (у | х, s0) = PN (у | х, s0, u), (4.6.13)
р (v I У. s0) = P(v|y, s0, x, u). (4.6.14)
В этом случае применима теорема переработки информации, из которой следует
/(UL; VL| s0)</(XN; Y*|s0). (4.6.15)
Символ s0 помещен в (4.6.15) просто для напоминания о том, что рассматриваемый совместный ансамбль зависит от данного начального состояния.
Далее пусть <Pe(s0)> является средней вероятностью ошибки на
букву источника, как это представлено равенством (4.3.2). Согласно
теореме 4.3.2 имеем
<Ре (s0)> \og(M — l) + X «Рв (s0)>) > -|- Я (UL | VLs0) > (4.6.16)
>_L[^(UL|s0)-/(Uz'; VL|s0)]> (4.6.17)
>_L[W(ULls0)-/(XiV; Y"| s0)]. (4.6.18)
Сделаем теперь дальнейшее предположение, состоящее в том, что вероятности источника не зависят от начального состояния канала, и применим теорему 3.5.1 для того, чтобы получить следующий результат:
