Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Это завершает наше рассмотрение отыскания пропускной способности. Можно догадаться использовать симметрию канала, использовать процедуру поиска с помощью вычислительной машины или решить уравнения, но решение уравнений часто является довольно громоздкой, если не невыполнимой задачей. В заключение этого параграфа приведем несколько интересных следствий теорем 4.5.1 и 4.4.2.
111
Следствие 1. Для любого распределения вероятностей на входе, на котором достигается пропускная способность дискретного канала без памяти, все выходные вероятности являются положительными. (Здесь предполагается, что каждый выход можно получить из некоторого входа.)
Доказательство. Пусть со (/) является вероятностью выхода /; на основании (4.5.2) имеем ¦'-I P{j\k)
Y Р (/1 k) log-----С при всех k, для которых Q (k) = О,
/= о ® 0)
(4.5.13)
Если какая-либо © (/) = 0, то любой вход, который дает выход j с ненулевой переходной вероятностью, должен иметь Q (k) = 0. Для такого k левая часть (4.5.13) равна бесконечности, что приводит к противоречию. |
Следствие 2. Выходной вектор вероятностей, на котором достигается пропускная способность, является единственным. Все входные векторы вероятностей с соответствующими нулевыми компонентами, которые приводят к этому выходному вектору, являются такими, на которых достигается пропускная способность.
Доказательство. Пусть Q0 и Qx — какие-либо два входных вероятностных вектора, на которых достигается пропускная способность С. При 0, лежащем между 0 и 1, входной вектор вероятностей 0Qo + + (1 — 0) Q2 также приводит к пропускной способности, так как выпуклость ^ информации / (X; Y) показывает, что средняя взаимная информация при 0QO + (1 — 0) 0.г не может быть меньше чем С. Используя те же самые условные вероятности
Qo (k) = Qx\z (k | 0) и Qx{k) = Qx\z{k\\),
как и в доказательстве теоремы 4.4.2, можно заметить, что I (X; Y) = = I (X; Y | Z). Из (4.4.31), однако, следует, что / (F; Z) = 0. Поэтому у и z статистически независимы и Ру \ z (/1 0) = Ру (/) = = Ру | z (/11). Это значит, что одно и то же распределение вероятности на выходе соответствует как Q0, так и Qx и этот выходной вектор вероятностей является единственным. Наконец, в силу того, что условия
(4.5.1) и (4.5.2) зависят от Q (k) только через выходные вероятности
2Q (k) Р (j \k), то любое Q (с соответствующим образом выбранными k
нулевыми компонентами), приводящее к этому выходному вектору вероятностей, удовлетворяет (4.5.1) и (4.5.2) и, следовательно, приводит к пропускной способности. |
Следствие 3. Пусть т наименьшее число входов, которое может быть использовано с ненулевыми вероятностями при достижении пропускной способности и пусть А обозначает это множество входов. Тогда m^.J, где J — объем выходного алфавита, и входное распределение вероятности на Л, на котором достигается пропускная способность при использовании только входов из А, является единственным.
112
Доказательство. Пусть <»> = [со (0), со (У — 1)] является выходным вектором вероятностей, на котором достигается пропускная способность канала. Входные вероятности, которые считаются неравными нулю только на множестве А, должны удовлетворять равенству
%Q(k)P(j | ft) = ©(/), 0</<У-1. (4.5.14)
¦ *е а
Это представляет собой систему J уравнений с т неизвестными и по предположению она имеет по крайней мере одно решение (заметим, что любое решение удовлетворяет условию 2Q (k) = 1). Предположим, что решение не единственно; пусть Q — вектор вероятностей, дающий решение, и пусть h — ненулевое решение однородных уравнений. Тогда Q + 0h удовлетворяет (4.5.14). Будем увеличивать 0, начиная от 0 до тех пор, пока некоторая компонента Q + 0h не достигнет 0. Это всегда можно сделать, так как ~Zh (k) = 0 и h имеет отрицательные компоненты. Этот вектор Q + 0h приводит к пропускной способности при т — 1 ненулевых компонентах и предположение о неединственности решения является ошибочным. В силу того, что решение единственно, число неизвестных т меньше или равно числу уравнений J. \
4.6. ДИСКРЕТНЫЕ КАНАЛЫ С ПАМЯТЬЮ
Для дискретного канала с памятью каждая буква выходной последовательности статистически зависит как от соответствующего входа, так и от прошлых входов и выходов (здесь и в дальнейшем предполагается, что канал является каналом без предвосхищения, т. е. при заданном текущем входе и заданных входах и выходах в прошлом текущий выход статистически не зависит от будущих входов). Без потери общности последовательность входов и выходов вплоть до заданного момента может быть рассмотрена как состояние канала в этот момент. В этих понятиях статистическое поведение канала описывается совместной вероятностной мерой на выходной букве и состоянии в заданный момент при условии, что заданы текущая входная буква и предыдущее состояние.
