Теоремы шеннона.

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

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

Помехи в передачи информации - свойство отнюдь не только технических систем. Это - вполне обычное дело в быту. Пример был выше; другие примеры - разговор по телефону, в трубке которого "трещит", вождение автомобиля в тумане и т.д. Чаще всего человек вполне прилично справляется с каждой из указанных выше задач, хотя и не всегда отдает себе отчет, как он это делает (т.е. неалгоритмически, а исходя из каких-то ассоциативных связей). Известно, что естественный язык обладает большой избыточностью (в европейских языках - до 70%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение "в словох всо глосноо зомононо боквой о". Здесь 26% символов "поражены", однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством.

Например, каждый фрагмент текста ("предложение") передается трижды, и верным считается та пара фрагментов, которая полностью совпала. Однако, большая избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении. Отсюда следует задача устранения избыточности, или эффективного кодирования. Впервые теоретическое исследование такого рода проблем предпринял К.Шеннон.

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

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

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

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

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

Таким образом, оптимальное кодирование принципиально возможно.

Наиболее важна для практики ситуация, когда М=2, то есть информацию кодируют лишь двумя сигналами 0 и 1.

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

К min (А, В)= I (A) / log 2 M= I (A) ,

здесь I (A) - средняя информация на знак первичного алфавита.

Ограничим себя ситуацией, когда M = 2, т.е. для представления кодов в линии связи используется лишь два типа сигналов - наиболее просто реализуемый вариант. Подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать "0" и "1. Удобство двоичных кодов и в том, что каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log 2 M = 1); тогда из (1), теоремы Шеннона:

и первая теорема Шеннона получает следующую интерпретацию:

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

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

Таблица 1. Варианты сочетаний

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

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

Если имеется источник информации с энтропией Н(х) и канал связи с пропускной способностью С, то если С > H(X), то всегда можно закодировать достаточно длинное сообщение таким образом, что оно будет передано без задержек. Если же, напротив, С < H(X), то передача информации без задержек невозможна.

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

Первая теорема Шеннона (переформулировка).

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

Какие же могут быть особенности вторичного алфавита при кодировании:

Элементарные коды 0 и 1 могут иметь одинаковые длительности (t0=t1) или разные (?).

Длина кода может быть одинаковой для всех знаков первичного алфавита (код равномерный) или различной (неравномерный код)

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

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

Помехи в передачи информации - вполне обычное дело во всех сферах профессиональной деятельности и в быту. Один из примеров был приведен выше, другие примеры - разговор по телефону, в трубке которого «трещит», вождение автомобиля в тумане и т.д. Чаще всего человек вполне справляется с каждой из указанных выше задач, хотя и не всегда отдает себе отчет, как он это делает (т.е. неалгоритмически, а исходя из каких-то ассоциативных связей). Известно, что естественный язык обладает большойизбыточностью (в европейских языках - до 7%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение «в словох всо глосноо зомононо боквой о». Здесь 26% символов «поражены», однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством.

Избыточность могла бы быть использована и при передаче кодированных сообщений в технических системах. Например, каждый фрагмент текста («предложение») передается трижды, и верным считается та пара фрагментов, которая полностью совпала. Однако, большая избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении. Впервые теоретическое исследование эффективного кодирования предпринял К.Шеннон.

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

Задача эффективного кодирования описывается триадой:

Х = {X 4i } - кодирующее устройство - В.

Здесь X, В - соответственно входной и выходной алфавит. Под множеством х i можно понимать любые знаки (буквы, слова, предложения). В - множество, число элементов которого в случае кодирования знаков числами определяется основанием системы счисления (например, т = 2). Кодирующее устройство сопоставляет каждому сообщению х i из Х кодовую комбинацию, составленную из п i символов множества В. Ограничением данной задачи является отсутствие помех. Требуется оценить минимальную среднюю длину кодовой комбинации.

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

n cр = п i Р i (средняя величина).

Этому среднему числу символов алфавита В соответствует максимальная энтропия Нтаx = n ср log т. Для обеспечения передачи информации, содержащейся в сообщениях Х кодовыми комбинациями из В, должно выполняться условие H4mах ≥ Н(х), или п cр log т ≥ - Р i log Р i . В этом случае закодированное сообщение имеет избыточность п cр ≥ H(x) / log т, n min = H(x) / log т.

Коэффициент избыточности

К u = (H max – H (x )) / H max = (n cp – n min) / n cp

Выпишем эти значения в виде табл. 1.8. Имеем:

N min = H (x ) / log2 = 2,85, K u = (2,92 - 2,85) / 2,92 = 0,024,

т.е. код практически не имеет избыточности. Видно, что среднее число двоичных символов стремится к энтропии источника сообщений.

Таблица 1.8 Пример к первой теореме Шеннона

Передача информации

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

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

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

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

Далее в основном ограничим себя ситуацией, когда M = 2 , т.е. для представления кодов в линии связи используется лишь два типа сигналов – с практической точки зрения это наиболее просто реализуемый вариант (например, существование напряжения в проводе (будем называть это импульсом) или его отсутствие (пауза); наличие или отсутствие отверстия на перфокарте или намагниченной области на дискете); подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать "0" и "1", но нужно воспринимать их как буквы, а не цифры. Удобство двоичных кодов и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log 2 M = 1) ; тогда из (1), теоремы Шеннона:

I 1 (A) K (2)

и первая теорема Шеннона получает следующую интерпретацию:

Применение формулы (2) для двоичного кодирования дает:

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

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

Шеннона

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

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

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

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

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

бит/с. (2.19)

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

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

Величина 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 с вероятностями их появления.

x i	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
p i	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 , приблизительно равна *Dx по определению плотности вероятности, причем приближение тем точнее, чем меньше интервал Dx. Если не уточнять значение X в пределах интервала Dx , а заменить его значением x k в начале интервала, то непрерывный ансамбль замениться дискретным, а его энтропия определиться в соответствии с формулой (2.3), в которой вместо вероятности следует подставить плотность вероятности

. (2.25)

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

(2.26)

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

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

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

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

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

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

Здесь 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.16)

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

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

, (2.31)

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

. (2.32)

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

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

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

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

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

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

Дисперсия процесса с равномерным распределением равна дисперсии s 2 нормального распределения при , поскольку . Следовательно . Тогда при заданной дисперсии s 2 дифференциальная энтропия нормального процесса больше энтропии процесса с равномерным распределением на величину = 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 0 , т.е. £ e 0 или .

После того, как введен критерий можно от общего определения 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 , при котором они еще эквивалентны по среднеквадратическому критерию. Таким образом, можно записать

где 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-энтропия гауссовского непрерывного источника

Величина характеризует минимальное отношение мощности сигнала к мощности шума воспроизведения, при котором 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) не зависит от математического ожидания и равна

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

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

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

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

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

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

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

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

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

, (2.49)

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

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