Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
89
группироваться вместе под влиянием замираний, вместо того чтобы быть статистически независимыми друг от друга. Таким образом, канал обладает памятью в том смысле, что он помнит, когда он находится в плохом состоянии и имеет тенденцию оставаться в плохом состоянии в течение определенного интервала времени.
4.2. ДИСКРЕТНЫЕ КАНАЛЫ БЕЗ ПАМЯТИ
Рассмотрим дискретный канал без памяти (ДКБП), входной алфавит которого X состоит из К целых чисел 0, 1, ..., К — 1 и выходной алфавит которого Y состоит из J целых чисел 0, 1, ..., J — 1. Использование целых чисел в качестве входных и выходных букв
упрощает обозначения в некоторых последующих рассмотрениях, а также вновь подчеркивает то обстоятельство, что обозначения, принятые для входных и выходных букв, ни на что не влияют.
Канал описывается переходными вероятностями P(j\k), заданными для
О <;/¦</—1 и 0 <&<;/(—1. По определению, Р (j | k) является условной вероятностью приема целого числа / при условии, что задан вход канала — целое число k.
Обозначим последовательность N букв на входе канала через х = = (*1, ..., хп, ..., xN), где xn, l<rc<;yV, принимают значения из входного алфавита, т. е. значения от 0 до К — 1. Аналогично, соответствующие последовательности выходных букв обозначим через У — {Уъ Уд'). гДе Уп принимают значения из выходного алфавита, т. е. значения от 0 до / — 1. Вероятность уп при условии, что задано хп, задается описанной выше переходной вероятностью Р (уп\хп).
В силу того, что канал является каналом без памяти, каждая выходная буква в последовательности зависит только от соответствующей входной буквы и условная вероятность выходной последовательности у = (уъ ..., уд/) при условии, что задана входная последовательность х = (л'ь ..., xN), определяется равенством
Pn(УIх) = П Р(уп\хп). (4.2.1)
П= 1
Более формально это можно выразить следующим образом: канал является каналом без памяти, если существуют такие переходные вероятности Р (/ | k), что (4.2.1) справедливо для всех N, всех у =
= (уъ yN) и всех х = {хъ ..., xN).
Для примера использования указанных выше обозначений
рассмотрим двоичный симметричный канал, изображенный на
рис. 4.2.1. Переходные вероятности для рис. 4.2.1 задаются следующим образом: Р (0|0) = 0,9, Р (110) = 0,1, Р (01 1) = 0,1, Р (1 |1) = 0,9. 90
Рис. 4.2.1. Переходные вероятности в двоичном симметричном канале. (Здесь и на некоторых последующих рисунках в десятичных дробях, целая часть которых равна нулю, нуль опускается.)
Для последовательностей длины 2 равенство (4.2.1) дает: Р„(00|00) — = (0,9) • (0,9) = 0,81, Р2 (10 | 00) = (ОД) • (0,9) = 0,09‘ и т. д.
Вероятность Р2 (00|00) обозначает вероятность приема двух нулей
при условии, что были переданы два нуля.
Отметим, что при описании канала ничего не было сказано о методе использования символов на входе канала. Если задать вероятностную меру на входных целых числах, обозначая через Q (k) вероятность использования числа k, то средняя взаимная информация между входом и выходом равна
I (X- Y) ,= Y s' Q (k) Р (/ ] к) log -.р(11к)-. (4.2.2)
А* 0 / — 0 Д'~ 1 — - -
2 QV)PU 10
/ = о
Вероятность приема числа / была выписана в виде 2 Q (0 Р(И0<
I
чтобы подчеркнуть, что она является функцией как распределения на входе, так и переходных вероятностей канала.
Так как относительные частоты букв на входе канала могут быть соответствующим образом выбраны с помощью кодера, то не должно быть удивительным то, что максимум / (X; Y) по входным вероятностям является величиной, которая имеет теоретико-информационный смысл. Пропускной способностью С дискретного канала без памяти (.ДКБП) называется наибольшая средняя взаимная информация 1 (Х\ Y), которая может быть передана по каналу при его однократном использовании, максимизированная по всем распределениям на входе:
С = max %Q(k)P (j | k) log • (4-2.3)
Q (o)..Q(K~i)k,i
Отметим, что в то время как / (X; Y) является функцией как канала, так и распределения на входе, С является функцией только канала. Вычисление С включает в себя максимизацию по К переменным с двумя ограничениями: одно в виде неравенства Q (k) ^ 0 и другое в виде равенства 2 Q (k) = 1. Максимальное значение существует в силу того, что функция является непрерывной и максимизация производится в замкнутой ограниченной области векторного пространства*’.
В §4.4 и 4.5 мы вернемся к задаче численного отыскания пропускной способности.
Основополагающее значение пропускной способности для ДКБП обосновывается теоремой кодирования, которая утверждает, что данные могут быть надежно переданы по каналу с любой скоростью,
