Духин А.А. Теория информации
Подождите немного. Документ загружается.
ГЛАВА ВТОРАЯ
ИСТОЧНИКИ
СООБЩЕНИЙ
§1
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
ДИСКРЕТНОГО ИСТОЧНИКА СООБЩЕНИЙ,
ЭНТРОПИЯ СТАЦИОНАРНЫХ ИСТОЧНИКОВ
Под
дискретным источником сообщений будем понимать устройство, по-
рождающее последовательности, составленные из букв конечного алфавита А
(jAj = п <
оо).
При этом буквы последовательностей порождаются в
дискретные моменты времени:
t = 0,1,2,...; t = ...-2,-1,0,1,2,...
Введение
таких ограничений как конечность алфавита А и порождение букв
з
дискретные моменты времени, что, собственно, и обусловливает название
таких
источников, не имеет принципиального значения. Всякий непрерывный
источник информации можно, в некотором смысле, "заменять" с заданной сте-
пенью
точности некоторым дискретным источником.
Последовательности, создаваемые дискретным источником, можно рассмат-
ривать
как траектории некоторых случайных процессов, задание которых и
позволит
ввести математическую модель источника.
Пусть
бесконечная в обе стороны последовательность букв
а =
(...,а
{1
,a
So
,a
Sl
,a
l2
,...)
(2.1.1)
представляет собой некоторую возможную реализацию источника. Будем рас-
сматривать последовательность а как элементарное событие некоторой сг-ал-
гебры,
задание
которой вместе с вероятностной мерой р, о которой речь пой-
дёт ниже,
даст основание интерпретировать а как некоторую траекторию слу-
чайного
процесса. Совокупность всех таких элементарных событий а вида
(2.1.1)
обозначим А
1
. Любое подмножество множества А
1
представляет не-
которое
событие а-алгебры. Введём в рассмотрение события следующего вида.
Пусть
в момент времени t
x
источник порождает букву а^ е А. Тогда это со-
бытие
c
tl
(ajj) является объединением всех таких элементарных событий а,
в
которых
координата с номером t, имеет фиксированное значение a
i(
. Ос-
тальные
координаты в последовательностях не фиксированы.
То
есть c
tl
(aij) = ja :(...x
tl
_ix
tl
=a
i3[
;x
tl
где x
t
- произвольные
буквы алфавита A, t * tj.
53
Определение 1.1. Цилиндрическим множеством (цилинд-
ром) называется случайное событие
c
t
lv
..,t
m
(
a
i!
*"»ai
m
).
На множестве всех конечномерных цилиндров
Z =
{Cti,...,t
m
(
a
ii >-">
a
i
m
))
естественным образом может быть задана согласованная вероятностная мера
р(с).
Обозначим
F
z
борелевское замыкание множества
Z. В
силу теоремы
о
продолжении вероятностной меры
р(с)
однозначно определяется вероятност-
ная мера
p(s)
для
любого борелевского множества seF
z
, совпадающая
с
ис-
ходной мерой
для
цилиндрических множеств: p(s) = p(c).
Таким образом, математическое описание источника
как
некоторого слу-
чайного процесса достигается заданием:
1) некоторого конечного алфавита
А;
2)
а-алгебры элементарных событий
(2.1.1);
3)
заданием вероятностной меры
p(s) для
всех борелевских множеств
s е F
z
.
Для источника введём обозначение [A,p(s)]. Если
seZ, то для
вероят-
ности этого события будем использовать обозначение
p(s).
Очевидно,
что
Р(А')
=
1.
Пусть
а е
А
1
.
Посредством
Та
обозначим последовательность:
Та=(...,а;_
1
,а;
0
,а|
1
,...).
где aj
k
=a
iR+1
-
со
<k<+co. (2,1.2)
Та представляет собой сдвиг
на
один шаг влево исходной последовательности
а. Если
Rс
А
1
,
то TR -
совокупность всех
Та, для
которых
а е R,
то
есть
aeRoTaeTR Очевидно,
что ТА
1
=
А
1
,
если
$
е
F
z
, то Ts
€
F
z
.
§ 1. МАТЕМАТИЧЕСКАЯ
МОДЕЛЬ ДИСКРЕТНОГО
ИСТОЧНИКА
СООБЩЕНИЙ,
ЭНТРОПИЯ
СТАЦИОНАРНЫХ
ИСТОЧНИКОВ
Вообще, если t
lv
..t
m
-
любые целые числа
а^ИД
еА, то
событие
c
t
|V
..,t
(
a
i,
>—9
a
i
) -
{источник порождает букву
a
ik
в
момент времени
t
k
(1
<k<
< m)}
-
есть множество всех последовательностей
а
вида
(2.1.1),
у
которых
x
t
=
а
!ь
(1
<k<m). Остальные координаты
не
фиксируются
и
могут принимать
произвольные значения
из А.
54
ГЛАВА
II.
Источники
СООБЩЕНИЙ
Определение
1.2.
Если
для
любого множества
s е F
z
выполняется p(Ts)
=
p(s),
то источник [Ар($)] называется стационар-
ным.
(2.1.3)
Дадим эквивалентное
Определение
1.2':
Если вероятность того,
что
источник
[Ap(s)] порождает некоторую
последовательность
a
ix
,...,a
i;
, составленную
из букв алфавита
А, в
моменты времени
1,2,...,£,
равна вероятности того,
что
порождается
в
точности такая же пос-
ледовательность
в
моменты времени
j
+1,—,j
+1 для
любых
j,^;a
i3(
>
wo
источник называется стационарным.
Стационарность означает неизменность
во
времени всех конечномерных
распределений соответствующего случайного процесса.
Основной характеристикой источника является скорость порождения
ин-
формации,
то
есть среднее количество информации, даваемое одним порож-
дённым символом.
Рассмотрим
I
последовательных моментов времени
t,t + l,...,t + ^-l.
В
эти
моменты времени источник [A,p(s)] может породить множество
{
c
t,...,t+^-l(
a
i
t
'
a
it+l »->
a
i
t+
,_i)}=C/»
состоящее
из
п'цилиндров.
Для каждого цилиндра
c
ut+H
(a
it
,H
M
a
lt+H
)6C^
определена вероятность:
p(
c
w+/>-i(
a
i
t
V.>a
IT+
^J
))=
p(c
w+
,_i(a
It
V»ai
t+
,_,
))•
Тогда множество есть конечная вероятностная схема
с
исходами
и
вероятностным распределением p(ct
v
^t+(?-l)' индуцированным мерой
p(s), и
при этом
£P<
C
W+M)
= I-
55
Согласно определению энтропии конечной вероятностной схемы C
fi
вве-
дённому в главе I, получаем:
Н(С,)=
-Zptw+M^it^a^,))
х (2.14)
x
togp(c
w+
,_,(a
it
,...,a,
t+M
)).
Если источник стационарен (ниже мы будем рассматривать такие источни-
ки),
то вероятность
p(ct
v
..,t+f-i(
a
ii
а следовательно, и энтропия
Н(С,,)
указанной совокупности цилиндров, не зависят от "начального момен-
та" и однозначно определяются природой источника и числом £.
В среднем на одну порождаемую источником букву приходится количество
информации, равное
—
.
Определение 1.3. Энтропией источника [А,р($)]
назовем величину: = lim ~, если
£-+ао £
введённый предел существует,
(2.1.5)
Определённая таким образом энтропия зависит только от природы ис-
точника, то есть от алфавита А и заданной вероятностной меры p(s). Она
равна
количеству информации, полученному при порождении одной буквы.
Пример 1.1. Пусть источник
[A,p(s)]
порождает последовательности а вида
(2.1.1) по схеме независимых испытаний, согласно вероятностно-
му распределению, заданному на алфавите А. В этом случае ко-
нечная вероятностная схема С^, составленная из п' -членных
цилиндров, может быть представлена как объединённая вероят-
ностная схема £ независимых вероятностных схем:
Следовательно, H(c
f
)=
1
v>*n
(2.1.6)
=
-Ep(ctv..,<W-i(a
it
v^a^^ ))log p(c
t
,^c
t+M
(a
lt
))=
=ЛКС,),где
H(C,)=-f)p
k
logp
k
.
k=l
§ 1. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
ДИСКРЕТНОГО
ИСТОЧНИКА
СООБЩЕНИЙ,
ЭНТРОПИЯ
СТАЦИОНАРНЫХ
ИСТОЧНИКОВ
56
ГЛАВА
II.
ИСТО
Ч НИК И
СООБЩЕНИЙ
В результате вычислений получаем,
что для
случая порождения последова-
тельностей
в
схеме независимых испытаний энтропия источника всегда
существует,
и она
равна
H(Cj).
Источники такого типа будем называть источниками
без
памяти, отмечая
этим
то, что
буквы, порождённые
в
предыдущие моменты времени,
не
влияют
на буквы, порождаемые
в
последующие моменты времени.
Докажем теорему
о
существовании энтропии
у
произвольного стационарного
источника.
Теорема
1.1. Для
произвольного стационарного источника существует
предел
Urn
—
—
s
-
= HL.
Доказательство. Совокупность всех цилиндров С
£+т
, длины £
+
m
t
с за-
данным вероятностным распределением можно рассматривать
как
объединён-
ную вероятностную схему двух вероятностных схем
С^ и С
т
. По
свойству
энтропии конечных вероятностных схем получаем:
Н(С,)
<
Н(С,
+И
)
< Н(С,)+Н(С
Ж
).
(2.1.7)
Из левого неравенства соотношения (2.1.7)
при т =
1
получаем:
Н(С,) < Н(С
М
).
(2.1.8)
Правое неравенство
в
соотношении (2.1.7) можно распространить
на
любое
конечное число слагаемых:
н(с
Л
)
=
=
Н:
^н(с,
(к
_
1)
)+н(с,)^н(с,
(к
_
2)
)+2н(с,)<.„^кн(с,).
<
TV
То есть получаем неравенство:
н(с,
к
)<кН(с<).
(2.1.9)
Полагая
в
(2.1.9)
I
=
1, получаем:
н(с
к
)<кн(с,).
Отсюда следует,
что для
любого натурального
к
^<Н(С,)<ОО.
к
v 17
Это соотношение показывает,
что
г
• t
H
(
C
k)
hm tnf —= a
<+oo.
k-»°o
k
57
Зададимся произвольным Б > 0 и положим, что натуральное q таково, что:
н
(
с
ч)
4 4
< а + s.
q
Для любого s > q определим натуральное число г > 1 так, чтобы (r-l)q <
<s<rq.
Тогда с учётом (2.1.7) получаем: H(C
s
)<H(C
rq
).
Аналогично, в силу (2.1.9) можем записать: H(C
r
q) <rH(Cq).
Имеем последовательность неравенств
s (r-l)q (r-l)q r-l
V
При достаточно большом s, а следовательно, и достаточно большом г, по-
лучаем: а~Б < ^^s)
<
,_£_^
a
+ 8
j <(
а
+ 2е).
s г-1
Так как е>0 может быть произвольно мало, то: lim
—
= а =
Ноо.
А
£-»00
s
В этом параграфе получен важный результат (теорема 2.1.1), что всякий
стационарный источник, в том числе и источник без памяти, имеет энтропию.
§ l.
МАТЕМАТИЧЕСКАЯ
МОДЕЛЬ ДИСКРЕТНОГО ИСТОЧНИКА СООБЩЕНИЙ, ЭНТРОПИЯ
СТАЦИОНАРНЫХ
ИСТОЧНИКОВ
§2
ТЕОРЕМЫ ШЕННОНА ДЛЯ ИСТОЧНИКОВ БЕЗ ПАМЯТИ
В этом параграфе в первой и второй теоремах Шеннона показаны свойства
так называемой информационной устойчивости (равнораспределённости) по-
следовательностей, порождённых простейшим типом источников - источником
без памяти.
Рассмотрим источник без памяти [A„p(s)j, генерирующий последователь-
ность фиксированной длины £. Оказывается, в распределении вероятностей
этих реализаций имеет место информационная устойчивость, что отражено в
следующей теореме:
Первая теорема Шеннона: Для любых е > 0, т) > 0 существует £
0
та-
кое, что при £>£
0
все реализации длины £
источника [A,p(s)] могут быть разбиты на
два класса: =С\
4-С".
(2.2.1)
Для любой последовательности е С\
имеет место:
-Jog
P(ci)
•Н
0
(2.2.2)
где = -^Tpj/og
Р{
- энтропия источника.
Суммарная вероятность последователь-
ностей из С" меньше s.
Доказательство. Зададимся произвольными г > 0, ц > 0. Для относи-
тельных частот встречаемости букв алфавита А в последовательностях С^,
реализованных на источнике без памяти, выполняется закон больших чисел:
Ve'
>
0, 8
>
0,
3*(е')
>
0,
W >
*(е'):
'У-Pi
<sj>l-e',
i = l,...,n,
(
22.3)
где itij - абсолютная частота встречаемости буквы а
}
в последовательности с
е
.
59
§ 2. ТЕОРЕМЫ ШЕННОНА ДЛЯ ИСТОЧНИКОВ БЕЗ ПАМЯТИ
Вероятность реализации последовательности с
е
=
....а^
на рассматривае-
мо
мом
источнике равна p(c^) = p
ij
...р^ =
J"JPI"'
•
Множество всех последовательностей разобьём на два непересекающих-
ся класса по следующему правилу. К первому классу C'f отнесём те и только
те последовательности, для которых
|т,-<р
8
|<€8
i =
l,...,n.
(
22.4)
Ко второму классу С\ отнесём все последовательности, для которых нера-
венства (2.2.4) не выполняются по крайней мере для одного индекса i.
Из (2.2.4) получаем равносильные неравенства:
Это означает, что компоненты пц случайного вектора (m
lv
..,m
n
) заключе-
ны в интервалах (^pj
-£Ъ^(,щ
Следовательно, для фиксированной реа-
лизации с\ еС'
е
существуют такие постоянные ©^ |®$|<1, i =
l
v
..,n,
что
С учётом такого представления m
i
получаем:
Р(С;)=ПР^
+Ш|
-
Сделаем ряд преобразований полученного выражения:
'«^=-E('pi+«ei)
&»Р|
=
Р(
с
е) ПТ
log
=
-<EP|fo*Pi-«E®|fo*Pi.
—R-^-H
00
=8Ze
i
/og
—.
I=1
i=l « i=l Pi
Используя неравенства |a +
b|
<|a| +
|b|,
получаем оценку для абсолютной
величины разности, стоящей в левой части равенства:
<ьт\е
{
\ь
8
-<фо
8
-.
i=l Pi 1=1 Pi
Так как вероятности p
s
букв алфавита А фиксированы и отличны от нуля, то
-log—.— Н
0
"
1
Yhg—<+
1 |,11Г
п
1=1
PI
60
ГЛАВА
II. ИСТОЧНИКИ
СООБЩЕНИЙ
Выбирая
5 =
т|
,
получаем,
что для
^>^(г|) будет выполняться
не-
Pi
равенство:
)io
g
-!—-n
Q
£
Р(с^)
Я*
(2.2.5)
Из определения последовательностей второго класса
(2.2.4)
получаем оцен-
ку
для их
суммарной вероятности:
Zp(c;)^tp(|in|-*Pi|^/e).
(
2 2б)
Для
ьго
слагаемого
в
первой части неравенства
(2.2.6),
согласно закону
больших чисел
(2.2.3), для Ve'> 0
3£
2
(в')> такое,
что для £>
£
2
(е!)
выполняется неравенство:
p{|mi ~£р
{
\> £Ь}<е'.
Полагая
е'=—,
получаем,
что
п
2>(cJ)<ii6
f
==e.
(2.2.7)
Выбирая
£
0
=
тах{^|(т|),^
2
(б)}, делаем вывод,
что при
£>£
0
одновремен-
но выполняются неравенства
(2.2.5) и (2.2.7). •
Следствие.
Из
доказанной теоремы
в
качестве следствия получаем,
что
вероятность
p(c'
f
)
оценивается сверху
и
снизу следующим образом:
а
^(н
а>
^)
<р(с
,
)<а
-£(н
00
-л)
Суммарная вероятность последовательностей
из
класса
С\ не
менее
1
- е.
Упорядочим
все
последовательности длины
£,
полученные
на
источнике
без
памяти [A,p(s)]
по
убыванию
их
вероятностей. Зададимся некоторым числом
а
(0 < а
<
1) и
будем отбирать наиболее вероятные последовательности, пока
их суммарная вероятность, оставаясь меньше заданного
а, не
будет обладать
таким свойством: добавление
к
этой сумме вероятности реализации следую-
щей последовательности делает
её
больше
а.
Множество отобранных после-
довательностей обозначим
МДа).