<< Предыдущая

стр. 7
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

41
4-3. Выводы

Таблица 4.2. Условная вероятность p(y,/Xj).


24
/
г2
/ Уз
У1

0 1
1/2 1/4 1/4
XI

1
0
1/7 3/7 3/7
XI

1
0 1/3 1/3
1/3
хз
1
0 1/3
1/3 1/3
Xi




4. В таблице 4.2 приведены условные вероятности, подсчитанные ис-
ходя из таблицы 4.1. Заметим, что при этом мы получили так назы-
ваемую стохастическую матрицу. Сумма условных вероятностей для
каждой строки равна 1.

= 1,5496. (4.20)
г=1 j = l




4.3. Выводы
Все приведенные в предыдущих разделах рассуждения в математи-
ческой форме сведены в табл. 4.3. Напомним, что основной идеей
теории информации является представление информации источни-
ка как меры неопределенности. Эта неопределенность раскрывается
посредством экспериментов со случайными событиями из алфавита
этого источника. Такой подход поясняют три столбца таблицы.
Так как информация исходит из случайности событий, в первом
столбце вводится понятие вероятности событий и совместной веро-
ятности пары событий как основополагающих величин. Для пары
событий вводится также понятие условной вероятности. Во втором
столбце дается определение информации события и нары событий,
а также условной и взаимной информации. И, наконец, в третьем
столбце, вводится понятие энтропии как меры неопределенности ис-
точника.
Энтропия источника, совместная и условная энтропии двух ис-
точников трактуются как математические ожидания соответствую-
щих информации событий. Условная вероятность - это вероятность
одного события при условии, что другое событие уже произошло, по-
(42 Глава 4- Энтропия связанных источников




Таблица 4.3. Дискретные источники без памяти X и У с сим-
волами х S X = {xi,xa, • • • , 1 м } и ;/ 6 У —
(
{г/1. №,•••, 1/JV}-

Информации Энтропия


Информация отдельного Энтропия
Вероятность
отдельного сим- символа
вола (априорная
I(x) = -log 2 p(x) бит
вероятность)
р(х)




Совместная ве- Информация пары сим-
роятность двух волов H(X,Y) -
символов
1(х,у) = - log2 р(х, у) бит
Р(х, У)



Условная веро- Условная информация
H(X/Y) =
ятность (апо-
Цх/у) = - \<щгр{х/у) бит
стериорная
I бит
вероятность) Цу/х) = - log2p(y/x) бит

H(Y/X) =
Р(.х,у)
р(х/у) =
р(у) I бит
р
^'у' log
Р(х,у)
Р(у/х) =
р{х)



Взаимная информация
,/ ч _, апостериорная вероятность , J
и
\ 'У/ - & априорная информация
2
4-3. Выводы

этому, понятия условной информации и условной энтропии вполне
естественно выводятся из условной вероятности.
Взаимная информация не имеет аналога в теории вероятности.
Это совершенно новое понятие теории информации, играющее цен-
тральную роль в информационной технике. Взаимная информация
связывает понятие канала с возможностью передачи информации по
нему, т.е. с его пропускной способностью. Это понятие будет подроб-
но рассмотрено в 7 главе этой книги.
ГЛАВА 5
СТАЦИОНАРНЫЕ
ДИСКРЕТНЫЕ ИСТОЧНИКИ
С ПАМЯТЬЮ


5.1. Энтропия
Сигналы аналоговых источников информации ограничены по поло-
се, поэтому коррелированы во времени. Примером может служить
аналоговый речевой сигнал в телефонной линии. После оцифров-
ки, аналоговый источник превращается в дискретный и, например,
после квантования сигнала на 256 уровней, мы получаем последо-
вательнось 8-ми битовых двоичных целых чисел от 0 до 255. Как
видно из рис. 5.1, значение двух соседних чисел близки друг к дру-
гу, т.к. телефонный сигнал передается в узкой полосе частот. Из-
за временной связи соседних отсчетов, то есть памяти отсчета, его
неопределенность (информация) снижается по сравнению с анало-
говым источником без памяти, поэтому основной задачей методов
сжатия, особенно при передаче видеосигналов, является снижение
избыточности.

;;
III!!
;I -
i iii
\y i!
Jf
л
i:
r- [
i \\c
({ -
\
%
j• lo
i
IT
i:

Рис. 5.1. Непрерывный сигнал.

Возникает вопрос о том, каким образом определить энтропию
дискретного источника с памятью. Начнем с постановки задачи.

Определение 5.1.1. Дискретный источник X можно представить
как дискретный во времени стохастический процесс, реализацией
5.1. Энтропия

которого является последовательность событий хп, принадлежащих
алфавиту источника X = {оц, «2,..., адг}-
Замечание. Во избежание путаницы, мы обозначили содержимое
алфавита греческими буквами. В этом случае на месте переменной
хп п-го события может быть поставленно любое число из алфави-
та X.

Определение 5.1.2. Дискретный источник является стационар-
ным, если совместные вероятности последовательностей событий не
зависят от выбора начальной точки отсчета времени.
Замечание. Независимость наблюдений от точки отсчета озна-
чает, что мы можем начинать выборку с любого момента-време-
ни, то есть статистика не зависит от времени начала наблюде-
}шй.

Определение 5.1.3. Стационарный дискретный источник мате-
матически полностью описан, если известны все совместные веро-
я т н о с т и р(хП1, хП2,..., д л я л ю б о й в ы б о р к и пх,П2,...,пм, где
хпм)
М —> оо.

Определение энтропии стационарного дискретного источника с
памятью следует из двух подходов, приводящих к одинаковому ре-
зультату. При первом подходе мы используем понятие совместной эн-
тропии, при втором - условной энтропии. В обоих случаях мы ищем
ответ на следующий вопрос: «Если память источника распростра-
няется на несколько последовательных событий, то какую дополни-
тельную информацию несет отдельное событие в том случае, если
блок предшествующих событий уже известен?»

Подход 1. Совместная энтропия.
Совместная энтропия двух источников Х\ и xi с одинаковыми
алфавитами и одинаковыми распределениями вероятностей событий
определяется как
мм
(5.1)
H(X1,X2) = -^2^2p(Xi,Xj)log2P(Xi,Xj).


Распространим это определение на L последовательных источников
Xi и найдем энтропию источника Xi как

i ^ , (5.2)
Глава 5. Стационарные дискретные источники с памятью /
j
где вектор X = (х\,х2, • • • ,?/,) и суммирование производится по вс^м
возможным компонентам вектора X. Устремляя L к бесконечнос+и,
мы полностью охватим память источника и получим предельное зна-
чение Hi(X) (если оно существует), равное i

Яоо(Х) = lim H(XL). (5.3)
L—юо

Подход 2. Условная энтропия.
Условная энтропия L-того события в случае, если L — 1 предше-
ствующих событий уже известны, определяется как

lim H(XL/X1,X2,...,XL_1). (5.4)
НО0{Х)=
L—too
Хотя в левых частях равенств (5.3) и (5.4) мы уже использовали оди-
наковое обозначение энтропии отдельного события, этот факт пред-
стоит доказать. Проведем это доказательство за 4 шага.

Теорема 5.1.1. Для стационарного дискретного источника с Hi{x) <
ос имеет место:
1. H(Xi\Xi, X2, • • •, XL^I) не возрастает с ростом длины блока L;
2.HL(X)>H(XL\Xi,X2,...,XL-1);
3. HL(X) не возрастает с ростом длины блока L;
4. Энтропия стационарного дискретного источника HL(X)
lim HL(X) = lim ff(Xt|Xi,X2,...,XL_i) = Я о о Р 0 .
L—too L—too
Доказательство.
1. Из определения энтропии, как меры неопределенности источ-
ника, непосредственно следует, что возрастание числа ограничений
не может повлечь за собой рост неопределенности, а следовательно
и энтропии.
2. Из «правила цепочки» для совместной энтронии следует

j[H(X1) + H(X2\X1) + --- +
Li . (5.5)
+ H(XL\X1,X2,...,XL^)].
Замечание. «Правило цепочки» для совместной энтропии следует
из «правила цепочки» для вероятностей. Простейший пример «пра-
вила цепочки» для вероятностей р(х, у) = р(х/у)р(у) и р(х, у, z) =
p(x/yz)p(y/z)p(z). Так как логарифмическая функция отображлет
произведение в сумму, получаем «правило цепочки» для совместной
энтропии.
5.1. Энтропия AT,

, Так как энтропия всегда неотрицательна и имеет место неравен-
ство

<< Предыдущая

стр. 7
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>