2.5. Прямая теорема о кодировании в канале с шумами

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

Пусть Н(В) и H(В) — энтропия на символ источника на входе ка­нала и, соответственно, энтропия на символ принятой на выходе канала последовательности (кодового блока). В силу свойства асимптотической равновероятности типичных множеств постоянных источников мож­но сделать следующее утверждение: группа типичных кодовых блоков длины n содержит около 2^nН(B) последовательностей. Аналогичным образом можно утверждать, что группа типичных принятых на выходе канала кодовых блоков длины n содержит последовательностей.

Допустим, что скорость кодаR отличается от величины энтропии Н(В) на сколь угодно малую конечную величину. ЕслиR< Н(В) < С, то число типичных отправляемых кодовых слов длиной в n символов бу­дет удовлетворять неравенству Проблема поиска опре­деленного кода состоит в определении того, какие именно из возможных последовательностей (кодовых блоков) выбираются в каче­стве2^пН(B) разрешенных для передачи (кодовых слов) и как они разби­ваются на 2^пR непересекающихся подгрупп выходных последо­вательностей. Рассматривается класс всевозможных кодов, которые получаются, если 2^пR разрешенных последовательностей размещать случайным образом среди 2^пН(B) возможных сигналов типичной груп­пы; задача заключается в выборе сильно отличающихся сигналов с по­следующей возможностью их надежного различения (находится сред­нее значение вероятности ошибки для этих кодов).

Далее представим следующие соображения.

1. Будем полагать, что последовательно передаются сигналы выбираемые каждый раз случайно (независимо от всех ранее пере­данных сигналов) с вероятностями , в результате чего в канал отправляется кодовое слово, представляемое в виде Таким образом, будем выбирать все нужные нам 2^nR кодовых слова из числа 2^пН(B) типичных кодовых блоков. Каждое передаваемое кодовое слово на приемном конце будет восприниматься как последовательность (блок) из некоторых n элементарных сигна­лов (в частности,r = т). В силу случайного характера помех, передавая много раз один и тот же блок , мы будем получать на приемном конце много разных блоков . Однако множество этих блоков обладает определенной закономерностью.

1. Рассмотрим теперь всевозможные последовательности вида , состоящие из nпереданных и тех n сигналов в кото­рых переданные преобразовались. В целях упрощения будем полагать r = т. Тогда общее число таких 2n-членных последовательностей, определяется величиной .R ним также можно приме­нить теорему о высоковероятных множествах, из которой вытекает, что если все сигналы выбираются независимо и передаются по кана­лу без памяти, то только из общего числа последовательно­стей будут типичными. Число типичных последовательностей 2n-членных блоков превосходит число n-членных последовательностей в раз. Отсюда можно заключить, что каждой типичной последовательности отвечает группа из типичных последовательностей принимаемых сигналов, в одну из ко­торых последовательность перейдет с большой вероятностью. Эта группа может рассматриваться как решающая область .

2. Два передаваемых кодовых слова и следует считать «сильно отличающимися друг от друга», если решающие области не пересе­каются между собой. Словам и будут соответствовать решающие области и . Очевидно, что если потребуется подобрать 2^пR раз­личных кодовых слов из n сигналов то для того чтобы вероятность ошибки при декодировании принятых сообщений была очень мала, до­статочно иметь возможность выбрать эти кодовые слова так, чтобы все 2^пR решающих областей не пересекались между собой.

3. Так как каждая группа содержит последовательно­стей то в2^пR областей будет входить последовательностей. Поскольку все такие после­довательности входят в типичные 2n-членные последовательности ,то и сами они естественно будут типичными. С другой стороны, общее число типичных n-последовательностей на выходе канала, связанных с энтропией кодовых символов , определяется величиной

4. Составим теперь отношение общего числа типичных по­следовательностей к суммарному числу таких после­довательностей, входящих в 2^nR областей :

(2.7)

Отсюда следует, что если бы Rбыло больше, чем С, то это отношение было бы меньше в единицы, т.е. полное число последовательностей в наших 2^пRобластях , было бы больше, чем общее число всех типичных последовательностей ; поэтому ясно, что при R>C кодовые слова никак нельзя подобрать, так, чтобы отвечающие им области не пересекались. Но если R<C то отношение(26) оказывается большим единицы; более того, при очень большом n,yне зависящим от R, оно оказывается равным 2, возведенному в очень большую степень, т.е. очень большим. В этом и состоит существо обосования справедливости утверждения, сформулированного в теореме.

Выражение (2.7) можно представить с ином виде; если с учетом того, что при величину R можно записать в следующей форме: , тогда

(2.7a)

Отсюда также следует, что поскольку μ выбрано не зависящим от n, то при отношение общего числа типичных последователь­ностей к суммарному числу таких последовательно­стей, входящих в 2^nR областей также стремится к бесконечности.

Таким образом, при большом п полное число последовательно­стей в 2^пR областях ; будет составлять ничтожную часть всего числа типичных последовательностей из nсигналов ; это обстоятельство делает очень правдоподобным предположение о том, что2^пR кодовых слов длины n можно выбрать так, чтобы решающие области кода не пересекались между собой. Эти соображения делают теорему Шен­нона весьма правдоподобной, хотя их и нельзя рассматривать как её строгое доказательство.

На этом же уровне строгости можно представить более формали­зованное доказательство прямой теоремы Шеннона.

Пусть принят некоторый сигнал . Вероятность ошибочного де­кодирования при этом равна вероятности того, что данный сигнал не может происходить более чем от одного из 2^nR разрешенных сиг­налов. Поскольку код получается случайным (равновероятным) выбо­ром 2^nR последовательностей из 2^пН(B) то вероятность того, что за­данный сигнал на входе канала попадет в число разрешенных, равна .

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

(2.8)

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

Используем далее то же представление дляR, что и выше [см. (V.7a)]

. (2.9)

Подставляя (26) в (27), получим

Нетрудно показать, что lim р = 1.

Действительно,

(2.9а)

Применяя правило Лопиталя, получаем

, (2.10)

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

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

Из доказательства теоремы становится понятно, что пропускная способность оказывается не просто максимально возможной скоро­стью передачи, но и максимальной скоростью (как определил Шеннон), при которой еще возможна передача со сколь угодно малой вероят­ностью ошибки.