3.12.4. Свойства функции ... и построение экспоненты случайного кодирования.

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

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

Определение 3.12.1. Величина определяемая следующим выражением:

называется энтропией распределения относительно распределения

Лемма 3.12.1. Для произвольных распределений на X функция неотрицательна и равна нулю в том и только том случае, когда для всех

Доказательство. Используя неравенство получим

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

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

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

Во всех таких случаях лемма 3.12.1 остается справедливой.

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

В следующей теореме устанавливается связь между фукциями и , а также устанавливаются некоторые свойства функции

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

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

2. Пусть стохастическая матрица, на которой достигается максимум в выражении (3.12.20). Тогда величины удовлетворяют следующей системе уравнений:

где

3. Обозначим через и вероятностный вектор который задает оптимальное распределение вероятностей на X при фиксированном значении обозначим через вероятностные векторы, соответствующие распределениям на и на соответственно. Пусть вероятностный вектор, соответствующий распределению на Тогда

где средняя взаимная информация, вычисленная в соответствии с распределением

4. В обозначениях имеет место равенство

Доказательство. Найдем частную производную по

В соответствии с теоремой Куна-Таккера (см. параграф 2.8) необходимые условия достижения максимума в (3.12.20) состоят в том, чтобы при каждом

где множитель Лагранжа, обусловленный ограничением и строгое неравенство в (3.12.26) возможно только при условии при данном у. Условия (3.12.26) эквивалентны условиям

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

Если то и условия (3.12.27) могут быть выполнены только в случае, Следовательно, откуда с учетом (3.12.27) получаются соотношения (3.12.21). Утверждение 2 доказано.

Заметим далее, что выражение под знаком логарифма в правой части (3.12.19) при является выпуклой вниз функцией Действительно, — выпуклая вниз функция у, а вся сумма является некоторой комбинацией с неотрицательными коэффициентами выпуклых вниз функций (см. задачу 2.5.2). Поэтому в силу монотонности логарифма максимум (3.12.20) единствен и, следовательно, уравнения (3.12.21) имеют единственное решение.

Покажем, что решением является система величин

и что при этом имеет место соотношение (3.12.20). Действительно, подстановка (3.12.28) в (3.12.19) дает

Подставляя теперь (3.12.28) в (3.12.22) и (3.12.23), получим

Таким образом, величины (3.12.28) удовлетворяют системе уравнений (3.12.21) и, следовательно, максимизируют правую часть соотношения (3.12.20), что доказывает утверждение 1.

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

где вычисляется по формуле (3.12.22), в которой заменено на Если теперь положить где дается соотношениями (3.12.28), то с учетом (3.12.20) и (3.12.21) получим

Кроме того,

что и завершает доказательство утверждения 3.

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

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

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

1. , причем равенство имеет место только при .

2. причем равенство в первом неравенство имеет место только при

Доказательство. При выражение под знаком логарифма в (3.12.15) равно единице, поэтому при Из (3.12.22) следует, что при поэтому и из утверждения 3 теоремы и леммы

3.12.1 вытекает, что

Так как согласно (3.12.24) производная неотрицательна при всех то отсюда следует первое доказываемое свойство. Третье свойство непосредственно следует из утверждения 4 теоремы. Это свойство показывает, что не возрастает по и поэтому выполняется свойство 2. Следствие доказано.

С помощью следствия можно легко максимизировать правую часть соотношения (3.12.16) по при заданном вероятностном векторе Пусть

Дифференцируя по выражение, стоящее под знаком максимума,

и приравнивая производную к нулю, получим следующее уравнение для максимизирующего значения

Используя свойство 3 следствия, получим, что любое неотрицательное решение этого уравнения максимизирует (3.12.29). Так как является непрерывной и убывающей функцией от то решение уравнения (3.12.30), лежащее в интервале [0, 1], существует, если

Рис. 3.12.1. Функция

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

Уравнения

задают значения при для фиксированного распределения вероятностей на входе

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

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

Теперь можно дать общий метод построения функции Из (3.12.31), дифференцируя по получим

Следовательно, при изменении от 0 до 1 значение убывает монотонно от до а монотонно возрастает от нуля до Взяв отношение производных, получим

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

Рис. 3.12.2. Функция как огибающая семейства касательных.

При значение достигает максимума при при условии, что Это можно увидеть, например, из рис. 3.12.1: отрезок, отсекаемый касательной на оси ординат, монотонно увеличивается с ростом Поэтому

Для каждого значения из интервала касательная к кривой в точке с абсциссой имеет наклон Эта касательная отсекает на оси ординат отрезок, равный

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

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

где

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

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