Информация может быть двух видов: дискретная (цифровая) и непрерывная (аналоговая). Дискретная информация характеризуется последовательными точными значениями некоторой случайной величины, а непрерывная – непрерывным процессом изменения некоторой случайной величины (сигнала). Непрерывную информацию может, например, выдавать датчик атмосферного давления и датчик скорости автомашины.
Дискретную информацию можно получить, измеряя непрерывную информацию через определенные интервалы времени. Чем короче эти временные интервалы (периоды дискретизации), тем точнее происходит перевод непрерывной информации в дискретную. Однако с уменьшением периода дискретизации растет и размер дискретных данных, и, следовательно, сложность их обработки, передачи и хранения. Таким образом, необходимо выбирать достаточно небольшой временной интервал с одной стороны для точной дискретизации непрерывной информации, а с другой – процесс дискретизации не должен быть слишком трудоемким. В дальнейшем, будет всегда рассматриваться дискретная информация.
Дискретная информация удобнее для обработки, хранения и передачи, поскольку она описывается последовательностью чисел. Если представить каждое число в двоичной системе счисления, то дискретная информация предстанет в виде последовательности нулей и единиц. Одна позиция для двоичной цифры в описании дискретной информации называется битом. Бит служит для измерения информации. Байт – это набор из 8 битов.
Пример 2.1.1. Сколько битов потребуется, чтобы размесить в памяти компьютера фразу «Я не горку шла»?
Поскольку каждый символ имеет ASCII-код объемом 8 битов, то всего потребуется 14 символов x 8 битов = 112 битов.
Большой класс дискретных сообщений, передаваемых по каналам связи, можно представить как набор из n символов (элементов), которые последовательно порождает некоторый источник информации. Элементы сообщения могут принимать значения из некоторого конечного алфавита мощности m. Элементами сообщений могут быть импульсы тока или напряжения, символы текста, биты и др.
Определим количество различных сообщений, которые можно составить из n символов, принимающих любое из m различных фиксированных значений. Первый элемент сообщения может принимать m значений, второй – также m значений и т.д. Тогда общее количество различных сообщений равно
Чем больше L, тем значительней отличается каждое данное сообщение от остальных, т. е. величина L может служить мерой количества информации для равновероятных сообщений. Однако более удобной мерой количества информации является логарифм числа возможных сообщений (здесь и далее )
Логарифмическая мера I(L) количества информации обладает следующими свойствами
Последнее соотношение выражает свойство аддитивности количества информации, т.е. количество информации нескольких независимых источников сообщений равно сумме количеств информации каждого источника
Пример 2.2.1. Определить количество информации, которое содержится в телевизионном сигнале, соответствующем одному кадру развертки. В кадре 625 строк, а сигнал, соответствующий одной строке, представляет собой последовательность из 600 случайных по амплитуде импульсов, причем амплитуда импульса может принять любое из 8 значений с шагом в 1 В.
Решение. В рассматриваемом случае длина сообщения, соответствующая одной строке, равна числу случайных по амплитуде импульсов в ней, т.е. n=600.
Каждый элемент сообщения может принимать любое из 8 значений амплитуды импульса, т.е. m=8.
Количество информации в одной строке
а общее количество информации в кадре бит или 137,33 Кб.
Пример 2.2.2. Определить минимальное число взвешиваний, которое необходимо произвести на равноплечих весах, чтобы среди 27 внешне неотличимых монет найти одну фальшивую, более легкую.
Решение. Так как монеты внешне неотличимые, то они представляют источник с равновероятными состояниями, а общая информация такого источника бит.
Каждое взвешивание имеет один из трех возможных исходов: левая чаша весов легче, правая чаша весов легче, весы находятся в равновесии. Так как все исходы равновероятны (нельзя заранее отдать предпочтение одному из них), то результат одного взвешивания представляет источник с тремя равновероятными состояниями, а общее количество информации такого источника составляет бит.
Так как количество информации отвечает требованию аддитивности и при этом , то для определения фальшивой монеты достаточно произвести три взвешивания.
Алгоритм определения фальшивой монеты следующий. При первом взвешивании на каждую чашку весов кладется по девять монет. Фальшивая монета будет либо среди тех девяти монет, которые оказались легче, либо среди тех, которые не взвешивались, если имело место равновесие. Аналогично, после второго взвешивания число монет, среди которых находится фальшивая монета, сократится до трех. Последнее, третье, взвешивание дает возможность точно указать фальшивую монету.
Рассмотренная выше оценка информации основана на предположении о равновероятности всех знаков алфавита источника информации. Рассмотрим теперь сообщения длины n, символы которого порождаются независимо некоторым источником информации в соответствии с распределением дискретной случайной величины, т.е. элементы сообщения могут принимать значения с вероятностями
соответственно,
. Вычислим среднюю вероятность такого сообщения.
Обозначим количество элементов сообщения, принимающих значение
,
. Очевидно, что
. Поскольку элементы сообщения принимают значения независимо, то вероятность сообщения равна
.
При достаточно больших n по теореме Бернулли допустимо такое приближение или
и тогда
. Последняя формула выражает среднюю вероятность сообщения.
По средней вероятности подсчитаем среднее число всех возможных сообщений . Зная среднее число L всех возможных сообщений, определим и среднее количество информации I(L), содержащееся в одном сообщении
.
Последнее соотношение было получено Шенноном для определения среднего количества информации в сообщении с произвольными вероятностями появления состояний. При равновероятных состояниях элементов сообщений, т.е. , формула Шеннона превращается в уже знакомую формулу
.
Пример 2.2.3. Источник информации A порождает сообщения, состоящие из символов с вероятностями
. Сравнить количество информации, приходящуюся на букву источника информации A с количеством информации, которая была бы у того же источника при равновероятном использовании букв.
Решение. При одинаковых вероятностях появления любой из всех m=4 букв алфавита количество информации, приходящуюся на одну букву, характеризует величина бит.
Найдем количество информации источника A.
бит
Таким образом, неравномерность распределения вероятностей использования букв снижает количество информации источника с 2 до 1.37 бит
Определение. Количество информации I(L), содержащееся в сообщении, зависит от длины сообщения n, числа возможных состояний m и вероятностей состояний . Поскольку I(L) от величины n зависит линейно, то в теории информации используют удельное количество информации, приходящееся на один символ сообщения. Эта величина называется энтропией Шеннона
Рассмотрим основные свойства энтропии.
Энтропия двоичного сообщения изменяется от 0 до 1 и достигает максимума при равных вероятностях , т.е. когда ситуация является наиболее неопределенной.
Если m>2, то максимальное значение энтропии также достигается в случае равновероятных состояний элементов
4. Энтропия сообщения, состоящего из некоторых частных независимых сообщений, равна сумме энтропий составляющих его частей.
Действительно, пусть имеются два независимых сообщения A и B с энтропиями H(A) и H(B) соответственно. Вероятность совместного события AB равна произведению вероятностей событий A и B p(AB)=p(A)p(B). Тогда
Это свойство энтропии, известное как правило сложения энтропий, хорошо согласуется со смыслом энтропии как меры неопределенности. Правило сложения энтропий распространяется и на большее число сообщений.
Пример 2.3.4. В таблицах заданы распределения вероятностей двух случайных дискретных величин X и Y
Сравнить энтропии данных случайных величин.
Решение. Энтропия не зависит от конкретных значений случайной величины. Так как вероятности появления символов в обоих случаях одинаковы, то
Согласно правилу сложения энтропий количество информации, содержащееся в двух различных независимых сообщениях, равно сумме количеств информации, содержащихся в отдельных сообщениях. Однако если сообщение содержит часть другого сообщения, то количество информации от двух таких сообщений не будет равно сумме количеств информации от каждого сообщения по отдельности, а будет меньше. Большое значение для определения количества информации, содержащейся в статистически зависимых сообщениях, имеет понятие условной энтропии.
Пусть имеются
два источника информации. Первый источник порождает символы
с вероятностями
, а второй источник
порождает символы
с вероятностями
. поскольку сообщения зависимы, то заданного символа
вероятности
появления
определяются условными
вероятностями
Для фиксированного символа совокупность условных
вероятностей определяет частную условную энтропию
которая характеризует
информативность сообщений после того, как стало
известен символ
. Если частную условную энтропию усреднить по всем
значениям
, то найдем общую условную энтропию сообщений
относительно сообщений
С учетом выражений для частных условных энтропий можно получить такое выражение
Известно, что
вероятность совместного появления двух статистически зависимых случайных
величин и
определяется
равенством
Поэтому окончательное выражение для условной энтропии можно записать так
Основной смысл
средней условной энтропии состоит в том, что показывает, какую энтропию дают
сообщения , когда уже известна энтропия сообщений
Приведем основные свойства условной энтропии.
1. Если сообщения и
статистически
независимы, то условная энтропия сообщений
относительно сообщений
равна безусловной
энтропии сообщений
, т.е.
2. Если сообщения и
статистически жестко
зависимые, т.е. появление одного из них непременно влечет появление другого, то
условная энтропия сообщений
относительно сообщений
равна нулю, т.е.
Пример 2.4.1. Известны энтропии
двух зависимых источников информации и
:
бит,
бит.
Определить, в каких пределах может изменяться величины условных энтропий
и
.
Решение. На
рисунках представлены различные варианты взаимосвязей энтропий источников и
.
При отсутствии взаимосвязи между источниками информации:
Если
источники информации независимы, то бит,
а
бит. И эти значения условных энтропий
являются максимальными.
По мере увеличения взаимосвязи источников условные энтропии и
будут уменьшаться:
При полной статистической зависимости двух источников один из
них не вносит никакой информации, поскольку при появлении неизбежно следует
, т.е.
при
и
. Поэтому
При этом бит.
Поэтому
будет изменяться от 10 бит до 5 бит при
максимально возможном изменении
от 5 бит до 0 бит.
Определение. Энтропия объединения двух
источников сообщений и
определяется суммой по всем возможным состояниям объединения
где – вероятность
совместного появления двух статистически зависимых состояний
и
Поскольку
вероятность совместного появления двух состояний может быть выражена через
вероятность появления одного из состояний и условную вероятность появления
другого состояния равенством
Первая сумма в
соотношении представляет собой энтропию сообщений > (поскольку
), а вторая сумма – условную энтропию
. Таким образом, окончательно имеем
Аналогично можно получить симметричное соотношение
Приведем основные свойства энтропии объединения.
1.
2. Если источники сообщений и
статистически
независимы, о энтропия
объединения равна сумме энтропий источников сообщений
и
3. Если два источника сообщений
и
являются полностью
статистически зависимыми, то
Пример 2.5.1 Закон
распределения вероятностей системы, объединяющей зависимые источники информации
и
задан в таблице
совместных вероятностей:
Y X |
y1 |
y2 |
y3 |
x1 |
0.4 |
0.1 |
0 |
x2 |
0 |
0.2 |
0.1 |
x3 |
0 |
0 |
0.2 |
Определить
величины ,
,
,
,
.
Решение
1. Сначала вычислим безусловные вероятности и
.
а) Сложив
вероятности по строкам таблицы, получим вероятности появления значений
б) Сложив
вероятности по столбцам таблицы, получим вероятности появления значений
2. Вычислим теперь энтропии источников
информации и
по формуле Шеннона,
используя вычисленные ранее значения безусловных вероятностей.
3. Определим условные вероятности события
при условии выполнения
события
по формуле
. Тогда
. Величины
заданы в таблице, а
– вычислены ранее.
Вычисленными
результатами заполним таблицу условных вероятностей события при условии выполнения
события
.
Y X |
y1 |
y2 |
y3 |
x1 |
0.8 |
0.2 |
0 |
x2 |
0 |
0.67 |
0.33 |
x3 |
0 |
0 |
0.1 |
4. Определим условную энтропию
источника информации при условии, что сообщения источника
Аналогично можно вычислить условную энтропию
источника информации при условии, что сообщения источника
5. Общая энтропия зависимых
источников информации и
определяется по
формуле
Проверим результат по формуле
бит
Значения совпадают.
С практической
точки зрения оценка количества информации необходима для построения экономичных
кодов, оценки свойств каналов связи и их пропускной способности, для
определения избыточности кодов и повышения их помехоустойчивости. При анализе
каналов связи нужно уметь определять максимальное количество информации,
которое может быть передано за единицу времени. Максимальное количество
информации на элемент сообщения может быть получено только в случае равновероятных
и независимых сообщений. Сообщения, энтропия которых равна максимальному
значению количество состояний
элементов сообщения, являются оптимальными сообщениями в смысле наибольшего
количества передаваемой информации. Реальные сообщения редко полностью
удовлетворяют этому условию, поэтому информационная нагрузка на каждый элемент
обычно меньше той, которую они могли бы передавать. Энтропия таких сообщений
меньше максимальной и сообщение обладает информационной избыточностью.
В теории информации избыточность показывает количество «лишней информации», которая определяется структурой множества состояний элементов и обычно заранее известна из статистических данных.
Определение. Мерой количественной оценки
того, насколько данное реальное сообщение отличается от соответствующего ему
оптимального сообщения, служит коэффициент
сжатия или относительная энтропия,
которая равна отношению энтропии реального сообщения к энтропии
соответствующего ему оптимального сообщения .
Коэффициент сжатия показывает, какая часть реальных сообщений может быть отброшена при переходе к оптимальному кодировании, т.е. какая доля сообщения является излишней или избыточной.
Определение. Наряду с коэффициентом
сжатия используется и величина избыточности
.
Для уменьшения избыточности сообщения необходимо увеличить энтропию сообщения, т.е. стремиться к тому, что элементы сообщения были максимально информативны.
Нахождение оптимальной избыточности кода при данном уровне помех является одной из главных задач теории информации и кодирования.
Пример 2.6.1. Для русского языка, состоящего из 32 букв (буквы «е» и «ё», «ь» и «ъ» не различаются, добавлен символ пробела « » ), максимальное значение энтропии при условии равновероятности букв составляет
Однако в русском языке появления разных букв алфавита происходит с неравными частотами. В таблице приведены частоты появления отдельных букв русского языка.
пробел |
О |
Е, Ё |
а |
и |
т |
н |
с |
p |
в |
л |
к |
м |
д |
п |
у |
я |
ы |
з |
ь, ъ |
б |
г |
ч |
й |
х |
ж |
ю |
ш |
ц |
щ |
э |
ф |
Используя эти
частоты в качестве вероятностей появления букв, можно получить приближенное
значение энтропии одной буквы русского языка бит, что меньше
максимального значения энтропии. Если учитывать статистику появления буквенных
сочетаний и словесных сочетаний, то исследования показали, что энтропия на
букву русского языка не превышает 2 бит.
Таким образом, коэффициент
сжатия или относительная энтропия для русского языка составляет , а величина избыточности >
.Коэффициент сжатия показывает, что объем текста на русском языке возможно сжать в 2.5 раза.
1. Сколько битов потребуется, чтобы размесить в памяти компьютера фразу
«Тили-тили тесто!»?
a) 16
b) 128
c) 32
Правильный ответ: b)
2. Максимальное значение энтропии источника, который порождает 16 различных символов равно
a) 4
b) 1
c) нельзя определить
Правильный ответ: a)
3. Коэффициент сжатия для
источника с вероятностями
равен
a) 0.875
b) 0.125
c) 1.338
Правильный ответ: a)
4. Энтропия Шеннона обладает свойством
a) аддитивности
b) ассоциативности
c) социальности
Правильный ответ: a)
5. Количество информации, содержащееся в двух статистически зависимых сообщениях, оценивается величиной
a) энтропии Шеннона
b) условной энтропии
c) относительной энтропии
Правильный ответ: b)