Ю.Д.Жданова. Лекції з МОКП. М4 Йм.-стат., теор.-складнісні, теор.-інформаційні основи. Лекція № 10

Лекція № 10 Тема: Ймовірнісні моделі джерел повідомлень

План лекції:

1. Ймовірнісні моделі джерел дискретних повідомлень.

2. Ентропія джерел дискретних повідомлень.

3. Умовна ентропія.

4. Щільність ентропії стаціонарного джерела дискретних повідомлень.

5. Однорідний ланцюг Маркова як модель джерела дискретних повідомлень.

6. Ймовірнісні моделі джерел неперервних повідомлень та їх ентропійні властивості.

1. Ймовірнісні моделі джерел дискретних повідомлень

Нехай розглядається довільне джерело повідомлень. Кожне повідомлення є деякою послідовністю символів (наприклад, букв англійського алфавіту, точок і тире в телеграфії, нулів і одиниць в комп'ютерній логіці і т. д.). Окремий символ повідомлення будемо позначати ; і будемо припускати числовою величиною, яка набуває всіх можливих значень з деякої множини,.

Множина значень символу повідомленняназивається алфавітом повідомлень. Якщо алфавітє скінченною множиною потужності:, то кажуть, що має місце джерело дискретних повідомлень (ДДП).

Величини називаються символами алфавіту, а число– потужністю алфавіту. Поява в повідомленні будь-якого символу алфавіту характеризується високою мірою невизначеності. Для математичного опису цієї невизначеності використаємо дискретну ймовірнісну модель. Нехай– ймовірнісний простір, що описує випадковий "експеримент" по появі (реєстрації) символу. Тоді кожному елементарному наслідкуцього експерименту ставиться у відповідність значення символу. Таким чином, символ– дискретна випадкова величина, яка цілком визначається дискретним розподілом ймовірностей:

,

причому

, .

Приклад. Розподіл ймовірностей символів англійського, українського і російського алфавітів.

Таблиця 1. Розподіл ймовірностей символів англійського алфавіту

Символ	Ймовірність	Символ	Ймовірність	Символ	Ймовірність
Е	0,123	L	0,040	В	0,016
Т	0,096	D	0,036	G	0,016
А	0,081	С	0,032	V	0,009
O	0,079	U	0,031	К	0,005
N	0,072	Р	0,023	Q	0,002
I	0,071	F	0,023	X	0,002
S	0,066	М	0,022	J	0,001
R	0,060	W	0,020	Z	0,001
Н	0,051	Y	0,019

Таблиця 2. Розподіл ймовірностей символів українського алфавіту,

включаючи апостроф

Символ	Ймовірність	Символ	Ймовірність	Символ	Ймовірність
О	0,084	M	0,029	Й	0,009
Н	0,071	Л	0,029	Ц	0,008
А	0,070	Д	0,028	Ю	0,007
И	0,055	У	0,025	Ж	0,007
Т	0,050	П	0,025	Ї	0,006
Е	0,049	3	0,020	Ф	0,005
Р	0,046	Я	0,019	Є	0,004
І	0,045	X	0,013	Ш	0,004
В	0,043	Ь	0,013	Щ	0,003
C	0,037	Б	0,012	’	0,001
K	0,030	Ч	0,012	Ґ	0,0003

Таблиця 3. Розподіл ймовірностей символів російського алфавіту,

включаючи пробіл

Символ	Ймовірність	Символ	Ймовірність	Символ	Ймовірність
Пробіл	0,175	K	0,028	Ч	0,012
О	0,090	M	0,026	Й	0,010
Е	0,072	Д	0,025	X	0,009
А	0,062	П	0,023	Ж	0,007
И	0,062	У	0,021	Ю	0,006
Н	0,053	Я	0,018	Ш	0,006
Т	0,053	Ы	0.016	Ц	0,004
C	0,045	3	0,016	Щ	0,003
Р	0,040	Ь	0,014	Э	0,003
В	0,038	Б	0,014	Ф	0,002
Л	0,035	Г	0,013

Таким чином, ДДП у випадку односимвольного повідомлення описується дискретною ймовірнісною моделлю . Ця модель описує лише поодинокий випадковий символ повідомлення. Повідомлення, породжуване ДДП, – це в загальному випадку послідовність,випадкових символів:

.

При цьому повний ймовірнісний опис ДДП задається ймовірнісною моделлю випадкового часового ряду (випадкового процесу) з дискретним часомі дискретним простором станів,:

,

, .

де –-вимірний дискретний розподіл ймовірностей-символьного повідомлення. Відзначимо, що-вимірні розподіли ймовірностей задовольняють умові самоузгодженості (.):

.

Означення. ДДП називається стаціонарним, якщо випадковий процес є стаціонарним (у вузькому розумінні), тобто якщо скінченновимірні розподілиінваріантні відносно зсуву початку відліку часу.

Означення. Стаціонарне ДДП називається джерелом без пам’яті, якщо для будь-яких справедлива факторизація-вимірного розподілу ймовірностей:

,

тобто породжувані ДДП випадкові символи незалежні в сукупності й однаково розподілені.