Параграф 1.6: Пропускная способность дискретного канала

В любой системе связи через канал передается информация. Её скорость передачи определяется выражением 1.23. Как видно из 1.23, эта скорость зависит не только от свойств самого канала, но и от подаваемого на его вход сигнала, и поэтому не может характеризовать канал как средней переедаемой информации. Попытаемся найти объективную характеристику способности канала передавать информацию.

Рассмотрим дискретный канал, через который передается в единицу времени v_k из алфавита объемом М. При передачи каждого символа в среднем передается информация I (U, Z) = H (U) – H (U / Z), где U и Z – ансамбли случайных символов на входе и выходе сигнала. Из четырех фигурирующих здесь энтропий лишь H (U) – собственная информация передаваемого сигнала, определяется источником входного сигнала и не зависит от свойств канала. Остальные три энтропии в общем случае зависят как от источника сигнала, так и от канала.

Представим себе, что на вход канала можно подавать символ от разных источников, характеризующих различными распределениями вероятностей P (U) при одних и тех же значениях v_k и М. Для каждого такого источника количество информации, переданной по каналу, принадлежит свое значение. Очевидно, существует какой-то источник входного сигнала с некоторым распределением вероятности P (U), для которого величина I (U, Z) максимальна. Максимальное количество переданной информации, взятой по всем возможным источникам входного сигнала, характеризует сам канал, и называется пропускной способностью канала в расчете на один символ:

С_символ = max I (U/ Z) (1.24а)

^{P (U)}

где максимизация произошла по всем возможным многомерным (учитывающим статическую взаимозависимость последовательно выдаваемых элементов сообщений) распределениям вероятностей P (U). Обычно определяют пропускную способность канала С в расчете на единицу времени:

С = max I’ (U/ Z) = v_k * С_символ (1.24)

^{P (U)}

которую называют просто пропускной способностью канала. Пропускная способность канала удовлетворяет неравенству: 0 ≤ С ≤ v_k log M (1.25)

причем С=0 при независимых входе и выходе канала, когда H (U / Z) = H (U) (обрыв канала или сильные помехи по каналу). Другое граничное значение С=v_klogM (1.25а) имеет место, когда помех в канале нет, и H (U / Z) = H (Z / U) = 0

H (U) = H (Z) = I (U, Z)

при этом при заданном М:

H_max (U) = log M (см. 2 свойство энтропии).

Т.о., пропускная способность канала без шума определяется равенством (1.25а). При наличии шума С < v_k log M (1.25б)

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

В таком канале каждый переданный кодовый сигнал может быть принят ошибочно с вероятностью Р и правильно с вероятностью (1 – Р) (т.е. вероятность ошибки не зависит от того, как символ передается, поэтому канал называется симметричным), причем в случае ошибки вместо переданного символа u_k может быть с равной вероятностью принят любой другой символ. Т.о. вероятность того, что принят символ z_j при условии, что был передан u_k: (1.26)

где N – объем алфавита источника, P (z_j / u_k) – переходная вероятность, а P (u_k / z_j) – апостериорная вероятность.

Термин «без памяти» означает, что вероятность ошибки в канале не зависит от того, какие символы передавались раньше и как они были приняты.

В соответствии с 1.24а, С_символ = max [H (Z) – H (Z / U)].

^{P (U)}

С учетом 1.9 и 1.26 имеем:

_{N N z=j N z≠k}

H (Z / U) = ∑ p (u_k) ∑ p (z_j / u_k) * log 1 / p (z_j / u_k) = ∑ p (u_k) (1 – p) * log 1 / (1 – p) +

_{N N} ^{k=1 j=1 k=1} _N

∑ p (u_k) ∑ p / (N – 1) * log (N – 1) / p = (1 – p)log 1/(1 – p) ∑ p (u_k) + (N – 1) p / (N – 1)

^{k=1 j=1 (∑1=N–1) k=1 (∑ p (uk)=1)}

* log (N – 1) / p ∑ p (u_k) = (1 – p)log 1/(1 – p) + p log (N – 1) / p (1.26a)

^{k=1 (∑ p (uk)=1)}

Итак,

С_символ = max [H (Z) – (1 – p)log 1/(1 – p) – p log (N – 1) / p].

В правой части от P (U) зависит только H (Z), следовательно, максимизировать нужно только его H (Z). В соответствии со 2 свойством энтропии, максимальное значение H (Z) = log N и реализуется оно тогда, когда все принятые символы z_j равновероятны и независимы. Легко убедиться, что это условие выполняется, если и входные символы равновероятны и независимы (при p (u_k) = 1 / N). В этом случае, по формуле полной вероятности имеем:

_{N N}

p (z_j) = ∑ p (u_k) * p (z_j / u_k) = 1 / N ∑ p (z_j / u_k)

^{k=1 k=1}

В соответствие с 1.26, последовательная сумма включает в себя одно слагаемое (1 – p) и (N – 1) – слагаемое p / (N – 1). Поэтому, можно записать:

p (z_j) = 1 / N (1 – p + (N – 1) * p / (N – 1),

т.е z_j имеет равномерное распределение. При этом, H (Z) = log N и пропускная способность в расчете на один символ будет равна

С_символ = log N + p log p / (N – 1) + (1 – p) log (1 – p) (1.27)

Отсюда, пропускная способность С равна:

С = v_k [log N + p log p / (N – 1) + (1 – p) log (1 – p)] (1.27a)

Для двоичного симметричного канала (N = 2), пропускная способность:

С = v_k [1 + p log p + (1 – p) log (1 – p)] (1.28)

Зависимость C / v_k (p) в соответствие с 1.28 имеет вид:

При p = 1 / 2, пропускная способность двоичного канала С = 0, т.к. при такой вероятности ошибки последовательность выходных двоичных данных символов можно получить, совсем не передавая сигналы по каналу, а выбирая их наугад.

Т.о., при р = 1 / 2, последовательность на вход и выход канала независимы (обрыв канал). ТО, что пропускная способность при р = 1 в двоичном канале такая же, что и р = 0 объясняется тем, что при р = 1 достаточно все входные символы проинвертировать, чтобы абсолютно правильно восстановить входной сигнал.