16. Двусторонние каналы с памятью

Общий дискретный двусторонний канал с памятью определяется совокупностью условных вероятностей

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

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

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

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

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

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

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

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

Чтобы доказать обратное утверждение, предположим, что не принадлежит В. Тогда для некоторого любое с номером лежит вне круга некоторого радиуса, скажем с центром в точке так как иначе было бы предельной точкой множества Предположим, что имеется код длины Тогда вероятности ошибок при его использовании ограничены снизу величиной, большей нуля, так как снова имеется случай, где получается независимость между «буквами».

Область В может быть названа областью пропускной способности для такого канала с возвратным состоянием. Легко показать, что В обладает теми же свойствами выпуклости, как и область пропускной способности для канала без памяти. Конечно, практическое вычисление В для конкретных каналов является даже менее. реальной задачей, чем в случае каналов без памяти.