Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Теорія інформації та кодування. Тема 1. Ентропія і інформація імовірнісних схем. Носов В.В.
Лекція 3. Кількість інформації та ентропія
Навчальні питання
1. Імовірнісна схема 1
2. Кількість інформації згідно Р. Хартлі 3
3. Кількість інформації за К. Шеноном 5
4. Аксіоми Хінчина і Фадєєва 7
Час – 2 год.
Література.
Вступ
Исходным понятием в теории информации является понятие вероятностной схемы. Пусть - вероятностное пространство2, где
произвольное множество, элементы которого называются элементарными событиями, исходами или точками;
M – некоторая зафиксированная система подмножеств M случайных событий, удовлетворяющая свойствам σ(сигма)-алгебры:
Р это числовая функция, которая определена на M и ставит в соответствие каждому событию B M число P(B), которое называется вероятностью события B. Эта функция должна быть конечной сигма-аддитивной мерой, равной 1 на всем пространстве, то есть обладать свойствами:
Пусть полная группа попарно несовместимых исходов события A.
Определение 1.1. Пара называется вероятностной схемой события .
Говорят, что вероятностная схема А дискретна, если число событий не более чем счётно. В этом случае будем записывать в виде:
(1)
где аk - исход вероятностной схемы, pk - вероятность исхода,
, .
Если число исходов {аk} более чем счётно, то вероятностная схема А называется непрерывной. Тогда её задают, описывая множество возможных исходов и указывая с помощью плотности распределения вероятностей p(x) вероятностное распределение на исходах.
Объединенная вероятностная схема
Пусть существует вероятностная схема события A
, , ,
и вероятностная схема события B
, , ,
тогда можно задать объединенную вероятностную схему некоторого события С, которое будет имеет вид:
,
дополнительно заметим, что
Важной характеристикой схемы является энтропия средняя мера неравновероятности исходов схемы. Энтропия и близкое понятие количество информации по-разному определялись рядом авторов. Приведём некоторые из этих определений.
В качестве основной характеристики сообщения теория информации принимает величину, называемую количеством информации. Это понятие не затрагивает смысла и важности передаваемого сообщения, а связано со степенью его неопределенности.
Согласно Р. Хартли3 количество информации, содержащееся в сообщении, должно удовлетворять двум требованиям:
Пусть алфавит источника сообщений состоит из знаков, каждый из которых может служить элементом сообщения. Количество возможных сообщений длины равно числу перестановок с неограниченными повторениями:
Если для получателя все сообщений от источника являются равновероятными, то получение конкретного сообщения равносильно для него случайному выбору одного из сообщений с вероятностью .
Чем больше (или меньше вероятность сообщения), тем большая степень неопределенности характеризует этот выбор и тем более информативным можно считать сообщение.
Очевидно, что количество информации, содержащейся в элементарном сообщении , является некоторой функцией от вероятности передачи этого сообщения :
. (1)
Определим вид этой функции Для этого потребуем, чтобы мера количества информации удовлетворяла двум интуитивным свойствам:
Вероятность совместного выпадения событий и определяется по формуле полной вероятности
. (2)
Тогда, в соответствии с требованием (2), должно выполняться условие
. (3)
Функцией, удовлетворяющей двум предъявляемым к ней условиям, является логарифм числа возможных сообщений
.
Эта логарифмическая функция характеризует количество информации. Указанная мера была предложена американским ученым Р.Хартли в 1928 г.
Иногда формулу Хартли для двоичных логарифмов и равновероятном появлении сообщений записывают так:
,
т. к. каждое из событий имеет равновероятный исход , то .
При этом выполняются следующие соотношения. Так как , то величина всегда положительна и конечна. При количество информации равно нулю, т.е. сообщение об известном событии никакой информации не несет. Присутствует свойство аддитивности, согласно которому количество информации, содержащееся в нескольких независимых сообщениях, равно сумме количества информации в каждом из них. Действительно, так как совместная вероятность независимых сообщений то количество информации в этих сообщениях равно
что соответствует интуитивным представлениям об увеличении информации при получении дополнительных сообщений.
Количество информации по Хартли удовлетворяет следующим аксиомам вероятностной схемы события A.
, , ,
Для заданной схемы справедливыми будут считаться аксиомы:
Аксиомы 1 и 2 подтверждают как бы то, что информация нескольких событий не может взаимно уничтожиться.
Аксиома 3 говорит о том, что при изменении вероятности события количество информации в нем неминуемо изменится.
Если предположить, что это сообщение длиною из алфавита знаков, то количество информации, приходящееся на один элемент сообщения (знак, букву), называется энтропией источника сообщений:
В принципе безразлично, какое основание логарифма использовать для определения количества информации сообщения и энтропии источника сообщения, т.к. в силу соотношения
переход от одного основания логарифма к другому сводится лишь к изменению единицы измерения.
Так как современная информационная техника базируется на элементах, имеющих два устойчивых состояния, то обычно выбирают основание логарифма равным двум, т.е. энтропию источника сообщения выражают как:
H = log2 m.
Тогда единицу количества информации на один элемент сообщения называют двоичной единицей или битом. При этом единица неопределенности (двоичная единица или бит) представляет собой неопределенность выбора из двух равновероятных событий (bit — сокращение от англ. binary digit — двоичная единица)
Так как из log2 m = 1 следует m = 2, то ясно, что 1 бит - это количество информации, которым характеризуется один двоичный элемент при равновероятных состояниях 0 и 1.
Двоичное сообщение длины n содержит n бит информации.
Единица количества информации, равная 8 битам, называется байтом.
Если основание логарифма выбрать равным десяти, то энтропия выражается в десятичных единицах на элемент сообщения - дитах, причем 1 дит = log102 бит = 3,32 бит.
Если основание логарифма выбрать равным e, то энтропия выражается в натуральных единицах – натах.
Пример1. Определить количество информации, которое содержится в телевизионном сигнале, соответствующем одному кадру развертки. Пусть в кадре 625 строк, а сигнал, соответствующий одной строке, представляет собой последовательность из 600 случайных по амплитуде импульсов, причем амплитуда импульса может принять любое из 8 значений с шагом в 1 В.
Решение. В рассматриваемом случае длина сообщения, соответствующая одной строке, равна числу случайных по амплитуде импульсов в ней: n = 600.
Количество элементов сообщения (знаков) в одной строке равно числу значений, которое может принять амплитуда импульсов в строке,: m = 8.
Количество информации в одной строке: I = n log m = 600 log 8, а количество информации в кадре: I = 625 I = 625 600 log 8 = 1,125 106 бит.
Рассмотренная выше оценка информации по Р.Хартли основана на предположении о равновероятности всех знаков алфавита источника сообщения.
В общем случае каждый из знаков появляется в сообщении с различной вероятностью.
К. Шеннон рассматривал порождение знаков сообщений в условиях вероятностной схемы:
, , ,
где каждый знак сообщения, а значит и само сообщение, имеет разную вероятность появления.
Относительно количества информации, содержащегося в сообщении длины , составленном по схеме независимых испытаний, К. Шеннон высказал следующие требования:
Пусть на основании статистического анализа известно, что в сообщении длины n знак ai появляется ni раз, т.е. вероятность появления знака из m-значного алфавита в сообщении длины n:
, i = 1,2,3, ... , m
Все знаки алфавита составляют полную систему случайных событий, поэтому:
.
Найдем оценку среднего значения количества информации знака алфавита в сообщении длины в виде:
где ni частота появления i-го знака в заданном множестве A;
n – длина сообщения;
m количество знаков в алфавите сообщения;
Ii количество информации i-го сообщения.
Тогда при , получим:
Переходя к произвольным основаниям логарифмов, получают формулы Шеннона для энтропии источника сообщения и количества информации в сообщении длины :
Таким образом, энтропия источника сообщения является суммой с противоположным знаком всех произведений вероятности появления i-го знака (элементарного сообщения источника), умноженных на их же двоичные логарифмы.
Энтропия — это количество информации, приходящейся на одно элементарное сообщение источника, вырабатывающего статистически независимые сообщения.
Энтропия — мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии n-ого порядка) встречаются очень редко, то неопределённость ещё более уменьшается.
А.Я. Хинчин к определению энтропии вероятностной схемы подошёл с аксиоматических позиций. Он установил, что энтропия конечной вероятностной схемы однозначно определяется с точностью до постоянного множителя при задании системы аксиом.
В аксиомах Хинчин использует объединенную вероятностную схему (см. п.1).
Аксиомы Хинчина
Система аксиом Фаддеева эквивалентна системе аксиом Хинчина и позволяет получить тот же результат.
Аксиомы Фаддеева
Разница в этих системах аксиом заключается в том, что 5 аксиома Хинчина (экстремальность функции энтропии) заменяется требованием положительности энтропии в одной точке. Аксиомы Хинчина 3 и 4 заменяются аксиомой III Фаддеева. Аксиома III естественна, так как неопределённость схемы
отличается от неопределённости схемы
на неопределённость, происходящую от подразделения ап на два подсобытия b1, b2 с условными вероятностями , . Эта неопределённость должна быть преодолена только в случае, если реализуется событие an, вероятность которого равна pn.
Если рассматривать энтропию как количественную меру неопределённости в реализации вероятностной схемы, то последняя аксиома естественна.
В системе аксиом Фаддеева может быть доказана справедливость представления функции энтропии
т.е. энтропия конечной вероятностной схемы однозначно определяется с точностью до постоянного множителя при задании системы аксиом.
Висновки
Контрольні питання
2 Вероятностное пространство — понятие, введённое А. Н. Колмогоровым в 30-х годах XX века для формализации понятия вероятности, которое дало начало бурному развитию теории вероятностей как строгой математической дисциплины.
3 Ральф Винтон Лайон Хартли (англ. Ralph Vinton Lyon Hartley, 30 ноября 1888, Спрус, Невада — 1 мая 1970, Нью-Джерси) — американский учёный-электронщик. Он предложил генератор Хартли, преобразование Хартли и сделал вклад в теорию информации, введя в 1928 логарифмическую меру информации H = Klog2(M), которая называется хартлиевским количеством информации.