Клод Шеннон: Математическая теория связи
<< Часть 4. Непрерывный канал | Оглавление |

Часть 5. Темп для непрерывного источника

Функции расчета точности

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

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

Во-первых, необходимо дать общую математическую формулировку понятия точности передачи. Рассмотрим нможество сообщений достаточной длины $T$. Источник описывается заданием плотности вероятности (в соответствующем пространстве) того, что будт выбрано данное сообщение $P(t)$. Система связи характеризуется (с точки зрения внешнего наблюдателя) заданием условной вероятности $P_x(y)$ того, что, при выдаче источником сообщения $x$, в точке приема будет восстановлено $y$. Система в целом (включая источник и систему передачи) описывается вероятностью $P(x,y)$ исходного сообщения $x$ и восстановленного - $y$. Если эта функция задана, известны все характеристики системы с точки зрения точности передачи. Любой расчет точности должен сводиться к некоторой операции над $P(x,y)$; операция эта должна обладать как минимум свойством упорядоченности, то есть о двух системах $P_1(x,y)$ и $P_2(x,y)$ должно быть можно сказать, в соответствии с этим критерием точности, что либо (1) первая более точна, либо (2) вторая более точна, или же (3) их точности равны. Это значит, что критерий точности может быть представлен численными функциями

$$v\bigl(P(x,y)\bigr)$$

аргументы которых могут принимать значения всех возможных функций вероятности $P(x,y)$

Покажем теперь, что, при достаточно общих и разумных условиях, функцию $v\bigl(P(x,y)\bigr)$ можно записать как усреднение $\rho(x,y)$ по всем значениям $x$ и $y$

Для получения этого достаточно принять, что (1) источник и система эргодичны, то есть достаточно длинная последовательность с вероятностью 1 типична для ансамбля, и что (2) метод расчета ``приемлем'' в том смысле, что его можно провести на основании типичных входного и выходного сообщений $x_1$ и $y_1$, причем с ростом длин выборок полученная оценка сходится с вероятностью 1 к точному значению, которое может быть рассчитано на основании полного знания $P(x,y)$. Пусть методом расчета (оценкой) будет $\rho(x,y)$. Тогда $\rho(x,y)$ стремится (при $T\to\infty$) к некоторой константе практически для всех $(x,y)$ из высоковероятной области системы

$$\rho(x,y)\to v\bigl(P(x,y)\bigr)$$

и, кроме того, можно записать

так как

что и доказывает вышеприведенный результат.

Функция $\rho(x,y)$ имеет смысл ``расстояния'' между $x$ и $y$ (Это, однако, не ``метрика'' в точном смысле, так как в общем случае не удовлетворяет условиям $\rho(x,y)=\rho(y,x)$ и $\rho(x,y)+\rho(y,z)\geq\rho(x,z)$). Она характеризует, насколько нежелательно (согласно нашему критерию точности) получение $y$ при передаче $x$. Вышеприведенный общий результат можно переформулировать следующим образом: любой приемлемый метод расчета можно представить как усреднение функции расстояния по множеству принятых $y$ и переданных $x$ сообщений, взвешенных согласно вероятности $P(x,y)$ данной пары при достаточной длине $T$ сообщений.

Приведем несколько простых примеров способов расчета точности.

Темп источника по отношению к расчету точности

Самое время определить темп производства информации непрерывным источником. Пусть заданы $P(x)$ для источника и функция расчета точности $v$, определяемая посредством расстояния $\rho(x,y)$, которое будем считать непрерывным как по $x$, так и по $y$. Для определенного $P(x,y)$ эта величина равна

Более того, темп выдачи двоичных цифр, соответствующих $P(x,y)$,

Определим темп производства информации $R_1$ для заданной точности $v_1$ восстановления как минимум $R$ при фиксированной $v=v_1$ и варьировании $P_x(y)$, то есть как

при условии

Это значит, что мы рассматриваем все системы связи, которые можно использовать для передачи с заданной точностью. Темп передачи в битах в секунду вычисляется для каждой из них. и мы выбираем ту, для которой он минимален. Этот темп мы и приписываем источнику с заданной точностью.

Доказательством этого служит следующая теорема.

Теорема 21: Если темп источника равен $R_1$ для точности $v_1$, выдаваемую им информацию им можно закодировать и передать по каналу пропускной способности $C$ с точностью, произвольно близкой к $v_1$ при $R_1\leq C$. Это невозможно при $R_1>C$.

Последнее утверждение теоремы немедленно следует из определения $R_1$ и предыдущих результатов. Если бы это было не так, можно было бы передать больше, чем $C$ бит в секунду по каналу пропускной способности $C$. Первая же часть может быть доказана методом, аналогичным использованному для теоремы 11. Мы можем, во-первых, разделить пространство $(x,y)$ на большое число маленьких ячеек и свести задачу к дискретному случаю. Это изменит функцию расчета точности не более чем на произвольно малое число (при достаточно малом размере ячеек) благодаря предположению о непрерывности $\rho(x,y)$. Пусть $P_1(x,y)$ - система, минимизирующая темп и дающая $R_1$. Выберем из высоковероятных $y$ случайный набор, содержащий

$$2^{(R_1+\epsilon)T}$$

элементов, где $\epsilon\to0$ при $T\to\infty$. При больших $T$ каждая из выбранных точек будет соединена линиями высокой вероятности (как на рис.10) с набором $x$. Расчет, аналогичный использованному при доказательстве теоремы 11, показывает, что при больших $T$ практически все $x$ покрываются линиями набора $y$ при практически любом выборе элементов $y$. Искомая система связи работает так. Выбранным точкам сопоставляются двоичные числа. Тогда произвольное сообщение $x$ будет (с вероятностью, стремящейся к единице при $T\to\infty$) принадлежать хотя бы одному из наборов, соответствующих этим числам. Соответствующее двоичное число (или произвольно выбранное, если из несколько) передается по каналу с надлежащим кодированием, дающим малую вероятность ошибки. Это возможно, так как $R_1\leq C$. В точке приема соответствующее $y$ восстанавливается и считается принятым сообщением.

Характеристика точности $v_1'$ для такой системы может быть произвольно близкой к $v_1$ выбором достаточно большого $T$, так как для любых длинных выборок переданного $x(t)$ и принятого сообщений $y(t)$ она стремится к $v_1$ (с вероятностью 1).

Интересно заметить, что в данной системе шум восстановленного сообщения на самом деле вызывается дискретизацией в преобразователе, а не шумом в канале. Это примерно соответствует шуму дискретизации при PCM-кодирования.

Расчет темпов

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

где фиксированы $P(x)$ и , а второе

с фиксированной $P_x(y)$ и, возможно, иными ограничениями (к примеру, ограничениями на среднюю мощность) вида .

Можно найти частное решение общей задачи максимизации для определения темпа источника. Используя метод Лагранжа, рассмотрим

Вариационное уравнение (первая вариация $P(x,y)$) приводит к

$$P_y(x)=B(x)e^{-\lambda\rho(x,y)}$$

где $\lambda$ определяется из условия требуемой точности, а $B(x)$ - для удовлетворения

$$\int B(x)e^{-\lambda\rho(x,y)}\,dx=1.$$

Это показывает, что, при надлежащем кодировании, условная вероятность определенного прообраза для данного принятого $y$, $P_y(x)$, убывает экспоненциально с ростом функции расстояния между $x$ и $y$.

В специальном случае зависимости функции расстояния $\rho(x,y)$ лишь от (векторной) разности $x$ и $y$

$$\rho(x,y)=\rho(x-y)$$

имеем

$$\int B(x)e^{-\lambda\rho(x-y)}\,dx=1.$$

Следовательно, $B(x)$ является константой, скажем, $\alpha$, и

$$P_y(x)=\alpha e^{-\lambda\rho(x-y)}.$$

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

Если функция расстояния $\rho(x,y)$ равна среднему квадрату разности $x$ и $y$ и ансамбль шума - белый шум, темп может быть определен. В этом случае имеем

$$R=\min\bigl[H(x)-H_y(x)\bigr]=H(x)-\max H_y(x)$$

где $N=\overline{(x-y)^2}$. Но $\max H_y(x)$ имеет место, если $y-x$ - белый шум, и равно $W_1\log 2\pi e N$, где $W_1$ - ширина диапазона частот ансамбля сообщения. Тогда

где $Q$ - средняя мощность сообщения. Это доказывает следуюущее:

Теорема 22: Темп для источника белого шума мощностью $Q$ в диапазоне $W_1$ оп отношению к мере точности наименьших квадратов равен

$$R=W_1\log\frac{Q}{N}$$

где $N$ - допустимый средний квадрат ошибки восстановленного сообщения.

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

Теорема 23: Темп любого источника диапазона частот $W_1$ ограничен неравенствами

$$W_1\log\frac{Q_1}{N}\leq R\leq W_1\log\frac{Q}{N}$$

где $Q$ - средняя мощность источника, $Q_1$ - его мощность энтропии, и $N$ - допустимый средний квадрат ошибки.

Нижний предел следует из того, что $\max H_y(x)$ для данного $\overline{(x-y)^2}=N$ имеет место для белого шума; верхний же может быть получен при размещении точек (использованных при доказательстве теоремы 21) не лучшим, а случайным образом внутри сферы радиуса $\sqrt{Q-N}$.

Приложение 5

Пусть $S_1$ - некоторое измеримое подмножество ансамбля $g$, а $S_2$ - подмножество ансамбля $f$, переходящее в $S_1$ под действием операции $T$. Тогда

$$S_1=TS_2.$$

Пусть $H^\lambda$ - оператор, сдвигающий все функции множества на время $\lambda$. Тогда

$$H^\lambda S_1=H^\lambda TS_2=TH^\lambda S_2$$

так как $T$ - инвариант, и, следовательно, коммутирует с $H^\lambda$. Таким образом, если $m[S]$ - мера вероятности множества $S$,

где второе равенство следует из определения меры в пространстве $g$, третье - из стационарности ансамбля $f$, и последнее - вновь из определения меры на $g$.

Для доказательства того, что свойство эргодичности сохраняется при инвариантных преобразованиях, рассмотрим подмножество $S_1$ ансамбля $g$, инвариантное относительно $H^\lambda$, и множество $S_2$ всех функций $f$, переходящих в $S_1$. Тогда

$$H^\lambda S_1=H^\lambda TS_2=TH^\lambda S_2=S_1$$

так что $H^\lambda S_2$ является подмножеством $S_2$ при всех $\lambda$. Теперь

$$m[H^\lambda S_2]=m[S_1]$$

откуда следует

$$H^\lambda S_2=S_2$$

для всех $\lambda$ с $m[S_2]\neq 0,1$. Это противоречие показывает, что $S_1$ не существует.

Приложение 6

Верхний предел, $\overline N_3\leq N_1+N_2$, соответствует тому, что мансимально возможная энтропия для мощности $N_1+N_2$ дается белым шумом. Мощность энтропии тогда равна $N_1+N_2$.

Для получения нижнего предела, рассмотрим два распределения $n$ измерений $p(x_i)$ и $q(x_i)$ с мощностями энтропии $\overline N_1$ и $\overline N_2$. Какую форму должны принимать $p$ и $q$ для минимизации мощности энтропии $\overline N_3$ их свертки

$$r(x_i)=\int p(y_i)q(x_i-y_i)\,dy_i?$$

Энтропия $H_3$ величины $r$ дается выражением

$$H_3=-\int r(x_i)\log r(x_i)\,dx_i.$$

Минимизируем это выражение при условиях


Рассмотрим теперь


Если $p(x)$ варьируется по некоторому аргументу $x_i=s_i$, вариация $r(x)$ равна

$$\delta r(x)=q(x_i-s_i)$$

и

$$\delta U=-\int q(x_i-s_i)\log r(x_i)\,dx_i-\lambda\log p(s_i)=0.$$

Варьирование $q$ проводится аналогично. Следовательно, условием минимума будет


Умножая первое на $p(s_i)$, а второе - на $q(s_i)$ и интегрируя по $s_i$, получаем

$$H_3=-\lambda H_1$$
$$H_3=-\mu H_2,$$

или, разрешая относительно $\lambda$ и $\mu$ и делая замену,


Пусть теперь распределения $p(x_i)$ и $q(x_i)$ - гауссовы


Тогда $r(x_i)$ также будет нормально распределено с квадратичной формой $C_{ij}$. Если формы, обратные к данным, суть $a_{ij}$, $b_{ij}$, $c_{ij}$, то

$$c_{ij}=a_{ij}+b_{ij}.$$

Покажем, что эти функции удовлетворяют условию минимизации тогда и только тогда, когда $a_{ij}=Kb_{ij}$, и, следовательно, определяют минимум $H_3$ при этих ограничениях. Имеем


Это должно быть равно

что требует $A_{ij}=\frac{H_1}{H_3}C_{ij}$. В этом случае $ A_{ij}=\frac{H_1}{H_2}B_{ij}$ и оба уравнения обращаются в тождества.

Приложение 7

Обозначим более общий и строгий подход к основным определениям теории связи. Рассмотрим пространство меры вероятности, элементами которого являются упорядоченные пары $(x,y)$. Отождествим переменные $x$ и $y$ с возможными передаваемыми и принятыми сигналами достаточно большой длины $T$. Назовем множество точек, у которых $x$ принадлежат подмножеству $S_1$ полосой по $S_1$, и, аналогично, у которых $y$ принадлежит $S_2$ - полосой по $S_2$. Поделим $x$ и $y$ на неперекрывающиеся измеримые подмножества $X_i$ и $Y_i$, приближающие темп передачи $R$

$$R_1=\frac1T\sum_i P(X_i,Y_i)\log\frac{P(X_i,Y_i)}{P(X_i)P(Y_i)}$$

где

$P(X_i)$- мера вероятности полосы по $X_i$
$P(Y_i)$- мера вероятности полосы по $Y_i$
$P(X_i,Y_i)$- мера вероятности пересечения этих полос.

Дальнейшее деление не может уменьшить $R_1$. Поделим $X_1$ на на $X_1=X_1'+X_1''$ и пусть

$P(X_1,Y_1)=d+e.$

Заменим в этой сумме (для пересечения $X_1$, $Y_1$)

$$(d+e)\log\frac{d+e}{a(b+c)}$$

на

$$d\log\frac{d}{ab}+e\log\frac{e}{ac}.$$

Легко показать, что, при нашем ограничении на $b$, $c$, $d$, $e$,

$$\biggl[\frac{d+e}{b+c}\biggr]^{d+e}\leq\frac{d^d e^e}{b^d c^e}$$

и, следовательно, сумма возрастает. Следовательно, различные возможные деления образуют упорядоченное множество, на котором $R$ монотонно возрастает при уменьшении размеров отдельных частей. Мы можем однозначно определить $R$ как наименьший верхний предел $R_1$ и записать его как

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

Другим понятием, которое необходимо точно определить при абстрактной формулировке является ``темп размерности'', то есть средняя размерность, требуемая для выделения элемента ансамбля за секунду. В случае оганиченного частотного диапазона достаточно $2W$ чисел в секунду. Общее определение может быть дано следующим образом. Пусть $f_\alpha(t)$ - ансамбль функций, а $\rho_T[f_\alpha(t),f_\beta(t)]$ мера ``расстояния'' между $f_\alpha$ и $f_\beta$ за время $T$ (к примеру, в смысле наименьших квадратов на этом интервале). Пусть $N(\epsilon,\delta,T)$ - наименьшее число элементов $f$, которые можно выбрать так, что все элементы ансамбля (за исключением множества меры $\delta$) лежат в пределах $\epsilon$ от как минимум одного из выбранных. Таким образом, мы покрыли пространство вплоть до расстояния $\epsilon$ за исключением множества малой меры $\delta$. Определим темп размерности $\lambda$ ансамбля как тройной предел

$$\lambda=\lim_{\delta\to0}\,\lim_{\epsilon\to0}\,\lim_{T\to\infty} \frac{\log N(\epsilon,\delta,T)}{T\log\epsilon}.$$

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

<< Часть 4. Непрерывный канал | Оглавление |
Астронет