Приклади розв’язання задач

Задача 6.2.1

Розподіл ймовірностей появи символів на виході немарковського джерела з алфавітом потужності є таким:

Тривалості символів

Розрахувати ентропію, продуктивність та надмірність джерела.

Розв’язання. Користуючись виразами (1.1), (1.3), (1.4), (1.5), знаходимо:

4) ентропія

2) середня тривалість символу

3) продуктивність

4) надмірність

R = 1 – 2,058 / log ₂ 5 = 0,114.

Задача 6.2.2

Маємо два дискретних немарковських джерела інформації з алфавітами та з такими розподілами ймовірностей появи символів:

Не розраховуючи ентропії джерел, дати відповідь, яке з них має більшу ентропію.

Розв’язання. Оскільки розподіл імовірностей появи символів на виході джерела з алфавітом є більш близьким до рівноймовірного, ентропія цього джерела буде більшою, ніж джерела з алфавітом .

Розрахунки підтверджують цей висновок:

Задача 6.2.3

Матриця ймовірностей сумісної появи символів на виходах двох немарковських джерел з алфавітами та має вигляд:

Визначити, яке з джерел має більшу ентропію та чи є джерела статистично незалежними.

Розв’язання. Для відповіді на перше запитання розрахуємо, користуючись виразами (1.13), безумовні ймовірності появи символів на

виходах першого та другого джерел:

p (x ₁) = 0,0336 + 0,3150 + 0,0714 = 0,42 ;

p (x ₂) = 0,0264 + 0,2475 + 0,0561 = 0,33 ;

p (x ₃) = 0,0200 + 0,1875 + 0,0425 = 0,25 ;

p (y ₁) = 0,0336 + 0,0264 + 0,0200 = 0,08 ;

p (y ₂) = 0,3150 + 0,2475 + 0,1875 = 0,75 ;

p (y ₃) = 0,0714 + 0,0561 + 0,0425 = 0,17 .

Тепер можемо знайти ентропії джерел за виразом (6.1):

Таким чином, джерело з алфавітом має більшу ентропію, ніж джерело з алфавітом .

Відповідь на друге запитання можна отримати різними способами. По-перше, оскільки вже відомі значення ентропій та , доцільно перевірити, чи виконується рівність (6.18). Для цього розрахуємо сумісну ентропію . Підставивши чисельні значення ймовірностей у вираз (6.11), отримаємо:

Оскільки ,джерела є статистично незалежними.

Другий спосіб базується на перевірці виконання співвідношень для всіх пар символів:

p (x ₁) × p (y ₁) = 0,42×0,08 = 0,0336 ;

p (x ₂) × p (y ₁) = 0,33×0,08 = 0,0264 ;

p (x ₃) × p (y ₁) = 0,25×0,08 = 0,0200 ;

p (x ₁) × p (y ₂) = 0,42×0,75 = 0,3150 ;

p (x ₂) × p (y ₂) = 0,33×0,75 = 0,2475 ;

p (x ₃) × p (y ₂) = 0,25×0,75 = 0,1875 ;

p (x ₁) × p (y ₃) = 0,42×0,17 = 0,0714 ;

p (x ₂) × p (y ₃) = 0,33×0,17 = 0,0561 ;

p (x ₃) × p (y ₃) = 0,25×0,17 = 0,0561 .

Як і слід було очікувати, розраховані ймовірності цілком збігаються із відповідними значеннями ймовірностей сумісної появи символів, що наведені в умовах задачі.

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

Ще один спосіб розв’язання задачі базується на аналізі матриці умовних імовірностей. Розрахуємо, наприклад, умовні ймовірності , користуючись виразом :

Всі елементи кожного стовпця однакові і дорівнюють безумовній ймовірності появи відповідного символу . Це означає, що ймовірність появи символу на виході першого джерела не залежить від символу на виході другого джерела. Можна переконатись, що i в матриці умовних ймовірностей всі елементи кожного стовпця будуть однаковими і дорівнювати .

 

Задача 6.2.4

Маємо три дискретних немарковських джерела інформації з алфавітами , , . Матриці ймовірностей сумісної появи пар символів є такими:

 

Визначити, між якими джерелами статистичний зв’язок найбільший, а між якими найменший.

Розв’язання. Для відповіді на поставлене запитання треба знайти значення повної взаємної інформації для всіх пар джерел, та порівняти їх. Найпростіше в даному разі користуватись виразом

.

Щоб обчислити безумовні ентропії кожного з джерел, знайдемо безумовні ймовірності появи символів на виході джерел за виразом (6.13):

Слід зазначити, що значення кожної з ймовірностей можна отримати двома шляхами. Так є сумою елементів відповідних ря-дків першої матриці, або елементів стовпців третьої матриці. Це означає, що матриці, наведені в завданні, відповідним чином узгоджені.

Розрахуємо ентропії джерел, користуючись (6.1):

H (X) = 1,157 біт; H (Y) = 0,971 біт; H (Z) = 1,0 біт.

Далі за виразом (1.11) знаходимо сумісні ентропії:

Нарешті отримаємо:

Рівність нулю означає, що джерела з алфавітами та статистично незалежні. Найбільший статистичний зв’язок має місце між джерелами з алфавітами та , оскільки має найбільше значення.

Задача 6.2.5

Маємо три дискретних немарковських джерела з алфавітами Ймовірності сумісної появи символів мають такі значення:

p ( x ₁, y ₁, z ₁ ) = 0,048;

p ( x ₁, y ₁, z ₂ ) = 0,012;

p ( x ₁, y ₂, z ₁ ) = 0,072;

p ( x ₁, y ₂, z ₂ ) = 0,162;

p ( x ₂, y ₁, z ₁ ) = 0,272;

p ( x ₂, y ₁, z ₂ ) = 0,068;

p ( x ₂, y ₂, z ₁ ) = 0,300;

p ( x ₂, y ₂, z ₂ ) = 0,060.

Знайти ентропії кожного з джерел, системи трьох джерел, а також повну взаємну інформацію для кожної пари джерел.

Розв’язання. Щоб знайти ентропію кожного з джерел, розрахуємо ймовірності появи символів на виході джерел згідно з виразами:

Маємо такі значення:

p ( x ₁) = 0,3; p ( x ₂) = 0,7; p ( y ₁) = 0,4;

p ( y ₂) = 0,6; p ( z ₁) = 0,692; p ( z ₂) = 0,308.

Знаходимо ентропії джерел:

H (X) = 1,8813 біт; H (Y) = 0,971 біт; H (Z) = 0,8909 біт.

Щоб обчислити повну взаємну інформацію, знайдемо ентропії для чого розрахуємо ймовірності сумісної появи пар символів, користуючись виразами типу:

Маємо

За виразом (1.11) обчислюємо ентропії кожної із систем двох джерел:

H (X, Y ) = 1,7975 біт; H (X, Z) = 1,653 біт; H (Y, Z) = 1,8345 біт.

Тепер знаходимо значення повної взаємної інформації для всіх пар джерел:

Аналогічно

Для обчислення ентропії системи трьох джерел скористуємось виразом (6.20), коли

Із виразу (1.16) отримаємо

Щоб знайти H (Z / Y, X), необхідно розрахувати умовні ймовірності типу . Для цього скористаємось виразами:

Отримаємо

Далі знаходимо частинні умовні ентропії

,

аналогічно

Тепер обчислимо повну умовну ентропію:

Нарешті

Задача 6.2.6

Марковське дискретне джерело інформації з алфавітом та глибиною пам’яті описується такою матрицею умовних ймовірностей виникнення символу x_i при умові, що йому передував символ x_k :

(6.29)

Обчислити ентропію такого джерела.

Розв’язання. Щоб розрахувати ентропію марковського джерела, необхідно знати безумовні ймовірності появи відповідних символів на виході джерела. Їх можна отримати, скористувавшись рівняннями:

Підставивши сюди значення умовних ймовірностей з матриці (1.29) та дещо спростивши, будемо мати систему лінійних рівнянь:

Розв'язання системи дає:

Тепер можна скористуватись безпосередньо виразом (6.27), або ж обчислити частинні умовні ентропії для кожного стану джерела, а потім знайти ентропію марковського джерела, як математичне сподівання вищезгаданих частинних умовних ентропій. Кожна частинна умовна ентропія – це ентропія розподілу умовних імовірностей, розташованих в одному з рядків матриці (6.29).

Обравши другий шлях, будемо мати:

Задача 6.2.7

Маємо два дискретних джерела з алфавітами та . Перше джерело – марковське з глибиною пам’яті h = 1. Воно описується матрицею умовних ймовірностей

(6.30)

виникнення символу при умові, що попереднім був символ . Ймовірність виникнення символу на виході другого джерела залежить від того, який символ з’явився на виході першого джерела, тобто ці ймовірності задаються матрицею

(6.31)

Визначити ентропію другого джерела та повну взаємну інформацію.

Зауважимо, що ця задача моделює ситуацію, коли вихід марковського джерела з глибиною пам’яті подано на вхід стаціонарного дискретного каналу без пам’яті, який задається матрицею перехідних ймовірностей (6.31).

Розв’язання. Друге джерело буде в загальному випадку марковським, більш того, глибина пам’яті цього джерела може перевищувати одиницю. Отримати вираз для ентропії через ймовірності появи символів на виході другого джерела при цих умовах досить важко, оскільки для цього необхідно знати не тільки безумовні ймовірності , але й умовні – тощо. Для вирішення цієї задачі краще скористуватись виразами (1.16, 1.17), з яких можна отримати

.

(1.32)

Ентропія для марковського джерела з глибиною пам’яті знаходиться за виразом (6.27). Розрахунок ентропії для такого джерела при наведено в задачі 6.2.6.

Умовна ентропія знаходиться за виразом (6.7) – значення ймовірностей та є відомими. Щоб визначити умовну ентропію , необхідно знати ймовірностіта . Перші можна отримати таким чином:

Для ймовірностей маємо із виразу (6.14):

.

Таким чином, отримали всі компоненти, щоб розрахувати всі складові правої частини (6.32).

Припустимо, що перше джерело має характеристики із задачі 6.2.6, потужність алфавіту другого джерела , а матриця (6.31) має вигляд

.

Послідовно виконуючи вищезгадані дії, отримаємо:

H (Y / X) = 1,073 біт ;

p (y ₁) = 0,56049; p (y ₂) = 0,18889; p (y ₃) = 0,25062;

H (X/Y) = 0,671 біт.

Ураховуючи, що H (X ) = 1,001 біт,маємо H (Y ) = 1,403 біт. Нарешті, повна взаємна інформація

I (X, Y) = H (X ) – H (X/Y) = H (Y ) – H (Y/X) = 0,33 біт.

Задача 1.2.8

Маємо два немарковських дискретних джерела інформації з алфавітами Ймовірності появи символів на виході першого джерела

Значення умовних ймовірностей виникнення символу на виході другого джерела при умові, що на виході першого з'явився символ , є такими:

. (6.33)

Розрахувати ентропії кожного з джерел, системи двох джерел та повну взаємну інформацію.

Розв'язання. Скористуємось формулою повної ймовірності

для визначення ймовірностей появи символів на виході джерела з алфавітом

Отримані значення збігаються із значеннями ймовірностей . Висновок про це можна було зробити, аналізуючи матрицю (6.33). Кожний рядок і кожний стовпець має у своєму складі по одній одиниці. Це свідчить, що між символами існує взаємно-однозначний зв'язок. Тому

H (X ) = H (Y ) = 1,28 біт.

Для визначення та розрахуємо ймовірності сумісної появи символів та за виразом (6.14):

.

Тепер неважко пересвідчитись (зробіть це самостійно), що

H (X,Y) = I (X, Y) = H (X ) = H (Y ) = 1,28 біт.

Дата добавления: 2014-10-17; Просмотров: 1596; Нарушение авторских прав?; Мы поможем в написании вашей работы!