Дискретный источник информации

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

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

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

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

Каким образом оценить количество информации, приходящееся на сообщение от такого источника?

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

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

.

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

Мера информации по Хартли

Очевидно, что неопределённость, и, как следствие, количество информации, возрастает с ростом числа состояний источника. Например, подбрасываемая монета может упасть на одну из двух сторон. Соответственно, чтобы передать её состояние, достаточно использовать двухсимвольный алфавит (например {0,1}), из которого формируются односимвольные сообщения.

В то же время, подбрасываемый кубик может упасть на одну из шести граней. Поэтому для передачи его состояния следует использовать либо алфавит большего объема (например, шестисимвольный алфавит {0,1,2,3,4,5} и односимвольные сообщения), либо сообщения большей длины (например, исходный двухсимвольный алфавит {0,1} и трехсимвольные сообщения вида 000, 001, 010 и т.п.).

Во втором случае неопределённость и количество информации очевидно больше, чем в первом.

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

Однако такая мера противоречит некоторым интуитивным представлениям. Например, при N = 1, когда источник может находиться лишь в одном состоянии и неопределённость вообще отсутствует, количество информации получается ненулевым.

Другой важный недостаток заключается в том, что подобная мера не является аддитивной. Суть этого требования заключается в следующем: если два независимых источника с числом равновероятных состояний N_A и N_B рассматривать как один составной источник, одновременно генерирующий пары состояний a_ib_i, то естественно ожидать, что неопределённость состояния (и, соответственно, количество информации) для такого объединенного источника должно определяться суммой неопределённостей каждого из источников в отдельности, т.е.

.

С другой стороны, из комбинаторики известно «правило умножения», которое определяет общее количество состояний подобного составного источника, как произведение чисел состояний отдельных источников:

где: N_AB – число вариантов составного сообщения,

N_A и N_B – числа вариантов первой и второй частей сообщения.

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

.

Одновременно выполняется и первое требование, т.е. при N = 1 .

Эта мера информации была предложена в 1928 году американским ученым Р. Хартли. Основание логарифма не имеет принципиального значения, однако т.к. современная цифровая техника использует в качестве основной двоичную систему счисления, то обычно выбирают основание логарифм основания, равный двум. При этом минимальная единица информации называется битом, от (bit – binary digit – двоичная цифра). Для однобуквенных сообщений N равно числу букв в алфавите информационного устройства. В частности, при числе букв, равном двум

.

При 32 буквах (как в русском алфавите) каждая буква оценивается в

.

В случае выбора натурального логарифма говорят о натах – натуральных единицах информации.

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

Как уже было сказано, основной единицей количества информации является бит. Однако для практического применения это – слишком мелкая единица. Более удобной единицей является байт (byte), равный восьми битам. Прибавляя к слову «байт» децимальные приставки «кило», «мега» и т. д. можно получать более крупные единицы измерения. Нужно только помнить об условности таких обозначений, так как их связывает множитель, равный не 1000, а 1024 =2¹⁰.

Мера информации по Шеннону

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

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

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

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

Будем считать, что алфавит дискретного источника информации образован N различными символами, обозначаемыми (u₁, u₂, …, u_N). Вероятности p_i выбора того или иного символа могут отличаться. Полная совокупность допустимых символов и соответствующих им вероятностей называется ансамблем U:

,

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

.

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

.

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

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

,

где N – число возможных сообщений, – вероятность i-го сообщения.

Полученная мера неопределённости получила название статистической меры по Шеннону или энтропии дискретного источника информации.

• Пример 1. При вынимании шаров из урны, где находится один черный и один белый шар, неопределенность составляет

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

• Пример 2. В урне находятся семь черных шаров и один белый. На этот раз неопределенность составит

.

Мера неопределенности уменьшилась почти вдвое по сравнению с первым примером.

Рассмотрим связь меры Шеннона и Хартли. Если источник равновероятно генерирует N различных символов, то вероятность появления каждого из них составляет . При этом неопределенность по Хартли, приходящаяся на каждый символ равна

.

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

.

Следовательно, мера Шеннона является естественным обобщением меры Хартли на случай ансамбля с неравномерным распределением вероятностей появления символов.

Раздел №3 (2 часа)

Общая характеристика процессов сбора, передачи, обработки и накопления информации

План:

• Процессы сбора, передачи, обработки и накопления информации

• Этапы обращения информации в информационно-измерительных и управляющих системах