Количественная мера информации.

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

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

Неожиданность характеризуется вероятностью, которая и закладывается в информационную меру.

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

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

Посмотрим на данную пример с позиции количества информации .итак, имеем источник информации ящики с шарами. Первоначально неопределенность о шарах характеризовалась вероятностью 0,5. Далее источник "заговорил" и выдал информацию; мы вытащили шар. Далее все стало определено с вероятностью 1. Степень уменьшения неопределенности о событии в результате опыта логично принять за количественную меру информации. В нашем примере это будет 1/0,5.

Теперь пример более сложный. Известно, что размер детали может быть 120,121,122, . . .,180 мм., то есть, имеет одно из 61-ого значений. Априорная вероятность того, что размер детали i мм равна 1/61.

У нас имеется весьма несовершенный измерительный инструмент позволяющий измерить деталь с точностью +5,-5 мм. В результате измерения получили размер 130 мм. Но фактически он может быть 125,126, . . .,135 мм.; всего 11 значений. В результате опыта остается неопределенность, которая характеризуется апостериорной вероятностью 1/11. Степень уменьшения неопределенности будет (1/11):( 1/61). Как и выше это отношение и есть количество информации.

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

. (1)

В первом примере 1 бит информации; во втором 2,46 бит информации. Бит – одна двоичная единица информации.

Теперь обратимся к реальному источнику информации, который представляет собой множество независимых событий (сообщений) с различными априорными вероятностями . Это множество представляет данные о параметрах объекта и есть информация о нем. Обычно, после выдачи сообщения источником, становится достоверно известно, какой параметр выдан. Апостериорная вероятность равна 1. Количество информации, содержащееся в каждом событии, будет равно

. (2)

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

. (3)

Или учитывая свойства логарифмической функции

. (4)

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

. (5)

Не трудно видеть , что если одна из вероятностей равно нулю, то вторая равна 1, а выражение энтропии при этом даст нуль.

Построим график зависимости энтропии от (рис.1).

Обратим внимание на то, что энтропия максимальна при вероятности равной 0,5 и всегда положительна.

Рис.1

Первое свойство энтропии. Энтропия максимальна при равновероятных событиях в источнике. В нашем примере двоичного источника эта величина равна 1. Если источник не двоичный и содержит N слов, то максимальная энтропия.

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

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

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

. (6)

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

Рассмотрим первый случай независимых ансамблей, появление сообщения ни в коей мере не определяется . Запишем выражение для энтропии:

, (7)

здесь - число сообщений в ансамблях.

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

, (8)

где и определяются по известным формулам.

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

. (9)

Учитывая это, найдем выражение для энтропии. Преобразование идет следующим образом:

. (10)

Учитывая равенство 1 суммы всех вероятностей событий, первая двойная сумма в последнем выражении дает энтропию источника X, H(x).

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

. (11)

Аналогичным образом можно доказать, что .

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

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

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

Рис. 2

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

. (12)

Усреднив это количество по всем возможным последующим символам, получим частную энтропию при условии, что предыдущем всегда выдается символ :

. (13)

Еще раз, усреднив эту частную энтропию по всем предыдущим символам, получим окончательный результат:

. (14)

Индекс 2 в обозначении энтропии свидетельствует о том , что статистическая связь распространяется только на два соседних символа.

Остановимся на свойствах энтропии эргодического источник.

-При независимости символов в источнике , формула (14) упрощается и приводится к обычному виду (4).

-Наличие статистических (вероятностных) связей между символами источника всегда приводит к уменьшению энтропии, .

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

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

. (15)

Величина находится в диапазоне от 0 до 1.

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

Рассмотрим пример. Источник – буквы русского алфавита, всего их 32. Определим максимальную энтропию: бит/сообщение.

Так как между буквами есть статистическая связь и вероятности их появления в тексте далеко не одинаковы, реальная энтропия равна 3 бит/сообщение. Отсюда избыточность .

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

. (16)

Итак, подведем итог. Характеристиками эргодического источника информации являются следующие:

количество информации в каждом знаке,

энтропия,

избыточность,

производительность.

Необходимо заметить, что сильной стороной введенной меры количества информации и , разумеется, всех характеристик является универсальность. Все введенные выше понятия применимы к любому виду информации: социологической, технической и т. д.. Слабая же сторона меры в том, что в ней не отражена значимость информации, ее ценность. Информация о выигрыше в лотерею авторучки и автомобиля одинакова по значимости.

1.2. Информационные характеристики канала

Вспомним о том, что информация передается по каналу связи. Мы ранее ввели информационные характеристики источника информации, а теперь введем информационные характеристики канала. Представим ситуацию так , как показано на рис. 1.

На входе канала присутствует входной алфавит, состоящий из множества знаков , а на выходе - .

Рис. 2

Связи между буквами алфавита принято оценивать условными вероятностями, например, вероятность приема при условии что передана . Это вероятность правильного приема. Точно также можно ввести условные вероятности ошибочных приемов, например, . Причины появления этих ненулевых вероятностей - помехи, от которых не свободен ни один из реальных каналов. Обратим внимание на то, что n и m , количество знаков (букв) в передаваемом и принимаемом массиве не обязательно равны между собой. На основании этой модели вводятся дальнейшие определения.

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

Здесь – вероятность ошибочного приема. Если эта вероятность не зависит от того, какие знаки передавались до данного символа, такой канал называется "канал без памяти". В качестве примера ниже на рис.3 показан граф симметричного двоичного канала без памяти.

Далее допустим , что алфавит на выходе канала содержит дополнительный символ, который появляется тогда, когда декодер приемника не может опознать переданный символ. В этом случае он вырабатывает отказ от решения. Это положение называется стиранием. Такой канал называется каналом без памяти со стиранием и его граф показан на рис. 4. Положение "стирание" здесь обозначено знаком вопроса.

Рис. 4.

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

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

.

Заметим, что все вероятности канальной матрицы образуют полную группу событий и их сумма равна 1: .

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

,

где - время задержки сигнала;

- множитель ослабления, учитывающий изменение уровня сигнала;

- входной сигнал;

- аддитивная помеха, складывающаяся с сигналом.

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

.

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

.

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

Высокая скорость передачи информации – основное требование, предъявляемое к каналам связи. Однако имеется ряд причин ограничивающих скорость.

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

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

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

.

Разберем небольшой пример. Имеем двоичный канал, число сообщений 2. Согласно свойству энтропии, она максимальна при равных вероятностях сообщений. При этом . Сигналы для передачи – прямоугольные импульсы длительностью (рис.5).

Для передачи по каналу такого сигнала требуется полоса пропускания ; чем короче сигнал, тем шире полоса.

1.3.Теоремы Шеннона для канала без помех.

На основании производительности источника и пропускной способности канала основана первая теорема К. Шеннона для канала без помех.

Если производительность источника меньше пропускной способности канала , , где - сколь угодно малая величина, то по такому каналу можно передать все сообщения источника.

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

Рис. 6

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

Существует следующее понятие: "статистическое или оптимальное кодирование". Оно позволяет приблизить скорость передачи к пропускной способности канала и, следовательно, обеспечить наилучшее использование канала без помех. Рассмотрим основные принципы такого кодирования на примере источника независимых сообщений, который необходимо согласовать с двоичным каналом. Вспомним принцип кодирования: это запись сообщений в виде двоичных чисел. Каждые 0 и 1 такого числа – электрические сигналы. Предположим, что длительность такого элементарного сигнала . Для каждого сообщения представляется сигналом ,которое представляет собой двоичное число имеющее разрядов. Таким образом, длительность сигнала будет равна . Сколько сообщений, столько сигналов и столько же длительностей.

Усреднив длительности, получим среднюю продолжительность сигнала:

.

Далее определим скорость передачи :

.

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

.

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

.

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

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

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

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

1.В первых двух столбцах располагают сообщения по убыванию их априорных вероятностей.

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

3.Последующие вспомогательные столбцы записываются по такому же принципу. Последний вспомогательный столбец представлен "1".

4. По данным таблице строится граф с вершиной "1". Ребра графа отражают вероятности, причем ребру с большей вероятностью присваивается значение "1", а с меньшей – "0".

5.Код сообщения получим проходя по ребрам от сообщения к вершине и фиксируя присвоенные значения.

Рассмотрим все это на примере источника информации состоящего из 4-х сообщении. Начнем заполнять таблицу.

 

Сообщение		Вспомогательные столбцы	Код
	0.6	0.6	0.6
	0.15	0.25	0.4
Сумма	0.13	0.15
Сумма	0.12

 

По данным таблицы построим граф.

 

 

 

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

 

1.4. Пропускная способность канала с помехами.

Теорема Шеннона.

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

Определим энтропию сигнала в таком канале.

Обозначим P(х_i) – априорную вероятность передаваемого сигнала. Допустим, произошла передача и принят сигнал , который позволяет судить о переданом. Введем апостериорную вероятность P(x_i/y_j). По сути мы провели опыт (передачу сигнала) и две вероятности: доопытную (априорную ) P(х_i) и послеопытную (апостериорную) P(x_i/y_j). Для понимания их смысла полезно обратится к модулю 2. Далее воспользуемся определением меры количества информации, как уменьшением меры неопределенности и определим ее при данных условиях:

 

.

 

 

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

 

Проведем анализ этого выражения, для чего воспользуемся теоремами статистики:

 

после чего получаем

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

 

, или

.

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

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

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

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

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

 

, (бит/знак*с).

Величина -пропускная способность канала.

Пропускная способность канала зависит от следующих факторов:

1. от статических свойств источника,

2. от интенсивности помех,

3. от полосы пропускания , которая определяет среднее время передачи сигнала.

Итак, мы ввели информационные характеристики канала с помехами.

В качестве примера найдем энтропию и пропускную способность двоичного канала. Его граф показан на рис.5.

 

Рис.5

Предполагаем , что длительность нулевых и единичных сигналов равны .

Тогда

 

.

Согласно свойству энтропии и

Найдем информационные потери, ненадежность:

 

.

Выше обозначено: - ошибочный переход, - правильный переход. После чего получим

 

 

Если p₀=0, то и при p₀=0.5 , то есть передача невозможна.

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

Шеннон впервые указал на то, что можно сделать. Ему принадлежит идея помехоустойчивого кода. Ранее, до Шеннона, повышение помехоустойчивости достигалось многократной передачи одной и той же информации и вынесением решения по большинству голосов. Это было крайне не рационально для канала, так как для передачи требовалось большее время. Теорема Шеннона, хотя и не конструктивна, утверждает что достоверность можно повысить другим методом – путем построения помехоустойчивого кода. В дальнейшем это положение было подробно разработано с применением математического аппарата комбинаторики и в теории связи появилось научное направление "помехоустойчивое кодирование". В данном разделе мы не будем его подробно рассматривать, а ограничимся изучение помехоустойчивого кода с проверкой на четность. Формирование этого кода идет по схеме показанной на рис.2.

 

 

 

Рис. 2

Кодер канала формирует помехоустойчивый код по первичному коду сообщения. Рассмотрим как это делается. Допустим первичный код представлен r разрядами (в данном на рис.3 примере 6 разрядов).

 

 

 

 

Рис.3

В комбинацию кода вводится еще один разряд k, который называется контрольным. Его значение определяется по очень простому правилу: количество единиц во всем кодовом слове должно быть четным. Например, r разрядов 011101, контрольный разряд k равен 0; r – 001110, k – 1. Это правило формирования кода известно в приемнике и его задача проверить выполнение условия. Если количество единиц четное, ошибок нет и информация поступает получателю. Если же нет, приемник вырабатывает сигнал ошибки, по которому запрашивается повторная передача. Такое правило позволяет обнаружить однократные ошибки. Существуют более сложные помехоустойчивые коды не только обнаруживающие, но и исправляющие ошибки.

Информационные характеристики непрерывных

источников и каналов связи.

 

 

.

12

---

Дата добавления: 2019-07-26; просмотров: 856;

---