3. Приклад виконання завдання

Два статистично незалежних джерела А та В визначаються матрицею ймовірностей p(a_i,b_j)

Визначити часткову та загальну умовну ентропію, ентропію об'єднання, безумовну ентропію цих джерел, а також кількість інформації, що припадає на пару повідомлень a_i,b_j.

Розв’язання:

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

Окрема розгортка по рядках (по i) без зміни j "поглинає" алфавіт a_j і дає безумовну ймовірність p(b_j), тобто ймовірні стну міру джерела B:

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

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

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

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

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

Окрема розгортка по рядках (по j) без зміни i "поглинає" алфавіт b_j і дає безумовну ймовірність p(a_i), тобто ймовірні стну міру джерела A:

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

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

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

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

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

З урахуванням p(b|a)=p(ab)/p(a); p(a/b)=p(ab)/p(b) дістаємо матрицю умовних ймовірностей:

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

при j=1;

при j=2;

при j=3.

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

.

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

при i=1;

при i =2;

при i=3.

Таким чином, кожний рядок є розподілом повідомлень b_i, спотворений через статистичний вплив повідомлень.

Тепер маючи відповідні данні розраховуємо безумовну ентропію джерела A:

Аналогічно обчислимо безумовну ентропію джерела B:

Часткова ентропія джерела А за

з урахуваннямстановитиме

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

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

становитиме

Загальна умовна ентропія джерела B відносно джерела A згідно

Ентропія об'єднання цих джерел, враховуючи становить

Кількість інформації, що припадає на одне повідомлення

Тема: Кодування інформації. Побудова оптимального коду алфавіту методом Шеннона-Фано

Мета роботи: Вивчення поняття кодування. Опрацювання процедури кодування по методу Шеннона-Фано.

1. Теоретичні відомості

1. Кодування інформації

Під кодуванням у загальному випадку розуміють перетворення алфавіту повідомлення A{х_і}, ( i = 1,2…K) в алфавіт деяким чином обраних кодових символів { a_j }, ( j = 1,2…N)... Звичайно (але не обов'язково) розмір алфавіту кодових символів { а_j } менше або набагато менше розміру алфавіту джерела A{ х_i }.

Кодування повідомлень може переслідувати різні цілі. Наприклад, це кодування з метою засекречування переданої інформації. При цьому елементарним повідомленням х_i з алфавіту A{ х_i } ставляться у відповідність послідовності, наприклад, цифр або букв зі спеціальних кодових таблиць, відомих лише відправникові й одержувачеві інформації.

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

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

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

Перш ніж перейти до питання ефективного кодування, коротко пояснимо суть самої процедури кодування.

Будь-яке дискретне повідомлення х_i з алфавіту джерела A{ x_i } обсягом у K символів можна закодувати послідовністю відповідним чином обраних кодових символів а_j з алфавіту { а_j }.

Наприклад, будь-яке число (а x_i можна вважати числом) можна записати в заданій позиційній системі числення в такий спосіб:

x_i = M = a_n1m ^n-1 + a_n-2m ^n-2 +…+a₀m⁰, (2.1)

де m - основа системи числення; a₀ … a_n-1 - коефіцієнти при степенях m; а  0, m - 1.

Нехай, наприклад, значення х_i = M = 59 , тоді його код по основі m = 8, буде мати вигляд

M = 59 = 7·8¹ + 3·8⁰ =73₈.

Код того ж числа, але по основі m = 4 буде виглядати в такий спосіб:

M = 59 = 34² + 24¹+ 34⁰ = 323₄

Нарешті, якщо основа коду m = 2, то

M = 59 = 12⁵ + 12⁴ + 12³ + 02² + 12¹ + 12⁰ = 111011₂.

Таким чином, числа 73, 323 і 111011 можна вважати, відповідно, вісімковим, четвірковим і двійковим кодами числа M = 59.

В принципі основа коду може бути будь-якою, однак найбільше поширення одержали дввійкові коди, або коди з основою 2, для яких розмір алфавіту кодових символів { а_j } дорівнює двом, а_j  0,1. Двійкові, тобто коди, що містять тільки нулі й одиниці, дуже просто формуються і передаються по каналах зв'язку і, головне, є внутрішньою мовою цифрових ЕОМ, тобто без усяких перетворень можуть оброблятися цифровими засобами. Тому, коли мова йде про кодування і коди, найчастіше мають на увазі саме двійкові коди. Надалі будемо розглядати в основному двійкові кодування.