Учебное пособие: Теория информации

Тогдаединицу количества информации на один элемент сообщения называют двоичной единицей или битом . При этом единица неопределенности (двоичная единица или бит) представляет собой неопределенность выбора из двух равновероятных событий ( bit — сокращение от англ. binary digit — двоичная единица)

Так как из log₂ m = 1 следует m = 2, то ясно, что1 бит - это количество информации, которым характеризуется один двоичный элемент при равновероятных состояниях 0 и 1.

Двоичное сообщение длины n содержит n бит информации.

Единица количества информации, равная 8 битам, называется байтом .

Если основание логарифма выбрать равным десяти, то энтропия выражается в десятичных единицах на элемент сообщения - дитах , причем 1 дит = log₁₀ 2 бит = 3,32 бит.

Пример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 × 10⁶ бит

Пример2 . Определить минимальное число взвешиваний, которое необходимо произвести на равноплечих весах, чтобы среди 27 внешне неотличимых монет найти одну фальшивую, более легкую.

Решение. Так как монеты внешне не отличимые, то они представляют источник с равновероятными состояниями, а общая неопределенность ансамбля, характеризующая его энтропию, поэтому составляет: H1= Iog₂ 27 бит.

Одно взвешивание способно прояснить неопределенность ансамбля насчитывающего три возможных исхода (левая чаша весов легче, правая чаша весов легче, весы находятся в равновесии).Так как все исходы равновероятны (нельзя заранее отдать предпочтение одному из них), то результат одного взвешивания представляет источник с равновероятными состояниями, а его энтропия составляет: H2= Iog₂ 3 бит.

Так как энтропия отвечает требованию аддитивности и при этом Н1=3Н2= 3 1 og ₂ 3 , то для определения фальшивой монеты достаточно произвести три взвешивания.

Алгоритм определения фальшивой монеты следующий. При первом взвешивании на каждую чашку весов кладется по девять монет. Фальшивая монета будет либо среди тех девяти монет, которые оказались легче, либо среди тех, которые не взвешивались, если имело место равновесие. Аналогично, после второго взвешивания число монет, среди которых находится фальшивая монета, сократится до трех. Последнее, третье, взвешивание дает возможность точно указать фальшивую монету.

Рассмотренная выше оценка информации основана на предположении о равновероятности всех знаков алфавита .

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

Пусть на основании статистического анализа известно, что в сообщении длины n знак x_i появляется n_i раз, т.е. вероятность появления знака:

, (i = 1, 2, 3, ... , m).

Все знаки алфавита составляют полную систему случайных событий, поэтому:

.

Число всех возможных сообщений длины n , в которых знак x_i входит n_i раз, где i = 1, 2, 3 ... ,m, определяется как число перестановок с повторениями из n элементов, спецификация которых {n₁ , n₂ , ..., n_m }. Поэтому количество возможных сообщений определяют по формуле:

.

Например, план застройки улицы 10 домами, среди которых 3 дома одного типа, 5 другого и 2 третьего, можно представить

.

Количество информации можно найти по формуле:

I = log N = log n! - (log n₁ !+log n₂ !+...+log n_m !).

Для достаточно больших n это выражение можно преобразовать с помощью приближенной формулы Стирлинга:

logn! »n(lnn - 1).

Воспользовавшись формулой Стирлинга и соотношением, получают: