1.5.2. Свойства функции надежности

Нахождение максимума по в формуле (1.33), естественно, зависит от того, как ведет себя функция Поэтому вначале исследуем свойства как функции

Поведение как функции описывается следующей теоремой, доказательство которой было получено Галлагером [12].

Теорема 1.5. Пусть задан канал с входным алфавитом из К символов, выходным алфавитом из символов и переходными вероятностями Будем считать, что вероятностный вектор задает распределение вероятностей на множестве входных символов канала. Предположим, что средняя взаимная информация между входом и выходом канала

положительна. Тогда при функция обладает следующими свойствами:

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

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

Доказательство опускается (см. работу [12]). Соотношения показывают, что как функция ведет себя так, как показано на фиг. 1.4.

Фиг. 1.4. Типичный график функции .

Используя теорему 1.5, можно достаточно просто провести максимизацию по при заданном Для этого введем функцию

Продифференцировав выражение в квадратных скобках в (1.39) по и приравняв его затем к нулю, получим

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

В этой области значений скорости передачи функцию удобно задавать параметрически следующими соотношениями:

В случае когда параметрическое задание посредством формул (1.42) и (1.43) не имеет смысла. В этой области скоростей передачи функция возрастает с ростом и достигает максимума при Следовательно,

На фиг. 1.5 показан график как функции построенный на основании формул (1.42) — (1.44).

Рассмотрим как функции задаваемые формулами (1.42) и (1.43). С одной стороны, из соотношений (1.38), (1.40) и (1.43) можно видеть, что является невозрастающей функцией

Фиг. 1.5. Типичный график функции

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

т.е. параметр в формулах (1.42) и (1.43) можно интерпретировать как наклон графика функции к оси

Из замечания к неравенству (1.38), приведенному в теореме 1.5, видно, что при всех если только при каком-либо одном значении В этом случае связь между задается

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

Рассмотрим еще один способ максимизации по Заметим, что при фиксированном функция является линейной по имеет наклон и пересекается с осью ординат в точке Таким образом, является огибающей сверху семейства указанных выше прямых линий, соответствующих различным значениям параметра из интервала [0, 1]. Отсюда следует, в частности, что является выпуклой вниз функцией

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

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

Теорема 1.6. Для любого дискретного канала без памяти функция надежности является положительной непрерывной выпуклой вниз функцией при О

Доказательство. Если то теорема тривиальна. Если то при том на котором достигается пропускная способность канала, функция будет положительной при всех Очевидно, что в этой области скоростей будет положительной и функция Кроме того, как мы уже видели выше, при любом вероятностном векторе функция является непрерывной выпуклой вниз функцией производная которой изменяется в интервале от 0 до — 1. Отсюда следует, что и огибающая этого семейства кривых также является непрерывной выпуклой вниз функцией.

Далее рассмотрим, каким образом можно аналитически максимизировать по Соотношение (1.33), задающее можно переписать в виде

Введем функцию

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

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

где

Эти неравенства при всех для которых переходят в равенства.

Доказательство этой теоремы здесь опускается, однако его можно найти в работе Галлагера [20]. В случае когда все положительны, соотношение (1.49) является простым следствием метода неопределенных коэффициентов Лагранжа максимизации при условии Неравенства (1.49) почти не облегчают задачу явного нахождения максимума но позволяют легко проверить, максимизирует ли тот или иной вероятностный вектор функцию Практически наиболее простыми методами максимизации оказываются численные методы.

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

1) Функция может быть задана с помощью формулы (1.47) совокупностью прямых

2) Построив график в зависимости от можно найти графически.

3) Функцию можно найти также с помощью соотношений (1.42) и (1.43), взяв для каждого то значение на котором достигается максимум

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

случае, если кодирование не производится. Очевидно, что в этом частном случае все компоненты вектора вероятностей максимизирующего равны а именно Для того чтобы убедиться в этом, достаточно подставить эти величины в формулу (1.49). Функция при таком значении имеет вид

Фиг. 1.6. График функции для двоичного симметричного канала.

Дифференцируя (1.52) и используя параметрическое задание из соотношений (1.42) и (1.43) получаем

где

Эти равенства справедливы при или, что то же самое, при

При меньших скоростях находим по формуле (1.44)

График функции задаваемой формулами (1.55) и (1.57), представлен на фиг. 1.6.