Ансамблі та джерела повідомлень

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

Якщо під час деякого часового проміжку дискретним джерелом вибрано деяке повідомлення а_і, яке ніяк не зумовлене повідомленням а_{і- 1}, вибраним у попередній проміжок часу, то таке джерело є дискретним джерелом без пам’яті.

Якщо в деякому часовому проміжку дискретним джерелом вибрано повідомлення а_і, пов’язане з попереднім повідомленням а_{і- 1} статистично зумовлене ним, то таке джерело називається дискретним джерелом із пам’яттю.

Крім дискретних, можуть бути також неперервні джерела повідомлень із пам’яттю та без пам’яті. Переліченими тут типами не вичерпуються всі відомі джерела повідомлень. Специфічні джерела повідомлень, в яких враховано статистичні якості фізичних параметрів.

Якщо кожного проміжку часу дискретне джерело повідомлень вибирає одне з k можливих повідомлень а ₁, а ₂,…, а_k, то кажуть, що А ={ а ₁,…, а_k } є дискретною множиною повідомлень, або просто множиною повідомлень А. Як правило, для повнішого опису джерела повідомлень на множині А визначають її ймовірнісну міру, тобто з кожним дискретним повідомленням а_і пов’язують ймовірність р_і його вибору джерелом. Таки чином, множині А ={ а ₁,…, а_k } зіставляється ймовірнісна міра у вигляді множини Р_k ={ p ₁,…, p_k }, на яку накладено обмеження у вигляді .

Дві множини А та Р дають достатньо повний опис дискретного джерела повідомлень у вигляді його ймовірнісної моделі, а тому разом вони утворюють ансамбль повідомлень дискретного джерела. Це означає, що кожного проміжку часу дискретним джерелом вибирається певне повідомлення з ймовірністю .

 

Кількісна міра інформації

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

1) у повідомленні про вірогідний випадок вона має дорівнювати нулю;

2) у двох незалежних повідомленнях вона має дорівнювати сумі кількостей інформації в кожному з них;

3) вона не повинна залежати від якісного змісту повідомлення (ступеня його важливості, відомостей тощо).

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

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

Для задоволення другої вимоги можна врахувати, що ймовірність двох незалежних повідомлень а ₁ та а ₂ за законом множення ймовірностей . Проте кількість інформації у цих двох повідомленнях

. (2.1)

Звідси випливає необхідність вибору такої функції f(p_i), значення якої при перемноженні її аргументів p_i додавалися б і щоб f(0)=f(1)=0. Єдиною функцією з такими властивостями є логарифмічна функція

, (2.2)

де k – коефіцієнт, який узгоджує розмірності, а логарифм береться за будь-якою зручною основою.

При такому визначенні кількості інформації задовольняються всі три наведені вище вимоги.

Таким чином, кількість інформації в повідомленні тим більша, чим воно менш ймовірне, тобто більш неочікуване.

 

Ентропія та її властивості

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

 

Таблиця 2.1

	a1	a2	a3	a4	a5	a6
I (ai), біт	0,4 1,322	0,3 1,737	0,15 2,737	0,1 3,322	0,03 5,059	0,02 5,644

 

Розглянемо, яку кількість інформації несуть більш-менш довгі послідовності таких повідомлень:

· перша послідовність

а ₃, а ₁, а ₄, а ₄, а ₂, а ₂, а ₁, а ₃, а ₁, а ₂,

а ₅, а ₁, а ₁, а ₂, а ₃, а ₂, а ₁, а ₂, а ₁, а ₁,

а ₁, а ₂, а ₁, а ₁, а ₁, а ₂, а ₂, а ₃, а ₄, а ₃;

 

· друга послідовність

а ₂, а ₁, а ₃, а ₂, а ₂, а ₁, а ₂, а ₁, а ₃, а ₁, а ₄,

а ₂, а ₄, а ₁, а ₁, а ₃, а ₁, а ₂, а ₁, а ₅.

У першій послідовності є 30 повідомлень, а в другій – 20. Розподіл імовірностей з ансамблю (див. табл.2.1.) настільки нерівномірний, що ні до першої, ні до другої послідовностей не ввійшло повідомлення а ₆. Справа в тому, що його за законами статистики можна було б помітити в послідовності повідомлень при довжині останньої, значно більшій від n =1/ p ₆=50. Отже, кількість інформації в першій послідовності

біт,

а в другій

біт.

Як бачимо, ці послідовності різняться не тільки кількістю повідомлень, а й кількістю інформації в кожній з них. Однак, якщо обчислити кількість інформації, яка припадає на одне повідомлення в одній послідовності та в іншій, то виявиться, що і ₁/30=2,0069 біт/повідомлення та і ₂/20=2,0456 біт/повідомлення. Це означає, що середня кількість інформації, яка припадає на одну літеру алфавіту повідомлень (це те саме, що й на одне повідомлення), не залежить від конкретних повідомлень і довжини послідовності їх.

Деяка різниця тут між і ₁/30 та і ₂/20 пояснюється лише недостатньою довжиною послідовностей повідомлень. Відповідно до статистичного закону великих чисел ці відношення збігатимуться краще, чим більшими будуть довжини порівнюваних послідовностей.

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

Точну ентропію можна визначити як математичне сподівання питомої кількості інформації

. (2.3)

Згідно з даними табл. 2.1 маємо Н (А)=0,4·1,322+0,3 1,737+0,15·2,737+0,1·3,322+0,03·5,059+0,02·5,644=2,0573біт/повідомлення.

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

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

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

. (2.4)

Наприклад,

i ₁ = 30 · 2,0573 = 61,719 біт; і ₂ = 20 · 2,0573 = 41,146 біт.

Розбіжність тут пояснюється невеликими значеннями N, адже ймовірність p_i обчислюються, як правило, за умови N→∞. Розглянемо вироджене дискретне джерело з єдиним повідомленням з р (а)=1. Тоді Н (А)=0 згідно з (2.3). Якщо р (а)=0, то Н (А) теж дорівнюватиме нулю. Таким чином, ентропія завжди додатна або дорівнює нулю, тобто невід’ємна. Це перша її властивість.

Друга властивість ентропії випливає з виразу (2.3), згідно з яким вона є величиною адитивною. Якщо N – вимірні послідовності повідомлень а ₁, а ₂, … а _N розглядати як збільшені повідомлення нового джерела, то його ентропія буде в N разів більшою від початкової.

Якщо алфавіт A ={ a ₁, a ₂, …, a_k } має k різних повідомлень, то Н (А) ≤ log k. Тут рівність стосується тільки рівноймовірних і статистично незалежних повідомлень . Число k називається обсягом алфавіту повідомлень.

 

Безумовна ентропія

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

За цим визначенням розглянута в п. 2.3 ентропія є безумов­ною. Зупинимося докладніше на безумовній ентропії та її вла­стивостях.

Якщо є дискретне джерело статистично незалежних повідом­лень з ансамблем A ={ a ₁, a ₂, …, a_i, …, a_k } та р ={ р ₁, р ₂, …, р_i, …, р_k }, то кількість інформації (середня), що припадає на одне по­відомлення й визначається формулою Шеннона

, (2.5)

є характеристикою цього джерела в цілому. Вона має фізичний зміст середньої за ансамблем невизначеності вибору джерелом повідомлення з А,причому байдуже, якого саме повідомлення, оскільки обчислення ентропії (2.5) «поглинає» індекс і. Наприк­лад, джерело з k =8 незалежними та рівноймовірними повідом­леннями має ентропію

біт/повідомлення.

Тут ураховано, що p_i = p =1/8. Для нерівноймовірних пові­домлень у цьому разі Н (А)< 3 біт/повідомлення.

Таким чином, основними властивостями безумовної ентро­пії дискретних повідомлень є такі:

• ентропія - величина дійсна, обмежена та невід'ємна;

• ентропія вірогідних повідомлень дорівнює нулю;

• ентропія максимальна, якщо повідомлення рівноймовірні та статистично незалежні;

• ентропія джерела з двома альтернативними подіями може змінюватися від 0 до 1;

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

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

Припустимо, що повідомлення а зустрічалося у довгому лан­цюзі з N =1000 повідомлень l₁ =200 разів, повідомлення b у цьому самому ланцюзі - l ₂=200 разів, а разом вони зустрілися лише l ₃=50 разів. Скориставшись теорією математичної ста­тистики, можна встановити, що ймовірність появи повідомлення а в цьому ланцюзі р (а) =l ₁/ N =0,25, а повідомлення b-p (b)= l ₂/ N =0,2. Крім того, р (аb)= l ₃/ N =0,05. При цьому p (ab)= p (a) p (b)=0,25·0,2=0,05, що є явною ознакою статистичної незалежності повідомлень а та b. Саме для таких повідомлень існує безумовна ентропія, про яку йшлося вище.

Коли б у цьому прикладі пара аb зустрілася l ₃=30 разів, то виявилося б, що р (аb)= l ₃/ N =0,03< p (a) p (b). Це є ознакою порушення статистичної незалежності повідомлень а та b, яка відбиває той факт, що вони не «прагнуть» зустрічатися разом у послідовностях повідомлень, тобто поява одного з них дає підставу з більшою впевненістю не очікувати появи іншого, ніж це було б до появи першого повідомлення.

3 іншого боку, при l ₃=100 маємо р (аb)= l ₃/ N =0,1> p (a) p (b), що дає підставу підозрювати взаємне «тяжіння» а до b,і навпа­ки. Тут теж проглядається порушення статистичної незалеж­ності, тобто відношення «байдужості» між повідомленнями а та b.

Мірою порушення статистичної незалежності (стану «бай­дужості») між повідомленнями а та b є умовна ймовірність по­яви повідомлення а за умови, що вже з'явилося повідомлення b: p (a / b), або умовна ймовірність появи повідомлення b,коли вже з'явилося повідомлення a: p (b / a), причому взагалі p (a / b)≠ p (b / a).

Теорія математичної статистики визначає умовну ймовір­ність через безумовні ймовірності р (a), p (b)та сумісну безумов­ну ймовірність р (аb)за законом множення ймовірностей:

р (аb) =р (а) р (b/а) =р (b) p (а/b). (2.6)

Звідси випливає, що

р (b/а) =р (аb) /р (а); р (а/b) =р (аb) /р (b). (2.7)

Зокрема, для статистично незалежних повідомлень а та b ( див. вище) маємо

р (b/а) = 0,05/0,25=0,2= р (b);

р (a/b) = 0,05/0,2=0,25= р (а),

тобтоумовні ймовірності появи повідомлень вироджуються в безумовні.

Розрізняють два різновиди умовної ентропії: часткову та загальну. Першу знаходять так:

; (2.8)

, (2.9)

де A ={ a ₁, a ₂, …, a_i, …, a_k }, B ={ b ₁, b ₂, …, b_j, …, b_l } - алфавіти повідомлень; а_і -конкретне повідомлення, відносно якого ви­значається часткова умовна ентропія Н (В/а_i)алфавіту В за умови вибору попереднього повідомлення a_i; b_j - конкретне повідомлення, відносно якого обчислюється часткова умовна ентропія Н (А/b_j)алфавіту А за умови вибору попереднього повідомлення b_j; і -номер повідомлення з алфавіту А; j - но­мер повідомлення з алфавіту В; р (а/b), р (b/а)- умовні ймовір­ності.

Часткова умовна ентропія визначається як статистичне усереднення за методом зваженої суми (2.8), (2.9) по індексу і =1… k або j =1… k відповідно.

Ураховуючи викладене вище, загальну умовну ентропію можна визначити так: якщо часткова умовна ентропія джерела А відносно конкретного повідомлення b_j дорівнює H (A / b_j), а розподіл імовірностей P_B джерела B задано ансамблем B із P_B ={ p (b ₁), …, p (b_j), …, p (b_k)}, то цілком природно обчислити середнє по j значення H (A / b_j) за всіма j як статистичне усереднення методом зваженої суми, тобто

, (2.10)

де H (A / B) – загальна умова відносно джерела ентропія джерела А відносно джерела В. Це питома (середньостатистична) кількість інформації, що припадає на будь-яке повідомлення джерела А, якщо відомо його статистичну взаємозалежність із джерелом В.

Аналогічно (2.10) загальна умовна ентропія джерела В відносно джерела А визначається виразом

, (2.11)

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

Загалом статистична залежність джерела В від джерела А від­бивається матрицею прямих переходів повідомлень а_і (і= 1... k)джерела А в повідомлення b_j (j = 1... k) джерела B:

 

 

A	B
b 1	b 2	…	b j	…	b k
a1 а2 … ai … ak	p (b 1/ a 1) p (b 2/ a 1) … p (b j/ a 1) … p (b k/ a 1) p (b 1/ a 2) p (b 2/ a 2) … p (b j/ a 2) … p (b k/ a 2) … … … … … … p (b 1/ a i) p (b 2/ a i) … p (b j/ a i) … p (b k/ a i) … … … … … … p (b 1/ a k) p (b 2/ a k) … p (b j/ a k) … p (b k/ a k)

 

На головній діагоналі цієї матриці розміщено умовні ймовір­ності прямої відповідності типу а ₁→ b ₁ ,..., а_k→b_k, які харак­теризують правильний вибір джерелом В своїх повідомлень (тобто відповідно до повідомлень джерела А).Решта ймовір­ностей відповідають неправильному вибору повідомлень дже­релом B.

Матриця відбиває вплив завад у каналі між джерелом А та спостерігачем В. Якщо завади непомітні або зовсім відсутні, то маємо однозначну відповідність а_i→b_i з умов­ної ймовірності р (b_i / а_i)=1 для і =1... k. Решта ймовірностей р (b_j / а_i)=0 для всіх j ≠ i.

Кожний рядок у матриці є спотвореним розподілом імовірнос­тей Р_B появи повідомлення . Джерело В має розподіл без­умовних імовірностей Р_B. Врахування статистичного впливу повідомлення спотворює цей розподіл (або уточнює його) і дає новий розподіл імовірностей Р (В/а_i)для і -го рядка матри­ці. Саме тому виконується закон нормування

, i =1… k. (2. 12)

Статистична залежність джерела А від джерела В відбивається матрицею зворотних переходів типу а_і ← b_j,складеною з умовних імовірностей p(a_i / b_i):

 

(2.13)

Вона відображає k розміщених стовпцями варіантів спотво­рених первинних розподілів імовірностей ансамблю А, які відчу­вають на собі статистичний вплив повідомлень b_j (j =1… k), вибраних джерелом В. Саме тому для кожного такого розподілу

, j =1… k (2.14)

Нехай задано таку матрицю Р (a_i , b_j) сумісних імовірностей появи повідомлень двох джерел А та В з алфавітами а_i та b_j,де i =1, 2,
3 та j = 1, 2, 3 (k = l =3):

(2.15)

Оскільки р (аb)- безумовні ймовірності, для них виконується закон нормування

Окрема розгортка по рядках (по i) без зміни j «поглинає» алфавіт а_i ідає безумовну ймовірність р (b_j),тобто ймовірнісну міру для джерела В (2.17):

0,2 + 0 + 0,1 = 0,3 = р (b₁) при j =1;

0 + 0,2 + 0,1 = 0,3 = р (b₂) при j = 2; 0,1 + 0,1 + 0,2 = 0,4 = p (b₃) при j = 3;

Перевіримо нормування:

р (b₁) + р (b₂) + р (b₃) = 0,3 + 0,3 + 0,4 = 1.

Окрема згортка по стовпцях (за j) без зміни i «поглинає» алфавіт b_j і дає безумовну ймовірність р (a_i),тобто ймовірнісну міру для джерела А (2.18):
0,2 + 0 + 0,1 = 0,3 = р (a₁) при i =1;

0 + 0,2 + 0,1 = 0,3 = р (a₂) при i = 2;

0,1 + 0,1 + 0,2 = 0,4 = p (a₃) при i = 3;

Перевіряємо нормування:

р (a₁) + р (a₂) + р (a₃) = 0,3 + 0,3 + 0,4 = 1.

З урахуванням (2.1) на підставі (2.15) дістаємо таку матрицю умов­них імовірностей:

(2.16)

Перевірка на виконання закону нормування дає позитивну від­повідь, тобто

= р (а ₁ /b ₁)+ р (а ₂ /b ₁)+ р (а ₃ /b ₁) при j =1;

= р (а ₁ /b ₂)+ р (а ₂ /b ₂)+ р (а ₃ /b ₂) при j =2;

= р (а ₁ /b ₃)+ р (а ₂ /b ₃)+ р (а ₃ /b ₃) при j =3;

Отже, кожний рядок (2.16) є розподілом повідомлень a_i, спотвореним через статистичний вплив повідомлень :

(2. 17)

Перевірка виконання закону нормування дає позитивну відпо­відь, тобто

2/3 + 0 + 1/3 = 3/3=1 = р (b ₁ /a ₁)+ р (b ₂ /a ₁)+ р (b ₃ /a ₁) при i =1;

0 + 2/3 + 1/3 = 3/3=1 = р (b ₁ /a ₂)+ р (b ₂ /a ₂)+ р (b ₃ /a ₂) при i =2;

0,25 + 0,25 + 0,5 =1 = р (b ₁ /a ₃)+ р (b ₂ /a ₃)+ р (b ₃ /a ₃) при i =3.

Таким чином, кожний стовпець (2.17) є розподілом повідомлень b_j,спотвореним через статистичний вплив повідомлень .

Тепер, маючи дані (2.16), розрахуємо безумовну ентропію дже­рела А:

Н (А) = - (0,3 lоg 0,3 + 0,3 lоg 0,3 + 0,4 lоg 0,4) = 1,57095 біт/повідомлення.

Аналогічно, маючи дані (2.17), обчислимо безумовну ентро­пію джерела В:

Н (В)= - (0,3 lоg 0,3 + 0,3 lоg 0,3 + 0,4 lоg 0,4) = 1,57095 біт/повідомлення.

У розглядуваному прикладі Н (В) = Н (А)тому, що збігаються розпо­діли безумовних імовірностей. До речі, максимального значення Н (А)та H (В)досягли б при рівноймовірному розподілі ймовірностей, тобто при р (a_i) = 1/3 та p (b_j)= 1/3 для {1,2, 3}.

Тоді було б

H _max(A) = H _max(B) = -log (1/ k) = log k = log 3 = 1,58496 біт/повідомлення.

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

Часткова умовна ентропія джерела А з урахуванням (2.16) становитиме

H (A/b ₁) =-[(2/3) lоg (2/3) + 0 lоg 0 + (1/3) lоg (1/3)] = 0,91829 біт/повідомлення;

H (A/b ₂) =-[0 lоg 0 + (2/3) lоg (2/3) + (1/3) lоg (1/3)] = 0,91829 біт/повідомлення;

H (A/b ₃) =-(0,25 lоg 0,25 + 0,25 lоg 0,25 + 0,5 lоg 0,5) = 1,5 біт/повідомлення.

Загальна умовна ентропія джерела А відносно джерела В

H (А/В)= 0,3 H (А/b ₁)+ 0,3 H (А/b ₂)+ 0,4 H (А/b ₃) = 2 · 0,3 · 0,91829 + 0,4 · 1,5= 1,15097 біт/повідомлення.

Часткова умовна ентропія джерела В становитиме

H (B/a ₁) =-[(2/3) lоg (2/3) + 0 lоg 0 + (1/3) lоg (1/3)] = 0,91829 біт/повідомлення;

H (B/a ₂) =-[0 lоg 0 + (2/3) lоg (2/3) + (1/3) lоg (1/3)] = 0,91829 біт/повідомлення;

H (B/a ₃) =-(0,25 lоg 0,25 + 0,25 lоg 0,25 + 0,5 lоg 0,5) = 1,5 біт/повідомлення.

Загальна умовна ентропія джерела В відносно джерела А

H (B/A)= 0,3 · 2 · 0,91829 + 0,4 · 1,5 = 1,15097 біт/повідомлення.

Відзначимо окремо такі властивості умовної ентропії:

1. Якщо джерела повідомлень А та В статистично незалежні,
то умовна ентропія джерела А відносно джерела В дорівнює
безумовній ентропії джерела А й навпаки:

H (А/В) = H (А); H (B/A) = H (В).

2. Якщо джерела повідомлень А та В настільки статистично
взаємозв'язані, що виникнення одного з повідомлень спричи­няє безумовну появу іншого, то умовні ентропії їх дорівнюють нулю:

H (А/В) = H (B/A) = 0.

3. Ентропія джерела взаємозалежних повідомлень (умовна ентропія) менша від ентропії джерела незалежних повідомлень (безумовна ентропія).

4. Максимальну ентропію мають джерела взаємонезалежних рівноймовірних повідомлень, умовна ентропія яких дорівнює нулю, а ймовірність появи символів алфавіту р= 1/ k,де k - кількість повідомлень в алфавіті.