пользователей: 21212
предметов: 10450
вопросов: 177346
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Основные идеи количественной оценки информации: энтропийный, объемный подходы, единицы измерения информации, способы оценки количества

Измерение информации

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

Рассмотрим некоторый опыт, связанный с получением N равновероятных исходов. Результатом выпадения одного из результатов будет выпадение одного из N знаков. Введём в рассмотрение численную величину, измеряющую неопределённость – энтропию (H), связанную с неопределённостью, существующей до начала опыта.

H = f(N)

  1. Чем больше N, тем больше неопределённость.

f – возрастающая.

H1 – неопределённость до выполнения опыта.

H2 – неопределённость после выполнения опыта.

I = H1 – H2 – количество информации, полученной в ходе осуществления опыта.

  1. H = f(1) = 0.

  2. Рассмотрим опыты α и β с количеством исходов 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


05.08.2014; 14:48
хиты: 681
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь