Пропускная способность канала с конечным числом состояний, состояние которого вычислимо на обоих концах

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

Чтобы удовлетворить первому требованию, необходимо, очевидно, чтобы для любого (достижимого) внутреннего состояния следующее состояние было функцией где — переданная буква.

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

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

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

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

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

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

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

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

Тогда — это эквивалентное число букв для данного канала К, так что его пропускная способность определяется равенством

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

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

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

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

В частности, для сравнимого с нулем по модулю (т. е. делящегося на диагональные элементы асимптотически ведут себя как постоянная, умноженная на . В то же время в противном случае эти утверждения являются хорошо известными результатами теории матриц с неотрицательными элементами. Они были впервые получены еще Фробениусом [4] и здесь доказываться не будут.

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

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

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

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

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

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

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