15. Общий метод нахождения области пропускной способности двустороннего канала

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

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

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

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

Выходными буквами для на конце 1 являются пары и на конце 2 пары т. е. пары полученных букв на обоих концах. Переходные вероятности для есть вероятности того, что появятся данные выходные пары при условии, что при вводе в канал К фиксированной пары букв были использованы данные стратегии. Таким образом,

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

из алфавита с

буквами. Выходными буквами на конце 1 являются -мерные векторы

принимающие поэтому значения из алфавита с обобщенными буквами. Переходные вероятности для канала выражаются через

переходные вероятности для канала К с помощью соотношения, обобщающего соотношение (39)

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

Теорема 5. Пусть есть нижняя граница для области пропускной способности производного канала растянутая в раз. Тогда при области стремятся к предельной области В, которая содержит каждую из них и является областью пропускной способности для канала К.

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

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

Докажем теперь, что при росте области стремятся к предельной области В, которая содержит все частные Под

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

Отсюда следует, что множества стремятся к пределу В, являющемуся объединением всех и их предельных точек. Множество В содержит также и при любом Ведь если, например, — общее кратное, например, то В содержит , в то время как содержит

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

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