Клод Шеннон: Математическая теория связи

<< Часть 3. Математические основы | Оглавление | Часть 5. Темп для непрерывного источника >>

Часть 4. Непрерывный канал

Пропускная способность непрерывного канала

В непрерывном канале входная информация или передаваемый сигнал являются непрерывными функциями времени $f(t)$ из некоторого множества, а выходная информация иди принятый сигнал - их искаженными версиями. Мы рассмотрим лишь случай переданного и принятого сигналов, ограниченных частотным диапазоном $W$. Такие сигналы можно представить на интервале времени $T$ набором $2 T W$ чисел, а их статистическую структуру - конечномерными функциями распределения. Тогда статистика передаваемого сигнала будет определяться

$$P(x_1,\dots,x_n)=P(x),$$

а шума - распределением условной вероятности

$$P_{x_1,\dots,x_n}(y_1,\dots,y_n)=P_x(y).$$

Темп передачи информации для непрерывного канала определим по аналогии с непрерывным случаем, а именно как

$$R=H(x)-H_y(x)$$

где $H(x)$ - энтропия на входе и $H_y(x)$ - ошибочность. Пропускная способность канала $C$ определяется как максимальное значение $R$ при варьировании входной информации по всем возможным ансамблям. Это значит, что в конечномерном случае мы должны варьировать $P(x)=P(x_1,\dots,x_n)$ для максимизации

Это можно записать как

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

Очевидно, что в такой записи $R$ и $C$ не зависят от выбора системы координат, так как и числитель, и знаменатель в $\log\frac{P(x,y)}{P(x)P(y)}$ умножаются на одно и то же число при одинаковом преобразовании $x$ и $y$. Данное интегральное представление $C$ является более общим, чем $H(x)-H_y(x)$. Соответственным образом проинтегрированное (см. приложение 7), оно определено всегда, тогда как $H(x)-H_y(x)$ в некоторых случаях принимает неопределенное значение $\infty-\infty$. Это имеет место, к примеру, когда $x$ ограничено поверхностью меньшей размерности, чем $n$ в $n$-мерном приближении.

При использовании двойки как основания логарифма при расчете $H(x)$ и $H_y(x)$ $C$ является максимальным числом двоичных знаков, которые можно послать за секунду по каналу с произвольно малой ошибочностью, так же, так и в дискретном случае. Физически это становится очевидным при делении пространства сигналов на большое число ячеек, достаточно малых для того, чтобы плотность вероятности $P_x(y)$ для сигнала $x$ в результате возмущения перейти в $y$ была достаточно постоянной по ячейке (как по $x$, так и по $y$). Если рассматривать эти ячейки как точки, ситуация становится совершенно аналогичной дискретному случаю, и можно воспользоваться соответствующим доказательством. С физической точки зрения ясно, что это ``квантование'' пространства на отдельные точки в любой практической ситуации не может сильно изменить ответ при достаточно малых размерах ячеек. Следовательно6 пропускная способность будет пределом соответствующих дискретных при стремлении размеров ячеек к нулю, что и отражено в вышеприведенном определении.

С математической точки зрения, можно вначале показать (см. приложение 7), что, если $u$ - сообщение, $x$ - сигнал, $y$ - принятый сигнал (искаженный шумом), и $v$ - восстановленное сообщение, то

$$H(x)-H_y(x)\geq H(u)-H_v(u)$$

вне зависимости от того, какими операциями из $u$ получается $x$, или из $y$ - $v$. Следовательно, все зависимости от того, как именно мы кодируем исходное сообщение или восстанавливаем его в точке приема, дискретный темп передачи двоичных знаков не превосходит введенной нами пропускной способности канала. С другой стороны, при достаточно общих условиях можно найти систему кодирования, позволяющую передавать двоичные знаки с темпом $C$ с произвольно малой частотой ошибок. Это верно, к примеру, тогда, когда при конечномерном приближении пространства функций сигналов $P(x,y)$ непрерывно как по $x$, так и по $y$ за исключением множества точек нулевой вероятности.

Важным частным случаем является добавление к сигналу шума, независимого от него (в статистическом смысле). Тогда $P_x(y)$ зависит лишь от разности $n=(y-x)$.

$$P_x(y)=Q(y-x)$$

и шум имеет определенную энтропию (не зависящую от статистики сигнала), именно - энтропию распределения $Q(n)$, которую мы обозначим $H(n)$.

Теорема 16: Если сигнал и шум независимы, и принятый сигнал равен сумме переданного и шума, темп передачи равен

$$R=H(y)-H(n),$$

то есть энтропия принятого сигнала меньше энтропии шума. Пропускная способность канала есть

$$C=\max_{P(x)} H(y)-H(n).$$

Так как $y=x+n$, имеем

$$H(x,y)=H(x,n).$$

Расписывая левую часть и пользуясь фактом независимости $x$ и $y$, имеем

$$H(y)+H_y(x)=H(x)+H(n).$$

Таким образом,

$$R=H(x)-H_y(x)=H(y)-H(n).$$

Так как $H(n)$ не зависит от $P(x)$, максимизация $R$ требует максимизации $H(y)$, энтропии принятого сигнала. Если есть некоторые ограничения на ансамбль передаваемых сигналов, максимизацию энтропии принятого сигнала необходимо проводить с учетом этих ограничений.

Пропускная способность канала с ограничением средней мощности

Простым приложением теоремы 16 является случай теплового белого шума и передаваемых сигналов, ограниченных некоторой средней мощностью $P$. Тогда средняя мощность принятого сигнала равна $P+N$, где $N$ - средняя мощность шума. Энтропия принятого сигнала максимальна, когда он также является ансамблем белого шума, так как он обладает наибольшей энтропией при заданной мощности. Это может быть достигнуто надлежащим выбором передаваемых сигналов, а именно - когда они образуют ансамбль белого шума средней мощности $P$. Энтропия принятого ансамбля (в секунду) тогда имеет вид

$$H(y)=W\log 2\pi e(P+N),$$

а шума -

$$H(n)=W\log 2\pi e N.$$

Пропускная способность канала тогда

$$C=H(y)-H(n)=W\log\frac{P+N}{N}.$$

Подытоживая, имеем следующий результат.

Теорема 17: Пропускная способность канала ограниченного диапазона частот $W$, возмущаемого тепловым белым шумом $N$ при средней передаваемой мощности, не превосходящей $P$, дается выражением

$$C=W\log\frac{P+N}{N}.$$

Это значит, что при достаточно сложной системе кодирования мы можем передавать двоичные знаки с темпом $W\log_2\frac{P+N}{N}$ с произвольно малой частотой ошибок. Передача с более высоким темпом без конечной положительной частоты ошибок невозможна при любой системе кодирования.

Для приближения к этому предельному темпу передачи передаваемый сигнал должен стремиться по статистическим свойствам к белому шуму (Это и другие свойства случая белого шума обсуждаются с геометрической точки зрения в ``Communication in the Presence of Noise,'' loc. cit.). Система, приближающаяся к идеальному темпу, может быть устроена так. Пусть построены $M=2^s$ выборок белого шума длительностью $T$ каждая. Им сопоставляются двоичные числа от $0$ до $M-1$. В передатчике сообщение разбивается на последовательности длиной $s$, и соответствующие им выборки белого шума передаются как сигналы. На стороне приемника эти выборки известны, и принятый сигнал сравнивается с ними. Переданным сигналом считается та выборка, которая наименее от него отличается (в смысле наименьших квадратов разностей), и восстанавливается соответствующее двоичное число. Этот процесс соответствует выбору наиболее вероятного апостериорного сигнала. Использованное число выборок шума $M$ будет зависеть от допустимой частоты ошибок. но практически для всех вариантов выборок

$$\lim_{\epsilon\to0}\lim_{T\to\infty}\frac{\log M(\epsilon,T)}{T}=W\log\frac{P+N}{N},$$

так что, вне зависимости от малости $\epsilon$ мы можем, при выборе достаточно большого $T$, передавать как угодно близко к $TW\log\frac{P+N}{N}$ двоичных цифр в секунду.

Формулы, похожие на $C=W\log\frac{P+N}{N}$, для белого шума были получены независимо несколькими другими авторами, хотя и в другой интерпретации. Отметим в связи с этим работы Винера(N. Wiener, Cybernetics, loc. cit.), Таллера (W. G. Tuller, ``Theoretical Limitations on the Rate of Transmission of Information,'' Proceedings of the Institute of Radio Engineers, v. 37, No. 5, May, 1949, pp. 468--78.) и Салливана (H. Sullivan).

В случае произвольного возмущающего шума (не обязательно белого теплового) задача максимизации при определении пропускной способности $C$, похоже, не может быть решена явно. Однако, можно наложить верхний и нижний пределы на $C$ в терминах средней мощности шума $N$ и мощности его энтропии $N_1$. Эти пределы в большинстве практических случаев достаточно близки друг к другу для того, чтобы считаться решением задачи.

Теорема 18: Пропускная способность канала диапазона частот $W$, возмущаемого произвольным шумом лежит в пределах

$$W\log\frac{P+N_1}{N_1}\leq C\leq W\log\frac{P+N}{N_1}$$

где

средняя передаваемая мощность
средняя мощность шума
мощность энтропии шума.

Здесь средняя мощность возмущенного сигнала вновь равна $P+N$. Максимальная энтропия для данной мощности $W\log 2\pi e(P+N)$ имела бы место, если бы принятый сигнал был белым шумом. Достижение этого невозможно, нельзя построить такой ансамбль перелаваемых сигналов, чтобы при сложении с шумом он двал белый шум; но как минимум это дает нам верхний предел на $H(y)$. Следовательно, имеем

Это - верхний предел, приведенный в теореме. Нижний же может быть получен при рассмотрении темпа передачи в случае, когда передаваемый сигнал является белым шумом мощности $P$. Тогда мощность энтропии принятого сигнала должна быть не меньшей сответствующей для белого шума мощности $P+N_1$, так как, как показано в предыдущей теореме, мощность энтропии суммы двух ансамблей не меньше суммы отдельных мощностей энтропии. Следовательно,

$$\max H(y)\geq W\log 2\pi e(P+N_1)$$

и

С ростом $P$ верхние и нижние пределы сходятся друг к другу, и мы имеем асимптотический темп

$$W\log\frac{P+N}{N_1}.$$

Если шум является белым, $N=N_1$, и результат сводится к доказанной выше формуле

$$C=W\log\Bigl(1+\frac P N\Bigr).$$

Если же шум гауссов, но не обязательно с плоским спектром, $N_1$ является геометрическим средним мощности шума по различным частотам диапазона $W$. Таким образом,

$$N_1=\exp\frac1W\int_W \log N(f)\,df$$

где $N(f)$ - мощность щума на ачстоте $f$.

Теорема 19: Если мы установим пропускную способность для данной передаваемой мощности $P$ равной

$$C=W\log\frac{P+N-\eta}{N_1},$$

то $\eta$ монотонно убывает с ростом $P$ и равна $0$ в пределе.

Пусть для заданной мощности $P_1$ пропусткая способность равна

$$W\log\frac{P_1+N-\eta_1}{N_1}.$$

Это значит, что лучшее распределение сигнала, скажем, $p(x)$, при добавлении к распределению шума $q(x)$ дает принятое распределение с мощностью энтропии $(P_1+N-\eta_1)$. Увеличим мощность до $P_1+\Delta P$ добавлением к сигналу белого шума мощности $\Delta P$. Энтропия принятого сигнала тогда равна как минимум

$$H(y)=W\log 2\pi e(P_1+N-\eta_1+\Delta P)$$

согласно теореме о минимальной мощности энтропии суммы. Следовательно, так как мы можем достичь обозначенной $H$, энтропия максимизирующего распределения должна быть не меньше, и $\eta$ должно монотонно убывать. Чтобы показать, что $\eta\to0$ при $P\to\infty$, рассмотрим сигнал, являющийся белым шумом с большим $P$. Вне зависимости от возмущающего шума принятый сигнал примерно останется белым шумом при достаточно большом $P$ в смысле мощности энтропии, приближающейся к .

Пропускная способность канала с ограничением максимальной мощности

В некоторых приложениях у передатчика ограничена не средняя, а мгновенная выходная мощность. Задача вычисления пропускной способности канала в таком случае сводится к максимизации (при варьировании ансамбля передаваемых сигналов)

$$H(y)-H(n)$$

при условии того, что все функции $f(t)$ ансамбля не превосходят, к примеру, $\sqrt{S}$ при всех $t$. Ограничение в данном случае влияет не так, как в предыдущей задаче, в которой было известно предельное среднее значение. В данном случае мы можем получить лишь нижний предел, справедливый для всех $\frac S N$, ``асимптотический'' верхний предел для больших $\frac S N$ и асимптотическое выражение для $C$ для малых $\frac S N$.

Теорема 20: Пропускная способность канала, ограниченного диапазоном частот $W$ и возмущаемого тепловым белым шумом мощности $N$, ограничена

$$C\geq W\log\frac{2}{\pi e^3}\frac S N,$$

где $S$ - максимально возможная передаваемая мощность. Для достаточно больших $\frac S N$

$$C\leq W\log\frac{\frac{2}{\pi e}S+N}{N}(1+\epsilon),$$

где $\epsilon$ произвольно мало. При $\frac S N\to0$ ( и в предположении того, что полоса частот начинается с $0$)

$$C \!\!\Bigm/\! W\log\biggl(1+\frac S N\biggr) \to 1.$$

Хотелось бы максимизировать энтропию принятого сигнала. При $\frac S N$ это будет иметь место примерно тогда же, когда максимальна энтропия переданваемого ансамбля.

Асимптотический верхний предел может быть получен при ослаблении наложенных на ансамбдь ограничений. Предположим, что величиной $S$ ограничена не мгновенная мощность, а лишь мощность в точках некоторой выборки. Маесимальная энтропия передаваемого ансамбля при этих ослабленных условиях. очевидно, не меньше, чем при исходных. При таком изменении задача легко решается. Энтропия максимальна, если различные выборки независимы и имеют функцию распределения, постоянную на интервале от $-\sqrt S$ до $+\sqrt S$. Энтропию можно рассчитать как

$$W\log 4S.$$

Принятый сигнал имеет тогда энтропию, меньшую, чем

$$W\log(4S+2\pi e N)(1+\epsilon)$$

с $\epsilon\to0$ при $\frac S N\to\infty$, и пропускная способность канала получается вычитанием энтропии белого шума $W\log 2\pi e N$

$$W\log(4S+2\pi e N)(1+\epsilon)-W\log (2\pi e N)=W\log\frac{\frac{2}{\pi e}S+N}{N}(1+\epsilon).$$

Это и есть верхний предел для пропускной способности канала.

Для получения нижнего предела рассмотрим тот же ансамбль функций. Пусть эти функции пропускаются через идеальный фильтр с треугольной передаточной функцией. Усиление равно единице на нулевой частоте и линейно падает до нуля на частоте $W$. Покажем вначале, что выходные функции такого фильтра ограничены мгновенной мощностью $S$ во всех точках (а не только в некоторой их выборке). Вначале заметим, что импульс $\frac{\sin 2\pi Wt}{2\pi Wt}$, проходя через фильтр, преобразуется в

$$\frac12\frac{\sin^2\pi Wt}{(\pi Wt)^2}$$

на выходе. Эта функция неотрицательна. Входная функция в общем случае может рассматриваться как сумма набора сдвинутых функций

$$a\frac{\sin 2\pi Wt}{2\pi Wt}$$

где амплитуда $a$ не превосходит $\sqrt S$. Следовательно, на выходе имеем сумму сдвинутых неотрицательных функций вышеприведенной формы с теми же коэффициентами. Наибольшее ее значение для любого $t$ может быть получено, когда все $a$ принимают максимальные значения, то есть $\sqrt S$. Это соответствует постоянному входному сигналу амплитуды $\sqrt S$, и, так как усиление фильтра на нулевой частоте равно единице, сигнал на выходе будет тем же. Следовательно, предельной мощностью выходного ансамбля будет $S$.

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

$$\int_0^W\log G^2\,df=\int_0^W\log\Bigl(\frac{W-f}{W}\Bigr)^2\,df=-2W.$$

Следовательно, выходная энтропия равна

$$W\log 4S-2W=W\log\frac{4S}{e^2}$$

и пропускная способность канала больше, чем

$$W\log\frac{2}{\pi e^3}\frac S N.$$

Покажем теперь, что для малых $\frac S N$ (отношение предельной мощности сигнала к средней) пропускная способность примерно равна

$$C=W\log\biggl(1+\frac S N\biggr).$$

Более точно, при $\frac S N\to0$. Так как средняя мощность $P$ не превосходит предельной $S$, для всех $\frac S N$

$$C\leq W\log\biggl(1+\frac P N\biggr)\leq W\log\biggl(1+\frac S N\biggr).$$

Следовательно, если мы можем найти ансамбль функций, соответствующий темпу примерно $ W\log\biggl(1+\frac S N\biggr)$, ограниченный диапазоном частот $W$ и пределной мощностью $S$, теорема будет доказана. Рассмотрим ансамбль фкнкций следующего типа. Выборки длины $t$ имеет постоянные значения, равные $+\sqrt{S}$ или $-\sqrt{S}$. Эти значения выбираются случайно с вероятностями $\frac12$ каждое. При пропускании такого ансамбля через фильтр с треугольной передаточной функцией ансамбль на выходе ограничен $\pm S$. Более того, средняя мощность примерно равна $S$ при достаточно больших $t$. Энтропия суммы такого сигнала и белого шума может быть найдена с использованием теоремы о сумме белого шума и малого сигнала. Эта теорема применима, когда

$$\sqrt{t}\frac S N$$

достаточно мало, что имеет место при достаточно малых $\frac S N$. Мощность энтропии произвольно близка к $S+N$, и, следовательно, темп передачи будет равен

$$W\log\biggl(\frac{S+N}{N}\biggr).$$
<< Часть 3. Математические основы | Оглавление | Часть 5. Темп для непрерывного источника >>
Астронет