• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Розв'язання

За частотами символів у повідомленні побудуємо приблизний закон розподілу їх ймовірностей (табл. 1).

Таблиця 1

Побудуємо таблицю кодів за алгоритмом Хаффмена (табл. 2):

Таблиця 2

Скориставшись таблицею кодів (табл. 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; 1) до нового [0; 0,2). Отже, після надходження першої букви результат кодування знаходитиметься в інтервалі [0; 0,2).

Наступний символ «А»кодується підінтервалом усередині інтервалу попередньої послідовності символів повідомлення, звужуючи цей інтервал до [0,04; 0,1) (верхня і нижня границі нового інтервалу знаходяться додаванням до початку попереднього інтервалу добутків його ширини на відповідні границі відрізка, що відповідає поточному символу повідомлення в таблиці кодера (табл. 2.7)), таким чином, нижня границя інтервалу повідомлення «МА» low_i=0+0,2*0,2=0,04; а верхня – high_i=0+0,2*0,5=0,1).

Наступний символ, що надходить на вхід кодера, - це буква «Т». Символу «Т» відповідає інтервал [0,5; 0,7) з таблиці кодера (табл. 2.7). Стосовно вже наявного інтервалу послідовності з попередніх букв повідомлення новим інтервалом буде [0,07; 0,082) (low_i=0,04+0,06*0,5=0,07; high_i=0,04+0,06*0,7=0,082).

Послідовність інтервалів, відповідних процесу кодування повідомлення «МАТЕМАТИКА» за арифметичним алгоритмом, зручно подати у вигляді такої таблиці (табл. 2.8).

Таблиця 2.8

Остаточний результат кодування повідомлення «МАТЕМАТИКА» - це дійсне число, що належить інтервалу [0,0784968448; 0,078496888). Це число знаходиться як частка від ділення цілого числа на мінімальний степінь 2 - це . Степінь 2 визначає розрядність коду повідомлення.

Отже, двійковий 24-розрядний код числа 1316259₁₀ = =000101000001100001011111₂ і є арифметичним кодом даного повідомлення:

Code(МАТЕМАТИКА)=00010100000110000101111.

Довжина коду L(X)=24 (біт).

Середня довжина коду (біт/сим).

Приклад 2 Д. в. в. може набувати два значення –0 і 1 з ймовірностями відповідно 2/3 і 1/3. Побудуємо арифметичний код для повідомлень завдовжки 3 символи.

Коди за арифметичним алгоритмом для всіх можливих повідомлень завдовжки 3 символи для заданої д. в. в. подаються такою таблицею (табл. 2.9):

Таблиця 2.9

Середня довжина коду =(5×1+4×2+3×2+2×4+3×2+1×4+3×4+2×8)=»0,8025 (біт/сим).

Наведемо процедуру кодування за арифметичним алгоритмом (у наближеному варіанті):

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

Крок 1 За таблицею інтервалів символів алфавіту визначається відрізок, що містить значення поточного коду, - і за цим інтервалом з тієї самої таблиці однозначно визначається символ повідомлення. Якщо це маркер кінця повідомлення, то кінець, інакше - перехід до кроку 2.

Крок 2 Від поточного коду віднімається нижня границя його інтервалу. Різниця ділиться на довжину цього інтервалу. Отримане значення вважається новим значенням поточного коду. Перехід до кроку 1.

Приклад 3 Довжина повідомлення 10 символів, його арифметичний код 000101000001100001011111₂= 1316259₁₀. Символи і інтервали повідомлення наведені у табл. 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

Наведемо процедуру декодування арифметичного коду:

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

Зразки розв'язування задач до розділу 5

Приклад 1Обчислити середні довжини кодів за алгоритмами Шеннона-Фано, Хаффмена, арифметичним для дискретної випадкової величини Х, заданої таким розподілом ймовірностей:

Переглядів: 1588