5.6. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КОДА С ЧИСЛОМ СЛОВ, БОЛЬШИМ ДВУХ

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

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

Лемма. Пусть являются вероятностями событий является вероятностью их объединения. При любом имеем

Доказательство леммы. Имеем

Неравенство (5.6.3) является обычной границей для вероятностей (см. задачу 2.16), а (5.6.4) является очевидной границей для вероятности. Если меньше чем 1, то увеличивается при возведении ее в степень и (5.6.2) следует из (5.6.3). Обратно, если то так что (5.6.2) следует из (5.6.4).

Доказательство теоремы. Имеем

где условная вероятность ошибочного декодирования при условии, во-первых, что на кодер поступило сообщение во-вторых, что заданная последовательность была выбрана в качестве кодового слова, и, в-третьих, что была принята последовательность у. Суммирование производится соответственно по всем входным и всем выходным последовательностям канала длины

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

Теперь имеем

Неравенство (а не равенство) в (5.6.6) возникает потому, что декодер по максимуму правдоподобия не обязательно делает ошибку, если при некотором Согласно определению имеем

Так как является глухим переменным суммирования в (5.6.8), то индекс можно опустить и граница становится не зависящей от В силу того, что существуют различных то, подставляя (5.6.8) в (5.6.7), получаем

Подставляя (5.6.9) в (5.6.5), будем иметь

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

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

что отдельные технические детали доказательства являются очень простыми и не связаны с какими-либо предыдущими результатами. Однако доказательство этой теоремы в значительной степени связано с результатом, относящимся к двум кодовым словам. Единственным новым фактом, использованным в доказательстве, является лемма. Аддитивная граница (5.6.3) довольно точна для независимых событий, если получающаяся в результате граница мала по сравнению с 1, но является, очевидно, очень плохой, когда получающаяся в результате граница велика по сравнению с 1. Лемма дает способ уточнения аддитивной границы в последних случаях за счет первых случаев. Лемма никогда не дает границу более точную, чем наименьшая из границ (5.6.3) и (5.6.4), но, как это было использовано в теореме, она позволяет получить удобную для исследования границу для

Используем теперь теорему 5.6.1 для случая дискретного канала без памяти, в котором

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

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

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

Рассматривая описанный выше ансамбль кодов как ансамбль -блоковых кодов с получаем

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

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

где

В силу того, что (5.6.13) справедливо для любого сообщения в коде, средняя вероятность ошибки по сообщениям при произвольном наборе вероятностей сообщений удовлетворяет неравенству

Наконец, так как являются произвольными в (5.6.13) и (5.6.14), наиболее точная граница получается после выбора так, чтобы максимизировать Таким образом, мы приходим к определению показателя экспоненты случайного кодирования

где максимизация по производится по всем распределениям вероятностей Отсюда получаем следующее следствие.

Следствие 1. Для ансамбля кодов с которое максимизирует (5.6.16), имеем

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

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

Так как средняя по ансамблю кодов вероятность ошибки удовлетворяет (5.6.18), то ясно, что по крайней мере один код из ансамбля должен иметь вероятность ошибки столь же малую, как и эта вероятность. Это следствие не дает способа отыскания такого кода и было бы удивительно, если бы случайно выбранный код имел вероятность ошибки гораздо большую, чем средняя вероятность. В частности, используя неравенство Чебышева (5.4.6), получаем

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

Рис. 5.6.1. Показатель экспоненты случайного кодирования для двух каналов. а — типичное поведение, б - частный случай, в котором

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

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

Следствие 2. Для любого дискретного канала без памяти, любого целого положительного N и любой положительной R существует -блоковый код, для которого

Доказательство. Выберем код с кодовыми словами, для которого при равновероятных сообщениях

Удалим кодовых слов из этого кода, устраняя, в частности, все слова, для которых

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

Используя (5.6.16) совместно с этим результатом, будем иметь

Таким образом, это множество кодовых слов удовлетворяет (5.6.20).

Свойства показателя экспоненты случайного кодирования Er(R)

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

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

вероятностей канала. нельзя просто интерпретировать как среднюю по ансамблю кодов взаимную информацию на символ.

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

Равенство в (5.6.24) имеет место тогда и только тогда, когда равенство в левой части (5.6.25) имеет место, когда и равенство в (5.6.26) имеет место тогда и только тогда, когда при всех таких, что имеем

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

Рис. 5.6.2. График

Можно заметить, рассматривая (5.6.14), что и легко проверить, выполняя дифференцирование, что

Доказательство оставшейся части теоремы содержится в приложении

Используя эту теорему, легко максимизировать по при заданном Определим

Уравнение для стационарной точки функции от имеет вид

Так как то любое решение уравнения (5.6.29) в интервале максимизирует (5.6.28). Более того, так как

является непрерывной и убывающей функцией от то решение уравнения (5.6.29) в интервале существует, если

Значение называется критической скоростью для заданного

При R, лежащей в указанном выше интервале, удобно использовать (5.6.29), чтобы связать параметрически через Получим

Дифференцируя равенства (5.6.31), будем иметь Следовательно, при изменении от 0 до 1 значение R монотонно убывает от до монотонно возрастает от 0 до Взяв отношение производных, получим

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

При значение достигает максимума (в интервале при что дает

И, наконец, в неинтересном случае, когда значение достигает максимума при давая

Подытожим сказанное. При R из интервала, задаваемого (5.6.30), и R связаны (5.6.31). При меньших значениях R функции и R связаны линейным соотношением (5.6.33), при больших значениях В зависимости от R функция строго убывает и является положительной при всех

Рассмотрим теперь частный случай, в котором Из равенства (5.6.26 а) теоремы 5.6.3 видно, что это соотношение должно удовлетворяться при всех если оно удовлетворяется при каком-нибудь В этом случае является постоянной и интервал, на котором справедливо (5.6.30), имеет нулевую протяженность (см. рис. 5.6.1, б). Этот частный случай является довольно искусственным и имеет место только для каналов без шума (для которых и для некоторых других довольно специфических каналов, таких, как изображенный на рис. 5.6.1, б).

Для обычного случая, в котором параметрические равенства (5.6.31) имеют силу на ненулевом интервале скоростей. Из (5.6.32) и (5.6.31) имеем следовательно, функция является

строго выпуклой по R в этом диапазоне Заметим, что так как этого диапазона, то функция является выпуклой по R при всех

Показатель экспоненты случайного кодирования можно теперь связать с следующим образом:

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

Рис. 5.6.3. Функция как огибающая сверху семейства линейных функций при в качестве параметра.

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

Теорема 5.6.4. (Теорема кодирования для канала с шумами.) Для любого дискретного канала без памяти показатель экспоненты случайного кодирования [см. (5.6.16) и (5.6.18)] является выпуклой убывающей положительной функцией R при

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

Для того чтобы максимизировать аналитически как по так и по целесообразно вначале провести максимизацию по

Функция не является выпуклой функцией однако, к счастью, она оказывается равной взятому со знаком минус логарифму выпуклой функции. Введем обозначение:

Значение на котором достигается минимум будет максимизировать

Теорема 5.6.5. При любом функция заданная (5.6.36), является выпуклой функцией в области, где является вектором вероятностей. Необходимыми и достаточными условиями того, что на векторе вероятностей достигается минимум [или максимум являются условия

с равенством при всех для которых Функция задается равенством

Доказательство. При функция является выпуклой функцией так как ее вторая производная неотрицательна. В силу того, что является линейной функцией из определения выпуклости следует, что является выпуклой функцией Поэтому

является выпуклой функцией

Согласно теореме 4.4.1 необходимыми и достаточными условиями того, что вектор вероятностей минимизирует являются условия

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

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

и затем решить (5.6.38) относительно Наконец, используя выпуклость легко найти максимум на вычислительной машине.

Так же как при отыскании пропускной способности, решение (5.6.37) и (5.6.38) относительно является единственным, а решение относительно не обязательно единственно. Если входной алфавит объема К больше, чем выходной алфавит объема то всегда можно отыскать максимум лишь на ненулевых значениях Единственным существенным отличием отыскания максимума от отыскания максимума является то, что выходные вероятности для пропускной способности всегда строго положительны, в то время как некоторые могут быть нулевыми.

Задавая на котором достигается максимум при каждом фиксированном можно использовать геометрический метод, показанный на рис. 5.6.3, чтобы найти кривую Для нахождения можно также использовать равенства (5.6.31) и (5.6.33), взяв для каждого значение на котором достигается максимум Чтобы показать, что эти равенства дают все точки на кривой заметим, что для каждого R существуют некоторые такие, что Для этого имеем Но так как параметрические равенства определяют для заданных то они также дают В примере 2 будет показано, однако, что эти равенства могут порождать некоторые дополнительные точки, лежащие строго ниже кривой

Пример 1. Для двоичного симметричного канала, изображенного на рис. 5.3.1, а, достигает максимума по при Для этого имеем

Параметрические равенства (5.6.31) могут быть приведены к виду

где параметр связан с параметром присутствующим в (5.6.31), соотношением

а и задаются равенствами

Эти равенства справедливы лишь для из интервала Для можно использовать (5.6.33) вместе с (5.6.40), чтобы получить

Равенству (5.6.41) можно дать геометрическую интерпретацию, как показано на рис. 5.6.4. Можно заметить, что как функция является уравнением касательной к кривой с точкой касания

Наиболее существенным в этом примере является то, что даже для такого простого канала невозможно дать другого выражения для кроме параметрического.

Пример 2. Рассмотрим канал, матрица переходных вероятностей которого приведена на рис. 5.6.5. Можно заметить, что, если используются только первые четыре входа, то канал является симметричным, а если используются только последние два входа, то канал сводится, по существу, к двоичному симметричному каналу.

Рис. 5.6.4. Показатель экспоненты случайного кодирования для двоичного симметричного канала.

Рис. 5.6.5. Разрывность наклона

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

Подставляя эти значения для в (5.6.31), можно получить кривую частично показанную на рис. 5.6.5. Имеется разрыв непрерывности наклона при переходе от и для из этого диапазона равенства (5.6.31) дают точки, как показано, лежащие строго ниже

Пример 3 (каналы с очень большим шумом). Рассмотрим канал с очень большим шумом в том смысле, что вероятность получения заданного выхода почти не зависит от входа. Выведем приближенное

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

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

Найдем теперь для этого канала, разлагая в ряд по степеням и отбрасывая все слагаемые порядка более высокого, чем 2. Имеем

Выводя из-под внутренней суммы и разлагая получаем

Используя (5.6.47), это выражение приводим к виду

где

Параметрические равенства (5.6.31) будут иметь вид

Средняя взаимная информация для входных вероятностей задается равенством (5.6.50 а) при Следовательно, пропускная способность задается в виде

Наконец, решая (5.6.50) относительно и используя (5.6.51), получаем

Для объединяя (5.6.33), (5.6.48) и (5.6.51), будем иметь

Это изображено на рис. 5.6.6.

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

Эти параллельные каналы можно рассмотреть, как единый канал, входами которого являются пары а выходами являются пары Можно применить теорему кодирования к этому составному каналу, в котором последовательности пар на входе являются кодовыми словами. Считая, что распределение вероятностей на входных парах, получаем

Если ограничиться такими для которых

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

где

Таким образом, сводится к сумме функций для отдельных каналов.

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

следует из (5.6.37), максимум достигается при таким образом,

Этот результат имеет интересную геометрическую интерпретацию. Пусть и являются показателем экспоненты и скоростью для параллельных каналов, параметрически связанными соотношениями (5.6.31) при оптимальном Пусть и аналогичные величины для отдельных каналов. Тогда

Рис. 5.6.6. Функция для каналов с очень большим шумом.

Рис. 5.6.7. Функция для параллельных каналов.

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