Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
lim CN — CN < е log/C. (4.6.56)
N-^oo
В силу произвольности е ;> 0 и того, что Cn ^ Cjv, это завершает доказательство теоремы. |
В то время как условие неразложимости ККЧС достаточно для того, чтобы С = С, для многих разложимых ККЧС оказывается также С — С. Каналы, имеющие память, связанную только с межсимвольной интерференцией, особенно легко исследовать в этом отношении. Предположим, что такой канал является полностью связанным, т. е., что любое состояние может быть достигнуто из любого другого состояния с помощью некоторой конечной последовательности входов. Предположим далее, что имеется некоторая последовательность входов, которая приводит канал в некоторое известное состояние (q(sn |х, s0) = = 1 при всех s0 и заданном х). Тогда существует также конечная входная последовательность, которая приводит канал в какое-либо желаемое состояние и с этого места можно достичь С сколь угодно точно, так что С = С. Можно показать (см. задачу 4.26), что если канал вообще может быть переведен в известное состояние, то он может быть переведен в такое состояние с помощью самое большее 2А входов.
ИТОГИ и выводы
В этой главе была исследована вероятностная модель канала связи. Для моделей дискретного канала без памяти и моделей канала с конечным числом состояний была определена пропускная способность как максимум средней взаимной информации. Основной результат главы составляет обращение теоремы кодирования, которое утверждает, что если скорость источника (т. е. энтропия источника в битах на единицу времени) превосходит пропускную способность канала (в битах на единицу времени), то надежная передача по каналу невозможна. Было сделано некоторое введение в теорию выпуклых функций, которые являются полезным инструментом при изучении всей теории информации, и было показано, как применить эту теорию при отыскании пропускной способности дискретного канала без памяти. Для канала с конечным числом состояний были даны два имеющих смысл определения пропускной способности и показано, что они совпадают друг с. другом для неразложимых каналов.
127
ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ И ССЫЛКИ
Общие идеи этой главы и их развитие принадлежат Шеннону (1948). Обращение теоремы кодирования (теорема 4.3.4) получено Галлагером (1964) и основано на теореме 4.3.1, полученной Фано (1952). Рейффен (1966) отметил, что теорема 4.3.4 может быть применена не только к источникам без памяти, но и к источникам с памятью. Теорема 4.4.1 является, по существу, частным случаем общего результата Куна и Тюкера (1951), относящегося к выпуклому программированию. Его применение к вычислению пропускной способности канала было независимо предложено Эйзенбергом (1963) и Галлагером (1962), однако необходимость условия (4.5.1) в теореме 4.5.1 была доказана Шенноном (1948).
Первая часть теоремы 4.6.1 и вторая часть теоремы 4.6.2 принадлежат Юдкину (1967), хотя Блекуэлл, Брейман и Томасян (1958) установили ранее слабое обращение теоремы кодирования для неразложимых ККЧС. (Неразложимые каналы Блекуэлла, Бреймана и То-масяна образуют тот же класс каналов, что и неразложимые каналы, рассмотренные здесь. Читатель может проверить это, если после прочтения статьи Блекуэлла, Бреймана и Томасяна он заметит, что, если цепь Маркова имеет периодическое множество состояний с периодом т, то т-я степень матрицы соответствует разложимой цепи с по крайней мере т замкнутыми множествами состояний.) Последняя часть теоремы 4.6.3 была доказана Томасяном (1963).
ПРИЛОЖЕНИЕ 4А
Начнем с двух лемм.
Лемма 1. Пусть XYZS является совместным ансамблем и пусть S содержит А точек. Тогда
|/(Х; Y | ZS) — /(X) Y\Z)\ ^ log А. (4А.1)
Доказательство. Представим I(XS\ Y | Z) следующими способами:
1(XS\Y\Z) = 1{X-Y\Z) + I(S; Y\ZX) = (4A.2)
= 1{X; Y | ZS) + /(S; Y | Z). (4A.3)
Последнее слагаемое в (4A.2) и последнее слагаемое в (4А.З) неотрицательны и ограничены сверху величиной H(S) < log А. Поэтому, приравнивая правые части (4А.2) и (4А.З), получаем (4А.1). |
Лемма 2. Пусть а , N = 1,2, ..., ограниченная последовательность
чисел и пусть
а = sup а и а — inf а .
N N - N N
(Под ограниченной последовательностью мы понимаем такую последовательность, для которой а < оо и а > — оо). Пусть при всех п > 1 и всех N >я
п N— п
aN> Y ап + aN—п • (4А.4)
128
Тогда
lim aN~a. (4A.5)
N -*• оо
Обратно, если при всех п > 1 и N > п
то имеем
л 7V— п , . „
