4.6. ДИСКРЕТНЫЕ КАНАЛЫ С ПАМЯТЬЮ

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

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

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

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

Рис. 4.6.1. Канал с конечным числом состояний; простая модель канала с замираниями (с пачками ошибок).

Последующие примеры являются частными случаями каналов с конечным числом состояний в которых имеется статистическая независимость между при условии, что заданы Можно представить с помощью графа, а с помощью обычных диаграмм, как это показано на рис. 4.6.1 и 4.6.2. На графах состояния изображены с помощью маленьких кружков. Направленные ребра обозначают переходы из одного состояния в другое; число на каждом ребре указывает вероятность перехода. Если вероятность перехода зависит от то значение соответствующее этой вероятности, дано в круглых скобках. Например, самое верхнее ребро на рис. 4.6.1 представляет переход из состояния 0 в состояние 1. Число, написанное на ребре, является условной вероятностью перехода в состояние 1 при условии того, что задано предыдущее состояние 0 и задана 0 или 1 как текущая входная буква, т. е. Подобно этому самое верхнее ребро на рис. 4.6.2 указывает, что для этого при

Заметим, что канал, изображенный на рис. 4.6.1, имеет тенденцию пребывать в том состоянии, в котором он находится, оставаясь в состоянии 0 для типичной серии из символов и в состоянии 1 для

типичной серии из 100 символов, Этот тип канала дает простую для понимания (но не всецело адекватную) модель для двоичной передачи данных по линиям связи с медленными замираниями. Большинство времени канал находится в состоянии 0, фактически не внося ошибки в передаваемые символы. Случайно канал переходит в состояние 1 (состояние замирания) и в течение примерно 100 символов около 3/10 принятых на выходе канала символов будут ошибочными. Этот канал можно представить себе как ДСК с зависящей от времени вероятностью ошибки, которая попеременно принимает значения и 0,3. Последовательность состояний, которая определяет эту вероятность ошибки, является цепью Маркова.

Рис. простая модель межсимвольной интерференции.

Эта модель не является полностью удовлетворительной моделью двоичной передачи данных по линии связи с замираниями отчасти в связи с тем, что ее, как не удивительно, трудно изучать, а отчасти потому, что каждый реальный канал оказывается требует отличную модель с конечным числом состояний (обычно с более чем двумя состояниями).

Канал, изображенный на рис. 4.6.2, является простой моделью канала с межсимвольной интерференцией. Можно заметить, что значение состояния, принимаемое в какой-либо момент времени, совпадает со входом в этот момент. Таким образом, в этом случае дает вероятность текущего выхода при условии, что заданы текущий и предыдущий входы. Вероятность ошибки (т. е. того, что больше, когда чем, когда Подсчитывая вероятность выхода при заданном текущем входе, находим, где распределение вероятностей для Важно отметить, что зависит от распределения на входе канала и, таким образом, не определяется полностью только каналом. Это вообще характерно для любого канала с конечным числом состояний, в котором последовательность

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

не имеет места, но также вероятности, входящие в зто выражение, не определяются только через понятия, описываюиие канал.

Будем называть каналы, такие, как на рис. 4.6.1, где не зависит от каналами без межсимвольной интерференции, а каналы, такие, как на рис. 4.6.2, где принимает только значения 1 и 0 и зависит от каналами, в которых имеется только память, связанная с межсимвольной интерференцией. В первом случае память возникает лишь из-за шума, а во втором случае — только из-за предыдущих входов. В общем ККЧС, конечно, присутствуют оба эффекта.

В силу того, что не определена в общем случае для ККЧС, в основном мы будем иметь дело с вероятностью заданных выходной последовательности и окончательного состояния в момент N при условии, что заданы входная последовательность и начальное состояние в момент 0. Эта вероятность может быть найдена по индукции из равенства

где

Можно просуммировать это выражение по окончательному состоянию и получить

Пропускную способность ККЧС можно с достаточными основаниями определить несколькими различными способами. Дадим здесь два определения (которые при вычислениях в общем случае приводят к различным числовым значениям) и затем покажем на некоторых примерах смысл каждого из этих определений. Определим нижнюю пропускную способность как

где

Подобно этому верхняя пропускная способность ККЧС С определяется следующим образом:

где

Следующая теорема, доказательство которой проведено в приложении устанавливает существование этих пределов.

Теорема 4.6.1. В канале с конечным числом А состояний

Из определений (4.6.4) и (4.6.7) очевидно следует, что

Отсюда прямым следствием теоремы является то, что для любого N

Это соотношение полезно при отыскании в особенности в случае, когда так как оно дает верхнюю и нижнюю границы для пределов, которые стремятся друг к другу при возрастании

В качестве первого примера, который позволит понять смысл рассмотрим рис. 4.6.3.

Рис. 4.6.3. ККЧС, пример канала, пропускная способность которого не определена.

Если начальным состоянием является то нетрудно заметить (рассматривая канал как пару параллельных каналов, как в

задаче 4.1, с одним каналом для каждого состояния), что средняя взаимная информация максимизируется при выборе статистически независимых входов и при для первого и всех входов в нечетные моменты, и при для второго и всех входов в четные моменты. Для этих распределения на входе и начального состояния Точно так же, если то средняя взаимная информация максимизируется при перемене мест двух указанных одномерных распределений входных букв. Следовательно, при всех

Рис. 4.6.4.

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

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

Для рассмотренного здесь примера нет основания для утверждения, что С или С является действительной пропускной способностью канала. Они просто применимы в близких физических ситуациях: одна к случаю, когда возможно провести некоторое измерение для определения фазы последовательности состояний, и другая — в случае, когда такое измерение невозможно.

На рис. 4.6.4 изображена задача другого типа. Канал остаетсй все время либо в состоянии 0 либо в состоянии 1. Пропускная способность канала, соответствующая состоянию 0, равна 1 бит, а пропускная способность канала, соответствующая состоянию 1, равна бит. При этом бит. С помощью несложных вычислений можно показать, что С да 0,965 бит достигается на независимых входах, используемых с вероятностями . Отсюда видно, С меньше, чем пропускная способность каждого из отдельных каналов, что следует из того, что одно и то же входное распределение должно давать среднюю взаимную информацию на букву, не большую С для каждого состояния.

Рис. 4.6.5. «Панический» канал.

Наконец, на рис. 4.6.5 представлен «панический» канал. Входная буква 2 является панической буквой и ее использование выводит из строя канал во все будущие моменты времени. Очевидно, что бит и бит.

Предыдущие примеры были отчасти вырожденными в том смысле, что влияние начального состояния не уменьшалось с увеличением времени. Далее будет определен класс ККЧС, в котором влияние начального состояния убывает на нет со временем, и будет показано, что для этих каналов До того как приступить к этому, установим два обращения теоремы кодирования для одно, соответствующее С, и другое — С.

Так же как и в § 4.3, рассмотрим дискретный источник с алфавитом объема который производит буквы со скоростью одна буква за каждые секунд. Последовательность источника и после соответствующей обработки должна быть передана по ККЧС и воспроизведена как последовательность для получателя у адресата. Пусть этот канал используется один раз каждые секунд; рассмотрим последовательности источника произвольной длины и последовательности канала с длиной, которая равна наибольшему целому числу, меньшему

Будем считать, что канал находится в некотором начальном состоянии и что устройство обработки данных помещено между источником и каналом и между каналом и адресатом. Вероятности источника, переходные вероятности канала, начальное состояние и устройство обработки определяют теперь совместный ансамбль Этот совместный ансамбль зависит от начального состояния которое в течение некоторого времени мы будем считать детерминированным. Предположим, как и в § 4.3, что последовательность источника связана с последовательностью, которая выдается адресату, с помощью -кратного использования канала, в том смысле, что для всех возможных имеем

В этом случае применима теорема переработки информации, из которой следует

Символ помещен в (4.6.15) просто для напоминания о том, что рассматриваемый совместный ансамбль зависит от данного начального состояния.

Далее пусть является средней вероятностью ошибки на букву источника, как это представлено равенством (4.3.2). Согласно теореме 4.3.2 имеем

Сделаем теперь дальнейшее предположение, состоящее в том, что вероятности источника не зависят от начального состояния канала, и применим теорему 3.5.1 для того, чтобы получить следующий результат:

Используя (4.6.19) и определение N [см. (4.6.12)] совместное (4.6.18), имеем

Теперь можно связать (4.6.20) с верхней и нижней пропускными способностями канала. В соответствии с определением (4.6.7) имеем

Подставляя (4.6.21) в (4.6.20) и переходя к пределу при получаем для всех

Важно отметить, что при выводе (4.6.22) не было сделано предположения о независимости Физически это означает, что (4.6.22) остается справедливым даже, если устройство обработки входных данных знает начальное состояние канала и использует это при отображении последовательности источника в последовательности на входе канала. Точно так же неравенство (4.6.22) остается справедливым вне зависимости от того, использует или нет устройство обработки данных на выходе начальное состояние при отображении последовательностей у в последовательности

Для того чтобы связать (4.6.20) с нижней пропускной способностью канала, нужно сделать дополнительное предположение в том, что не зависит от начального состояния Теперь, используя определение , получаем, что для некоторого начального состояния

Так как согласно теореме то получаем, что для любого N и некоторого

Если имеется распределение вероятностей на начальных состояниях, то можно усреднить и получить общую вероятность ошибки на букву источника

Если является наименьшей из этих вероятностей начальных состояний, то для каждого начального состояния, и для (4.6.24) можно получить следующую границу:

Соотношения (4.6.24) и (4.6.25) не обязательно справедливы в случае, если устройство обработки данных на входе может использовать начальное состояние, однако они остаются в силе независимо от того, использует или нет устройство обработки данных на выходе какие-либо сведения об этом состоянии. Эти результаты можно подытожить следующей теоремой.

Теорема 4.6.2. Пусть дискретный стационарный источник с алфавитом объема производит одну букву каждые сек и имеет предельную энтропию на букву Пусть канал с конечным числом состояний с верхней пропускной способностью С и нижней пропускной

способностью С используется один раз каждые Если в пределе при последовательность источника из букв связана с последовательностью адресата с помощью N -кратного использования канала [т. е. имеют место равенства (4.6.13) и (4.6.14)], то независимо от начального состояния канала вероятность ошибки на букву источника удовлетворяет (4.6.22). Если в дополнение ансамбль на входе канала не зависит от начального состояния, то для каждого значения N существует некоторое начальное состояние, для которого справедливо (4.6.24). Если, кроме того, имеется распределение вероятностей начального состояния с наименьшей вероятностью то справедливо (4.6.25).

Неразложимые каналы

Определим теперь обширный класс каналов, известных как неразложимые ККЧС, для которых Грубо говоря, неразложимым ККЧС называется такой ККЧС, для которого влияние начального состояния исчезает со временем. Точнее, пусть

ККЧС является неразложимым, если для любого сколь угодно малого существует такое что для всех справедливо

При любых

Читателю предлагается проверить, что каналы, представленные на рис. 4.6.3 и 4.6.5, не являются неразложимыми. Можно заметить, что канал на рис. 4.6.2 является неразложимым и, в действительности, левая часть (4.6.26) равна нулю для всех Ниже будет показано, что канал на рис. 4.6.1 также является неразложимым.

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

При будем считать, что равно 2:

Как показывает следующая лемма, зависимость от в смысле этой вероятностной меры не увеличивается с увеличением

Лемма 4.6.1. Для любых заданных входов любых заданных определенное выше расстояние не увеличивается с ростом

Доказательство. При имеем

Ограничивая сверху модуль суммы суммой модулей, получаем

Следующая лемма дает условие, при котором стремится к 0 с ростом

Лемма 4.6.2. Предположим, что при некотором некотором и каждом существует некоторое для которого

Тогда стремится к 0 экспоненциально с ростом N и

Доказательство. Имеем

Введем обозначение:

Замечая, что

представим (4.6.35) в виде

Ограничивай Модуль суммы с помощью суммы модулей и замечая, что будем иметь

После суммирования получаем

По предположению, по крайней мере для одного значения следовательно,

Используя последнее неравенство при затем при затеи при и вспоминая, что получаем

В силу того, что не увеличивается с ростом это доказывает лемму.

Следующая ниже теорема дает критерий того, является ли ККЧС неразложимым или нет.

Теорема 4.6.3. Необходимым и достаточным условием того, что ККЧС будет неразложимым, является существование при некотором фиксированном для каждого х такого состояния что

может зависеть от Более того, если канал является неразложимым, то указанное выше можно всегда выбрать меньшим где А — число состояний канала.

Доказательство. Достаточность. Если (4.6.42) справедливо для некоторого то, так как могут принимать только конечное число значений, существует некоторое такое, что

при всех всех х и некотором зависящем от х.

Также в силу того, что вероятности в канале не зависят от времени, имеем для любых N и некоторого зависящего от

Таким образом, условия предыдущей леммы удовлетворяются и

стремится к нулю экспоненциально при , равномерно по х, . Следовательно, (4.6.26) справедливо для достаточно больших и канал является неразложимым.

Необходимость. Выберем где А — число состояний, выберем N достаточно большим, чтобы удовлетворялось (4.6.26), и для заданного выберем так, чтсбы Тогда согласно для всех и условие теоремы удовлетворяется при равном этому

Доказательство того, что Для заданных определим матрицу связности

Эта матрица размера на из нулей и единиц, в которой индексом строки является а индексом столбца является Данный элемент равен 1, если соответствующее ему может быть достигнуто из ющего ему при заданном х. Так как то можно выразить с помощью в виде

В силу того, что существует лишь ненулевых матриц размера на из двоичных элементов, то последовательность матриц должна содержать две одинаковые матрицы, допустим с Если исходя из последовательности символов выбрать всех то из (4.6.46) следует, что при, всех Если при этом выборе не имеет столбцов из единиц при то она не будет иметь столбцов из единиц при всех больших Но это означает, что при этих х, не существуют для которых при всех таким образом, канал не является неразложимым. Поэтому для того чтобы канал был неразложимым, при любом х матрица должна иметь единичный столбец при некотором Наконец, если имеет единичный столбец при некотором то из (4.6.46) следует, что эта матрица имеет столбец из единиц при всех больших следовательно, для неразложимого канала имеется некоторое наименьшее для которого имеет столбец из единиц для всех

Для канала, изображенного на рис. 4.6.1, условие (4.6.42) удовлетворяется при следовательно, этот канал является неразложимым.

Теорема 4.6.4. Для неразложимого ККЧС

Доказательство. При произвольном N пусть являются распределением на входе и начальным состоянием, которые максимизируют и пусть обозначает начальное состояние, которое минимизирует при том же самом распределении на входе. Таким образом, по определению и имеем

Положим теперь где положительные целые числа. Пусть обозначает ансамбль входных последовательностей обозначает ансамбль последовательностей соответствующих распределению на входе Аналогично пусть обозначают ансамбли выходов при условии, что задано Имеем теперь

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

Отсюда можно заметить, что второе слагаемое в правой части (4.6.50) равно нулю. Также первое слагаемое ограничено сверху числом так как в ансамбле содержится элементов. Наконец, из леммы следует, что последнее слагаемое не больше, чем Таким образом,

Оценивая подобным же образом снизу, используя вместо и ограничивая снизу первое слагаемое в (4.6.50) нулем, получаем

Используя (4.6.51), заметим, что среди условий, при которых рассматривается информация, условие на может быть опущено в (4.6.52) и (4.6.53), будем иметь

Далее можно оценить сверху это выражение, взяв модуль каждого слагаемого в сумме и оценив сверху значение для каждого с помощью В результате получим:

где является верхней границей для справедливой при всех Согласно определению неразложимого канала при любом можно выбрать так, чтобы Для этого фиксированного значения

В силу произвольности и того, что См это завершает доказательство теоремы.

В то время как условие неразложимости ККЧС достаточно для того, чтобы для многих разложимых ККЧС оказывается также Каналы, имеющие память, связанную только с межсимвольной интерференцией, особенно легко исследовать в этом отношении. Предположим, что такой канал является полностью связанным, т. е., что любое состояние может быть достигнуто из любого другого состояния с помощью некоторой конечной последовательности входов. Предположим далее, что имеется некоторая последовательность входов, которая приводит канал в некоторое известное состояние при всех и заданном Тогда существует также конечная входная последовательность, которая приводит канал в какое-либо желаемое состояние и с этого места можно достичь С сколь угодно точно, так что Можно показать (см. задачу 4.26), что если канал вообще может быть переведен в известное состояние, то он может быть переведен в такое состояние с помощью самое большее входов.