5.9. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КАНАЛОВ С КОНЕЧНЫМ ЧИСЛОМ СОСТОЯНИЯ

В § 4.6 были описаны каналы с конечным числом состояний с помощью условной вероятностной меры Эта вероятностная мера определяет вероятность любой последовательности на выходе при условии, то задана последовательность на входе и задано начальное состояние Вместе с тем теорема 5.6.1 является теоремой кодирования, которая справедлива для любого распределения вероятности для канала (т. е. теорема 5.6.1 справедлива не только для каналов без памяти). Единственная трудность для прямого применения здесь этого результата состоит в том, что не ясно, как поступить с начальным состоянием. Нашей целью здесь является доказательство теоремы кодирования, которая может быть применена независимо от начального состояния. Главным результатом будет следующее утверждение: для любой скорости кода R и любом существуют коды с достаточно большой длиной блока, такие, что независимо от сообщения и начального состояния где положительна при Как было показано в § нельзя сделать сколь угодно малой (независимо от начального состояния) при

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

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

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

при любом Ясно, что наиболее точная граница в (5.9.1) может быть получена с помощью минимизации по всем распределениям вероятности на входе

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

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

при всех

Для упрощения этого выражения удобно сначала вынестн сумму по из квадратных скобок (5.9.2).

Используя неравенства при (см. задачу находим, что правая часть (5.9.2) будет ограничена сверху следующим выражением:

Умножая и деля сумму по на понимая как распределение вероятностей для и используя неравенство при задачу будем иметь

где сумма была ограничена наибольшим слагаемым, умноженным на

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

Теорема 5.9.1. В произвольном канале с конечным числом состояний при любом положительном целом числе N и любой положительной R существует -код, у которого для всех сообщений всех начальных состояний и всех

где

Доказательство. Подставляя (5.9.7) и (5.9.8) в (5.9.6), видим, что (5.9.6) будет совпадать с (5.9.5), если заменить на большую величину

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

Граница в (5.9.6) имеет экспоненциальный вид и теперь будет установлено, что стремится к постоянной величине при В процессе доказательства этого станет ясно, почему удобно было включить выражение — в определение функции

Лемма 5. 9. 1. В любом заданном канале с конечным числом состояний функция определенная равенством (5.9.7), удовлетворяет неравенству

при всех положительных целых числах таких, что

Доказательство. Разобьем последовательность на входе на подпоследовательности и разобьем на Пусть при заданном будут распределениями вероятностей, на которых достигаются максимумы соответственно; рассмотрим распределение вероятностей для задаваемое равенством

Пусть, наконец, является начальным состоянием, на котором достигается минимум Тогда

и имеем

При переходе от (5.9.11) и (5.9.12) были использованы те же неравенства для суммы по которые были использованы при переходе от (5.9.2) к (5.9.4). Преобразуя суммы [как при переходе от (5.5.7) к получаем

где последнее выражение в фигурных скобках в (5.9.13) было ограничено сверху максимальным значением этого выражения по Используя, наконец, неравенство Минковского (см. задачу при изменении порядка суммирования по будем иметь

где было проведено суммирование по и затем найден максимум по начальному состоянию Преобразуя (5.9.15), получаем (5.9.9), что завершает доказательство.

Лемма 5.9.2. Пусть Тогда

При сходимость является равномерной по равномерно непрерывна.

Доказательство. Применяя теорему 5.6.3 с использованием вместо и вместо будем иметь

При входном алфавите с К буквами имеются последовательностей на входе длины N и поэтому (5.9.17) может быть далее оценена следующим образом:

Отсюда и из (5.9.7) при любых выводим

Из этого, в частности, следует, что при любом функция ограничена выражением, не зависящим от Таким образом, сочетая лемму 5.9.1 и лемму 2 приложения 4 А, получаем (5.9.16). Равномерная сходимость и равномерная непрерывность вытекают из того, что, как показывает (5.9.19), наклон является ограниченным при всех

Теорема 5.9.2. Пусть задан произвольный канал с конечным числом состояний и пусть

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

Более того, при функция является строго положительной строго убывающей с ростом R и выпуклой

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

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

при любых

Доказательство. При любых неравенство (5.9.6) можно переписать в виде

Лемма 5.9.2 утверждает, что при любом можно выбрать так, чтобы при

Подставляя (5.9.24) в (5.9.23), получаем

При на котором достигается максимум граница (5.9.25) сводится к (5.9.21). Предположим теперь, что и покажем, что Положим равным Согласно теореме 4.6.1, N можно выбрать достаточно большим, так, чтобы

Пусть при таком N будет распределением на входе, на котором достигается Тогда согласно теореме 5.6.3 имеем

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

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

Но, так как

при любых то это означает, что

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

Состояние известно на приемном конце

Рассмотрим теперь частный случай полученных выше результатов, в котором состояние в момент является детерминированной функцией выхода в момент и состояния в момент т. е. . В этом случае приемник способен проследить за состоянием канала, если оно было известно когда-либо в прошлом. Пример такого канала представлен на рис. 5.9.1 и в этом примере является функцией только . В каждом состоянии канал является выходы соответствуют входу 0, а выходы 2 и 3 соответствуют входу 1. Выходы 0 и 3 соответствуют состоянию 0, а выходы 1 и 2 соответствуют состоянию 1. Можно увидеть, если не обращать внимания на числа, что эта модель является моделью того самого типа, что и модель, представленная на рис. 4.6.1, за исключением того, что здесь выходной алфавит был расширен для того, чтобы учесть предположение о том, что состояние канала является известным. Эта модель является простой и довольно грубой аппроксимацией канала с замираниями, в котором используется алфавит из двух сигналов на входе и в котором приемник не только строит решения о том, что было на входе, но также измеряет уровень принятого сигнала.

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

Для того чтобы доказать (5.9.32), заметим, что для любого у сумма по не равна нулю лишь в случае, когда и для этого значения имеем Таким образом, (5.9.32) эквивалентно определению в (5.9.8).

Рис. 5.9.1. Простая модель канала с замираниями.

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

В этом случае (5.9.32) приводится к виду

где был изменен порядок взятия произведения и суммирования, так же как и при переходе от (5.5.6) к (5.5.10). Если для заданных определить

то будем иметь

Определим теперь матрицу

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

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

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

Лемма 5.9.3. Пусть К будет наибольшим собственным значением неприводимой матрицы и пусть и будут наибольшей и наименьшей компонентами положительного правого собственного вектора соответствующего Тогда при любом

Доказательство. Согласно (5.9.40) имеем

Так как имеет неотрицательные элементы, то компоненты вектора-строки являются неотрицательными и поэтому можно оценить сверху, оценивая сверху компоненты в рассматриваемом случае величиной Отсюда

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

Подставляя (5.9.41) в (5.9.39) и используя обозначение к для того, чтобы отметить зависимость X от получаем,

где правая часть (5.9.44) не зависит от Таким образом, доказана следующая теорема.

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

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

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

по Используя такие же рассуждения, как в примере 4 § 4.6 с параллельными каналами, можно показать, что минимум достигается на произведении распределений

где при каждом на распределении достигается минимум выражения

Рис. 5.9.2. Двоичный канал с двумя состояниями; состояние известно на приемном конце.

Рис. 5.9.3. Канал, изображенный на рис. 5.9.1, у которого устранена память.

Если то же самое минимизирует при любых то не зависит от и не зависит такж от Следовательно

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

Пример, изображенный на рис. 5.9.1, дает канал из указанного выше класса и для него почти очевидно, что входы нужно использовать независимо и с равными вероятностями в ансамбле кодов. Для этого канала изображена на рис. 5.9.2. Для сравнения на нем также изображена для канала без памяти, представленного на рис. 5.9.3. Этот канал эквивалентен каналу, представленному на рис. 5.9.1, с вероятностями равными 1/2 при любых или, говоря более наглядно, этот канал является каналом

рис. 5.9.1, в котором устранена память. Заметим, что пропускная способность С не изменяется при устранении памяти (см. задачу 5.39), однако показатель экспоненты возрастает. Это может быть качественно объяснено тем, что среднее время, проводимое в каждом состоянии, не изменяется при устранении памяти, а вероятность пребывания в плохом состоянии (состоянии 1) значительно дольше, чем среднее время, существенно уменьшается при устранении памяти. Например, в канале, представленном на рис. 5.9.3, при вероятность пребывания в плохом состоянии в течение всего блока приближенно равна при наличии памяти и равна при отсутствии памяти.

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