Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
При определении того, что мы понимаем под симметричным каналом, было бы довольно неуклюже рассматривать каналы поодиночке
109
Рис. 4.5.2. Пропускная способность двоичного симметричного канала и двоичного стирающего канала.
и говорить, что такой канал как (в) является симметричным, а такой канал, как (г) — нет. Введя определение симметрии, мы заметим, что в канале (в) имеются два выхода 0 и 2, которые подобны друг другу, и другой выход, который отличен. После этого будет неудивительно, что общее определение симметричных каналов будет включать в себя разбиение множества выходов на подмножества подобных выходов.
ДКБП называется симметричным, если множество выходов может быть разбито на подмножества таким образом, что для каждого подмножества матрица переходных вероятностей (используя входы как строки и выходы подмножества как столбцы) обладает тем свойством, что каждая строка является перестановкой любой другой строки и каждый столбец (если их больше чем 1) является перестановкой любого другого столбца. Так, например, разбивая выходы канала (в) на рис. 4.5.1 на 0, 2 и 1
/'
О 2 I
0.2
0,2
Так как каждая из приведенных выше матриц обладает перестановочным свойством, приведенным в определении, то канал является симметричным.
Теорема 4.5.2. В симметричном дискретном канале без памяти пропускная способность достигается при использовании входных букв с равной вероятностью.
Доказательство. При равновероятных входах имеем
^ р(Л*)
l(x = k- К)= ^ p(/l^)log (i/^)sР (Л 0- (4-5’8)
/=о >
При каком-либо разбиении выходов каждый столбец Р (; | ^-матрицы является перестановкой любого другого столбца и, таким образом, выходная вероятность (1//Q2P (/1 0 °Дна и та же для всех выходов
i
в разбиении. Это значит, что при разбиении выходов матрица с элементами Р (j | k) IХ-. у (k; /) имеет те же самые перестановочные свойства, что и Р (j\k) и, таким образом, сумма этих слагаемых в (4.5.8) одна и та же для каждого входа. Следовательно, (4.5.1) справедливо и пропускная способность достигается. |
Рассмотрим далее, как найти пропускную способность канала (5) на рис. 4.5.1. С интуитивных позиций кажется, что вход 1 плохо выбирать при передаче информации и наше предположение будет состоять в том, что пропускная способность достигается на Q (0) = = Q (2) = У2. Проверяя это предположение, находим, что / (х = 0; Y) = 1 (х = 2; У) = 1 и I (х = 1; К) = 0. Таким образом,
(4.5.1) и (4.5.2) удовлетворяются, и доказано, что наше предположение правильно,
110
К сожалению, иногда возникает интерес к отысканию пропускной способности канала, который не является симметричным и для которого невозможно угадать оптимальное Q. Самым легким является использование вычислительной машины для отыскания максимума. В силу того, что функция является выпуклой программа для вычислительной машины состоит просто в варьировании Q для увеличения I (X; У) до достижения локального (й, следовательно, глобального) максимума.
Если кто-либо особенно настаивает, однако, на отыскании традиционного решения для условий (4.5.1) и (4.5.2), то можно иногда найти ответ следующим образом. Предположим сначала, что все Q (k) ненулевые. Перепишем теперь (4.5.1) в виде
'fl1 Р (j I k) logР (j \k)~yiP (/ I k) log со (/) = С, (4.5.9)
/= о
где выходные вероятности со (/) равны
“(/)= Q{k)P(j\k). (4.5.10)
*— о
Из (4.5.9) и (4.5.10) имеем
2 Р и I k) [С + log со (;)] - 2 Р (/ j k) log P (/1 k). (4.5.11)
/
Это дает К линейных уравнений для J неизвестных (С + log со (/)). Если К — J и если матрица Р (/1 k) является невырожденной, то эти линейные уравнения могут быть решены. Если решениями будут = С + log со (/), то С можно найти из условия 2со (/) = 1, что приводит к равенству
С = log2 2 2Р^ бит, (4.5.12)
i
где все логарифмы взяты по основанию 2. К сожалению, нет уверенности в том, что С, задаваемая равенством (4.5.12), является пропуск-
ной способностью канала. Сначала нужно использовать С, чтобы найти со (/), и затем провести решение (4.5.10) относительно входных вероятностей Q (k). Если все Q (k) неотрицательны, то решение правильно, в противном случае — неправильно.
Если J > К, то равенства (4.5.11) в общем случае имеют неединственное решение, однако только одно из них будет давать решение Для (4.5.10). Нахождение С в этом случае состоит в решении системы нелинейных уравнений. Даже если решение найдено, может оказаться, что некоторые Q (k) будут отрицательными, и это делает решение непригодным.
