Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Розв'язання. За частотами символів у повідомленні побудуємо приблизний закон розподілу їх ймовірностей (табл
|
|
За частотами символів у повідомленні побудуємо приблизний закон розподілу їх ймовірностей (табл. 1).
Таблиця 1
| Символ xi | A | B |
| Імовірність pi | 5/8 | 3/8 |
Побудуємо таблицю кодів за алгоритмом Хаффмена (табл. 2):
Таблиця 2
| Символ xi | A | B |
| Імовірність pi | 5/8 | 3/8 |
| Код |
Скориставшись таблицею кодів (табл. 2), закодуємо повідомлення
Code (ABAAABBA)= 01000110.
Довжина коду L (X)= 8 (бітів).
Повідомлення ABAAABBA можна розбити на 4 блоки довжиною 2 символи.
Побудуємо приблизний статистичний закон розподілу ймовірностей блоків повідомлення, розглядаючи їх як одиниці повідомлення (табл. 3).
Таблиця 3
Блок повідомлення 
| AВ | AA | BA |
| Імовірність pi | 1/2 | 1/4 | 1/4 |
Побудуємо таблицю кодівза алгоритмом Хаффмена для блоків повідомлення (табл. 4).
Таблиця 4
| Блок повідомлення
| AB | AA | BA |
| Імовірність pi | 1/2 | 1/4 | 1/4 |
| Код |
Блоковий код повідомлення
Code (ABAAABBA) = 010011.
Довжина коду L (X)= 6 (біт).
Задачі до розділу 4
1 Дискретна випадкова величина X задана таким розподілом ймовірностей: P (X = A)= 1/4, P (X=B)= 1/2, P (X=C )=1/4. Побудувати блоковий код Хаффмена 2-го порядку. Обчислити середню довжину отриманого коду.
2 Дискретна випадкова величина X задана таким розподілом ймовірностей: P (X = A)= 1/3, P (X=B)= 1/2, P (X=C)= 1/6. Побудувати код Хаффмена і блоковий код Хаффмена 2-го порядку. Обчислити середню довжину отриманих кодів.
3 Дискретна випадкова величина X задана таким розподілом ймовірностей: P (X = A)= 1/3, P (X=B)= 7/15, P (X=C)= 1/5. Побудувати блоковий код Хаффмена 2-го порядку. Обчислити середню довжину отриманого коду.
4 Для кодування двійкового джерела з імовірністю одиниці 0,4 використовується блоковий код Хаффмена. Побудувати таблиці кодів для блокових кодів Хаффмена 2-го й 3 -го порядків. Обчислити середню довжину отриманих кодів. Якою буде мінімальна середня довжина коду, необхідного для кодування цього джерела?
5 Дискретна випадкова величина X може набувати два значення A і B з такими ймовірностями: P (X = A)= 2/3, P (X=B)= 1/3. Побудувати блокові коди Хаффмена 2-го й 3-го порядків. Обчислити середню довжину кодів.
6 Закодувати повідомлення 0101110110 блоковим кодом Хаффмена 2-го порядку. Обчислити довжину коду й швидкість стиснення даних.
7 Закодувати повідомлення FFAXAXXF кодом Хаффмена і блоковим кодом Хаффмена 2-го порядку. Обчислити довжину отриманих кодів. Приблизний закон розподілу ймовірностей знайти з аналізу повідомлення.
8 Дискретна випадкова величина X задана таким розподілом ймовірностей: P (X = A)= 1/3, P (X=B)= 7/15, P (X=C)= 1/5. Закодувати повідомлення BAABCB кодом Хаффмена і блоковим кодом Хаффмена 2-го порядку. Обчислити довжину отриманих кодів.
Розділ 5 АРИФМЕТИЧНЕ КОДУВАННЯ
Алгоритми Шеннона-Фано і Хаффмена в найкращому випадку не можуть кодувати кожний символ повідомлення менш ніж одним бітом інформації. Припустимо, що в повідомленні з 0 та 1 одиниці трапляються в 10 разів частіше. Ентропія такого повідомлення (що визначає верхню границю стиснення даних) HX ≈0,469 (біт / сим) суттєво менше одиниці, тому кодування таких повідомлень оптимальними алгоритмами буде не достатньо ефективним. У таких випадках бажано використовувати алгоритми, що дозволяють кодувати символи повідомлення менш ніж 1 бітом інформації. Одним із найкращих таких алгоритмів є алгоритм арифметичного кодування.
За розподілом ймовірностей дискретної випадкової величини (далі д. в. в.) складається таблиця з пересічних в граничних точках відрізків для кожного із значень д. в. в. Об'єднання цих відрізків утворює інтервал [0; 1], а їхні довжини пропорційні ймовірностям значень д. в. в.
Алгоритм кодування полягає в побудові інтервалу, що однозначно визначає конкретну послідовність значень д. в. в. Інтервали повідомлення будуються так. Якщо є відрізок повідомлення завдовжки n-1 символів, то для побудови відрізка повідомлення завдовжки n попередній інтервал розбивається на стільки частин, скільки можливих значень має д. в. в. Для знаходження початку і кінця нового інтервалу повідомлення до початку попереднього інтервалу необхідно додати значення добутків його ширини на відповідні границі відрізка поточного нового символу з таблиці символів і їхніх інтервалів (таблиці кодера). З отриманих інтервалів вибирається той, що відповідає конкретному повідомленню завдовжки n символів.
Для побудованого таким чином інтервалу повідомлення знаходиться число, що належить цьому відрізку, як правило, це ціле число, розділене на мінімальний степінь 2. Це дійсне число і буде кодом даного повідомлення. Усі можливі коди - це числа, строго більші 0 і менші 1, тому лідируючий 0 і десяткову крапку можна не враховувати.
У міру надходження символів повідомлення його інтервал звужується, відповідно кількість розрядів, необхідна для подання інтервалу збільшується. Більш імовірні символи меншою мірою звужують інтервал, ніж менш імовірні, і, отже, додають менше розрядів до результату.
Основна відмінність арифметичного кодування від алгоритмів Шеннона-Фано і Хаффмена полягає в його неперервності, тобто відсутності необхідності блокування повідомлення. Ефективність арифметичного кодування зростає із зростанням довжини повідомлення, проте й потребує значно більших обчислювальних ресурсів. Пояснимо ідею арифметичного кодування на прикладах.
Приклад 1 Закодуємо за арифметичним алгоритмом рядок «МАТЕМАТИКА».
Алфавіт повідомлення містить такі символи: {М, А, Т, Е, И, К}. Знайдемо частоту кожного з цих символів у повідомленні і призначимо кожному з них відрізок, довжина якого визначається імовірністю відповідного символу (табл. 2.7).
Таблиця 2.7
| Символ | Імовірність | Інтервал |
| М | 0,2 | [0; 0,2) |
| А | 0,3 | [0,2; 0,5) |
| Т | 0,2 | [0,5; 0,7) |
| Е | 0,1 | [0,7; 0,8) |
| И | 0,1 | [0,8; 0,9) |
| К | 0,1 | [0,9; 1,0) |
Символи в таблиці символів і їх інтервалів можна розміщувати у будь-якому порядку: у міру їх появи в тексті, в алфавітному або за збільшенням ймовірностей - це непринципово. Результат кодування може відрізнятися, але ефект буде однаковим.
Після надходження першого символу повідомлення «М» кодер звужує початковий інтервал [0; 1) до нового [0; 0,2). Отже, після надходження першої букви результат кодування знаходитиметься в інтервалі [0; 0,2).
Наступний символ «А» кодується підінтервалом усередині інтервалу попередньої послідовності символів повідомлення, звужуючи цей інтервал до [0,04; 0,1) (верхня і нижня границі нового інтервалу знаходяться додаванням до початку попереднього інтервалу добутків його ширини на відповідні границі відрізка, що відповідає поточному символу повідомлення в таблиці кодера (табл. 2.7) ), таким чином, нижня границя інтервалу повідомлення «МА» lowi = 0 + 0,2 * 0,2 = 0,04; а верхня – highi = 0 + 0,2 * 0,5 = 0,1).
Наступний символ, що надходить на вхід кодера, - це буква «Т». Символу «Т» відповідає інтервал [0,5; 0,7) з таблиці кодера (табл. 2.7). Стосовно вже наявного інтервалу послідовності з попередніх букв повідомлення новим інтервалом буде [0,07; 0,082) (lowi = 0,04 + 0,06 * 0,5 = 0,07; highi = 0,04 + 0,06 * 0,7 = 0,082).
Послідовність інтервалів, відповідних процесу кодування повідомлення «МАТЕМАТИКА» за арифметичним алгоритмом, зручно подати у вигляді такої таблиці (табл. 2.8).
Таблиця 2.8
| Символ – інтервал | Інтервал повідомлення | Ширина інтервалу |
| М - [0; 0,2) | [0; 0,2) | 0,2 |
| А - [0,2; 0,5) | [0,04; 0,1) | 0,06 |
| Т - [0,5; 0,7) | [0,07; 0,082) | 0,012 |
| Е - [0,7; 0,8) | [0,0784; 0,0796) | 0,0012 |
| M - [0; 0,2) | [0,0784; 0,07864) | 0,00024 |
| А - [0,2; 0,5) | [0,078448; 0,07852) | 0,72 × 10-4 |
| Т -[0,5; 0,7) | [0,078484; 0,0784984) | 0,144 × 10-4 |
| И -[0,8; 0,9) | [0,07849552; 0,07849696) | 0,144 × 10-5 |
| К - [0,9; 1,0) | [0,078496816; 0,07849696) | 0,144 × 10-6 |
| А - [0,2; 0,5) | [0,0784968448; 0,078496888) | 0,432 × 10-7 |
Остаточний результат кодування повідомлення «МАТЕМАТИКА» - це дійсне число, що належить інтервалу [0,0784968448; 0,078496888). Це число знаходиться як частка від ділення цілого числа на мінімальний степінь 2 - це 
. Степінь 2 визначає розрядність коду повідомлення.
Отже, двійковий 24 - розрядний код числа 1316259 10 = = 000101000001100001011111 2 і є арифметичним кодом даного повідомлення:
Code ( МАТЕМАТИКА ) = 00010100000110000101111.
Довжина коду L(X) = 24 (біт).
Середня довжина коду 
(біт / сим).
Приклад 2 Д. в. в. може набувати два значення – 0 і 1 з ймовірностями відповідно 2/3 і 1/3. Побудуємо арифметичний код для повідомлень завдовжки 3 символи.
Коди за арифметичним алгоритмом для всіх можливих повідомлень завдовжки 3 символи для заданої д. в. в. подаються такою таблицею (табл. 2.9):
Таблиця 2.9
| Повідомлення та їх інтервали | Код | pi | |||||
| [2/3; 1) | [8/9; 1) | [26/27; 1] ' 31/32® | 1/27 | ||||
| [8/9; 26/27] ' 15/16 ® | 2/27 | ||||||
| [2/3; 8/9) | [22/27; 8/9] ' 7/8® | 2/27 | |||||
| [2/3; 22/27] ' 3/4® | 4/27 | ||||||
| [0; 2/3) | [4/9; 2/3) | [16/27; 2/3] ' 5/8® | 2/27 | ||||
| [4/9; 16/27] ' 1/2® | 4/27 | ||||||
| [0; 4/9] | [8/27; 4/9] ' 3/8® | 4/27 | |||||
| [0; 8/27] ' 1/4® | 8/27 |
Середня довжина коду 
= 
(5×1+4×2+3×2+2×4+3×2+1×4+3×4+2×8)= 
»0,8025 (біт / сим).
Наведемо процедуру кодування за арифметичним алгоритмом (у наближеному варіанті):
Set low to 0.0Set high to 1.0While there are still input symbols do get an input symbol code_range = high - low. high = low + code_range*high_range(symbol) low = low + code_range*low_range(symbol)End of Whileoutput lowДекодеру, як і кодеру, відома таблиця розподілу інтервалів символів алфавіту. Декодування арифметичного коду повідомлення здійснюється за таким алгоритмом:
Крок 1 За таблицею інтервалів символів алфавіту визначається відрізок, що містить значення поточного коду, - і за цим інтервалом з тієї самої таблиці однозначно визначається символ повідомлення. Якщо це маркер кінця повідомлення, то кінець, інакше - перехід до кроку 2.
Крок 2 Від поточного коду віднімається нижня границя його інтервалу. Різниця ділиться на довжину цього інтервалу. Отримане значення вважається новим значенням поточного коду. Перехід до кроку 1.
Приклад 3 Довжина повідомлення 10 символів, його арифметичний код 000101000001100001011111 2= 1316259 10. Символи і інтервали повідомлення наведені у табл. 2.7. Розкодуємо це повідомлення.
Дійсне число, яке належить інтервалу, що однозначно визначає закодоване повідомлення 
0,07849687. Це число є значеннямпоточного коду. З таблиці символів і інтервалів (табл. 2.7) визначається відрізок, якому належить це число, - [0; 0,2) і відповідно, що перший закодований символ – це «М».
Виключимо з результату декодування вплив тепер відомого символу «М»: для цього віднімемо від поточного коду нижню границю інтервалу розкодованого символу і розділимо отриманий результат на ширину цього інтервалу, тобто наступне значення поточного коду 
= 0,39248435. Це число належить відрізку [0,2; 0,5), що відповідає символу «А» (табл.2. 7), отже, другим символом декодованої послідовності буде «А».
Виключимо з отриманого інтервалу [0,2; 0,5) вплив букви «А». Для цього віднімемо від поточного коду нижню границю цього інтервалу і розділимо на його ширину: 
= 0,6416145. Результат належить відрізку [0,5; 0,7) символу «Т» - це черговий декодований символ і т. д., поки не декодуємо всі символи (табл. 2.10).
Таблиця 2.10
| Декодоване число | Символ на виході | Інтервал | Ширина інтервалу |
| 0,07849687 | М | [0; 0,2) | 0,2 |
| 0,39248435 | А | [0,2; 0,5) | 0,3 |
| 0,6416145 | Т | [0,5; 0,7) | 0,2 |
| 0,7080725 | Е | [0,7; 0,8) | 0,1 |
| 0,080725 | М | [0; 0,2) | 0,2 |
| 0,403625 | А | [0,2; 0,5) | 0,3 |
| 0,67875 | Т | [0,5; 0,7) | 0,2 |
| 0,89375 | И | [0,8; 0,9) | 0,1 |
| 0.9375 | К | [0,9; 1,0) | 0,1 |
| 0.375 | А | [0,2; 0,5) | 0,3 |
Наведемо процедуру декодування арифметичного коду:
get encoded number Do find symbol whose range straddles the encoded number output the symbol range = high_range(symbol)- low_range(symbol) subtract low_range(symbol) from encoded number divide encoded number by range until no more symbolsПрактична реалізація арифметичного кодування дещо складніша. По-перше, в процедурі декодування необхідно передбачити наявність ознаки кінця повідомлення. Це може бути довжина вектора даних, що потрібно стиснути, або ж спеціальний символ кінця блоку. По-друге, остаточний інтервал повідомлення стає відомим тільки після закінчення процесу кодування, проте передачу коду можна почати раніше, ніж надійде останній символ. У міру того, як інтервал повідомлення звужується, його старші розряди перестають змінюватися (табл. 2.8), і ці розряди вже можуть передаватися. Отже, передача коду здійснюється з незначною затримкою, яка не залежить від довжини повідомлення. По-третє, це питання точності представлення інтервалу, що кодує повідомлення. Кількість десяткових розрядів числа інтервалу необмежено зростає при збільшенні довжини повідомлення. Відтак, ця проблема вирішується використанням арифметики із скінченною розрядністю.
Зразки розв'язування задач до розділу 5
Приклад 1 Обчислити середні довжини кодів за алгоритмами Шеннона-Фано, Хаффмена, арифметичним для дискретної випадкової величини Х, заданої таким розподілом ймовірностей:
| X | . | |||||
| P | 0,2 | 0,1 | 0,3 | 0,25 | 0,15 |
Date: 2015-11-15; view: 501; Нарушение авторских прав