910.11K

Category:

informatics

Лекция №5. Количество информации и избыточность

1.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
Лекция № 5
Часть 1. Условная энтропия и взаимная информация
1.1. Условная энтропия
1.2. Взаимная информация
1.3. Пример с троичным каналом
Часть 2. Каналы передачи информации
2.1. Структурная схема системы передачи информации (повторение)
2.2. Технические и информационные характеристики канала связи без помех
2.3. Обобщенные характеристики сигналов и каналов
Часть 3. Каналы передачи информации с помехами
3.1. Вероятностные модели каналов передачи информации:
– двоичный канал
– троичный канал
3.2. Характеристики каналов передачи информации с помехами
1

2.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 3, 4
Информационная мера Шеннона
1. Информационная мера Хартли. Аддитивность информационной
меры Хартли
2. Информационная мера Шеннона. Связи с мерой Хартли
3. Количество информации и энтропия
4. Свойства энтропии дискретного источника сообщений
5. Количество информации и избыточность
16

3.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
5. Количество информации и избыточность
По определению избыточности
1 H ( A) / max H ( A) 1 H ( A) / log 2 N
Лекция № 3, 4
3

4.

Курс: «Теория информации» 2022
Заключение!!!
Бакалавры МО, ПРО - 3 курс
Лекция № 3, 4
18
Лекция № 3, 4
Информационная мера Шеннона
1. Информационная мера Хартли. Аддитивность информационной
меры Хартли
2. Информационная мера Шеннона. Связи с мерой Хартли
3. Количество информации и энтропия
4. Свойства энтропии дискретного источника сообщений
5. Количество информации и избыточность
N
1
I log 2 N log 2 N
i 1 N
n
H ( ) pi log 2l / pi
i l

5.

6.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
Часть 1. Условная энтропия и взаимная
информация
1. Условная энтропия
2. Взаимная информация
I ( , ) H ( ) H ( ).
3. Пример с троичным каналом
N
M
H (Y / X ) p ( xi y j ) log 2
i 1 j 1
1
p( y j / xi )
.
2

7.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
1. Условная энтропия
Пусть ξ и η – случайные величины с множествами возможных
значений X = {x1,x2,…, xn}, Y = {y1,y2,…, ym}
Количество информации H(ξ) при наблюдении случайной величины
ξ X = {x1,x2,…, xn} с распределением вероятностей P = {p1, p2, …,
pn} задается формулой Шеннона:
n
H ( ) pi log 2l / pi
i l
Количество информации H(η) при наблюдении случайной величины
η Y = {y1,y2,…, ym} с распределением вероятностей Q = {q1, q2, …,
qm} задается формулой Шеннона:
m
H ( ) qi log 2l / qi
i l
3

8.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
3
1. Условная энтропия
Условной энтропией величины η при наблюдении величины ξ называется
N
M
1
H ( ) H ( / ) H (Y / X ) p(xi y j ) log 2
.
p( y j / x i )
i 1 j 1
Справедливы соотношения:
H ( , ) H ( ) H ( ),
N
M
1
H ( , ) p(x i y j ) log 2
.
p( y j x i )
i 1 j 1

9.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
Часть 1. Условная энтропия и взаимная
информация
1. Условная энтропия
I
(
,
)
H
(
)
H
(
).
2. Взаимная информация
3. Пример с троичным каналом
N
M
H (Y / X ) p ( xi y j ) log 2
i 1 j 1
1
p( y j / xi )
.
4

10.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
10
2. Взаимная информация
Взаимной информацией величин ξ и η называется I ( , ) H ( ) H ( ).
Справедливы следующие соотношения:
N
M
I ( , ) p (x i y j ) log 2
i 1 j 1
p(x i y j )
p(x i ) p( y j )
,
I ( , ) I ( , ) H ( ) H ( ),
I ( , ) H ( ) H ( ) H ( , ),
Закон аддитивности в общем случае:
H ( , ) H ( ) H ( ) I ( , ),
0 I ( , ) H ( ), 0 I ( , ) H ( ).
Если ξ и η – независимы, то I(ξ, η) = 0.

11.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
11
2. Взаимная информация
При расчетах условной энтропии и взаимной информации удобно пользоваться
следующими соотношениями теории вероятностей:
1) теорема
умножения вероятностей
p(x i y j ) p(x i ) p( y j / x i ) p( y j ) p(x i / y j )
M
2) формула полной вероятности
p(xi ) p(xi , y j );
j 1
3) формула Байеса
p(x i / y j )
p(x i ) p( y j / x i )
p( y j )
p(x i ) p( y j / x i )
N
p(x ) p( y / x )
i
i 1
j
i
.

12.

13.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
3. Пример с троичным каналом (с матрицей)
Пример 1. Дана матрица
1 1 1
8 8 8
1
1
P( X , Y )
0
X , Y
8
8
1 1 1
8 8 8
Определить: H( ), H( ), H ( ), H ( ), H( , ), I ( , ).
Решение. По формуле полной вероятности имеем:
3
P ( x1 ) p ( x1 , y j )
j 1
3
1
, P (x 2 ) ,
8
4
3
3
3
P ( x 3 ) , P ( y1 ) p ( x i , y1 ) , P ( y 2 ) 1 , P ( y 3 ) 3 .
8
8
4
8
i 1
3
3
1
Следовательно, H ( ) p( xi ) log 2
1,57;
p
(
x
)
i 1
i
H ( ) p( yi ) log 2
i 1
1
1,57.
p( y i )
13

14.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 5 курс
Лекция № 5
3. Пример с троичным каналом (с матрицей)
По теореме умножения
1
,
3
p( x1 / y 2 )
1
,
2
p( x2 / y2 ) 0,
p( x 2 / y 3 )
1
,
3
p ( x 1 / y 1 ) p ( x 1 y 1 ) / p ( y1 )
p ( x 2 / y1 )
1
,
3
p ( x 3 / y1 )
1
1
1
, p( x 3 / y 2 ) , p ( x 3 / y 3 ) .
3
2
2
p( x 1 / y 3 )
1
,
3
Следовательно,
3
3
H ( ) p( xi y j ) log 2
I 1 J 1
Аналогично
1
1,43.
p( x i / y j )
H ( ) 1,43; H ( , ) H ( ) H ( ) 3; I ( , ) H ( ) H ( ) 0,14.
14

15.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
Лекция № 5
Часть 2. Каналы передачи информации
2.1. Структурная схема системы передачи информации (повторение)
2.2. Технические и информационные характеристики канала связи
без помех
2.3. Обобщенные характеристики сигналов и каналов
15

16.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
Часть 2. Каналы передачи информации
2.1. Структурная схема системы передачи информации (повторение)
2.2. Технические и информационные характеристики канала связи
без помех
2.3. Обобщенные характеристики сигналов и каналов
16

17.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
2.3. Структурная схема информационной системы
Примеры:
электрические,
электромагнитные,
механические,
ультразвуковые,
звуковые,
Проводная линия связи
Радиолиния
световые.
постоянный ток и переменные токи сравнительно
невысоких частот
электромагнитные колебания высоких частот
17

18.

19.

Курс: «Теория информации» 2022
2.
Бакалавры МО, ПРО - 3 курс
Лекция № 5
Технические и информационные характеристики канала связи без помех
Источник
сообщений
Приемник
сообщений
Источник
помех
Выходной алфавит символов источника сообщений:
A ai , A a1 , a2 ,...., an
Количество информации, приходящееся в среднем на один символ источника:
n
H ( A) pi log 2 1 / pi , где pi – вероятность появления символа ai на выходе источника.
i 1
Алфавит символов канала связи:
B b1 , b2 ,...., bm
19

20.

Курс: «Теория информации» 2022
2.
Бакалавры МО, ПРО - 3 курс
Лекция № 5
Технические и информационные характеристики канала связи без помех
Среднее количество информации, выдаваемое источником в единицу времени –
информационная производительность:
dI ( A) / dt A H ( A),
Скорость передачи информации по каналу:
dl ( B) / dt B H ( B),
Источник
сообщений
Приемник
сообщений
Источник
помех
20

21.

Курс: «Теория информации» 2022
2.
Бакалавры МО, ПРО - 3 курс
Лекция № 5
Технические и информационные характеристики канала связи без помех
Источник
сообщений
Приемник
сообщений
Источник
помех
Пропускная способность канала:
C k max dI ( B) / dt , где p множество всех возможных распределений
p
вероятностей символов алфавита B канала.
Пропускная способность канала (с учетом свойств энтропии):
Ck B log 2 m
21

22.

23.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
23
3. Обобщенные характеристики сигналов и каналов
Сигнал может быть охарактеризован различными параметрами. Таких параметров, вообще
говоря, очень много, но для задач, которые приходится решать на практике, существенно
лишь небольшое их число. Например, при выборе прибора для контроля технологического
процесса может потребоваться знание дисперсии сигнала; если сигнал используется для
управления, существенным является его мощность и так далее.
Рассматривают три основных параметра сигнала, существенных для передачи информации
по каналу.
• время передачи сигнала
Tc
• мощность Pс сигнала,
передаваемого по
каналу с определенным
уровнем помех Pz
• спектр частот Fc
Чем больше значение Pс по сравнению с Pz,
тем меньше вероятность ошибочного приема.
Таким образом, представляет интерес
отношение Pс /Pz. Удобно пользоваться
логарифмом этого отношения, называемым
превышением сигнала над помехой:
Pc
L log a( )
c
Pz

24.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
24
3. Обобщенные характеристики сигналов и каналов
Эти три параметра позволяют представить любой сигнал в трехмерном пространстве с
координатами L, T, F в виде параллелепипеда с объемом Tc Fc Lc
Объем сигнала Vc
Vc Tc Fc Dc
Информационный канал характеризуется:
• временем использования канала Тк
• шириной полосы частот, пропускаемых каналом Fk
• динамическим диапазоном канала Dk характеризующим
его способность передавать различные уровни сигнала
Емкость канала Vk
Tk Tk Fk Dk
Неискаженная передача сигналов возможна только при условии, что сигнал по своему
объему «вмещается» в емкость канала.
Согласование сигнала с каналом передачи информации определяется соотношением
Vc Vk

25.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
3. Обобщенные характеристики сигналов и каналов
Однако соотношение выражает необходимое, но недостаточное
условие согласования сигнала с каналом. Достаточным условием
является согласование по всем параметрам:
Для информационного канала пользуются понятиями:
скорость ввода информации
скорость передачи информации
пропускная способность канала
Tc Tk
Fc Fk
Dc Dk
Скорость ввода информации (потоком информации) V(A) - среднее количество
информации, вводимое от источника сообщений в информационный канал в единицу
времени. Эта характеристика источника сообщений определяется только статистическими
свойствами сообщений.
Скорость передачи информации V(X,Y) – среднее количество информации,
передаваемое по каналу в единицу времени. Зависит от статистических свойств
передаваемого сигнала и от свойств канала.
Пропускная способность С – наибольшая теоретически достижимая для данного
канала скорость передачи информации. Характеристика канала не зависит от статистики
сигнала.
25

26.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
3. Обобщенные характеристики сигналов и каналов
С целью наиболее эффективного использования
информационного канала нужно, чтобы
скорость передачи информации была как можно ближе к
пропускной способности канала.
При этом скорость ввода информации не должна
превышать пропускную способность канала,
иначе не вся информация будет передана по каналу.
Основное
условие
согласования
26

27.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
3. Обобщенные характеристики сигналов и каналов
Одним из основных вопросов в теории передачи
информации:
определение зависимости скорости передачи
информации и пропускной способности от
параметров канала и
характеристик сигналов и помех.
Эти вопросы были впервые глубоко исследованы
К. Шенноном.
27

28.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
Лекция № 5
Часть 3. Каналы передачи информации с
помехами
3.1. Вероятностные модели каналов передачи информации:
– двоичный канал
– троичный канал
3.2. Характеристики каналов передачи информации с помехами
Источник
сообщений
Приемник
сообщений
X1
1-P1
P1
Источник
помех
X2
P1
1-P1
28

29.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
Часть 3. Каналы передачи информации с
помехами
3.1. Вероятностные модели каналов передачи информации:
– двоичный канал
– троичный канал
3.2. Характеристики каналов передачи информации с помехами
Источник
сообщений
Приемник
сообщений
X1
1-P1
P1
Источник
помех
X2
P1
1-P1
29

30.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
30
5.1 Вероятностные модели каналов передачи информации
Двоичный канал
Пример 1. По двоичному каналу связи с помехами
передаются две цифры 1 и 0 с вероятностями p1 = p2 = 0,5.
Вероятность перехода единицы в единицу и нуля в нуль
соответственно равны p(1/1) = p, p(0/0) = q.
Определить закон распределения вероятностей случайной
величины ξ – однозначного числа, получаемого на приемной
стороне.

31.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
31
5.1 Вероятностные модели каналов передачи информации
Двоичный канал
Решение. ξ X = {0, 1}. Нуль (ξ = 0) на приемной стороне
может быть получен в двух случаях: при передаче нуля или
при передаче единицы. Следовательно, по формуле полной
вероятности
P (0) P(0,0) P(1,0) P(0) P(0 / 0) P(1) P(0 / 1),
P(0 / 1) 1 P(1 / 1).

32.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
5.1 Вероятностные модели каналов передачи информации
Двоичный канал
Поэтому
P (0) 0,5q 0,5(1 p) 0,5(1 q p).
, ) 0,5(1 q p).
Аналогично P (1) P (0,1) P (11
Распределение вероятностей представлено в табл.
xi
0
1
pi
0,5(10p + q)
0,5(1 ‒ p + q)
32

33.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
33
5.1 Вероятностные модели каналов передачи информации
Троичный канал
Пример 1. Дана матрица
1
8
1
P( X , Y )
8
1
8
1 1
8 8
1
0
, X , Y
8
1 1
8 8
Определить: распределения вероятностей на входе и на выходе канала,
условное распределение вероятностей появления сигналов на выходе
канала при фиксированном входе и на входе канала при фиксированном
выходе канала.

34.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
5.1 Вероятностные модели каналов передачи информации
Троичный канал
Решение. По формуле полной вероятности имеем:
3
P ( x1 ) p ( x1 , y j )
j 1
3
,
8
3
1
3
3
P ( x 2 ) , P ( x 3 ) , P ( y1 ) p ( x i , y1 ) ,
8
4
8
i 1
P(y2 )
1
,
4
P(y3 )
По теореме умножения
1
p ( x 1 / y 1 ) p ( x 1 y 1 ) / p ( y1 ) ,
3
1
p( x1 / y 2 ) ,
2
p( x 1 / y 3 )
1
,
3
p ( x 2 / y1 )
1
,
3
p( x 2 / y 2 ) 0,
p( x 2 / y 3 )
1
,
3
p ( x 3 / y1 )
1
,
3
p( x 3 / y 2 )
1
,
2
p( x 3 / y 3 )
1
.
2
3
.
8
34

35.

36.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
5.2. Характеристики каналов передачи информации с
помехами
Источник
сообщений
Приемник
сообщений
Источник
помех
Выходной алфавит символов источника сообщений:
A ai , A a1 , a2 ,...., an
Количество информации, приходящееся в среднем на один символ источника:
n
H ( A) pi log 2 1 / pi, где pi – вероятность появления символа ai на выходе источника.
i 1
Среднее количество информации, выдаваемое источником в единицу времени –
информационная производительность:
dI ( A) / dt A H ( A),
где υA – среднее число символов, выдаваемое источником в единицу
времени.
36

37.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
37
5.2. Характеристики каналов передачи информации с
помехами
Алфавиты символов канала связи:
Bвх X x1 , x2 ,..., xm , Bвых Y y1 , y2 ,..., yl
Матрица переходных вероятностей:
l
p( yi / xk ) , где k 1...m, i 1...l ; p( yi / xk ) 1
i 1
Среднее количество информации на один входной и на один выходной
символ канала:
m
l
i 1
j 1
H ( X ) p( xi ) log 2 1 / p( xi ); H (Y ) p( y j ) log 2 1 / p( y j )

38.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
38
5.2. Характеристики каналов передачи информации с
помехами
Информация, которую несет выход канала о входе:
I (Y , X ) H ( X ) H y ( X ) H (Y ) H x (Y )
где Hy(X) – ненадежность канала, Hx(Y) – энтропия шума.
Скорость передачи информации по каналу:
dl ( B) / dt B I ( X ,Y ),
где υB – среднее число символов, выдаваемое каналом в единицу времени.
Пропускная способность канала:
C k max dI ( B) / dt , где p множество всех возможных распределений
p
вероятностей входного алфавита символов канала
C k B max I ( x, y ) n, m, l , A , B
– {p} характеристики канала.

39.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
5.2. Характеристики каналов передачи информации с
помехами
ПРИМЕР
1. Найти пропускную способность двоичного симметричного канала – канала с
двухсимвольными входными и выходными алфавитами и одинаковыми
вероятностями ошибок (см. рисунок)
X1
1-P1
P1
P1
X2
1-P1
если априорные вероятности появления входных символов
p( x1 ) p1 p, p( x2 ) p2 1 p
39

40.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
5.2. Характеристики каналов передачи информации с
помехами
РЕШЕНИЕ. В соответствии с моделью канала условные вероятности
y
y
y
y
p ( 1 ) p( 2 ) pl , p ( 1 ) p ( 2 ) 1 pl
x2
x1
x1
x2
Пропускная способность канала
Найдем энтропию шума
Ck B max H (Y ) H (Y / X )
p
2
2
H ( X / Y ) p( xi y j ) log 2 1 / p( y j / xi )
i 1 j 1
По теореме умножения
следовательно,
p ( y j , xi ) p ( xi ) p ( y j / xi )
p( x1 y1 ) p(1 pl )
p( x 2 y1 ) (1 p) pl
p( x1 y1 ) ppl
p( x 2 y 2 ) (1 p)(1 pl )
Подставляя в формулу, получаем H (Y / X ) pl log 2 1 / pl (1 pl ) log 2 1 /(1 pl )
Таким образом, H(Y/X) не зависит от распределения входного алфавита, следовательно,
Ck k max H (Y ) н H (Y / X )
p
40

41.

Курс: «Теория информации» 2022
Бакалавры МО, ПРО - 3 курс
Лекция № 5
41
5.2. Характеристики каналов передачи информации с
помехами
Определим энтропию выхода
H (Y ) p ( y1 log 2 )1 / p ( y1 ) p ( y 2 ) log 2 1 / p ( y 2 ),
где p( y1 ) p ( y1 x1 ) p ( y1 x 2 ) p (1 pl ) pl (1 p );
p( y 2 ) p ( y 2 x1 ) p ( y 2 x 2 ) ppl (1 p )(1 pl )
Таким образом,
H (Y ) p(1 pl ) pl (1 p) log 2 1 / p(1 pl ) pl (1 p) ppl (1 p)(1 pl )
log 2 1 / ppl (1 p)(1 pl )
Варьируя p, убеждаемся, что максимальное значение H/Y, равное I, получается при
равновероятных входных символах p(y1) и p(y2).
Следовательно,
Ck k 1 pl log 2 1 / pl (1 pl ) log 2 1 /(1 pl ) .

42.

Курс: «Теория информации» 2022
Заключение!!!
Бакалавры МО, ПРО - 3 курс
Лекция № 5
Лекция № 5
Часть 1. Условная энтропия и взаимная информация
1.1. Условная энтропия
1.2. Взаимная информация
1.3. Пример с троичным каналом
Часть 2. Каналы передачи информации
2.1. Структурная схема системы передачи информации (повторение)
2.2. Технические и информационные характеристики канала связи без помех
2.3. Обобщенные характеристики сигналов и каналов
Часть 3. Каналы передачи информации с помехами
3.1. Вероятностные модели каналов передачи информации:
– двоичный канал
– троичный канал
3.2. Характеристики каналов передачи информации с помехами
1

English Русский Rules