риклад виконання завдання

риклад виконання завдання

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

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

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

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

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

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

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

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

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

p(b1)+p(b2)+p(b3)=0,3+0,3+0,4=1.

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

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

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

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

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

p(a1)+p(a2)+p(a3)=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.

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

.

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

при i=1;

при i =2;

при i=3.

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

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

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

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

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

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

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

становитиме

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

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

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


ЛАБОРАТОРНА РОБОТА №3

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

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

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

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

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

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

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

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



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

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

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

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

xi = M = an-1×m n-1 + an-2×m n-2 +…+a0×m0, (2.1)

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

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

M = 59 = 7·81 + 3·80 =738.

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

M = 59 = 3×42 + 2×41+ 3×40 = 3234

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

M = 59 = 1×25 + 1×24 + 1×23 + 0×22 + 1×21 + 1×20 = 1110112.

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

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

3.1.2 Способи представлення кодів

Найпростішим способом представлення або завдання кодів є кодові таблиці, що ставлять у відповідність риклад виконання завдання повідомленням хi відповідні їм коди (таблиця 3.1).

Таблиця 3.1 – Кодова таблиця для алфавіту з 8 символів кирилиці

Буква хi Число хi Код з основою 10 Код з основою 4 Код з основою 2
А
Б
У
Г
Д
Е
Ж
З

Іншим наочним і зручним способом опису кодів є їхнє представлення у виді кодового дерева (рисунок 3.1).

Для того, щоб побудувати кодове дерево для даного коду, починаючи з деякої точки - кореня кодового дерева - проводяться галузі - 0 або 1. На вершинах кодового дерева знаходяться букви алфавіту джерела, причому кожній букві відповідають своя вершина і свій шлях від кореня до вершини. Наприклад, букві А відповідає код 000, букві В – 010, букві Е риклад виконання завдання – 101 і т.д.

Корінь 0 1 0 1 0 1 1 0 1 0 1 0 1 0 А Б В Г Д Е Ж З 1 2 3 4 5 6 7 8 Рис. 4.

Рисунок 3.1 – Кодове дерево для алфавіту з 8 символів кирилиці

Код, отриманий з використанням кодового дерева, зображеного на рис.1, є рівномірним трьохрозрядним кодом.

Рівномірні коди дуже широко використовуються в силу своєї простоти і зручності процедур кодування-декодування: кожній букві – однакове число біт; прийняв задане число біт – шукай у кодовій таблиці відповідну букву.

3.1.3 Нерівномірні коди

Поряд з рівномірними кодами можуть застосовуватися і нерівномірні коди, коли кожна буква з алфавіту джерела кодується різним числом символів, приміром, А - 10, Б – 110, У – 1110 і т.д.

Кодове дерево для нерівномірного кодування може виглядати, наприклад, так риклад виконання завдання, як показано на рисунку 3.2.

При використанні цього коду буква А буде кодуватися, як 1, Б - як 0, У – як 11 і т.д. Однак можна помітити, що, закодувавши, приміром, текст АББА = 1001 , ми не зможемо його однозначно декодировать, оскільки такий же код дають фрази: ЖА = 1001, АЕА = 1001 і ГД = 1001.

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

Рисунок 3.2 – Кодове дерево для нерівномірного кодування

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

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

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

Рисунок 3.3 – Кодове дерево для коду що допускає однозначне декодування

Прийом і декодування нерівномірних кодів – процедура набагато більш складна, ніж для рівномірних. При цьому ускладнюється апаратура декодування і синхронізації, оскільки надходження елементів повідомлення (букв) стає нерегулярним. Так, приміром, прийнявши перший 0, декодер повинен подивитися в кодову риклад виконання завдання таблицю і з'ясувати, якій букві відповідає прийнята послідовність. Оскільки такої букви немає, він повинен чекати приходу наступного символу. Якщо наступним символом буде 1, тоді декодування першої букви завершиться – це буде Б, якщо ж другим прийнятим символом знову буде 0, прийдеться чекати третього символу і т.д.

Розглянемо приклад кодування повідомлень хi з алфавіту обсягом K = 8 за допомогою довільного n-розрядного двікового коду.

Нехай джерело повідомлення видає деякий текст з алфавітом від А до З и однаковою імовірністю букв Р(хi ) = 1/8.

Кодуючий пристрій кодує ці букви рівномірним трьохрозрядним кодом (див. табл. 3.1).

Визначимо основні інформаційні характеристики джерела з таким алфавітом:

– ентропія джерела , ;

– надмірність риклад виконання завдання джерела ;

– середнє число символів у коді ;

– надмірність коду .

Таким чином, при кодуванні повідомлень з рівноймовірними буквами надмірність обраного (рівномірного) коду виявилася рівної нулеві.

Нехай тепер імовірності появи в тексті різних букв будуть різними (таблиця 3.2).

Таблиця 3.2 – Імовірності появи символів

А Б У Г Д Е Ж З
Ра=0.6 Рб=0.2 Рв=0.1 Рг=0.04 Рд=0.025 Ре=0.015 Рж=0.01 Рз=0.01

Ентропія джерела в цьому випадку, природно, буде меншою і складе = 1.781.

Середнє число символів на одне повідомлення при використанні того ж рівномірного трьохрозрядного коду

Надмірність коду в цьому випадку буде

,

або досить значною величиною (у середньому 4 символи з 10 не несуть ніякої інформації).


documentafkojif.html
documentafkoqsn.html
documentafkoycv.html
documentafkpfnd.html
documentafkpmxl.html
Документ риклад виконання завдання