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

Обновлено: 05.07.2024

N = 2 i

(1.1)

Бит. Для количественного выражения любой величины необходимо сначала определить единицу измерения. Так, для измерения длины в качестве единицы выбран метр, для измерения массы - килограмм и т. д. Аналогично, для определения количества информации необходимо ввести единицу измерения.

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

1 байт = 8 битов = 2 3 битов.

В информатике система образования кратных единиц измерения несколько отличается от принятых в большинстве наук. Традиционные метрические системы единиц, например Международная система единиц СИ, в качестве множителей кратных единиц используют коэффициент 10 n , где n = 3, 6, 9 и т. д., что соответствует десятичным приставкам "Кило" (10 3 ), "Мега" (10 6 ), "Гига" (10 9 ) и т. д.

В компьютере информация кодируется с помощью двоичной знаковой системы, и поэтому в кратных единицах измерения количества информации используется коэффициент 2 n

Так, кратные байту единицы измерения количества информации вводятся следующим образом:

1 килобайт (Кбайт) = 2 10 байт = 1024 байт;

1 мегабайт (Мбайт) = 2 10 Кбайт = 1024 Кбайт;

1 гигабайт (Гбайт) = 2 10 Мбайт = 1024 Мбайт.

Таким образом, количество экзаменационных билетов равно 32.

Разложим стоящее в левой части уравнения число 8 на сомножители и представим его в степенной форме:

8 = 2 × 2 × 2 = 2 3 .

Алфавитный подход к определению количества информации

Рис. 1.5. Передача информации

С помощью этой формулы можно, например, определить количество информации, которое несет знак в двоичной знаковой системе:

Таким образом, в двоичной знаковой системе знак несет 1 бит информации. Интересно, что сама единица измерения количества информации "бит" (bit) получила свое название ОТ английского словосочетания "Binary digiT" - "двоичная цифра".

Информационная емкость знака двоичной знаковой системы составляет 1 бит.

С помощью формулы (1.1) определим количество информации, которое несет буква русского алфавита:

Таким образом, буква русского алфавита несет 5 битов информации (при алфавитном подходе к измерению количества информации).

Количество информации, которое несет знак, зависит от вероятности его получения. Если получатель заранее точно знает, какой знак придет, то полученное количество информации будет равно 0. Наоборот, чем менее вероятно получение знака, тем больше его информационная емкость.

В русской письменной речи частота использования букв в тексте различна, так в среднем на 1000 знаков осмысленного текста приходится 200 букв "а" и в сто раз меньшее количество буквы "ф" (всего 2). Таким образом, с точки зрения теории информации, информационная емкость знаков русского алфавита различна (у буквы "а" она наименьшая, а у буквы "ф" - наибольшая).

Так, каждая цифра двоичного компьютерного кода несет информацию в 1 бит. Следовательно, две цифры несут информацию в 2 бита, три цифры - в 3 бита и т. д. Количество информации в битах равно количеству цифр двоичного компьютерного кода (табл. 1.1).

10.30 Базовые определения теории информации

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

Характеристика степени неопределенности результата испытания должна быть функцией k и при k=1 обращаться в нуль, так как неопределенность в этом случае отсутствует.

Предположим, что имеется два независимых испытания А и Б и пусть А имеет k равновероятных исходов, при испытании Б возможны l равновероятных исходов. Тогда комбинированное испытание АБ будет иметь неопределенность равную сумме неопределенностей испытания А и Б, ведь неопределенность испытания АБ характеризуется числом возможных исходов k×l. Этот факт наводит на мысль, что степень неопределенности испытания при k равновероятных исходах должна характеризоваться log(k).

Каждый отдельный исход, имеющий вероятность 1/k, вносит неопределенность, равную (1/k)×log(k).

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

Генный набор человека характеризуется примерно 2 Гбайт, людей на земле уже около 10 миллиардов. Таким образом, для описания генных наборов всех людей потребуется около 20 экзабайт данных. Но можно ли утверждать, что эти экзабайты информационно более емки, чем формула E=m×c 2 ? То есть существенным является не только количество информации, но и ее практическая важность (область прагматики).

Проблема оценки качества информации всегда была актуальной. Я после онончания института много работал и времени для чтения было мало. По это причине я выбирал книги, написанные до 17-го века, так как они дошли до нас благодаря переписчикам. Я полагал, что плохую книгу не стали бы переписывать. Сегодня одним из критериев качества стал индекс цитирования. Его пытаются фальсифицировать с помощью алгоритма "кукушка хвалит петуха за то, что хвалит он кукушку". Но лучших критериев качества пока не придумано. Для программ одним из критериев качества можно считать число ошибок на 1000 строк кода.

Если число букв в алфавите равно n, а количество используемых элементарных сигналов - m, то при любом методе кодирования среднее число элементарных сигналов на одну букву алфавита не может быть меньше . Однако оно может быть сколь угодно близко к этому отношению. В простейшем случае, когда при передаче используется только два уровня сигнала, m=2, т.е. число бит на одну букву равно log(n)/log(2).

Часто встречающиеся символы содержат малое количество информации, а редко встречающиеся большее. Если i-й символ определяется в результате k_i альтернативных выборов, то вероятность его появления равна (1/2) k_i . Соответственно для выбора символа, который встречается с вероятностью p_i, нужно k_i= log₂(1/p_i) выборов. Смотри раздел Статический алгоритм Хафмана.

Количество информации, содержащееся в символе, которое определяется частотой его появления, равно:

Отсюда среднее количество информации на один произвольный символ равно:

E называют средним количеством информации на символ или энтропией источника информации. Результатом отдельного альтернативного выбора может быть или . Тогда всякому символу соответствует некоторая последовательность и . Такая последовательность является кодировкой символа. Энтропия одной буквы русского языка равна примерно Е₁≈4,35 бит.

Если при некотором кодировании символов i-ый символ имеет длину N_i, то средняя длина слов равна:

Если предположить, что набор символов можно поделить на равновероятные подмножества, то L=E. Следует иметь в виду, что на самом деле всегда E ≤ L (следствие теоремы кодирования Шеннона).

Разность L-E называется избыточностью кода , а 1-(E/L) - относительной избыточностью кода. Смотри раздел "Коррекция ошибок".

Представленные выше логарифмические зависимости косвенно подтверждаются законом Меркеля (1885 г). Время реакции испытуемого при требовании выбора определенного предмета из N имеющихся пропорционально log(N).

Если рассмотреть процесс подбрасывания монеты, то энтропия неизвестного результата следующего бросания максимальна, если вероятности выпадания каждой из сторон монеты равны (максимальная неопределенность; вероятностью вставания монеты на ребро пренебрегаем).

Обычный способ определения энтропии текста базируется на модели Маркова для текста. При этом вероятность появления очередного символа предполагается независимой от предыдущего символа (что, разумеется не всегда верно).

Если мы имеем n-буквенный алфавит и используем m-ичныйое кодовое представление (m уровней сигнала, при m=2 получем двоичное представление), то для передачи одной буквы может требоваться ~log(n)/log(m) элементарных сигналов.

Разность R = 1 - E_∞/H₀ показывает, насколько меньше единицы отношение предельной энтропии E_∞ к величине H₀ = log(n), которая характеризует наибольшую информацию, содержащуюся в одной букве алфавита с данным числом букв. Шеннон назвал эту разность избыточностью языка. Избыточность русского языка превышает 50%.

Одной из заслуг Шеннона является установление факта зависимости ограничения пропускной способности канала от уровня шума.

Иногда энтропия выражается в битах в секунду. Если для канала без памяти энтропия символа равна Е, и если источник генерирует один символ каждые t секунд, то энтропия в битах в секунду равна E/ t .

v = (L log(m))/E букв/ед. времени

Для каждого канала без памяти, емкость канала С=supI(X;Y) имеет следующее свойство (теорема Шеннона).

Для любого e > 0 и R e .

Если вероятность ошибки при передаче бита (BER) p_b приемлема, то достижимы скорости передачи вплоть до R(p_b), где

и E₂(p_b) является двоичной энтропийной функцией

Для любого p_b, скорости передачи выше R(p_b) не достижимы.

Для случая "белого" гауссова шума, когда все частоты имеют равные уровни, а амплитуды имеют гауссово распределение имеем:

где N_S - средняя мощность сигнала, а N_N - средняя можность шума. Из этой формулы непосредственно следует традиционная формула теоремы Шеннона для канала с заданной полосой пропускания и уровнем шума.

Энтропия указывает предельный уровень сжатия данных архиваторами. Написать программу, которая бы обеспечила более высокий уровень сжатия теоретически невозможно. Величина сжатия определяется избыточностью обрабатываемого массива бит. Каждый из естественных языков обладает определенной избыточностью. Среди европейских языков русский обладает одной из самых высоких уровней избыточности. Об этом можно судить по размерам русского перевода английского текста. Обычно он примерно на 30% больше.

Энтропия составных событий. Условная энтрпия

Пусть имеется два независимых опыта Х и У с таблицами вероятностей исходов:

Рассмотрим составной эксперимент , состоящий в том, что одновременно выполняются испытания Х и У. Такой эксперимент может иметь km исходов:

X1Y1,X1Y2. X1Ym; A2Y1, X2Y2. X2Ym;. ; XkY1, XkY2. XkYm,

где X1Y1 означает, что эксперимент X имел исход X1, а эксперимент Y - исход Y1. Понятно, что неопределенность эксперимента XY будет больше неопределенности каждого из X и Y в отдельности. Энтропия T(XY=E(X) + E(Y).

Если теперь предположить, что результаты опытов X и Y не являются независимыми. В этом случае уже нельзя предполагать, что энтропия составного опыта XY может быть равна сумме энтропий X и Y. Энтропия составного опыта XY будет равна:

E(XY) = - p(X1Y1)log(p(X1Y1)) - p(X1Y2)log(p(X1Y2)) - . - p(X1Ym)log(p(X1Ym)) - .
- p(X2Y1)log(p(X2Y1)) - p(X2Y2)log(p(X2Y2)) - . - p(X2Ym)log(p(X2Ym)) - .
- p(XkY1)log(p(XkY1)) - p(XkY2)log(p(XkY2)) - . - p(XkYm)log(p(XkYm)) ,

Здесь уже нельзя заменить вероятности p(X1Y1), p(X1Y2) и т.д. произведениями вероятностей (p(X1Y1) не равно p(X1)p(Y1), а p(X1)p_X1(Y1) - условная вероятность события Y1 при условии X1. Энтропия Е_Х(У) называется условной энтропией опыта Y при условии реализации опыта X.

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

При языковых исследованиях следует учитывать то, что появление в тексте определенной буквы меняет распределение вероятностей для следующей. Так появление буквы "е" делает весьма вероятным появление еще одной буквы "e". Но появление комбинации "ee" делает появление еще одного "e" крайне мало вероятным. Примеров таких корреляций можно привести достаточно много.

Для языков, использующих латинский алфавит, частоты использования отдельных букв весьма различны. Так если разместить символы букв по мере убывания их частоты использования, то для английского языка мы получим _ETAONRI. для немецкого - _ENISTRAD. и для французского - _ESANITUR. .Во всех случаях символ _ обозначает пробел между словами.

Классическое определение информационной энтропии (H) выглядит как:

где p_i - вероятность того, что реализуется конкретное значение х_i (i может принимать значения от 1 до n. I(x) - целочисленная случайная функция (информационное содержимое Х).

Информация, данные, сигналы. Источники информации и ее носители. Количество информации и энтропия. Формулы Хартли и Шеннона.

Информация будем определять через ее основные свойства (т.к. наряду с материей и энергией она является первичным понятием нашего мира и поэтому в строгом смысле не может быть определена):

Энтропия –это мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита.

Мера неопределенности источникас равновероятными состояниями и характеризующего его ансамбля U – это логарифм объема алфавита источника:

(1.1)

Впервые данная мера была предложена Хартли в 1928г. Основание логарифма в формуле не имеет принципиального значения и определяет только масштаб или единицу количества информации.

В общем случае, если вероятности различных состояний источника не одинаковы, степень неопределенности конкретного состояния зависит не только от объема алфавита источника, но и от вероятности этого состояния, тогда

(1.2)

(1.3)

(1.4 а) –формула Шеннона.

В тоже время энтропия по Шеннону это среднее количество информации содержащееся в одном из не равновероятных состояний. Она позволяет учесть статистические свойства источника информации.

Формула Хартли – частный случай формулы Шеннона для равновероятных альтернативных событий. Подставив в формулу (1.4 a)вместо , которое в равновероятном случае не зависит от i, значение , получим:

(1.4 b) –формула Хартли.

Из (1.4 b) следует, что чем больше количество альтернатив N, тем больше неопределенность H. Эти величины связаны в формуле (1.4 b) не линейно, а через двоичный логарифм. Логарифмирование по основанию 2 и приводит количество вариантов к единицам измерения информации – битам. Энтропия будет являться целым числом лишь в том случае, если N является степенью числа 2.

Свойства энтропии:

1) Энтропия любого дискретного ансамбля не отрицательна (1.5).

(1.1)

(1.2)

(1.3)

(1.4 а) –формула Шеннона.

(1.4 b) –формула Хартли.

Свойства энтропии:

1) Энтропия любого дискретного ансамбля не отрицательна (1.5).

Коды различаются по числу элементарных символов (сигналов), из которых формируются комбинации, иными словами - по числу возможных состояний системы . В азбуке Морзе таких элементарных символов четыре (точка, тире, короткая пауза, длинная пауза). Передача сигналов может осуществляться в различной форме: световые вспышки, посылки электрического тока различной длительности, звуковые сигналы и т. п. Код с двумя элементарными символами (0 и 1) называется двоичным. Двоичные коды широко применяются на практике, особенно при вводе информации в электронные цифровые вычислительные машины, работающие по двоичной системе счисления.

Предположим, что перед нами поставлена задача: закодировать двоичным кодом буквы русской азбуки так, чтобы каждой букве соответствовала определенная комбинация элементарных символов 0 и 1 и чтобы среднее число этих символов на букву текста было минимальным.

Первое, что приходит в голову - это, не меняя порядка букв, занумеровать их подряд, приписав им номера от 0 до 31, и затем перевести нумерацию в двоичную систему счисления. Двоичная система - это такая, в которой единицы разных разрядов представляют собой разные степени двух. Например, десятичное число 12 изобразится в виде

и в двоичной системе запишется как 1100.

Десятичное число 25 -

- запишется в двоичной системе как 11001.

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

В этом коде на изображение каждой буквы тратится ровно 5 элементарных символов. Возникает вопрос, является ли этот простейший код оптимальным и нельзя ли составить другой код, в котором на одну букву будет в среднем приходиться меньше элементарных символов?

Чтобы составить такой код, очевидно, нужно знать частоты букв в русском тексте. Эти частоты приведены в таблице 18.8.1. Буквы в таблице расположены в порядке убывания частот.

Читайте также: