Файл: прикладная теория информации.pdf

28
????(????
2
|????
2
) =
????(????
2
|????
2
)????(????
2
)
????(????
2
)
=
0,95 ∙ 0,1 0,104
= 0,9134.
Как видно, в канале с шумом значение вероятности правильного приема символа зависит от степени его повторяемости и особенностей статистических характеристик канала. Чем чаще символ повторяется, тем достовернее его прием.
Пример 2.2 .1. Имеется дискретный канал без памяти с входным источ- ником ???? = {????
1
, ????
2
}, ????
1
= 0, ????
2
= 1 и выходным источником ???? = {????
1
, ????
2
}, ????
1
=
0, ????
2
= 1. Cимволы источника ???? появляются с вероятностью ????(????
1
) = 0,9 и
????(????
2
) = 0,1.
В канале имеются шумы. В отличие от примера 2.2, переходные вероятно- сти для символов ????
1
и
????
2
источника
???? имеют равные значения. Пусть
????(????
1
|????
1
) = ????(????
2
|????
2
) = 0,99,
????(????
2
|????
1
) = ????(????
1
|????
2
) = 0,01.
1. Определяем вероятности появления символов на выходе канала.
????(????
1
) = ????(????
1
|????
1
)????(????
1
) + ????(????
1
|????
2
)????(????
2
) =
= 0,99 ∙ 0,9 + 0,01 ∙ 0,1 = 0,892,
????(????
2
) = ????(????
2
|????
1
)????(????
1
) + ????(????
2
|????
2
)????(????
2
) =
= 0,01 ∙ 0,9 + 0,99 ∙ 0,1 = 0,108.
2. По теореме Байеса получаем:
????(????
1
|????
1
) =
????(????
1
|????
1
)????(????
1
)
????(????
1
)
=
0,99 ∙ 0,9 0,892
= 0,99887,
????(????
2
|????
2
) =
????(????
2
|????
2
)????(????
2
)
????(????
2
)
=
0,99 ∙ 0,1 0,108
= 0,91666.
Как видно, вероятность правильного приема также зависит от степени по- вторяемости символов источника и уровня шумов в канале.
Значения вероятностей ошибок в реальных каналах передачи информации зависят от многих факторов:
– свойств физических каналов;
– свойств сигналов, которые являются физическими переносчиками сооб- щений;
– метода обработки сигналов на приемной стороне;
– отношения средней мощности сигнала к средней мощности шума
P
s
P
N
на выходе канала передачи информации.
Величину отношения мощности сигнала к мощности шума часто выража- ютв логарифмическом масштабе:

29
P
s
P
N
= (10 log
10
????
????
????
????
) дБ.
Например, для цифрового телевизионного вещания с хорошим качеством стандартные значения отношения
????
????
????
????
составляют (60 – 70) дБ. В этом случае от- ношение
????
????
????
????
превышает величину
10 6
2.6. Количественная оценка информации
Понятие количества информации, предложенное К. Шенноном в 1948 г. определяется при выполнении трех аксиом:
1. Информация события (символа)
????
????
∈ ????, появляющегося с вероятностью
????
????
, имеет положительное значение:
????(????
????
) ≥ 0.
2. Аксиома суммируемости информации.
Пусть независимые события ????
????
и
????
????
появляются с вероятностью
????
????
и
????
????
Напомним, если исход одного события не влияет на исход другого, то такие со- бытия называются независимыми и для таких событий вероятность совместного события (????
????
,
????
????
) равна ????(????
????
, ????
????
) = ????
????
∙ ????
????
Совместная информация двух независимых событий (????
????
, ????
????
) равна сумме их информаций:
????(????
????,????
) = ????(????
????
) + ????(????
????
).
Пример 2 .3. Пусть двоичный источник без памяти ???? = {0,1} формирует символ ????
1
с вероятностью
???? = 0,2 и символ ????
2
с вероятностью (
1 − ????) = 0,8. Ве- роятность появления сообщения вида (????
2
????
1
????
1
????
2
????
1
) = (10010) равна
????(????
2
????
1
????
1
????
2
????
1
) = ????(10010) = ????
3
(1 − ????)
2
= 0,2 3
(1 − 0,2)
2
= 0,00512.
Если вы получили сообщение о том, что 1 июня температура воздуха в
Минске достигнет +20 °С и, что экзамен состоится в аудитории 505-3 – это неза- висимые события. Содержание этого сложного сообщения равняется сумме ин- формации о погоде и экзамене.
3. Информация является непрерывной функцией вероятности события.
Определение 2.5. Количество информации, передаваемое источником при появления одного символа ????
????
с вероятностью
????, равно

30
???? = log
1
????
= − log ????. (2.22)
Замечание. Формула 2.22 определяет понятие собственной информации сообщения ????
????
дискретного источника
????.
Для логарифма может быть использовано основание 10, основание 2, осно- вание e натуральных логарифмов. Разные основания только изменяют единицы меры информации. Измерение объема информации по формуле (2.22) впервые было предложено Р. В. Л. Хартли в 1928 г. (R. V. L. Hartley (амер. ученый (1888
– 1970))) При использовании логарифмов с основанием 10 количество информа- ции измеряется в единицах Хартли.
Пример 2.4. Пусть ???? = 10
−5
. Получаем ???? = log
10 1
????
= − log
10 10
−5
= 5 единиц информации Хартли.
Пример 2.5. Пусть ???? = 10
−1
. Получаем одну единицу информации
Хартли:
???? = log
10 1
????
= − log
10 10
−1
= 1.
Пример 2.6. Пусть ???? = 1 (событие непременно состоится). Получаем нуль единиц информации Хартли:
???? = log
10 1
????
= − log
10 1 = 0 .
При использовании логарифмов с основанием 2 количество информации измеряется в битах.
П р и м е р . 2.7. Пусть
???? =
1 2
. Получаем
???? = log
2 1
1 2
⁄
= − log
2 1
2
= 1 бит.
Пример .2.8. Пусть???? =
1 32
, тогда
???? = log
2 1
1 32
⁄
= − log
2 1
32
= 5 бит.
Пример 2.9 . Пусть передается сообщение ???? = (????
1
????
2
????
3
????
4
????
5
) = (10010), составленное из независимых символов ????
????
∈ {0,1}. События ????
????
появляются с ве- роятностью ????
????
=
1 2
. Количество информации в этом сообщении равно
???? = log
2 1
????(????
1
????
2
????
3
????
4
????
5
)
= log
2 1
(
1 2
)
5
= − log
2 2
−5
= 5 бит.

31
Полученное значение соответствует сумме информаций пяти независимых событий:
????(????) = ????(????
1
) + ⋯ + ????(????
5
) = 5 бит.
На рис. 2.7 показан график, характеризующий количественное изменение
???? в зависимости от вероятности события.
Рис. 2.7. Изменение количества информации ???? в зависимости от вероятности возникновения события
Как видно, с уменьшением вероятности появления события или увеличе- нием его неопределенности, количество информации возрастает.
Определение информации можно трактовать как некоторое отражение воз- никновения событий.
2.7. Энтропия
Пусть двоичный дискретный источник без памяти ???? = {????
1
, ????
2
}, ???? = 2 фор- мирует символ ????
1
= 0 с вероятностью ???? и символ ????
2
= 1 с вероятностью (1 − ????).
Если получен символ ????
1
, то это сообщение оценивается количеством информа- ции, равным
????(????
1
) = − log ????.
Аналогично, при приеме символа ????
2
количество полученной информации определяется как
????(????
2
) = − log(1 − ????).
Одной их характеристик двоичного дискретного источника без памяти является среднее количество (ожидаемое количество) информации, выдаваемой источником. Так как источник формирует случайные события, то математиче- ское ожидание определяется по формуле

32
????(????) = ∑
????
????
????(
????
????=1
????
????
) = ∑
????
????
????(
2
????=1
????
????
) = ????
1
????(????
1
) + ????
2
????(????
2
) =
= −???? log ???? − (1 − ????)log(1 − ????).
П р и м е р 2 . 1 0 . Пусть двоичный источник формирует символ
????
1
= 0 с ве- роятностью ???? = 0,2 и символ ????
2
= 1 с вероятностью (1 − ????) = 0,8. Сообщения оцениваются количеством информации, равным
????(????
1
) = − log 0,2 = 2,3219 бит, ????(????
2
) = − log 0,8 = 0,3219 бит.
Полученные значения ????(????
????
) соответствуют точкам на графике, показанном на рис. 2.7.
Cреднее значение количества информации источника
????(????) = 0,2 ∙ 2,3219 + 0,8 ∙ 0,3219 = 0,7219 бита.
Определение 2.6. Энтропия ???? источника информации – это средняя ин- формация, полученная для всех возможных событий.
Энтропия источника (пример 2 .10) равна ???? = 0,7219 бит/символ. В этом примере энтропия источника информации определяется как математиче- ское ожидание количества информации
????(????) = ????.
Для дискретного источника двух независимых событий ???? = {0,1} с веро- ятностями ???? и (1 − ????) энтропия определяется как
???? = −???? log
2
???? − (1 − ????)log
2
(1 − ????). (2.23)
Замечание. Энтропия двоичного источника, вычисляемая по формуле
(2.23), называется функцией (формулой) Шеннона.
На рис. 2.8 показан график энтропии двух событий как функция вероятно- сти. Максимальное значение энтропии равно 1 бит/символ, когда ????
1
= ????
2
=
=
1 2
???? = −???? log
2
???? − (1 − ????)log
2
(1 − ????) =
= −
1 2
log
2 1
2
−
1 2
log
2 1
2
= 1 бит/символ.
Это соответствует наибольшей неопределенности для двух событий. Для значения ????, равного нулю или единице, события имеют полную определенность, и никакая информация не передается.

33
Рис. 2.8. Энтропия двоичного источника
Определение 2.7. Энтропия дискретного источника без памяти с символами алфавита ???? = {????
1
, ????
2
, … , ????
????
} и соответствующими вероятностями ????
1
, ????
2
, … , ????
????
равна
???? = ????(????
1
, ????
2
, … , ????
????
) = ∑
−????
????
????
????=1
log ????
????
. (2.24)
Замечания:
1. Величину (2.24) называют также неопределенностью источника.
2. Из Определения 2.7 следует понятие энтропии как среднее количество информации, приходящейся на один символ источника.
П р и м е р 2 . 1 1 . Вычислим энтропию источника с алфавитом из четырех символов ???? = {????
1
, ????
2
, ????
3
, ????
4
} = {????, ????, ????, ????} с вероятностями ????
1
=
1 2
, ????
2
=
1 4
, ????
3
=
=
1 8
, ????
4
=
1 8
Решение:
???? = ∑
−????
????
4
????=1
log
2
????
????
= −(
1 2
log
2 1
2
+
1 4
log
2 1
4
+
1 8
log
2 1
8
+
1 8
log
2 1
8
) =
=
1 2
∙ 1 +
1 4
∙ 2 +
1 8
∙ 3 +
1 8
∙ 3 = 1,75 бит/символ.

34 2. Для дискретного источника без памяти с равной вероятностью ????
????
=
1
????
энтропия увеличивается с увеличением размерности алфавита ????.
Пример 2 .12 . Вычислим энтропию источника с алфавитом из четырех символов ???? = {????
1
, ????
2
, ????
3
, ????
4
} = {????, ????, ????, ????} с равными вероятностями ????
1
=
1 4
, ????
2
=
1 4
, ????
3
=
1 4
, ????
4
=
1 4
Решение:
???? = ∑
−????
????
4
????=1
log
2
????
????
=
= −(
1 4
log
2 1
4
+
1 4
log
2 1
4
+
1 4
log
2 1
4
+
1 4
log
2 1
4
) = 2 бит/символ.
В примере 2.11, где разные значения вероятностей
????
????
,
???? = 1,75 бит/сим- вол.
Теорема 2.1. Если все события имеют одинаковую вероятность
????
????
… = ????
????
, энтропия дискретного источника без памяти максимальна и равна
????
0
= log
2
???? бит/символ.
В этом случае неопределенность источника максимальна и источник пере- дает максимально возможное среднее количество информации, приходящее на один символ (см. рис. 2.8 и пример 2.12).
Определение 2.8. Величина
????
0
определяет емкость дискретного источника как системы хранения информации.
3. Источник без памяти с разными значениями вероятности появления сим- волов алфавита обладает энтропией, меньшей log
2
????.
Сравнивая источник примера 2.11, где ???? = 4, ???? = 1,75 бит/символ c ис- точником такого же размера, но с одинаковыми значениями вероятностями ????
1
=
????
2
= ????
3
= ????
4
=
1 4
, имеем
???? = 1,75 < ????
0
= log
2
???? = 2.
4. Энтропия блокового источника равна
????
′
= ????????, где ???? – энтропия источника одиночных символов.
П р и м е р 2 . 1 3 .
1. Источник формирует символы
???? = {????
1
, ????
2
} = {0,1} c вероятностями {????
1
=
1 3
, ????
2
=
2 3
}. Размерность алфавита ???? = 2. Энтропия источника одиночных симво- лов равна

35
???? = ∑
−????
????
2
????=1
log
2
????
????
=
1 3
∙ 1,585 +
2 3
∙ 0,585 = 0,918 бит/символ.
2. Имеется блоковый источник
????
2
= {????
1
, ????
2
, ????
3
????
4
}, ???? = 2. Символы ????
1
=
= (00), ????
2
= (01), ????
3
= (10), ????
4
= (11) получены расширением источника оди- ночных символов ???? = {????
1
, ????
2
} = {0, 1} c вероятностями {????
1
=
1 3
, ????
2
=
2 3
}. Вычис- лить энтропию источника ????
2
Решение
1. Вычисляем вероятности появления символов источника ????
2
. Вероятность
????(????
????
, ????
????
) совместного события ????
????
и
????
????
равна
????(????
????
, ????
????
) = ????
????
∙ ????
????
Получаем следующие значения вероятностей:
????(????
1
) = ????
1
∙ ????
1
=
1 9
,
????(????
2
) = ????
1
∙ ????
2
=
2 9
,
????(????
3
) = ????
2
∙ ????
1
=
2 9
,
????(????
4
) = ????
2
∙ ????
2
=
4 9
2. Энтропия источника равна
????′ = ∑
−????(????
????
)
4
????=1
log
2
????(????
????
) =
1 9
∙ 0,585 +
2 9
∙ 2,1699 +
2 9
∙ 2,1699 +
+
4 9
∙ 1,1699 = 1,83 бит/символ.
Как видно, энтропия блокового источника определяется свойством 4,
????
′
= ???????? = 2 ∙ 0,918 = 1,83 бит/символ.
2.8. Относительная избыточность источника
Определение 2.9. Избыточность дискретного источника без памяти
???? ={????
1
, ????
2
, … , ????
????
} – это разность между емкостью ????
0
источника и энтропией ???? источника:
???? = ????
0
− ????. (2.24)

36
Определение 2.10.Относительной избыточностью источника называется величина
???? =
????
????
0
= 1 −
????
????
0
. (2.25)
Пример. 2.1 4 . Используя данные примера 2.11 (источник ???? =
= {????
1
, ????
2
, ????
3
, ????
4
} с разными вероятностями, ???? = 1,75) и значение ????
0
= 2 для та- кого же источника, но с одинаковыми вероятностями, получаем величину избы- точности
???? = 2 − 1,75 = 0,25.
Относительная избыточность источника равна
???? = 1 −
1,75 2
= 0,125 ≅ 12,5 %.
2.9. Задания для самостоятельного выполнения
1. Вычислить количество информации выдаваемой источником, если раз- мерность алфавита ???? = {????
1
, ????
2
, … , ????
????
} равна ???? = 3. Вероятности появления символов источника равны:
????
1
= 0,15, ????
2
= 0,5, ????
3
= 0,35.
2. Пусть передается сообщение (
????
1
????
2
????
2
????
1
????
3
????
4
????
5
????
6
). Вычислить количе- ство информации в этом сообщении. Размерность алфавита ???? = {????
1
, ????
2
, … , ????
6
} равна ???? = 6. Вероятности появления символов источника равны: ????
1
= 0,05, ????
2
=
0,15, ????
3
= 0,05, ????
4
= 0,4, ????
5
= 0,2, ????
6
= 0,15.
3. Вычислить энтропию дискретного источника без памяти с символами алфавита ???? = {????, ????} c вероятностью ????
????
=
6 8
, ????
????
=
1 4
4. Вычислить энтропию дискретного источника без памяти с символами алфавита ???? = {????, ????, с} c вероятностью ????
????
=
1 2
, ????
????
=
1 3
, ????
????
=
1 6
5. Источник формирует символы
???? = {????
1
, ????
2
, … , ????
6
} = {????, ????, ????, ????, ????, !}. Ве- роятности символов задаются множеством {????
1
= 0,05, ????
2
= 0,15, ????
3
= 0,05,
????
4
= 0,4, ????
5
= 0,2, ????
6
= 0,15}. Вычислить:
5.1. Энтропию дискретного источника.
5.2. Емкость дискретного источника.
5.3. Избыточность дискретного источника.
5.4. Относительную избыточность дискретного источника.
6. 1 . Имеется дискретный канал с входным источником
???? = {????
1
, ????
2
}, ????
1
=
0, ????
2
= 1 и выходным источником ???? = {????
1
, ????
2
}, ????
1
= 0, ????
2
= 1. Cимволы ???? появ- ляются с вероятностью ????(????
1
) = 0,4 и ????(????
2
) = 0,6. Переходные вероятности ка- нала соответственно равны: ????(????
1
|????
1
) = 0,9, ????(????
2
|????
2
) = 0,95. Определить веро- ятности появления символов на выходе канала c шумами.

37 6.2. Найти вероятности
????(????
1
|????
1
), ????(????
2
|????
2
) получения символов источника
???? на приемной стороне.
7. 1 . Имеется дискретный канал с входным источником
???? = {????
1
, ????
2
}, ????
1
=
0, ????
2
= 1 и выходным источником ???? = {????
1
, ????
2
}, ????
1
= 0, ????
2
= 1. Cимволы ???? появ- ляются с вероятностью ????(????
1
) = 0,5 и ????(????
2
) = 0,5. Переходные вероятности ка- нала соответственно равны: ????(????
1
|????
1
) = 0,9, ????(????
2
|????
2
) = 0,95. Определить веро- ятности появления символов на выходе канала c шумами.
7.2. Найти вероятности достоверного приема символов источника
???? на приемной стороне.