Определение количества информации

ИССЛЕДОВАННИЕ ДИСКРЕТНЫХ ИСТОЧНИКОВ ИНФОРМАЦИИ

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

Подготовка к выполнению работы

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

Общие сведения из теории информации

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

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

Источник дискретных сообщений в общем случае характеризуется ансамблем X = {x₁, ..., x_i, ..., x_Ni} сообщений, представляющих собой конечное число символов x_i. Совокупность символов x₁,...,x_i,..., x_Ni называется алфавитом источника сообщений, а число различных символов N_i - является объёмом алфавита источника сообщений. Для полного описания источника сообщений необходимо задать вероятности появления символов P(x₁), ..., P(x_i), ..., P(x_Ni), причём их сумма равна 1. В частном случае символами алфавита источника могут быть буквы.

Кодер источника, который иногда может и отсутствовать, служит для представления сообщений в более удобной для передачи и компактной форме без потери информации. Кодер источника имеет свой алфавит G = {g_k}, k = 1, 2, ..., N_k, где N_k - объём алфавита кодера источника. Например, русские буквы алфавита источника могут в кодере источника перекодироваться в цифры десятичной системы счисления с символами (буквами) алфавита {0, 1, 2, ..., 9} с объёмом N_k = 10, или в двоичный код с алфавитом {0, 1} и, следовательно, с объёмом алфавита N_k = 2 (например первичный код МТК-2,). С помощью кодера источника возможно устранение избыточности источника сообщений путём применения эффективного статистического кодирования.

Кодер канала может иметь свой алфавит q = {q_s}, s = 1, 2, ..., N_s. С помощью кодера канала может вводиться избыточность при применении корректирующих кодов, в целях повышения помехозащищённости системы связи. Таким образом, в процессе преобразования сообщения в сигнал операция кодирования позволяет в итоге уменьшить влияние различных помех и искажений на передачу сообщений.

Итак, в процессе кодирования сообщений могут выполняться следующие операции:

- преобразование сообщений из одной формы в другую, например, непрерывных в дискретные (натуральное, первичное кодирование);

- устранение естественной избыточности источника сообщений (эффективное или статистическое кодирование);

- введение специально рассчитанной искусственной избыточности в сообщение (помехоустойчивое кодирование).

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

Определение количества информации

Комбинаторное определение количества информации дано американским инженером Р. Хартли.

До получения сведений о состоянии системы имеется ап­риорная неопределенность ее состояния. Сведения позволяют снять эту неопределенность, то есть определить состояние системы. Поэтому количество информации можно определить как меру снятой неопределенности, которая растет с ростом числа состояний системы.

Количественная мера информации устанавливается сле­дующими аксиомами.

Аксиома 1. Количество информации, необходимое для снятия неопределенности состояния системы, представляет собой монотонно возрастающую функцию числа состояний системы.

В качестве количественной меры информации можно вы­брать непосредственно число состояний системы N, которое является единственной характеристикой множества X.

Однако такое определение не удобно с точки зрения его практического применения. Поэтому в теории информации вводится несколько иная количественная мера информации, которая является функцией N. Вид указанной функции по­зволяет установить аксиома 2.

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

Если для снятия неопределенности первой подсистемы необходимо количество информации, равное I(N₁), а для второй подсистемы количество информации, равное I(N₂), то для снятия неопределенности сложной системы необходи­мо количество информации, равное

I(N₁N₂) = I(N₁) + I(N₂) ,

где N₁ — число состояний первой подсистемы; N₂ — число состояний второй подсистемы; N₁N₂—число состояний слож­ной системы.

Единственным решением полученного функционального уравнения является логарифмическая функция:

I(N)=К log_а N, (11.1)

которая определяет количество информации как логарифм числа состояний системы. Произвольный коэффициент К выбирается равным единице, а основание логарифма а опреде­ляет единицу измерения количества информации. В зависи­мости от значения а единицы измерения называются двоич­ными (а=2), троичными (а=3) и в общем случае a-ичными. В дальнейшем под символом log будем понимать двоичный логарифм. Двоичная единица иногда обозначается bit.

Каждое передаваемое слово из п букв, записанное в ал­фавите, содержащем N букв, можно рассматривать как отдельное «укрупненное» состояние источника сообщений. Всего таких состояний (слов) будет Nⁿ. Тогда количество информации, которое несет слово из п букв, равно I=log_aNⁿ=nlog_aN. Отсюда следует, что одна буква несет log_aN а-ичных единиц информации.

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

К. Шеннон учёл требуемую зависимость и предложил определять количество информации, содержащееся в сообщении x_i (i = 1, 2, ..., N)и относящееся к выбору данной буквы x_i алфавита источника, в виде:

, (11.2)

где P(x_i)- вероятность появления сообщения x_i, причём сумма всех P(x_i) = 1. Величина I(x_i) называется собственной информацией сообщения x_i. Как следует из (11.2), количество информации, содержащееся в сообщении, тем больше, чем меньше вероятность этого сообщения. Такая зависимость соответствует интуитивным представлениям об информации. Действительно, сообщения, ожидаемые с большей вероятностью, легко угадываются получателем, а достоверные сообщения, вероятность которых равна 1, вообще не содержат информации, так как всегда могут быть предсказаны точно (очевидно, если P(x_i) = 1, то I(x_i) = 0). Наоборот, сообщения, являющиеся сенсациями, имеют малую вероятность появления и их трудно предсказать, поэтому они содержат больше информации.

Количество информации является случайной величиной, принимающей значение I(x_i) с вероятностью P(x_i) в зависимости от появления буквы x_i в сообщении источника. Однако при передаче больших массивов сообщений важно не количество информации в одном конкретном символе I(x_i), а количество информации, усреднённое по всем возможным сообщениям, содержащим n символов. Такой мерой количества информации является математическое ожидание (среднее значение) случайной величины I(x_i), содержащей n символов (букв), усреднённое по всему ансамблю X:

. (11.3)

Это соотношение носит название формулы Шеннона. Для равновероятных сообщений (P(x_i) = 1/N) меры информации по Хартли (11.1) и по Шеннону (11.3) совпадают:

.

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

Из определения собственной информации и свойств логарифма непосредственно вытекают следующие свойства собственной информации.

1. Неотрицательность: .

2. Монотонность: если x₁, x₂ÎX, P(x₁) ≥ P(x₂), то I(x₁) ≤ I(x₂).

3. Аддитивность. Для независимых сообщений x₁, x₂, ..., x_n имеет место равенство .

Энтропия

Определенная выше мера информации, содержащейся в сообщении, представляет собой случайную величину. Собственная информация сообщения x_i дискретного ансамбля X = {x_i, P(x_i)} характеризует "информативность" или "степень неожиданности" конкретного сообщения. Естественно, среднее значение или математическое ожидание этой величины по ансамблю X = {x_i, P(x_i)} будет характеристикой информативности всего ансамбля.

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

Энтропией дискретного ансамбля X = {x_i, P(x_i)} называется величина

.

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

1. .

2. . Равенство имеет место в том и только в том случае, когда элементы ансамбля X равновероятны.

3. Если для двух ансамблей X и Y распределения вероятностей представляют собой одинаковые наборы чисел (отличаются только порядком следования элементов), то H(X)= H(Y).

4. Если ансамбли X и Y независимы, то H(XY)= H(X) + H(Y).

5. Энтропия – выпуклая ∩ функция распределения вероятностей на элементах ансамбля X .

6. Пусть X = {x_i, P(x_i)} и A Í X. Введем ансамбль X¢ = {x_i, P¢ (x_i)}, задав распределение вероятностей P′(x_i) следующим образом

Тогда H(X') ≥ H(X).Иными словами, «выравнивание» вероятностей элементов ансамбля приводит к увеличению энтропии.

7. Пусть задан ансамбль X и на множестве его элементов определена функция g(x_i). Введем ансамбль Y = {y = g(x_i)}. Тогда H(X) ≥ H(Y). Равенство имеет место тогда и только тогда, когда функция g(x_i)обратима.

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

Из свойства 2 следует, что максимальная энтропия источника H_max(X) достигается лишь в случае равных вероятностей выбора букв алфавита, т.е. когда P(x_i) = 1/N, (i = 1,2,...,N), тогда:

.

Такой источник называют идеальным (оптимальным), так как каждый его символ несет максимальное количество информации.

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

Если источник выдаёт последовательность букв из алфавита объёмом N = 32 и буквы выбираются равновероятно и независимо друг от друга, то энтропия источника H_max(X) = log(N) = 5 бит.

Если буквы передаются не хаотически, а составляют связный, например, русский текст, то появление их неравновероятно (вероятность появления буквы "О" в 45 раз больше, чем буквы "Ф"). Вероятности появления букв в текстах на различных языках приведены в таблице 11.1.

Таблица11.1

Распределение вероятности букв в текстах

Помимо неравновероятности появления букв, буквы в тексте зависимы. Так, после гласных не может появиться "Ь", мала вероятность сочетания более трёх согласных подряд, вероятность последовательности, не образующей осмысленных слов (идеальный источник), практически равна нулю. Расчёты показывают, что для текстов русской художественной прозы энтропия оказывается менее 1,5 бит на букву. Еще меньше, около 1 бита на букву, энтропия поэтических произведений, так как в них имеются дополнительные вероятностные связи, обусловленные ритмом и рифмами. Слово, рифмуемое с окончанием предыдущей стихотворной строки, легко угадывается без произнесения или чтения его, и поэтому информации не несет (I(x_i) = 0). Энтропия телеграмм обычно не превышает 0,8 бит на букву, поскольку их тексты довольно однообразны (особенно поздравительных).

Условная энтропия

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

Рассмотрим ансамбли X = {x_i} и Y={y_j} и их произведение XY={(x_i,y_j), P(x_i,y_j)}. Для любого фиксированного y_jÎY можно построить условное распределение вероятностей P(x_i/y_j)на множестве X и для каждого x_iÎX подсчитать собственную информацию

,

которую называют условной собственной информацией сообщения x_i при фиксированном y_j.

Ранее мы назвали энтропией ансамбля X среднюю информацию сообщений x_iÎX. Аналогично, усреднив условную информацию I(x_i/y_j)по x_iÎX, получим величину

,

называемую условной энтропией X при фиксированном y_jÎY. Заметим, что в данном определении имеет место неопределенность в случае, когда P(x_i/y_j)=0. Следует отмечалось, что выражение вида z log z стремится к нулю при z® 0 и на этом основании мы считаем слагаемые энтропии, соответствующие буквам x_i с вероятностью P(x_i/y_j)=0, равными нулю.

Вновь введенная энтропия H(X/y_j) – случайная величина, поскольку она зависит от случайной переменной y_j. Чтобы получить неслучайную информационную характеристику пары вероятностных ансамблей, нужно выполнить усреднение по всем значениям y_j. Величина

называется условной энтропией ансамбля X при фиксированном ансамбле Y . Отметим ряд свойств условной энтропии.

1. .

2. , причем равенство имеет место в том и только в том случае, когда ансамбли X и Y независимы.

3. .

4. .

5. причем равенство имеет место в том и только в том случае, когда ансамбли X и Y условно независимы при всех zÎ Z.

Обсудим «физический смысл» сформулированных свойств условной энтропии. Свойство 2 устанавливает, что условная энтропия ансамбля не превышает его безусловной энтропии. Свойство 5 усиливает это утверждение. Из него следует, что условная энтропия не увеличивается с увеличением числа условий. Оба эти факта неудивительны, они отражают тот факт, что дополнительная информация об ансамбле X, содержащаяся в сообщениях других ансамблей, в среднем, уменьшает информативность (неопределенность) ансамбля X . Замечание «в среднем» здесь очень важно, поскольку неравенство H(X/y_j) ≤ H(X), вообще говоря, не верно.

Из свойств 1 – 5 следует неравенство

, (11.4)

в котором равенство возможно только в случае совместной независимости ансамблей X₁, …, X_n.

Напомним, что вычисление энтропии – это вычисление затрат на передачу или хранение букв источника. Свойства условной энтропии подсказывают, что при передаче буквы X_n+1 следует использовать то обстоятельство, что предыдущие буквы X₁, …, X_n уже известны на приемной стороне. Это позволит вместо H(X_n+1)бит потратить меньшее количество H(X_n+1/X₁,…,X_n) бит. В то же время неравенство (11.4) указывает другой подход к экономному кодированию. Из этого неравенства следует, что буквы перед кодированием нужно объединять в блоки и эти блоки рассматривать как буквы нового «расширенного» источника. Затраты будут меньше, чем при независимом кодировании букв. Какой из двух подходов эффективнее?

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: