Главная > Разное > Принципы цифровой связи и кодирования
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

ПРИЛОЖЕНИЕ 3В. АЛГОРИТМ ВЫЧИСЛЕНИЯ ПРОПУСКНОЙ СПОСОБНОСТИ (Аримото [1972], Блахут [1972])

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

Тогда пропускная способность канала задается равенством

где

Пусть любое множество условных вероятностей:

и

Пусть, наконец,

Лемма. Для любого имеем

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

Доказательство. Из неравенства (1.1.8) для каждого у имеем

причем равенство достигается тогда и только тогда, когда для всех х. Заметив, что

видим, что непосредственно вытекает из

Приведенная лемма дает соотношение

где максимум достигается на

Пропускную способность канала можно представить в виде

Допустим теперь, что мы зафиксировали и ищем максимум по входным распределениям Из вытекает, что при фиксированном функци

выпукла на множестве входных распределений Теорема Куна-Таккера (см. приложение 3Б) устанавливает необходимые и достаточные условия обращения в максимум в точке

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

Для оно превращается в соотношение

или

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

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

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

Алгоритм заключается в следующем:

Шаг. 1. Взять исходное входное распределение и положить (можно выбрать равномерное распределение.

Шаг 2. Вычислить в соответствии с

Шаг 3. Вычислить в соответствии с

Шаг 4. Сменить индекс на и перейти к шагу 2.

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

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

Доказательство. Пусть

так что из следует

Из имеем где

Из определения в для вчдно, что два первых члена обращаются в нуль, что дает

Допустим теперь, что пропускная способность достигается на так что Рассмотрим

Воспользуемся вновь неравенством (1.1.8) и получим

а из получим

Заметим, что и суммируя по от 0 до получим;

Из неравенства (1.1.8) имеем

и, следовательно,

Верхняя граница в конечна и не зависит от , следовательно, - сходящийся ряд, поэтому

Аналогичные эффективные алгоритмы были разработаны для границы с выбрасыванием (Леш [1976]), заданной соотношениями (3.3.13) и (3.3.14), и для границы сферической упаковки (Аримото [1976], Леш [1976]), заданной соотношением (3.6.47). Напомним, что граница среднего по ансамблю совпадает с границей сферической упаковки при больших скоростях и легко выводится из

Задачи

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление