Энтропия и информация для систем с непрерывным множеством состояний

 

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

Рассмотрим систему х, которая определяется непрерывной случайной величиной х с плотностью распределения f(x).

Определим энтропию системы. Заменим непрерывную кривую f(x) ступенчатой.

Площади прямоугольников f(x_i)*Dx – вероятности попадания в них случайных величин.

 

 

 

 

Энтропия системы:

При достаточно малых сумму можно заменить интегралами

       , т.к. интеграл вероятностей, следовательно

- энтропия непрерывной системы

Когда величина , особый случай. В этом случае  и , т.е. чем выше точность определения состояния системы, тем выше неопределённость (H(x)).

 - приведённая энтропия

 

 

Условная энтропия непрерывной системы

 

Пусть имеется две системы: X и Y, они взаимозависимы и непрерывны.

f(x, y) – плотность распределения для состояния определнной системы.

f₁(x) – плотность распределения системы X.

f₂(y) – плотность распределения системы Y.

f(y/x), f(x/y) – условная плотность распределения. Имея эти плотности, можно определить

условную энтропию.

 

Частная условная энтропия

Полная средняя условная энтропия получившаяся в результате осреднения

Для непрерывных систем – энтропия совместимых систем равна сумме энтропий.

 

H(x, y) = H(x) + H(y / x)

 

Пример: Найти энтропию непрерывной системы X, все состояния которой на участке от до  равновероятны.

 

H^* = =

Пример: Для нормального закона распределения.

 

 

H(x) =

Подставляем f(x) и log в интеграл, получим после вычисления

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

 

Количественное определения избыточности

 

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

Пример, который подтверждает справедливость данного утверждения.

 

Пример: Пусть имеется два элемента a, в.   Рассмотрим случаи передачи информации с помощью этих элементов:

 1) Элементы независимы и равновероятны

1 бит/символ           m – количество переданных символов

 

2) Элементы независимы и неравновероятны

  

 бит/символ

 

3) Элементы взаимозависимы и равновероятны

 

p(a) = p(b) = ½

 

Пусть p(a / a) = p(b / b) = p₁ – вероятность повторения символов

      p(a / b) = p(b / a) = p₂ - вероятность чередования символов

 

 

p1,p2	½, ½	¼, ¾	1/8, 4/8	0, 1
	1	0.815	0.541	0

 

4) Элементы взаимозависимы и неравновероятны

 

p(a) = ¾;                  p(b) = ¼

p(a / a) = 2/3            p(b / a) = 1/3

p(a / b) = 1               p(b / b) = 0

 

I^| = = 0.685 бит/символ

 

Пусть передаётся сообщение из n взаимозависимых и не равновероятных элементов.

I = n * I^|

 

Если устранить внутренние вероятностные связи, то информация возрастёт до максимального значения I_max. При этом тоже количество информации может содержаться в сообщении из меньшего числа элементов n_0.

 

 В данном случае мерой избыточности может служить относительное число лишних элементов. Обозначим избыточность символом D.

 

 - мера избыточности

Если принять, что избыточность определяется только взаимосвязью элементов, то

 

Если принять, что избыточность определяется только распределением вероятностей, то в качестве , m – количество элементов

 

Таким образом, выделяют две частных избыточности:

1) Частная избыточность, обусловленная взаимосвязью между элементами

 

 

2) Частная избыточность, зависящая от распределения вероятностей

      m – количество символов алфавита

 

3) Выделяют полную информацию избыточность

D = D_p + D_s – D_pD_s D_p + Вы

 

Рассмотрим основные цифры и порядки для рассмотрения примера

 - относительная величина

 

                               D_s * D_p = 0.03 принебрегаем

Пример избыточности в нашем языке можно проиллюстрировать следующими цифрами. Если бы все комбинации букв были возможны, то имея 30 букв, можно было бы составить 30¹ = 30 однобуквенных слов. 30² = 900 – двухбуквенных слова. 30³ = 27 000 – трёхбуквенных слова. 30⁴ = 810 000 – четырёх буквенных слова.

Обычный язык содержит 50 000 слов, т.е. среднее число букв в слове, составляет примерно 3,5. В обычном в языке среднее число букв в слове семь, следовательно, возможные комбинации 30⁷ = 21 * 10⁹ - столько слов можно было бы иметь, следовательно, количество букв, которые являются словами = .

Один из методов борьбы с избыточностью применение неравномерных кодов. Метод построения оптимального неравномерного кода Шеннона - Фана. Пусть в алфавите имеется n букв и вероятности появления этих букв. Расположим эти буквы в порядке убывания их вероятностей. Затем разбиваем их на две группы так, чтобы суммарная вероятность в каждой группе по возможности была одинаковой (верхнюю группу кодируем единицей, а нижнюю нулём). Это будет первый символ кода. каждую из полученных групп делим снова на две части возможно близкой к суммарной вероятности, присваиваем каждой группе двойной символ: (один или ноль). Процесс деления продолжаем, пока не придём к первой группе.

 

Пример: Данный алфавит, содержит шесть букв.

 

Буква	Вер-ть	1	2	3	4
a1	0.4	1
a2	0.2	0	1
a3	0.2	0	0	1
a4	0.1	0	0	0	1
a5	0.05	0	0	0	0	1
Длина буквы a6	0.05	0	0	0	0	0

В случае равномерного кодирования потребовалось бы три бита (2³ = 8).

Для данного кода

Длина буквы

 бит/символ

 

Подсчитаем энтропию данного алфавита

бит/сим

m – количество символов вторичного алфавита

Если вторичный алфавит – двоичный, то m = 2, следовательно .

 

Пример: Задан алфавит из восьми букв и вероятности их появления. Построить оптимальный неравномерный код Шеннона-Фана.

 

Буква	Вер-ть	1	2	3	4
a1	0.25	1	1
a2	0.25	1	0
a3	0.125	0	1	1
a4	0.125	0	1	0
a5	0.625	0	0	1	1
a6	0.625	0	0	1	0
a7	0.625	0	0	0	1
a8	0.625	0	0	0	0

 

 бит

 бит/символ

Коэффициент статического сжатия

Коэффициент общей эффективности

К_СС и К_ОЭ характеризуют оптимальность алфавита

 

Пример: Построить оптимальный код Шеннона-Фана.

 

Буква	Вер-ть	1	2	3	4
а1	0.25	1	1
а2	0.25	1	0
а3	0.25	0	1
а4	0.1	0	0	1
а5	0.1	0	0	0	1
а6	0.5	0	0	0	0

 

l_ср  = 2.4 бит

 

 бит/символ – т.к. разделили неравномерно три столбца, лучше не получиться.

       

 

Блочное кодирование

 

Пусть первичный алфавит содержит 2-е буквы: а и б. p(A) = 0.7; p(B) = 0.3

 

H = - 0.7*log 0.7 – 0.3 log 0.3 = 0.881 бит/символ

 

Составим новый алфавит из 2-х буквенных комбинаций

АА	0.49	1
АВ	0.21	0	1
ВА	0.21	0	0	1
ВВ	0.09	0	0	0

 

L_ср = 1 * 0.49 + 2 * 0.21 + 3 * 0.21 + 4 * 0.09 = 1.81 бит

 

На одну букву

бит < 1                             l_ср > H                   3%

Пример: Составим алфавит из трёх буквенных комбинаций.

 

Буква	Вероят.	1	2	3	4
ААА	0.343	1	1
ААВ	0.147	1	0
АВА	0.147	0	1	1
ВАА	0.147	0	1	0
АВВ	0.063	0	0	1	1
ВАВ	0.063	0	0	1	0
ВВА	0.063	0	0	0	1
ВВВ	0.027	0	0	0	0

 

l_ср = 2.686 бит

.895 бит - это больше 1,5% и H, следовательно, можно делить по четыре группы.

 

Избыточность от округления

Пример: Кодируются цифры от 0 до 10. Чтобы их представить в виде двоичных, надо

2³<10<2⁴

4 бита   

1 символ – 4 бита

Кодируем блоки по 2 цифры

00

01

…

99

Для передачи информации с помощью двоичной системы 2⁶<99<2⁷

                                              7 бит

На 1 символ: 7/ 2 = 3,5 бита

 

Кодируются блоки по 3 цифры

000

2^10= 1024, 10 бит информации, следовательно, на один символ: 10/3 = 3,3 бита

001

…

999

 

Подсчитаем энтропию

Н = log n = log 10 = 3,32 бит

 

Чтобы определить избыточность, вызванную округлением, воспользуемся:

где m1 – число символов первичного алфавита; m2 – число символов вторичного алфавита; L – длина кодовой комбинации.

,

 

Пример: Передается алфавит из 5 символов: 1, 2, 3, 4, 5, следовательно, m₁=5 с помощью двоичных символов 0,1, следовательно, m₂=2.

Для передачи сообщения потребуется:

 

D₀ – избыточность от округления

                               m - коэффициент;

                                                                                              К – большее целое число.

Пример:

Пример: Определить избыточность сообщений от округления при побуквенном и поблочном кодировании, если кодируются цифровые сообщения и передаются в двоичном коде. Кодирование осуществляется блоками по 4, 5, 6 цифр.

 

Первичный алфавит m₁=10

Вторичный алфавит m₂ = 2

Первичный алфавит из 2-х букв                 m₁=10000  m₂=2

Первичный алфавит из блоков по пять          m₁=100000

 

Кодируются символы по шесть букв                    m₁=10⁶

 , следовательно, этот алфавит наиболее близок к оптимальному.

 

 

Код Хафмана

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

Методика построения кодов следующая:

Пусть есть алфавит А, содержащий буквы а₁, а₂, …, а_n, вероятности появления которых р₁, р₂,…, р_n. Буквы алфавита располагаем в порядке убывания их вероятностей  . Берем две последние буквы   и объединяем их в одну букву b. Получаем новый алфавит А₁

а₁, а₂, …, а_n-2 b

p₁, р₂,…, р_n-2 p_n-1 + p_n

 

Алфавит А₁ называют сжатым, полученным из алфавита А путем однократного сжатия.

Буквы алфавита А₁ располагаем в порядке убывания их вероятностей. Затем проводим процедуру сжатия, получаем алфавит А₂. Продолжаем процедуру сжатия до тех пор, пока у нас не останется 2 буквы.

Буква а1 а2 а3 а4 а5 а6	А Вероятность 0,4 0 0,2 10 0,2 111 0,1 1101 0,05 11001 0,05 11000	Сжатые алфавиты
		А1 0,4 0 0,2 10 0,2 111 0,1 1101 0,1 1100	А2 0,4 0 0,2 10 0,2 111 0,2 110	А3 0,4 0 0,4  11 0,2 10	А4 0,6 (1) 0,4 (0)

 

Процедура кодирования

 

Две буквы последнего алфавита кодируем 1 и 0. Затем кодируется предыдущий алфавит. Процесс кодирования закончен. Чтобы определить эффективность, надо посчитать среднее число символов на алфавит.

Кодирование алфавита по методу Хафмана не является однозначно определенной процедурой. Можно получать разные коды Хафмана.

 

Чтобы посмотреть изменение кода Хафмана, рассмотрим пример другой кодировки:

 

Буква а1 а2 а3 а4 а5 а6	А Вероятность 0,4 11 0,2 01 0,2 00 0,1 100 0,05 101 0,05 1010	Сжатые алфавиты
		А1 0,4 11 0,2 01 0,2 00 0,1 101 0,1 100	А2 0,4 11 0,2 10 0,2 01 0,2 00	А3 0,4 0 0,4 11 0,2 10	А4 0,6 (1) 0,4 (0)

 

Если посчитать , то оно не изменилось ,т.е. каким образом кодировать роли не играет.

Процедура декодирования кодов Хафмана является однозначной.

Используя методику Хафмана, можно строить оптимальные коды, если для кодирования используется m элементарных сигналов. При построении таких кодов используется процедура сжатия, при которой сливаются каждый раз m букв алфавита. Последовательность сжатия приводит к алфавиту из m букв.

Число букв исходного алфавита n должно быть представляемо  n = m + k *(m -1), k – целое число. Этого условия всегда можно достичь, если ввести в исходный алфавит фиктивные буквы, вероятность которых равна нулю.

Дан алфавит из 6 букв с вероятностями. Построить троичный код Хафмана 0, 1, 2.

 

Требуемое число букв:

n = 3 + k * (3 - 1),

k = 1 n = 5

k = 2 n = 7

не хватает одной буквы а₇ с вероятностью равной нулю

 

Буква а1 а2 а3 а4 а5 а6 а7	А Вероятность 0  0,4 2  0,2 10 0,2 11 0,1 120 0,05 121 0,05 122 0	С ж а т и е
		А1 0 0,4 2    0,2 10 0,2 11 0,1 12 0,1	А2 0,4 (0) 0,4 (1) 0,2 (2)

 

Подсчитаем энтропию

m – количество символов

Существует еще одна методика

(7)

1

1 0

Схема получения кода Хафмана с помощью кодового дерева

1 0

Дан алфавит. Располагаем буквы в порядке убывания вероятностей

	1 0

1

0,28

а₁    0,5

(4)

0,05

0,22

0,08

001  а₂    0,15

011  а₃    0,12 1

(2)

010  а₄    0,1   0                       

0,13

00011 а₅    0,04 1

(3)

00010 а₆    0,04 0

(1)

00001 а₇    0,03 1

00000 а₈    0,02 0

 

1. Находят 2 буквы с вероятностями (а₇ и а₈) и проводят от них линию к точке, в которой вероятность равна их сумме

2. Теперь меньшими вероятностями обладают буквы а₅ и а₆. Соединяют их линиями в одной точке с вероятностью 0.08

3. Соединяем 0,08 и 0,05, получает 0,13

4. Соединяем буквы а₃ и а₄

5. Соединяем 0,15 и 0,13

И так далее…

 

Кодируем ветки

Обозначим цифрой один верхнюю линию узла, нижнюю ноль.

Коды представляют собой последовательность 0 и 1, которые встречаются по пути от точки с вероятностью единица, до кодируемой буквы.

 

Передача информации по дискретным каналам связи

 

Для анализа информационных возможностей канала связи используется обобщённая информационная модель каналов связи.

 

 

 

               Z               X                            Y                И

							ПИ

П2

П1

ИИ

 

 

             ЛС

 

ИИ – источник информации

П₁, П₂ – преобразователи

ЛС – линия связи

ИП – источник помех

ПИ – приёмник информации

Источник информации создаёт cигналы z, которые кодируются в преобразователе П1, превращаются в сигналы x и поступают в линию связи (ЛС). В результате действия помех, сигнал Y на приёмном конце, отличается от X. Помехи создаются воображаемым источником помех (ИП) и поступают в линии связи в виде мешающего сигнала . Преобразователь П2 декодирует сигналы, и передаёт в приёмник информации. Приёмник информации перерабатывает принятое сообщение. Для организации эффективной передачи информации решают три задачи:

1. Определение максимально возможной скорости передачи информации по каналу;

2. Разработка кодов, позволяющих увеличить скорость передачи информации;

3. Согласование канала с источником.

Важнейшей характеристикой канала является пропускная способность (обозначается символом С). - Наибольшая возможная скорость передачи информации по каналу. Пропускная способность определяют следующим образом:

, где V_x- средняя скорость передачи символов, I_y®x – максимальное возможное значение среднего количества информации на один символ принятого сигнала.

, - средняя длительность передаваемых символов

Взаимная информация

           - характеризует потери информации.

 

При отсутствии помех H(x / y) = 0 и . А максимальные I_y®x = log₂m

Пропускная способность канала

       m – количество символов алфавита, который кодируется