Примеры каналов, обладающих памятью

В этом разделе мы рассмотрим несколько простых примеров каналов, обладающих памятью, а также установим важный результат, следствием которого окажется тот факт, что в случае канала, имеющего конечную память, любое эргодическое р. в. на входе оказывается допустимым. Будут рассмотрены также несколько оставшихся открытыми вопросов, подсказанных частным случаем канала без памяти.

При рассмотрении каналов без памяти уже из самого их определения было ясно, как приступить к построению примера канала с ненулевой пропускной способностью. Наш главный результат относительно пропускной способности расширений заданного канала без памяти по существу означает, что пропускная способность таких каналов являлась бы неизменной и, кроме того, C_s = C_e. Существование максимизирующего р. в. на входе было очевидным. Из этих результатов также следовало, что теорема кодирования не выполняется, если Н > С. Естественно спросить, в какой мере эти результаты можно распространить, на дискретные каналы с памятью.

Сохранить равенство C_s = C_e без ограничения нельзя; немного погодя мы приведем пример, где C_s положительно, а C_e не определено, так как не существует никакой допустимой входной меры. Этот канал по необходимости имеет бесконечную память; для канала с конечной памятью предположение C_s = C_e не кажется неразумным.

По вопросу о том, достигаются ли в действительности C_s = C_e для каналов с конечной памятью, так же как по вопросу об отрицательном утверждении теоремы о кодировании при Н > С, трудно строить предположения, не имея нескольких хорошо изученных примеров таких каналов.

Наконец, все еще не очень понятен случай полунепрерывных каналов с памятью, определяемых, так же как и каналы без памяти, с помощью замены Y произвольным пространством Щ, на котором определено борелевское поле. Некоторые интересные результаты были получены Мак-Милланом, однако мы не станем углубляться в них.

Обратимся теперь к построению разных примеров дискретных каналов, обладающих памятью. Наш первый пример будет относиться к тому случаю, когда C_s > 0, а C_e не определено. Пусть X, Y₁, p₁ (|х) и X, Y₂, p₂ (|х) — два дискретных канала без памяти с ненулевыми пропускными способностями C₁ и С₂ соответственно, обладающие одним и тем же множеством передаваемых символов. Пусть Y = Y₁ Y₂. Тогда p₁ (| х) и p₂ (| х) могут рассматриваться как распределения вероятностей на Y. Для каждого х_? Х^I мы определяем вероятностную меру н (| х_?) на Y^I, полагая н (| х_?) = [???p₁ (| х_-1)? p₁ (| х₀)? p₁ (| х₁) … + (1.12).

+ ???p₂ (| х_-1) ?p₂ (| х₀) ?p₂ (| х₁) …],.

где х_? = (…, х_-1, х₀, х₁, …).

Легко убедиться в том, что X, Y, н (| х_?) определяют канал с памятью. Ясно далее, что для любого входа µ() з (Y^I₁) = з (Y^I₂) =, а Y^I₁ и Y^I₂ измеримые и инвариантные множества на Y^I. Следовательно, з не является эргодической, а значит, и щ не может быть эргодической. С другой стороны, пусть С — пропускная способность канала без памяти X, Y, [p₁ (| х) + p₂ (|х)], и пусть p р. в. на входе, при котором достигается С. Очевидно, что Сmax (C₁, С₂)>0, и легко видеть, что в X, Y, н (| х_?) достигается эргодическая пропускная способность C_s = C для р. в., на входе имеющего вид произведения µ=???p ()?p ()… Отметим, между прочим, что этот канал удовлетворяет условию для m = 0. Простейшим случаем, для которого мы можем подсчитать скорость создания сообщений источника информации X^I, µ (), является случай, в котором р, () определяется простой Марковской цепью. Простая (стационарная) Марковская цепь определяется заданием вероятностей «состояний» Р₁ ,.. ., P_N, удовлетворяющих условиям.

= 1, и вероятностей «перехода» p_ij, i, j = 1,.. ., N, удовлетворяющих условиям, i=1, …N и, j=1, …, N.

Если X содержит N элементов x₁, …, x_N, опpeделим вероятностную меру µ () на X^I, полагая.

µ ([х_i]) = P_i; µ ([х_{i ,}х_j]) = P_i p _ij; µ ([х_{i ,} х_j, х_k])= P_i p_ij p_jk и т. д.

Поскольку, очевидно,.

µ ([х₀] | [x_-1,…, x_-n]) = µ ([х₀] | [x_-1] ,.

получаем сразу же.

H (K) = ([x_-1, х₀])| [x_-1]= _i p _ij (1.13).

Канал простого типа, обладающий конечной памятью, можно построить следующим образом. Выбрав два конечных абстрактных пространства X и Y, определим для каждой пары (х_{1 ,} х₂) X? Х на Y распределение вероятностей н₁ (| х₁, х₂). Определим для любого х_? X^I на Y^I вероятностную меру, полагая н₁ (| х_?) = ??? н₁ (| х₀, х_-1)? н₁ (| х₁, х₀)? …, где x= (…, х_-1, х₀, х₁,…).

Легко убедиться, что X, У, н (| х_?) действительно определяет канал, обладающий памятью m = 1. Если в качестве р. в. на входе этого канала взять µ (), определенную простой Марковской цепью, то легко увидеть, что тогда и () и () определяются простой Марковской цепью; таким образом, мы можем получить простое выражение для скорости передачи сообщений в канале относительно µ ().

Для того чтобы µ() была эргодической, достаточно, чтобы для определяющей ее Марковской цепи выполнялось условие p _ij >0 для всех i, j. Любое эргодическое р. в. на входе допустимо для канала, обладающего конечной памятью. Следовательно, нетрудно выбрать распределение н₁(|х₁, х₂) так, чтобы не обращалась в нуль скорость передачи информации канала относительно р. в. на входе приведенного выше типа. Мы, таким образом, имеем простой пример канала с памятью, для которого С_е > 0. Только что определенный канал имеет память m=1, однако удовлетворяет условию для m = 0. Нетрудно также построить каналы с конечной памятью, но удовлетворяющие условию для m = 0. Здесь мы приведем только основную идею построения. Исходим из того, что, грубо говоря, в сущности означает требование, чтобы «шумовые выборки», разделенные интервалом, большим m, были независимы, в то время как выборки, разделенные интервалом, не превосходящим m, были бы статистически зависимы. Шумовые выборки вообще описываются вероятностными процессами, т. е. последовательностью (вообще говоря, бесконечной) случайных величин. Нам нужен теперь стационарный процесс n_i, —? < i < ?, такой, что любые две группы величин n_i зависимы при любых индексах i одной группы и j другой группы, исключая случай, когда выполнено условие |i — j| > m. Примеры таких процессов легко построить; если r_i, —? < i < ?, — последовательность независимых одинаково распределенных случайных величин, то n_i= представляет процесс, удовлетворяющий; нужным требованиям.

Подобным же образом легко можно построить примеры, в которых удовлетворяются для данного m одновременно, но для m—1 какое-либо из этих условий не удовлетворяется.