Математические основы каналов с памятью. 
Теорема кодирования

Перейдем теперь к определению класса каналов, обладающих памятью. Обозначим через (X, х) конечное абстрактное множество. Пусть X^I означает множество всех бесконечных в обе стороны последовательностей (…, x_-1, х₀, х₁,.. .), где х_i X, i = 0, ±1, ±2,…; т. е, X^I = X_i, где X_i =X. Если n — положительное целое число, а₀, …, a_n-1 — элементы X, t — заданное целое число, то множество всех последовательностей из X^I, удовлетворяющих соотношению x_t+k = a_k, k = 0,…, n — 1, мы назовем цилиндрическим множеством; цилиндрическое множество определяется заданием n, t и а₀, …, a_n-1. Борелевское поле элементов X^I, порожденное всеми цилиндрическими множествами, обозначим через _X.

Обозначим через Т преобразование переноса, определяемое на X^I соотношением.

T (…, x_-1, x₀, x₁ ,…) = (…, x'_-1, x'₀, x'₁ ,…)(1.4).

где x'_i= x_i+1. Тогда существует Т^-1 и справедливы следующие утверждения:

• 1. T X^I = X^I и Т^-1 X^I = X^I
• 2. Как Т, так и Т^-1 переводят цилиндрические множества в цилиндрические же множества.
• 3. Как Т, так и Т^-1 переводят измеримые множества в измеримые; ни одно из них не переводит неизмеримые множества в измеримые.

Утверждения 1 и 2 очевидны, а первая часть утверждения 3 просто следует из рассуждений о борелевских полях, полученных путем отображения. Что касается второй части утверждения 3, то в случае, когда Т^-1S измеримо, Т (Т¹S)=S также будет измеримым.

Пусть µ - вероятностная мера на _X. Говорят, что мера µ стационарна, если µ (TS) = µ (S) для каждого S _X. Если, кроме того, µ (S) = 0 или µ (S) =1 для инвариантных S, т. е. для S, удовлетворяющих условию TS = S, то µ называется эргодической мерой. В дальнейшем µ будет всегда считаться стационарной. Однако поскольку некоторые из наших результатов справедливы для вероятностных мер, являющихся стационарными, но не обязательно эргодическими, мы не будем предполагать эргодичности меры, если она особо не оговорена.

Определим теперь источник информации, образованный пространством X^I, борелевским полем _X и вероятностной мерой µ. Нашим первым результатом будет определение скорости создания сообщений источником информации.

Предположим, что X^I содержит N элементов. Тогда для заданных t и n можно определить в точности Nⁿ цилиндрических множеств. Вместе с вероятностной мерой µ это семейство цилиндрических множеств определяет конечное пространство элементарных событий Х^{n, t}. Поскольку µ стационарна, количество информации, содержащейся в Х^{n, t}, не зависит от t. Обозначим это количество информации через Н (n). Величину Н (Х)= назовем скоростью создания, сообщений (на одну букву) источника X^I, _X, µ.

Чтобы показать, что действительно существует, заметим, что по лемме Н (m+n) Н (m) + H (n) для любых m и n. Пусть a = inf, тогда для любого е > 0 существует такое целое q, что a + е. Для любого целого n? q мы определим целое k_n соотношением (k_n —1) qnnq. Тогда H (n) H (k_nq) k_nH (q) и, следовательно,. Далее, при n имеем k_n, а значит,. Отсюда следует, что lim sup для всех е > 0, что и означает lim sup а. Поскольку, с другой стороны, то = a = H (X).

Если µ — произведение мер, тогда, очевидно, Н (n) = nН (1); следовательно, Н (Х) = Н (1), что вполне согласуется с нашим предыдущим пониманием символа H (X).

Для определения дискретного канала с памятью введем конечное множество принимаемых сигналов Y. Как и выше, определим Y' и _Y. Наконец, для любого х_? X^I обозначим через н (|х_?) вероятностную меру на _Y, обладающую следующими свойствами:

• 1. Для любого цилиндрического множества S Y^I функция н (S |х_?) измерима на X^I.
• 2. н (|х_?) стационарна, т. е. для любого S _Y,

н (TS |Tх_?) = н (S |х_?),(1.5).

где Т — преобразование переноса на X^I и Y^I одновременно.

3. н (|х) есть мера без предвосхищения, т. е. она обладает следующим свойством: если S Y таково, что из того, что (…, y-1, н0, y1, …) S для некоторого фиксированного t, следует (…, y-1, н0, y1, …) S при y’к, для которых y’i=yi, it, то н (S |х) = н (S |х') при любых х и х, для которых х’i=хi, it.

Условие 1 является техническим, и важность его очевидна. Условие стационарности 2 не нуждается в пояснениях; следует, однако, подчеркнуть, что в, общем случае мера н (|х_?) не стационарна при фиксированном х_?. Условие 3 указывает на то, что для нумерации компонент х_? существенна их зависимость от времени.

Множество объектов X, X^I, _x, Y, Y^I, _Y и мера н (|х_?) определяют канал с памятью. Поскольку X^I, _x, Y^I, и _Y однозначно определяются по X и Y, мы будем обозначать канал просто X, Y и н (|х_?).

Пусть X^IY^I обозначает, как обычно, множество всех пар (х_?, y_?), и пусть _{x, y} — определенное борелевское поле на X^IY^I.

Заданная вероятностная мера µ на _x, позволяет естественным образом определить вероятностную меру на _{x, y}. Действительно, пусть S [х_?], обозначает сечение множества S _{x, y} вдоль х_?. Тогда при любом х_? имеем S [х_?] _y и н (S [х_?] |х_?) — измеримая функция х_?. Отсюда просто получаем, что.

щ (S) = (1.6).

определяет вероятностную меру на _{x, y} кСтационарность щ () непосредственно вытекает из стационарности н (|х_?) и µ. Далее, мы можем определить стационарную меру на _Y, полагая з (S) = щ ([X^IS]) для любого S _y; заметим, что µ = щ ([]).

Пусть, как и выше, означает семейство цилиндрических множеств на X^I с заданными n, t; определяем аналогично. Для краткости мы будем писать и вместо и соответственно. Тогда щ можно рассматривать как вероятностную меру на XⁿYⁿ; µ = щ ([]) — как вероятностную меру на Xⁿ и з = щ ([Xⁿ]) —как вероятностную меру на Yⁿ. Таким образом, Н (), H () и Н () полностью определены, поскольку из существования Н (Х)= следует, что Н (Y)= и Н (Х, Y)=также существуют.

По лемме Н () H () + H (), а отсюда R=H (X)+H (Y)—Н (Х, Y) 0. Назовем R скоростью передачи информации (на одну букву) канала X, Y, н (|х_?) относительно р. в. на входе i (). Наименьшую верхнюю границу R по всем р. в. на входе µ мы называем стационарной пропускной способностью С_s канала X, Y, н (|х_?) (на одну букву). Наименьшую верхнюю границу R по всем эргодическим входам, для которых щ также эргодична, будем называть эргодической пропускной способностью С_е канала X, Y, н (|х_?). Назовем эргодическую меру на входе µ допустимой, если соответствующая мера щ также эргодична.

Уже сейчас очевидно, что каналы с памятью требуют более тонких исследований, чем для каналов без памяти. В частности, уже определены две пропускные способности C_s и С_е. Но мы еще не можем утверждать, что C_s или С_е достигается на некотором р. в. на входе или на некотором допустимом р. в. на входе соответственно. Мы можем пока только утверждать, что справедливо очевидное соотношение C_s С_е. Как мы сейчас увидим, именно с помощью понятия эргодической пропускной способности формулируются известные нам результаты для дискретных каналов с памятью. Основную лемму мы можем обобщить на случай дискретных каналов с памятью только при предположении об эргодичности мер µ и щ. Прежде чем переходить к установлению этого результата, отметим известный факт: стационарное произведение мер в бесконечномерном произведении пространств — таких, как X^I, Y^I, и X^IY^I, эргодично.

Таким образом, если в качестве р. в. на входе расширений каналов без памяти используется произведение мер, то вопрос об эргодичности решается сам собой.

Лемма может быть обобщена следующим образом.

Пусть µ эргодична. Тогда для любых е, д > 0 существует такое целое положительное n (е, д), что если Sⁿ — семейство цилиндрических множеств u из Xⁿ, для которых неравенство.

| | е (1.7).

не выполняется, то (Sⁿ) д при nn (е, д) Как показано, X^IY^I можно считать эквивалентным (XY)^I. Таким образом, этот результат можно применять к XⁿYⁿ и Н (Х, Y) всегда, когда щ эргодична, и к Yⁿ и H (Y) в случае, когда з эргодична.

Отметим, что из эргодичности щ следует, что меры =щ ([]) и з=([X^I]) эргодичны. Действительно, если S _X, то S _{X, Y}; если TS = S, то Т (S) = S.

Значит, если щ эргодична, то щ (S= 1 или щ (S=0, т. е. (S)=l или (S)= 0, а это означает, что мера эргодична. Аналогично доказывается эргодичность меры з. Следовательно, допустимая мера является эргодической.

Пусть X, Y, н (|х_?) — заданный дискретный канал с памятью, имеющий эргодическую пропускную способность С_е > 0. Для любого Н < С_е мы, следовательно, можем найти допустимое р. в. на входе, такое, что H (X)+H (Y) — Н (Х, Y) > Н. Будем обозначать элементы Хⁿ и Yⁿ буквами u и х соответственно. Зададимся произвольными е, д₁ > 0 и обозначим через Z'_n множество тех (u, х), для которых | |, а через S'_n — множество тех, для которых | |. Из САР следует, что для достаточно больших n имеем щ (Z'_n) > 1- и щ (X_n S'_n)= > 1- .(1.8).

Тогда, полагая Z_n = Z'_n, получаем щ (Z'_n) > 1- Положим = (что уже определено для всех S'_n); тогда для любых ()Z_n имеем.

| | (1.9).

Оставшиеся действия тривиальны. В отличие от случая канала без памяти, где задается заранее, здесь мы должны определить в соответствии с формулой= имеющей смысл всюду, исключая подмножество Xⁿ -меры нуль, что не вызывает затруднений. Теперь мы можем сформулировать, следующий результат.

Теорема. Пусть X, Y, н (|х_?) — дискретный канал с памятью, обладающий эргодической пропускной способностью С_е > 0. Тогда для любых Н и е, удовлетворяющих неравенствам 0 < С_е, е > 0, существует такое целое положительное n (е, Н), что для любого n > n (е, Н) найдутся в Xⁿ элементы u₁,…, u_N, N 2^nH, а в Yⁿ — непересекающиеся множества А₁,…, А_N, такие, что р (A_i | u_i) 1 — е, i = 1, …, N.

Как подразумевается в формулировке теоремы, элементы u_i таковы, что р (|u_i) определено, т. е. (u_i) > 0, где р. в. на входе канала, которое используется для доказательства теоремы. Отметим, что в случае отсутствия памяти утверждение теоремы кодирования не содержало ссылок на р. в. на входе, используемое в доказательстве теоремы. Это расхождение объясняется тем, что интерпретация соотношения р (A_i | u_i) 1 — е здесь совершенно отлична от интерпретации. Нельзя интерпретировать это неравенство как утверждение, что «вероятность получения последовательности у₀, … у_n-1, такой, что [у₀, … у_n-1]A_i, когда последовательность xⁱ₀, … xⁱ_n-1, определяющая u_i, передана, будет не меньше 1 — е^u. Действительно, слова «u передано» описывают не элементарное событие, каким является передача фиксированного x_?, а скорее класс (т. е. цилиндрическое множество) событий u_i.

Вероятностная мера р (| u_i), определенная на _Y, является вероятностным распределением на при условии, что передаются только последовательности x_?u_i; условные вероятности передачи задаются вероятностной мерой = определенной на борелевском поле всех измеримых подмножеств цилиндрического множества u_i. Для того чтобы иметь возможность интерпретировать неравенство р (A_i | u_i) 1—е так же, как и в случае отсутствия памяти, нам нужны условия независимости в каком-то смысле. Следующие условия, наложенные на н (|х_?), оказываются достаточными.

П. 1. Существует фиксированное положительное m, такое, что для любого цилиндрического множества [у_t, … у_t+n-1 ] из Y^I справедливо соотношение н ([у_t, … у_t+n-1 ] |х_?) = н ([у_t, … у_t+n-1 ] |х'_?) при любых x'_i = x _i, i = t — m, …, t+n—1.

П. 2 Для любых двух цилиндрических множеств [у_i, … у_j ] и [у'_k, … у'_n ], таких, что j+m_t, … у_t+n-1 ] |х_?) = н ([у_t, … у_t+n-1 ] |х'_?) = н ([у_i, … у_j ] [у'_k, … у'_n ] |х_?), (1.10).

для всех х_?.

Наименьшее m, для которого данный канал удовлетворяет этим двум условиям, называется памятью канала. Если такого m не существует, мы будем говорить, что канал обладает бесконечной памятью. Заметим, что при таком определении канал с нулевой памятью вполне характеризуется заданием значений н ([у₀] |х_?) для всех возможных у₀ и всех возможных последовательностей х_?, отличающихся компонентой х₀. Таким образом, канал с нулевой памятью суть просто канал без памяти.

Заметим также, что П. 1 вместе с общим требованием отсутствия предвосхищения н (|х_?) гарантирует измеримость функции н (S |х_?) по х_? для всех цилиндрических множеств S.

Для канала, обладающего конечной памятью m, условия р (A_i | u_i) 1 — е, i = 1,.. ., N, легко сводятся к условиям для н (|х_?). Пусть u_i = [xⁱ₁, … xⁱ_n], a z обозначает произвольную последовательность x_-m+1, … x₀; обозначим цилиндр [ x_-m+1, … x₀, xⁱ₁, … xⁱ_n ] через [z, u_i ]. Тогда.

р (A_i | u_i) = = ([z, u_i]) н (A_i |[z, u_i]) 1 — e (1.11).

Поскольку ([z, u_i]) = = 1, отсюда следует, что по крайней мере для одного z, например для z_i, должно иметь место неравенство н (A_i|[z_i, u_i])1—е. Интерпретация этого неравенства получается сразу же. В комбинации с П. 2 оно позволяет нам «передавать» последовательность (z_i, u_i) в любом желаемом порядке и при этом принимать каждую последовательность правильно в соответствии с законом больших чисел по крайней мере в 1—е случаях из всех случаев, когда она передавалась, если число случаев стремится к бесконечности.

Невыясненным остается только один пункт. По-прежнему имеется N2^nH последовательностей, но длины их теперь равны n+m. Однако, поскольку m фиксировано, а n выбирается произвольно большим, выход из этого положения очевиден. Мы доказываем теорему для некоторого Н', удовлетворяющего неравенству Н < Н' С, и выбираем n настолько большим, чтобы Н' H. Количество последовательностей тогда определится числом N 2^nH' 2^(n+m)H