Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра ЗІ
ЗВІТ
про виконання лабораторної роботи №3
з навчальної дисципліни “ Теорія інформації та кодування ”
Арифметичне кодування
Варіант – 26
Виконав
студент групи КБ – 202
Греділь О. М.
Перевірив:
Будз І. С.
Львів 2023
Мета роботи : розглянути алгоритми побудови арифметичних кодів
Теоретичні відомості
Алгоритми Шеннона-Фано і Хаффмена в найкращому випадку не можуть кодувати кожний символ повідомлення менш ніж одним бітом інформації. Припустимо, що в повідомленні з 0 та 1 одиниці трапляються в 10 разів частіше. Ентропія такого повідомлення (що визначає верхню границю стиснення даних) HX≈0,469 (біт/сим) суттєво менше одиниці, тому кодування таких повідомлень оптимальними алгоритмами буде не достатньо ефективним. У таких випадках бажано використовувати алгоритми, що дозволяють кодувати символи повідомлення менш ніж 1 бітом інформації. Одним із найкращих таких алгоритмів є алгоритм арифметичного кодування.
За розподілом ймовірностей дискретної випадкової величини (далі д. в. в.) складається таблиця з пересічних в граничних точках відрізків для кожного із значень д. в. в. Об'єднання цих відрізків утворює інтервал [0; 1], а їхні довжини пропорційні ймовірностям значень д. в. в.
Алгоритм кодування полягає в побудові інтервалу, що однозначно визначає конкретну послідовність значень д. в. в. Інтервали повідомлення будуються так. Якщо є відрізок повідомлення завдовжки n-1 символів, то для побудови відрізка повідомлення завдовжки n попередній інтервал розбивається на стільки частин, скільки можливих значень має д. в. в. Для знаходження початку і кінця нового інтервалу повідомлення до початку попереднього інтервалу необхідно додати значення добутків його ширини на відповідні границі відрізка поточного нового символу з таблиці символів і їхніх інтервалів (таблиці кодера). З отриманих інтервалів вибирається той, що відповідає конкретному повідомленню завдовжки n символів.
Для побудованого таким чином інтервалу повідомлення знаходиться число, що належить цьому відрізку, як правило, це ціле число, розділене на мінімальний степінь 2. Це дійсне число і буде кодом даного повідомлення. Усі можливі коди - це числа, строго більші 0 і менші 1, тому лідируючий 0 і десяткову крапку можна не враховувати.
У міру надходження символів повідомлення його інтервал звужується, відповідно кількість розрядів, необхідна для подання інтервалу збільшується. Більш імовірні символи меншою мірою звужують інтервал, ніж менш імовірні, і, отже, додають менше розрядів до результату.
Основна відмінність арифметичного кодування від алгоритмів Шеннона-Фано і Хаффмена полягає в його неперервності, тобто відсутності необхідності блокування повідомлення. Ефективність арифметичного кодування зростає із зростанням довжини повідомлення, проте й потребує значно більших обчислювальних ресурсів. Пояснимо ідею арифметичного кодування на прикладах.
Хід роботи
Завдання 1
Побудувати арифметичний код для повідомлення згідно варіанту, поданого в таблиці 3. Обчислити його довжину. Закон розподілу ймовірностей символів визначити з аналізу повідомлення.
1. Згідно варіанту повідомлення створюємо таблицю символів, їх ймовірностей та інтервалів
2
. Застосовуємо алгоритм арифметичного кодування для подальшого кодування знайденого значення
3. Будуємо таблицю кінцевих значень
4. З знайдених значень вираховуємо розрядність коду та число що буде закодовано5. Кодуємо повідомлення, переводячи його з десяткової системи числення у двійкову
Завдання 2
Закодувати за арифметичнималгоритмом повідомлення BAABC дискретної випадкової величини X, заданої таким розподілом ймовірностей: P(X=A)=1/3, P(X=B)=7/15, P(X=C)=1/5. Обчислити довжину коду.
1. Згідно варіанту повідомлення створюємо таблицю символів, їх ймовірностей та інтервалів
2. Застосовуємо алгоритм арифметичного кодування для подальшого кодування знайденого значення
3
. Будуємо таблицю кінцевих значень та схему роботи кодера
4. З знайдених значень вираховуємо розрядність коду
5. Кодуємо повідомлення, переводячи його з десяткової системи числення у двійкову
Завдання 3
Побудувати арифметичний код для повідомлення AFXAFF. Обчислити його довжину. Закон розподілу ймовірностей символів визначити з аналізу повідомлення.
1. Згідно варіанту повідомлення створюємо таблицю символів, їх ймовірностей та інтервалів
2. Застосовуємо алгоритм арифметичного кодування для подальшого кодування знайденого значення
3. Будуємо таблицю кінцевих значень та схему роботи кодера
4. З знайдених значень вираховуємо розрядність коду
5. Кодуємо повідомлення, переводячи його з десяткової системи числення у двійкову
Висновок: У ході виконання цієї лабораторної роботи ми детально розглянули алгоритми побудови арифметичних кодів. Арифметичне кодування є ефективним методом кодування, який використовується для стиснення даних і базується на законі розподілу ймовірностей символів.
Ми визначили закон розподілу ймовірностей символів на основі аналізу повідомлення, що дозволило нам краще зрозуміти, як арифметичне кодування може бути оптимізовано для конкретного набору даних.
Ця робота показала, що арифметичне кодування є важливим інструментом в теорії інформації та кодування. Завдяки його здатності ефективно стискати дані без втрат, арифметичне кодування продовжує знаходити застосування в сучасних системах передачі даних.