Шеннона

2.4. Основная теорема Шеннона для дискретного канала

 

Определенную в разделе 2.3 скорость передачи I^!(X,Y) от X к Y можно интерпретировать и как скорость передачи информации по дискретному каналу, если под ансамблями X и Y понимать ансамбли сообщений на его входе и выходе

. (2.18)

Из четырех энтропий, фигурирующих в этом выражении, только H(X) - собственная информация передаваемого сообщения, определяемая источником дискретного сообщения и не зависящая от свойств канала. Остальные три энтропии в общем случае зависят как от источника, так и от канала. Отсюда следует, что такой параметр, как скорость передачи не может характеризовать канал как средство передачи.

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

Максимальное количество информации, передаваемое в единицу времени, взятое по всем возможным источникам, называется пропускной способностью канала

бит/с. (2.19)

В качестве примера определим пропускную способность дискретного симметричного канала без памяти, через который в единицу времени передаются u символов из алфавита с объемом m.

Можно записать с учетом (2.18) и (2.19)

. (2.20)

Величина H(Y/X) в данном случае легко находится, поскольку условная вероятность p(y_j/x_i) принимает только два значения

, (2.21)

где p - вероятность того, что при передаче символа x_i будет принят любой другой символ, кроме y_j, т.е. вероятность ошибки. Первое из этих значений возникает с вероятностью p, а второе - 1-p возникает с вероятностью 1-p. К тому же, поскольку рассматривается канал без памяти, результаты приема отдельных символов независимы. Поэтому в соответствии с полученной ранее формулой (2.8) и с учетом (2.21) можно записать .

Следовательно, при этих условиях H(Y/X) не зависит от распределения вероятностей в ансамбле X, а определяется только переходными вероятностями канала.

Таким образом, поскольку в выражении (2.20) только член H(Y) зависит от распределения вероятностей p(X), то максимизировать необходимо именно его.

Максимальное значение H(Y) реализуется тогда, когда все выходные символы y_j равновероятны и независимы, а это условие, в свою очередь, выполняется, когда равновероятны и независимы входные символы x_i. При этом в соответствии с (2.4) . Отсюда пропускная способность канала в расчете на единицу времени

.

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

бит/с.

При p=0,5 пропускная способность двоичного канала C=0, поскольку при такой вероятности ошибки последовательность выходных двоичных символов можно получить, совсем не передавая сигналы по каналу (канал не нужен), а просто выбирая их наудачу (например, бросая монету), т.е. при p=0,5 последовательности символов на входе и на выходе канала независимы. То, что пропускная способность при p=0 (канал без шумов) равна пропускной способности при p=1, объясняется тем, что p=1 означает, что все входные символы при прохождении через канал обязательно преобразуются под воздействием помех в противоположные. Следовательно, чтобы правильно восстановить на выходе входное сообщение, достаточно инвертировать все выходные символы.

Пусть, например, по каналу передается сообщение, формируемое из 8 символов x_i с вероятностями их появления.

 

xi	x1	x2	x3	x4	x5	x6	x7	x8
pi	0,20	0,15	0,20	0,15	0,10	0,10	0,05	0,05

Канал имеет полосу пропускания, позволяющую передавать элементы сообщения со средней длительностью t_и = 0,5 мс. Шум в канале отсутствует.

Тогда, поскольку шум отсутствует, энтропия шума H(Y/X) из формулы (2.18) равна нулю. Тогда из этой же формулы . В соответствии с (2.4) , т.е. . Канал способен пропускать в единицу времени символов. Следовательно С = 3*2000 = 6000 бит/с. Скорость передачи определяется по формуле (2.18) . Величина H(Y) находится по определению энтропии (2.3) =0,464+0,411+0,464+0,411+0,332+0,332+

+0,216+0,216=2,846 бит/символ. Тогда скорость передачи = 2000*2,846 = 5692 бит/с.

Пропускная способность канала характеризует потенциальные возможности канала по передаче информации. Они раскрываются в фундаментальной теореме теории информации, известной как основная теорема Шеннона.

Применительно к дискретному источнику и каналу она формулируется так: «Если производительность источника сообщений меньше пропускной способности С канала , то существует способ кодирования (преобразования сообщения в сигнал на входе) и декодирования (преобразования сигнала в сообщение на выходе канала), при котором вероятность ошибочного декодирования может быть сколь угодно малой. Если , то таких способов не существует». Таким образом, согласно теореме Шеннона, конечная величина С - это предельное значение скорости безошибочной передачи информации по каналу.

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

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

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

Так как по определению скорость передачи информации не превышает значения пропускной способности канала, то неравенство является необходимым условием для точной передачи сообщения. Но является ли оно достаточным? Вопрос сводится к тому, можно ли установить такое соответствие (код) между сообщением X и сигналом Y, чтобы вся информация, полученная на выходе канала о сигнале Y, была в то же время информацией о сообщении X?

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

В общем случае в канале имеются помехи, сигнал Y принимается с ошибками, так что скорость передачи информации по каналу меньше производительности кодера . Отсюда с учетом подчеркнутого выше (2.22) утверждения следует, что

. (2.23)

Это значит, что производительность кодера, на выходе которого формируется сигнал Y, должна быть выше производительности источника, на выходе которого формируется сообщение X. Следовательно, Y содержит кроме информации об X дополнительную собственную информацию. Часть информации о сигнале Y в канале теряется. Вопрос сводится к следующему: можно ли осуществить кодирование так, чтобы терялась только дополнительная, избыточная часть собственной информации Y, а информация об X сохранялась? Теорема Шеннона дает на этот вопрос почти положительный ответ, с той лишь поправкой, что скорость потери информации не равна в точности нулю, но может быть сделана сколь угодно малой. Соответственно, сколь угодно малой может быть сделана вероятность ошибочного декодирования. При этом, чем меньше допустимая вероятность ошибочного декодирования, тем сложнее должен быть код.

Верхняя граница средней вероятности ошибочного декодирования по всем возможным кодам определяется выражением

, (2.24)

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

Из выражения (2.24) следует, что верность передачи тем выше, чем больше Т, т.е. чем длиннее кодируемый отрезок сообщения, а, следовательно, и больше задержка при приеме информации, и чем менее эффективно используется пропускная способность канала, т.е. чем больше разность , называемая иногда запасом пропускной способности. Из этого следует также, что существует возможность обмена между верностью, величиной задержки и эффективностью системы. С увеличением Т существенно возрастает сложность кодирования и декодирования (число операций, число элементов и стоимость аппаратуры). Поэтому чаще всего на практике предпочитают иметь умеренное значение Т, которое, кстати, не во всех системах можно произвольно увеличивать, и добиваются повышения верности за счет менее полного использования пропускной способности канала.

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

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

 

2.5. Энтропийные характеристики непрерывных информационных объектов

 

Обобщим понятия энтропии и взаимной информации на ансамбли непрерывных информационных объектов.

Пусть X - случайная величина - сечение или отсчет случайного процесса, определенная в некоторой непрерывной области. Ее распределение вероятностей характеризуется плотностью вероятности . Разобьем область значений X на небольшие интервалы Dx. Вероятность того, что значение X лежит в интервале x_k<X< x_k+Dx, приблизительно равна * Dx по определению плотности вероятности, причем приближение тем точнее, чем меньше интервал Dx. Если не уточнять значение X в пределах интервала Dx, а заменить его значением x_k в начале интервала, то непрерывный ансамбль замениться дискретным, а его энтропия определиться в соответствии с формулой (2.3), в которой вместо вероятности следует подставить плотность вероятности

. (2.25)

Теперь увеличим точность определения значения X, уменьшая Dx. В пределе при Dx®0 получается энтропия непрерывной случайной величины X, т.е.

(2.26)

Анализируя полученное выражение, приходим к выводу о том, что энтропия непрерывного сигнала X стремиться к бесконечности при неограниченном уменьшении величины Dx.

Первый член правой части выражения (2.26) является конечным и полностью определяется статистикой значений сигнала X. Это та часть энтропии непрерывного сигнала, которая зависит от функции плотности вероятности . Эту величину называют дифференциальной энтропией и обозначают

. (2.27)

Второй член правой части выражения (2.26) зависит лишь от интервала неопределенности Dx и при увеличении или уменьшении величины Dx энтропия соответственно монотонно убывает или возрастает.

Дифференциальная энтропия h(X) обладает свойствами во многом аналогичными свойствам энтропии дискретных сигналов H(X). Но есть и различия.

Дифференциальную энтропию, в отличие от обычной энтропии дискретного ансамбля, нельзя рассматривать как меру собственной информации. Она не обладает многими свойствами обычной энтропии, в частности, может принимать и отрицательные значения. Информационный смысл имеет не сама дифференциальная энтропия, а разность двух дифференциальных энтропий, чем и объясняется ее название. Дифференциальная энтропия непрерывного сигнала не изменится, если к сигналу прибавить некую неслучайную величину, т.е. дифференциальная энтропия не зависит от постоянной составляющей сигнала или, другими словами, от математического ожидания соответствующей случайной величины.

Определим далее взаимную информацию между двумя непрерывными случайными процессами X(t) и Y(t). Для этого воспользуемся приведенным выше предельным переходом и аналогией с формулой (2.17), полученной для дискретных ансамблей. Тогда получим

. (2.28)

Здесь h(X) и h(Y) - дифференциальные энтропии процессов X(t) и Y(t), определяемые в соответствии с (2.27), а h(X/Y) - условная дифференциальная энтропия отсчета X(t) при известном отсчете Y(t) и h(Y/X) - условная дифференциальная энтропия отсчета Y(t) при известном отсчете X(t). Приведенные в (2.28) дифференциальные энтропии имеют тот же смысл, что и в (2.17), т.е., например, h(Y/X) представляет собой дифференциальную энтропию шума в канале на один отсчет помехи. Условная дифференциальная энтропия h(X/Y) может быть найдена из выражения

. (2.29)

Определение взаимной информации через дифференциальные энтропии позволяет продолжить аналогии с дискретным случаем и определить скорость передачи по непрерывному каналу с дискретным временем по формуле, аналогичной (2.16)

, (2.30)

где u - число отсчетов сигнала, передаваемое по каналу в единицу времени.

В качестве примера, который будет использоваться и в дальнейшем, найдем дифференциальную энтропию случайной величины X с нормальным распределением вероятности, т.е.

, (2.31)

где a - математическое ожидание, s² - дисперсия X. Подставив (2.31) в (2.27),

получим

. (2.32)

В выражении (2.32) первый интеграл по общему свойству плотности вероятности равен 1, второй - по определению дисперсии равен s².

Тогда

. (2.33)

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

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

Сравним дифференциальные энтропии нормального процесса и процесса с равномерным распределением на интервале (-а, а), если их дисперсии одинаковы.

Дифференциальная энтропия процесса с нормальным распределением находится по формуле (2.33) .

Дифференциальную энтропию процесса с равномерным распределением можно найти из общего определения дифференциальной энтропии (2.27) .

Дисперсия процесса с равномерным распределением равна дисперсии s² нормального распределения при , поскольку . Следовательно . Тогда при заданной дисперсии s² дифференциальная энтропия нормального процесса больше энтропии процесса с равномерным распределением на величину = 0,3 бита и не зависит от величины дисперсии.

Если не накладывать ограничений на дисперсию сигнала, то дифференциальная энтропия достигает максимума, когда значения сигнала распределены по равномерному закону.

Продолжим рассмотрение для случая, когда по каналу передается сигнал X(t), представляющий собой нормальный случайный процесс с нулевым математическим ожиданием и дисперсией , ав канале действует независимый от сигнала аддитивный нормальный шум N(t) с нулевым математическим ожиданием и дисперсией . Найдем дифференциальные энтропии h(X) входногои h(Y) выходного сигналов и условные дифференциальные энтропии h(Y/X) и h(X/Y). В соответствии с выражением (2.33) . Выходной сигнал Y(t) в силу аддитивности шума в канале Y(t) = X(t) + N(t). Так как X(t) и N(t) независимы и имеют нормальное распределение, Y(t) будет также распределен по нормальному закону с дисперсией . Тогда в соответствии с (2.33) .

Условная дифференциальная энтропия Y(t) при известном X(t) определяется энтропией шума в канале (2.17) . Условная дифференциальная энтропия отсчета X(t) при известном отсчете Y(t) находится с помощью выражения, аналогичного (2.17)

При этом среднее за один отсчет сигнала количество информации, переданное по каналу, определяется по формуле (2.28) и после всех подстановок полученных выражений для энтропий и преобразований равно: .

Второй член выражения (2.26) стремиться к бесконечности. Это значит, что собственная информация любой непрерывной случайной величины бесконечно велика. Смысл этого вывода заключается в том, что для передачи непрерывного сообщения с абсолютной точностью нужно было бы передать бесконечно большое количество информации, что невозможно сделать за конечное время, пользуясь каналом с конечной пропускной способностью.

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

Пусть допустимая неточность измеряется некоторым малым параметром e. То минимальное количество информации, которое требуется передать по каналу для воспроизведения непрерывного сообщения с неточностью не более e называется e - энтропией. (2.35)

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

При передаче дискретных сообщений верность передачи определяется вероятностью правильного приема или вероятностью ошибки. Такое определение верности можно распространить и на непрерывные сообщения, если понятие «правильно» заменить понятием «эквивалентно». Тогда под верностью передачи непрерывных сообщений будет пониматься вероятность того, что принятое сообщение эквивалентно переданному.

Чтобы пользоваться таким определением верности, нужно установить критерий эквивалентности. Наиболее часто применяемым методом определения эквивалентности служит критерий среднего квадрата разности между принятым и переданным сообщениями.

Если обозначить переданное непрерывное сообщение X(t), а принятое - Y(t), то случайный процесс e(t) = Y(t) - X(t) называется шумом воспроизведения. Сообщения будем называть эквивалентными, если среднеквадратическое отклонение не превышает заданной величины e₀, т.е. £ e₀ или .

После того, как введен критерий можно от общего определения e-энтропии перейти к более конкретному ее определению. Взаимная информация I(X,Y) между двумя не тождественно равными непрерывными сообщениями в общем случае конечна. Из (2.28) следует . Дифференциальная энтропия h(X) полностью определяется плотностью вероятности w(x). Условная дифференциальная энтропия h(X/Y) в свою очередь зависит от условной плотности вероятности w(x/y). Варьируя w(x/y) можно добиться минимального (2.35) значения величины I(X,Y) при заданных требованиях к точности e воспроизведения.

Тогда можно определить e-энтропию непрерывной величины X как минимальное количество информации, необходимое для того, чтобы непрерывная величина Y воспроизводила X со среднеквадратической погрешностью, не превышающей заданной величины e. Или, другими словами, e-энтропией называется минимальное количество информации, содержащееся в Y относительно X, при котором они еще эквивалентны по среднеквадратическому критерию. Таким образом, можно записать

, (2.36)

где min или max берется по всем w(x/y) для которых .

Продолжим начатый в предыдущем параграфе пример, т.е. положим, что источник непрерывного сообщения - гауссовский, т.е. сообщение X(t) - стационарный гауссовский процесс с заданной мощностью P_x. Поскольку X(t) = Y(t) - e(t), то условная дифференциальная энтропия h(X/Y) при заданном X(t) полностью определяется шумом воспроизведения e(t). Поэтому . На основании утверждения (2.34) и формулы (2.33) можно записать

, (2.37)

где - фиксированная дисперсия шума воспроизведения. При заданной дисперсии сообщения дифференциальная энтропия источника на основании (2.33)

. (2.38)

Следовательно, e-энтропия гауссовского непрерывного источника

. (2.39)

Величина характеризует минимальное отношение мощности сигнала к мощности шума воспроизведения, при котором X(t) и Y(t) еще эквивалентны.

e-энтропия, полученная в соответствии с выражением (2.39) с учетом утверждения (2.34) может быть названа максимальной e-энтропией непрерывного сигнала и этот максимум достигается при нормальном распределении сигнала X(t), т.е.

. (2.40)

После получения значения максимальной e-энтропии (2.40) можно определить избыточность непрерывного стационарного источника по формуле, аналогичной (2.5) для дискретного источника

. (2.41)

Производительность источника непрерывных сообщений можно определить как количество информации, которое необходимо передать в единицу времени, чтобы восстановить сообщение при заданном критерии эквивалентности.

Если источник выдает независимые отсчеты сообщения дискретно во времени со средней скоростью n, то его e-производительность по аналогии с (2.6) может быть найдена как

. (2.42)

Для источников непрерывных сообщений, ограниченных частотной полосой F_C, согласно теореме Котельникова, шаг дискретизации , т.е. необходимое число отсчетов в секунду равно 2F_C.

Тогда для гауссовского источника с учетом (2.39) e-производительность равна

. (2.43)

Сопоставим e-производительность источника с нормальным распределением с e-производительностью источника с равномерным распределением при условии, что их дисперсии одинаковы, а дисперсия шума воспроизведения фиксирована. В соответствии с (2.43) , а в соответствии с (2.36) , где - дифференциальная энтропия источника,а - энтропия шума воспроизведения, которая, как следует из выражения (2.37), равна . Для нормального процесса - . Ранее получено, что , тогда для процесса с равномерным распределением - . Разность между ними .

Таким образом, при одинаковых дисперсиях e-производительность источника с нормальным распределением больше e-производительности источника с равномерным распределением на фиксированную величину.

Количество информации, выдаваемое гауссовским источником за время T_C, равно

, (2.44)

что с точностью до смысла совпадает с выражением для объема сигнала.

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

. (2.45)

Для примера найдем пропускную способность непрерывного канала без памяти, имеющего полосу пропускания шириной F_K, если средняя мощность (дисперсия) сигнала не превышает некоторой заданной величины P_C, Пусть в канале действует аддитивный гауссовский шум с мощностью (дисперсией) в полосе частот канала равной P_Ш. Отсчеты входного X и выходного Y сигналов связаны равенством Y = X + N, поскольку шум аддитивный, а N - отсчет шума в канале. Так как N по условиям задачи имеет нормальное распределение с нулевым математическим ожиданием, то условная плотность вероятности w(y/x) при фиксированном x будет также нормальной с математически ожиданием, равным x, и дисперсией Р_Ш, а дифференциальная энтропия нормального распределения w(y/x) в соответствии с (2.33) не зависит от математического ожидания и равна

. (2.46)

Поэтому для нахождения пропускной способности такого канала следует найти такую плотность вероятности w(x) при которой максимизируется h(Y).

Поскольку X и N - независимые случайные гауссовские величины, то дисперсия Y будет равна сумме их дисперсий (1.29), т.е. P_C + P_Ш. Тогда

. (2.47)

Переходя к пропускной способности в расчете на секунду, заметим, что информация, переданная за несколько отсчетов, максимальна в том случае, когда отсчеты независимы. Для гауссовских процессов независимость означает отсутствие корреляции. Из теоремы Котельникова следует, что отсчеты будут взаимно некоррелированы, если они взяты через интервал . Поэтому пропускная способность такого канала

. (2.48)

Это выражение иногда называют формулой Шеннона.

Этот весьма важный результат указывает теоретический предел скорости передачи информации по каналу при ограниченной средней мощности передаваемых сигналов и при наличии аддитивной помехи в виде белого шума. Пропускная способность, определяемая формулой (2.48), есть предельная скорость передачи информации по каналу со сколь угодно редкими ошибками, достигаемая путем определенных преобразований и соответствующего кодирования. Для обеспечения этой скорости передаваемый сигнал должен обладать свойствами белого шума. Это должен быть случайный нормально распределенный и слабо коррелированный, имеющий широкий равномерный энергетический спектр, сигнал. Если распределение отличается от нормального, то скорость передачи информации будет меньше пропускной способности канала.

Так как энергетический спектр помехи типа белого шума равномерен в полосе частот от 0 до , мощность в формуле (2.48) можно выразить через удельную мощность на единицу частоты. Тогда формула (2.48) примет вид . При расширении полосы пропускания канала пропускная способность увеличивается, но стремится к конечному пределу при измерении в битах. Это ограничение, вносимое помехой с уровнем мощности , которое не может быть превышено без увеличения мощности сигнала.

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

Формула Шеннона устанавливает зависимость пропускной способности рассматриваемого канала от таких его технических характеристик, как ширина полосы пропускания канала и отношения сигнал/шум в канале. Кроме того, она указывает на возможность обмена полосы пропускания на мощность и наоборот. Однако, поскольку пропускная способность зависит от полосы линейно, а от отношения сигнал/шум - по логарифмическому закону, компенсировать возможное сокращение полосы пропускания увеличением мощности сигнала, как правило, невыгодно. Более эффективным оказывается обратный обмен мощности сигнала на полосу пропускания.

Максимальный объем информации, который можно передать в среднем по каналу с пропускной способностью, определяемой по (2.48) за время действия канала Т_К определяется выражением

, (2.49)

которое при с точностью до смысла совпадает с выражением для объема канала.

Существует основная теорема Шеннона и для непрерывного канала. Она формулируется следующим образом «Если при заданном критерии эквивалентности сообщений источника его e-производительность меньше пропускной способности канала, т.е. , то существует способ кодирования и декодирования при котором неточность воспроизведения сколь угодно близка к . При такого способа не существует.» (2.50)