Лекции по теории информации. Фурсов teoria_informacii. Лекции по теории информации под редакцией Н. А. Кузнецова

• Название: Лекции по теории информации под редакцией Н. А. Кузнецова
• Анкор: Лекции по теории информации
• Дата: 17.04.2022
• Размер: 1.32 Mb.
• Имя файла: Фурсов teoria_informacii.pdf
• Тип: Лекции; #480820
• страница: 7 из 16

6.6 Эпсилон-энтропия случайной величины
В этом разделе мы вернемся к рассмотрению понятия энтропии непрерыв-
ной случайной величины, воспользовавшись для этого теперь уже известным нам понятием количества информации.
В разделе 5.1 мы показали, что энтропия непрерывной случайной величины бесконечна, вследствие того, что реализации могут отличаться на сколь угодно малые величины. В действительности на практике, с одной стороны, нет воз- можности фиксировать сколь угодно малые отличия реализаций вследствие по- грешности измерительной аппаратуры, с другой стороны, это обычно и не тре- буется. Поэтому разумной представляется идея: судить о непрерывной случай- ной величине Z по значениям другой статистически связанной с ней случайной величины
V
, если мера их различия не превышает заданной верности воспро- изведения.
Для количественной оценки степени сходства вводят функцию
( , )
z v

, имеющую смысл «расстояния» между реализациями, а в качестве меры сходст- ва – ее среднее значение по всему множеству значений
z
и
v
:
( , )
( , ) ( , )
Z V
p z v
z v dzdv


 
 

 
(6.11)

58
Здесь
( , )
p z v
– плотность совместного распределения вероятностей случайных величин Z и
V
Наиболее популярным является среднеквадратический критерий. При этом с учетом равенства
( , )
( / ) ( )
p z v
p z v p v

критерий сходства может быть записан в виде
2 2
( , )
(
)
( / ) ( )
Z V
z
v p z v p v dzdv


 
 



 
,
(6.12) где
( / )
p z v
– условная плотность распределения, характеризующая вероятность воспроизведения конкретного сигнала
z
сигналом
v
, а

– заданное значение верности воспроизведения.
В соответствии с (6.10) количество информации о случайной величине Z , содержащейся в воспроизводящей величине
V
равно
2
( / )
( , )
( )
( )
( / ) ( ) log
( )
v
p z v
I Z V
h Z
h Z
p z v p v
dzdv
p z
 
 



 
(6.13)
Заданную верность воспроизведения случайной величины Z желательно обес- печить при минимальном количестве получаемой информации. Поэтому услов- ную плотность


/
p z v
вероятности того, что в тех случаях, когда была зафик- сирован сигнал
z
, имел место сигнал
v
, следует подобрать так, чтобы в (6.13) имел место минимум информации


,
I Z V
по всем


/
p z v
Величину
( )
H Z

, определяемую как
( / )
( )
min ( , )
p z v
H Z
I Z V


,
(6.14) при условии
2
( , )
Z V



,
(6.15) называют эпсилон-энтропией (

-энтропией) непрерывной случайной величины
Z . В соответствии с (6.10) ее также можно определить как


( / )
( / )
( )
min
( )
( )
( )
max
( )
V
V
p z v
p z v
H Z
h Z
h Z
h Z
h Z






59
6.7 Избыточность сообщений
Сообщения, энтропия которых максимальна, являются оптимальными с точки зрения наибольшего количества передаваемой информации. Мерой отли- чия энтропии реального сообщения от оптимального является коэффициент сжатия:
( )
( )
opt
H Z
H
Z
 
(6.16)
Если оптимальное и неоптимальное сообщения характеризуются одинако- вой общей энтропией, то имеет место равенство
 
 
opt
nH Z
n H
Z


,
(6.17) где
n
– число элементов неоптимального сообщения,
n
– число элементов оп- тимального сообщения.
С учетом (6.17) коэффициент сжатия (6.16) можно представить в виде
( )
( )
opt
H Z
n
H
Z
n




Для характеристики близости энтропии реальных сообщений к оптималь- ному значению вводится также коэффициент избыточности:
( )
( )
1
( )
opt
z
opt
H
Z
H Z
n
n
K
n
H
Z




 


Увеличение избыточности приводит к увеличению времени передачи со- общений. Однако некоторая избыточность может быть полезной с точки зрения повышения надежности системы.

60
Лекция 7
Оценка информационных характеристик
источников сообщений
7.1 Понятие эргодического источника сообщений
Для построения модели источника дискретных сообщений достаточно за- дать объём алфавита и вероятности появления на выходе источника отдельных знаков. Наиболее широко используется модель Шеннона – эргодический ис- точник сообщения. Эта модель предполагает, что источник представляется эр- годической случайной последовательностью.
Свойства эргодической модели:
1) вероятности знаков не зависят от их места в последовательности;
2) статистические характеристики, полученные на одном длинном сооб- щении, справедливы для всех сообщений, создаваемых этим источником.
Если вероятности знаков не зависят от времени, то источник называется
стационарным. Если вероятности не зависят и от предыдущих состояний, то источник называется стационарным без памяти. Стационарный источник без памяти, в котором каждый знак выбирается независимо от других, всегда эрго- дический.
Если имеет место корреляция между знаками, то в качестве модели ис- пользуют цепь Маркова. Неопределенность этих источников описывается фор- мулами (4.20), (4.21) (лекция 4). Порядок цепи зависит от того, сколько знаков связано корреляционной зависимостью.
Предположим, что вероятности знаков, формируемых источником с тремя возможными состояниями, следующие:
 
1 0,1
p z 
,
 
2 0,3
p z

,
 
3 0,6
p z

Ясно, что в этом случае знак
2
z в среднем должен встречаться в три раза чаще, чем
1
z , но в два раза реже, чем
3
z . Однако в конкретной последовательности, длина которой ограничена, знаки могут отсутствовать или появляться реже или чаще, чем это определено указанными вероятностями. Вероятности формиро-

61 вания различных последовательностей, связанные со свойствами эргодических последовательностей знаков, даются следующей теоремой.
7.2 Теорема о свойствах эргодических
последовательностей знаков
Как бы ни были малы числа
0
 
и
0
 
при достаточно большом
N
все эргодические последовательности могут быть разбиты на две группы:
1. Нетипичные последовательности. Различных вариантов таких последо- вательностей большое число, однако любая из них имеет настолько ничтожную вероятность, что даже суммарная вероятность всех таких последовательностей очень мала и при достаточно большом
N
меньше сколь угодно малого чис- ла

2. Типичные последовательности, вероятности которых p при больших
N
одинаковы и удовлетворяют неравенству
2 1
1
log
( )
H Z
N
p



(7.1)
Соотношение (7.1) называют свойством асимптотической равномерности.
Доказательство. Для эргодического источника без памяти в длинной по- следовательности из
N
элементов алфавита объемом
m


1 2
,
,...,
m
z z
z
с вероят- ностями появления знаков
1 2
,
,...,
m
p p
p будет содержаться
1
Np элементов
1
z ,
2
Np элементов
2
z и т.д. Тогда вероятность
p
появления конкретной последова- тельности с учетом свойства независимости знаков
1 2
1 2
1
m
i
m
Np
Np
Np
Np
m
i
i
p
p
p
p
p





(7.2)
Логарифмируя обе части равенства (7.2) получаем
2 2
1
log log
m
i
i
i
p
N
p
p



(7.3)
Из (7.3) при
N  
следует
2 1
1
log
( )
H Z
N
p

,
(7.4)

62 что доказывает вторую часть теоремы.
Заметим, что это утверждение можно объяснить с несколько иных пози- ций. Поскольку по предположению источник выдает только эргодические по- следовательности, при
N  
вероятности появления знаков в них будут соот- ветствовать типичным для этих последовательностей значениям, следователь- но, вероятности
p
появления этих последовательностей будут одинаковы. Об- щее число этих (типичных) последовательностей будет равным соответственно
1/ p
. Частная неопределенность каждой такой последовательности в соответст- вии с (4.4), (4.6)


2 2
log log 1
p
p


, а неопределенность в среднем на один знак этой последовательности будет равна


2
log 1
/
p
N
, но эта величина по опреде- лению и является энтропией.
Покажем теперь, что при достаточно большом
N
типичные последова- тельности составляют незначительную долю от общего числа возможных вари- антов различных последовательностей.
Общее число возможных вариантов последовательностей
1
n , которое мо- жет быть сформировано из знаков алфавита объема
m
(с использованием ос- новного логарифмического тождества) можно представить в виде
2 2
log log
1 2
2
N
m
N
m
N
n
m



С другой стороны, в соответствии с (7.4) число типичных последовательностей определяется как
 
1 2
NH Z
T
n
p


Запишем их отношение:
 
 
2 2
log
[log
]
1 2
2 2
N
m
N
m H Z
NH Z
T
n
n



В разделе 4.3 мы установили, что максимум энтропии
 
2
log
H Z
m

имеет место лишь в случае, когда знаки равновероятны. Это означает, что, если ис- ключить случай равновероятного выбора элементов сообщений, в показателе степени двойки
2
( )
log
H Z
m

и, следовательно, при
N  
1
T
n
n


63
7.3 Производительность источника дискретных сообщений
Производительность источника сообщений – это количество информации, вырабатываемое источником в единицу времени. Обычно помехи в источнике малы и их учитывают эквивалентным изменением модели канала связи. При этом производительность источника
( )
и
I Z

численно равна величине энтропии в единицу времени и определяется соотношением
( )
( )
и
и
H Z
I Z



,
(7.5) где
и

– средняя длительность формирования одного знака.
Длительность выдачи каждого отдельного элемента сообщения в общем случае зависит не только от типа формируемого знака, но и от состояния ис- точника. Поэтому средняя длительность
и

выдачи источником одного знака в общем случае определяется как
1
( )
(
)
i
N
и
i
z q
q
i
p q
p z q






,
(7.6) где
i
z q

– длительность выдачи знака
i
z в состоянии
q
,
(
)
i
p z q – вероятность появления знака
i
z в состоянии
q
, а
( )
p q
– вероятность состояния
q
Из формулы (7.5) следует, что повысить производительность источника можно либо путем увеличения его энтропии, либо за счет уменьшения средней длительности формирования знаков. В соответствии с (7.6) уменьшение сред- ней длительности
и

наиболее эффективно за счет уменьшения длительности формирования тех знаков, которые имеют относительно высокие вероятности появления. Если длительности формирования знаков не зависят от состояний источника и одинаковы, повышение производительности возможно только за счет увеличения его энтропии.

64
7.4 Эпсилон-производительность источника
непрерывных сообщений
Понятие эпсилон-производительности источника вводится подобно тому, как в разделе 6.6 было введено понятие эпсилон-энтропии непрерывной слу- чайной величины.
Эпсилон-производительность (

-производительность) источника непре- рывных сообщений
 
H
Z


определяют как минимальное количество информа- ции, которое необходимо создать источнику в единицу времени, чтобы любую реализацию
 
l
z t
можно было воспроизвести с заданной верностью

Предположим, что на достаточно длинном интервале T непрерывный сиг- нал
( )
T
z t воспроизводится реализацией
( )
T
v t . Если указанные сигналы облада- ют ограниченным спектром F , то в соответствии с теоремой Котельникова ка- ждую из этих реализаций можно представить составленными из отсчетов
N
- мерными (
/
2
N
T
t
FT

 
) векторами


1 2
,
,...,
N
z z
z
и


1 2
, ,...,
N
v v
v
соответст- венно. Соответствующие ансамбли сообщений можно представить
N
-мерными случайными векторами Z ,
V
, компонентами которых являются случайные ве- личины
1 2
,
,...,
N
Z Z
Z ,
1 2
,
,...,
N
V V
V . Эти векторы могут быть статистически описа- ны с использованием
N
–мерных плотностей распределения –
 
p Z
,
 
p V
,


,
p Z V
,


/
p Z V
,


/
p V Z
С использованием указанных
N
-мерных плотностей распределения, запи- шем соотношение (6.10) для количества информации, содержащегося в воспро- изводящем векторе относительно исходного (здесь интегралы
N
–мерные):






   
2
,
,
,
log
N
p
I
p
d d
p
p

 
Z V
Z V
Z V
Z V
Z V
Z
V
(7.7)
Количество информации, приходящееся в среднем на один отсчет, определится как




,
,
/
N
I
I
N

Z V
Z V
(7.8)

65
С использованием
N
-мерных плотностей распределения


/
p Z V
и
 
p V
по аналогии с (6.11) можно также записать соотношение для количественной оценки степени сходства случайных векторов Z ,
V
:

   

Z V
( , )
/
,
p
p
d d



 
Z V
Z V
V
Z V
Z V ,
(7.9) где


,
 Z V
– функция, характеризующая близость случайных векторов Z и
V
В соответствии с определением

-производительности источника непре- рывных сообщений можно записать
 


( /
)
1
min
,
p
и
H
I



Z V
Z
Z V

,
(7.10) при условии


2
,



Z V
, где


,
I Z V
,


,
 Z V
определяются соотношениями (7.7)–(7.9) соответственно, а
1/ 2
и
F


– время формирования одного отсчета источником.
Геометрически требование обеспечения заданной верности воспроизведе- ния непрерывного сигнала можно представить как требование того, чтобы ко- нец соответствующего сообщению
( )
T
z t
N
-мерного вектора


1 2
,
,...,
N
z z
z
по- пал в

-область
N
-мерного вектора


1 2
, ,...,
N
v v
v
, соответствующего воспроиз- водящему непрерывному сигналу
( )
T
v t . Следует заметить, что заданная вер- ность воспроизведения будет достигаться лишь при большой длительности со- общений при том, что
/
2
N
T
t
FT

 
, т.е. когда погрешностью от замены не- прерывных сообщений совокупностью отсчетов можно пренебречь.

66
Лекция 8
Информационные характеристики каналов связи
8.1 Модели дискретных каналов
Канал связи – совокупность устройств, предназначенных для передачи со- общения от одного места к другому или от одного момента времени к другому.
Канал, предназначенный для передачи дискретных сообщений, называют дис- кретным. Сигнал в таком канале при передаче от входа к выходу обычно под- вергается преобразованиям в следующей последовательности устройств: ис- точник сообщения – кодер источника – модулятор – передатчик – линия связи – приемник – демодулятор – декодер – приемник сообщения.
По линии связи, как правило, передается непрерывный сигнал. Считается, что именно в линии связи возникают наибольшие помехи. Поэтому при теоре- тическом исследовании модели канала с помехами полагают, что помехи в ис- точнике отсутствуют, т.к. они малы по сравнению с помехами в канале. Если помехи в канале связи также невелики, то для теоретического анализа в первом приближении можно использовать идеализированную модель канала без помех.
Дискретный канал считается заданным, если известны множества симво- лов (алфавиты) на входе и выходе, а также вероятностные свойства формиро- вания (передачи) этих символов.
Для передачи по каналу сообщение из знаков алфавита источника
1 2
,
,...
l
z z
z преобразуется в дискретные последовательности символов из другого алфавита
1 2
, ,...
m
v v
v , как правило, меньшего объёма.
В каждом состоянии канал характеризуется некоторой переходной вероят- ностью
(
)
j
i
p v
z
того, что переданный символ
i
z будет восприниматься на вы- ходе как символ
j
v
. Если указанные вероятности не зависят от времени, то ка- нал называют стационарным, если зависят от времени, то – нестационарным.
Если эти вероятности зависят от предшествующего состояния, то имеет место канал с памятью, если не зависят, то это канал без памяти.

67
Если число символов на входе и на выходе канала одинаково и равно
k
, такой канал называют
k
-ичным. Стационарный двоичный канал без памяти ха- рактеризуется четырьмя переходными вероятностями (рисунок 8.1). Если
(0 0)
(1 1)
p
p

и
(1 0)
(0 1)
p
p

, то канал называется симметричным. а) б)
Рис. 8.1 – Схемы каналов: а) двоичный; б) двоичный со стиранием
Иногда также рассматривают модель канала со стиранием. На рисунке
8.1, б приведена схема двоичного канала со стиранием. В данном случае на вы- ходе канала фиксируются состояния
S
, которые с равной вероятностью могут быть отнесены как к единице, так и к нулю. При декодировании этот символ
S
расшифровывают с учетом дополнительной информации.
Если в канале имеется возможность формировать запрос на повторную пе- редачу в случае обнаружения ошибки, такой канал называют каналом с обрат-
ной связью.