Измерение информации
Если информацию можно представить в виде сообщения, то возникает вопрос, а нельзя ли измерить её количество. Информацию связали с понятием энтропии (неопределённость). Получение информации связано с понижением информационной неопределённости.
Рассмотрим некоторый опыт, связанный с получением N равновероятных исходов. Результатом выпадения одного из результатов будет выпадение одного из N знаков. Введём в рассмотрение численную величину, измеряющую неопределённость – энтропию (H), связанную с неопределённостью, существующей до начала опыта.
H = f(N)
-
Чем больше N, тем больше неопределённость.
f – возрастающая.
H1 – неопределённость до выполнения опыта.
H2 – неопределённость после выполнения опыта.
I = H1 – H2 – количество информации, полученной в ходе осуществления опыта.
-
H = f(1) = 0.
-
Рассмотрим опыты α и β с количеством исходов Nα и Nβ. Рассмотрим сложный опыт – одновероятное выпадание α и β. Число возможных исходои равно Nα·Nβ и все они равновероятны. Неопределённость исходов сложного опыта будет больше, чем неопределённость α или β.
f(Nα·Nβ). Из независимости α и β следует, что в сложном опыте Nα не зависит от Nβ, следовательно, суммарной неопределённостью опыта будет f(Nα·Nβ) = f(Nα) + f(Nβ) – аддитивность.
Такими тремя свойствами обладает лишь логарифм.
За единицу информации было принято количество информации, связанное с проведением опыта, состоящего в получении одного из двух равновероятных исходов. Это количество информации решили назвать битом.
I = H1 = log2N – формула Хартли.
N = 2I или I = -log2p, p – вероятность исходов.
Если исходы не равновероятны, то I = -log2pi.
Вывод формулы Шеннона.
Пусть имеется некоторый алфавит и будут вытаскиваться буквы, т.е. имеется генератор, который может демонстрировать любую букву из K букв алфавита. Генерирование происходит по закону распределения:
|
A1 |
A2 |
… |
Ak |
|
p1 |
p2 |
… |
pk |
Каждая из букв появляется в соответствии со своей вероятностью. Пусть имеется N испытаний. Если заинтересоваться появлением буквы Ai, то она появится N·pi раз. Каждое появление даст количество информации Ii1 = -log2pi. А общее количество информации, связанное с появлением этой буквы будет Iis = -N·pi·log2pi, т.к. букв k, значит, суммарное количество информации будет равно . Если было проведено N опытов, то среднее количество информации одного опыта будет равно: - формула Шеннона.
Так как формула по форме похожа на формулу вычисления энтропии, то способ вычисления количества информации получил название - энтропийный.
Объёмный подход к измерению информации
Если в сообщении имеется N знаков, а знаки берутся из одного алфавита, содержащего K знаков, то вычисляется вероятность, приходящаяся на один знак алфавита: Ii1 = -log2pi, 1 ≤ i ≤ k. Суммарное количество информации, содержащейся в сообщении: I = -N·log2p.
Введём следующее понятие: избыточность текста равна . Информация полученная по объёмному способу больше информации полученной по энтропийному способу. Избыточность – бесполезное количество совершаемых альтернативных выборов при распознавании. Избыточность достигает половины текста. Чем выше избыточность, тем с большей вероятностью восстанавливается информация из текста.
I0 – равновероятное появление всех символов
I1 – с учётом вероятности появления одного символа
I2 – с учётом вероятности появления сочетаний из двух знаков (например, в английском языке I2(e) = 3,32 бит, а I1(e) = 4,04 бита.)
I3 – учитываются сочетания из трёх символов (I3(e) = 3,10 бит)
…
I8 – I8(e) = 1,9
Если экстраполировать на большее число символов, то появляется I∞ - минимальное количество информации на один знак для данного языка.
Отсюда и появляется избыточность (относительная).
Информация доносится структурой самого языка, то есть может быть выражена, установлена без явного указания в буквенном виде. Для английского языка Шенноном подсчитано, что I∞ = 1,4..1,5, I0 = 4,7555, следовательно, R = 0,68 – избыточность. Для европейских языков избыточность колеблется от 60% до 70%.
Избыточность полезна, когда есть необходимость восстановления информации при наличии помех (шумов). Чем больше избыточность, тем больше становится вероятность восстановления текста.
Шенноном был получен рез-т:
Всегда возможен такой способ кодирования, при котором сообщения будут передаваться с какой угодно высокой достоверностью, если только скорость передачи не превышает пропускной способности канала связи.(это формулировка первой Теоремы Шеннона).
Пропускная способность-максимальное кол-во символов, передаваемых по каналу в единицу времени при отсутствии помех.
Есть источник, представляющий сообщение в дискретном виде. Тогда источник называется первичным и использует алфавит, называемый первичным алфавитом.
Пусть N- кол.знаков в алфавите А, М-кол-во знаков в алфавите В.
А-первичный алф.; IA- среднее кол-во информации на знак 1го алфавита
В-вторичный алфавит; IВ-…на знак 2го алфавита.
Пусть некоторое сообщение имеет n знаков в алф. А и m знаков в алф. В. Если исходное сообщение содержит Iис.(А)- кол-во информации в исходном сообщении. Iкод(В)-кол-во информ в закодированном сообщении.
Iис.(А)<= Iкод(В)- условие обратимости кодирования, т.е. не исчезновения инф-и при кодировании.
При кодировании кол-во информации может увеличиваться но не уменьшаться!
n·IА≤m·IB. Тогда , где - среднее число знаков вторичного алфавита, приходящееся на число знаков первичного алфавита (длина кода), -обозначение длины кода
,
то есть на один знак первичного алфавита приходится несколько знаков вторичного. Способов построения кода множество, поэтому возникает проблема выбора наилучшего кода. Минимально возможным средним значением длины кода будет - нижний предел длины кода, а ниже произойдет потеря информации. но оно не устанавливает способ приближения K(A,B) стремится к KMIN.
Вторая Теорема Шеннона: При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором среднее значение числа знаков кода, приходящихся на один знак первичного алфавита будет сколь угодно близко к отношению средней информации на один знак первичного и вторичного алфавитов. (т.е. ).
Избыточность кода- мера превышения К(А,В) над Кmin
