Лекція 06. Сучасні методи стискання без втрат інформації
Курс “Теорія інформації та кодування”

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

Огляд методів стискання без втрат
Словникові методи стискання. Сімейство алгоритмів LZ*
Сортувальний метод стискання
Спеціалізовані методи стискання звуку без втрат

6.1 Огляд методів стискання без втрат

Підходи сучаних методів стискання
При тому, що статистичне стискання теоретично здатне наблизити код повідомлення до мінімального можливого обсягу, цей метод не враховує суттєвих обмежень практики, зокрема обмеженості обчислювальних ресурсів (і відповідно — швидкості виконання) та обмеженості потрібної комп'ютерної пам'яті. Отже, практичні методи, які широко застосовуються в сфері IT, досить суттєво відрізняються від суто теоретичної схеми. Основні риси підходів практики пояснює зокрема рис.6.1.

Рисунок 6.1 Огляд практичних сучасних підходів до стискання без втрат

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

Врахування закономірностей контексту є найбільш важливою особливістю сучасних методів стискання. Типовим в цьому плані є врахування сталих сполучень знаків (наприклад, слів текста). Їх можна компактно кодувати як цільні об'єкти. Другий напрямок — врахування закономірної близькості сусідніх елементів повідомлення (наприклад, амплітуд семплів). Тут економічним виявляється кодування різниці між такими елементами. Врахування закономірностей змін сусідніх знаків (наприклад, зростання або спадання звукових амплітуд) дозволяє прогнозувати наступні значення. В цьому разі можна компактно кодувати саме різниці між прогнозними та фактичними значеннями.

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

Сфера використання визначає два великих класа методів: універсальні (які придатні для широкого кола повідомлень) та спеціалізовані (які використвуються в досить вузьких сегментах). До першої категорії належать методи стискання, що використовуються в сучасних архіваторах. Вони можуть застосовуватись для будь-яких типів повідомлень. Друга категорія включає методи, що відображують специфіку певних типів повідомлень. Наприклад, для звуку та відео важливою додатковою вимогою до стиснених повідомлень є можливість «прокрутки», що виключає обробку повідомлення як цілого. Далі ми розглянемо обидва названі напрямки, але найбільшу увагу приділемо саме універсальним методам стискання, які використовуються найширше.

Огляд універсальних комплексних методів стискання
У сучасній практиці використовується кілька принципово різних підходів до контекстного стискання і, відповідно, до формування універсальних комплексних методів (рис.6.2):

Рисунок 6.2 Властивості основних універсальних методів стискання

- «словниковий» метод набув найбільшого поширення. Він заснований на заміні ланцюжків знаків (наприклад, слів), що раніше зустрічалися в тесті, короткими посиланнями на їх попередників (ми згадували даний підхід вище). Для пошуку повторюваних ланцюжків виконуються так звані «словники», що містять уже оброблену частину повідомлення. Статистичне стиснення тут виконується для числових параметрів посилань. Існує різноманітність способів пошуку ланцюжків, які застосовуються в численних версіях методу. Але всі ці версії зазвичай мають в своїх назвах префікс LZ на честь винахідників методу Лемпеля та Зіва;

- «сортувальний» метод, передбачає обробку блоків даних повідомлення.
Завдяки спеціальному перетворенню, запропонованому Барроузом і Уиллером (Burrows-Wheeler transform - BWT), всі однакові знаки, які зустрілися в різних позиціях блоку, збираються в однорідні ланцюжки. В подальшому використовується статистичне стиснення за Хафманом. Останнє виявляється найбільш ефективним, якщо попередньо застосувати перетворення MTF (move-to-front, рух до початку), в результаті якого частіше використовувані знаки отримують менші номери;

- «прогнозний» метод ми уже розглядали в попередній лекції. Нагадаємо, що тут на етапі контекстного аналізу виявляються повторювані сполучення знаків різної «глибини» та ведеться підрахунок частот їх появи. Для ефективного статистичного стиснення виконується прогнозування появи наступних знаків з урахуванням накопиченої статистики та регулярна корекція таблиці кодування за Хаффменом. Метод зазвичай позначають абревіатурою PPM - Prediction by Partial Matching - прогноз щодо часткового збігу.

Щодо показників ефективності стискання ці напрямки характеризуються наступним: «словниковий» метод є найбільш швидким при поміркованих показниках щільності та вимогливості до пам'яті; «прогнозний», напроти, забезпечує високу щільність, але є відносно повільним; «сортувальний» метод дає проміжні значення за всіма показниками.
Надалі ми детально розглянемо всі згадані тут методи.

Контрольні запитання
1) Чому методи статистичного кодування, які розглянуті рані, не задовольняють повністю постреби практики стискання повідомлень.
2) Назвіть основні практичні критерії ефективності методів стискання без втрат.
3) Наведіть приклади закономірностей контексту повідомлень, які створюють умови для додаткового стискання.
4) В чому полягає суть двох-етапного підходу, який реалізується в комплексних методах стискання.
5) Поясніть особливості універсальних та спеціалізованих методів стискання. Чому наприклад для звуку та відео використання універсальних методів може бути недостатнім.
6) Спираючись на рис.6.2, поясніть основні особливості трьох основних напрямків створення універсальних методів стискання без втрат.


6.2 Словникові методи стискання. Сімейство алгоритмів LZ*

Спосіб «вікна, що ковзає»
Найбільшого поширення набув спосіб, де словник являє собою «вікно», що переміщається текстом повідомлення (рис.6.3). При цьому:

Рисунок 6.3 Схема стискання із «словиком, що ковзає»

- Словник заповнюється в міру обробки повідомлення. Це схоже на переміщення рамки, яка рухається від початку тексту до його кінця і всередину якої потрапляють кілька тисяч знаків (обсяг кількох сторінок книги). Пошук повторюваних ланцюжків ведеться тільки всередині рамки (Словника) і знаки, які опинилися за її лівою межою "забуваються". На початку рамки (біля правої межі) є вузький "проріз" (так званий "Буфер") для знаків, чиї коди підлягають стисненню (зазвичай їх число не велика - наприклад, від 16 до 64);

- Кодер вибирає ланцюжок знаків із Буфера і намагається знайти такий самий в словнику. Якщо це вдається, то зміст Буфера можна замінити коротким посиланням на фрагмент Словника. Інакше Кодер поступово скорочує шуканий ланцюжок і повторює процедуру. Якщо навіть короткі ланцюжки в Словнику не знайдені, Кодер передає цю частину повідомлення по окремим знакам. У будь-якому випадку всі оброблені знаки поповнюють словник, одночасно відтіль видаляються знаки «застарілі». Зі збільшенням обсягу словника зростає ймовірність знаходження співпадаючих ланцюжків, однак при цьому час пошуку швидко збільшується;

- стиснений код повідомлення поміщається в архівний файл. Він включає коди посилань на знайдені ланцюжки в словнику. Таке посилання формату [d,l] включає номер першого знака d (distance) і довжину ланцюжка l (length). До словника також потрапляють стандартні коди знаків для випадків, коли ланцюжки в словнику не виявлялися. Щоб розрізняти ці два типи кодів, їх передує двійковий префікс (0 для коду знака і 1 для коду ланцюжка). Наприклад, якщо обсяг буфера становить 32 знака, то l = log232 = 5 біт, а при обсязі словника 1024 знака d = log21024 = 10 біт. Разом з двійковим префіксом довжина коду ланцюжка складе 10+5+1 = 16 біт. При цьому довжина коду знака з урахуванням префікса складе 8 + 1 = 9 біт.

Приклад стиснення способом "вікна, що ковзає"
Розглянемо приклад стиснення фрази «коси косой, косой Косой», в якій очевидно присутні повторювані ланцюжки знаків (рис.6.4). При цьому:

Рисунок 6.4 Приклад стискання способом "вікна, що ковзає"

- для перших п'яти знаків в словнику (кроки 1-5) не знаходиться відповідних ланцюжків і вони передаються окремо (за рахунок використання бітових ознак на цьому етапі ми програємо в обсязі коду);

- далі в словнику знаходиться ланцюжок "кіс", якій відповідає посилання [1,3] (починаючи з першого знака в словнику - довжина 3 знаки) - крок 6. Виходячи із довжини буфера і словника довжина коду ланцюжка складе 3+4+1 = 8 біт. Наступні 3 знаки передаються окремо (кроки 7-9);

- кроки 10-12 - передача коду довгого ланцюжка з 6 знаків, а потім 2 окремих знаків. Нарешті, крок 13 - передача коду ланцюжка з 4 знаків. На цьому етапі ми отримуємо найбільш істотний ефект зі стиснення;

- в цілому довжина стиснутого коду в прикладі становить 66% від початкової. Звернемо увагу, що помітних втрат в ефективності пов'язані з початковим заповненням словника. У прикладі значимість цього етапу дещо перебільшена, оскільки розглядаєтьс короткий текст. В середньому ступінь стиснення тексту словниковим методом становить зазвичай 40-60%.

Спосіб «прямої адресації ланцюжків»
Значне уповільнення стискання при великих обсягах словника для способу "ковзного вікна" спонукало використовувати альтернативний спосіб організації словника, який характеризується меншим часом пошуку (рис.6.5):

Рисунок 6.5 Схема стискання із «прямою адресацією ланцюжків»

- Cловник являє собою не довгу однорідну послідовність, а таблицю, кожен рядок якої містить ланцюжок знаків. При цьому двійковий номер рядка і є кододом такого ланцюжка. Спочатку таблиця містить стандартний набір знаків з однобайтном кодами. Надалі вона доповнюється ланцюжками знаків, що з'являються. Зміст таблиці охоплює всю оброблену частину повідомлення. Щоб обмежити її обсяг, видаляються рядки, які рідко використовуються;

- Кодер шукає в таблиці словника рядки з ланцюжками знаків, що з'являються в буфері. Такий пошук значно швидше, ніж пошук в «лінійній» послідовності, і мало залежить від довжини словника. До знайденого ланцюжка кодер додає наступний знак із повідомлення і заводить для доповненого варіанта новий рядок, доповнюючи словник. Слабкістю даного методу є повільне заповнення словника, оскільки нові ланцюжки кожен раз збільшуються лише на один знак;

- стислий код містить номери рядків словника, які є посиланнями на ланцюжки знаків. При цьому для одиночних символів такі коди є однобайтними, а для ланцюжків вони збільшуються в міру зростання їх довжини, проте їх зростання є досить повільним (наприклад, рядок з номером 2000 матиме довжину всього 11 біт).

Приклад способу «прямої адресації ланцюжків»
Приклад стиснення ілюструє ріс.6.6. Зокрема тут:

Рисунок 6.6 Приклад стискання способом «прямої адресації ланцюжків»

- перші п'ять знаків (кроки 1-5) зберігаються у вигляді стандартних кодів, в той же час в словнику зберігаються перші короткі двохзнакові ланцюжки, яким привласнюються номери, наступні за ємністю байта;

- на кроці 6 вперше з'являється можливість використовувати ланцюжок знаків зі словника. При цьому в словник поміщається його доповнений варіант. Надалі збереження окремих знаків (кроки 7-11, 14, 15, 17) чергується зі збереженням посилань на ланцюжки (кроки 12, 13, 16);

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

Огляд реалізацій словникового стиснення
Показова і досить цікава історія розвитку словникового методу (рис.6.7):

Рисунок 6.7 Порівняння напрямків розвитку словникового стискання

- первісна реалізація методу була розроблена близько 50 років тому Лемпелем і Зивом: спочатку в варіанті зі змінним словником (алгоритм LZ77), а потім - із прямою адресацією ланцюжків (алгоритм LZ78). В обох випадках це були теоретичні роботи, в яких не розглядалися проблеми ефективності (за швидкістю і потрібною пам'яттю). Цікаво, що для LZ78 була показана збіжність середньої довжини коду до ентропії, але лише для дуже довгих повідомлень. Надалі обидві гілки розвивалися в напрямку практичної оптимізації;

- практичні алгоритми, пристосовані для програмної реалізації, були запропоновані Сторером і Шиманьскі (LZSS), а також Велчем (LZW). У наведеному вище описі ми спиралися саме на ці алгоритми. Надалі вони стали основою подальших розробок, які вже займалися оптимізацією за окремими показниками ефективності;

- для напрямку "ковзного словника" можна навести приклади удосконалень на базі LZSS. Зокрема, алгоритм LZM оптимізований по швидкості (за рахунок використання де це можливо швидкого стиснення RLE) і дещо програє в стисненні. Алгритм LZH, навпаки, збільшує щільність шляхом стиснення по Хаффмену посилань, але при цьому він помітно повільніше;

- для напряму «прямої адресації ланцюжків» на основі LZW був створений покращений за швидкістю алгоритм LZC (в основному за рахунок оптимізації програмної реалізації). Пізніше на його базі реалізований алгоритм LZMV, в якому за рахунок прискорення зростання довжини ланцюжків в словнику поліпшена щільність стиснення;

- в цілому існує велика різноманітність алгоритмів сімейства LZ. Кожен з них має свої особливості і переваги (огляди наведені, зокрема, в [...]).

Особливості сучасного алгоритму LZMA (архіватор 7-Zip)
Як приклад вдалого сучасного рішення можна привести алгоритм LZMA (Lempel-Ziv-Markov Algorithm), реалізований в архіваторі 7-Zip, з яким ми познайомимося в лабораторній роботі (ріс.6.8). До його особливостей належать, зокрема:

Рисунок 6.8 Характеристика удосконаленого словникового алгоритму LZMA

- використання попереднього «різницевого» кодування для вхідного потоку знаків. Потік вихідних кодів знаків перетворюється в їх різниці. При цьому набір використовуваних значень і необхідна розрядність значно скорочуються. Наприклад, для тексту різницю кодів букв не перевищує 5 біт, а для чисел - 4 біт. Тим часом, при вихідному кодуванні в Unicode для кожного знака потрібно 16 біт;

- вдосконалена біт-орієнтована модель стислих даних, яка дозволяє більш економічно кодувати посилання. Зокрема, тут використовується гнучкий змінний формат посилання, вибір якого залежить від контексту;

- застосування арифметичного кодування замість кодування Хаффмена для додаткового статистичного стиснення вихідного потоку даних;

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

Алгоритм LZMA наочно демонструє, наскільки важливою є «тонка» оптимизація програмної реалізації методу. В даний час він є однією з найбільш ефективних і популярних реалізацій словникового підходу до стиснення.

Контрольні запитання
1) Поясніть принцип стиснення зі «словником, що ковзає», спираючись на рис.6.3.
* 2) Прокоментуйте приклад стиснення із «словником, що ковзає», спираючись на рис.6.4.
3) Поясніть принцип стиснення з «прямою адресацією ланцюжків», спираючись на рис.6.5.
* 4) Прокоментуйте приклад стиснення з «прямою адресацією ланцюжків», спираючись на ріс.6.6.
5) Охарактеризуйте напрямки і етапи розвитку словникових методів, використовуючи рис.6.7.
* 6) Розкажіть про основні особливості алгоритму LZMA, спираючись на ріс.6.8.

6.3 Сортувальний метод стискання

Опис підходу
Сортувальний метод передбачає перетворення контексту в форму, найбільш зручну для статистичного стиснення. Таке перетворення виконується в рамках окремих блоків повідомлення. Однією з найбільш популярних реалізацій методу є алгоритм bzip2, структуру якого характеризує (ріс.6.9):

Рисунок 6.9 Схема сортувального стискання

- на першому етапі в потоці даних повідомлення виділяються блоки знаків (довжиною порядку сотні знаків) і виконуєтьсь перетворення по Барроузу-Вілеру. В результаті однакові знаки, які були розосереджені по всьому блоку, групуються в однорідні ланцюжки;

- на другому етапі по відношенню до результатів попереднього може виконуватися перетворення MTF (move-to-front), яке ще називають сортуванням за методом «стопки книг». Тут часто вживані знаки отримують менші номери. До того ж всі знаки однорідної ланцюжка крім першого замінюються нулями. В результаті в блоці утворюється велика кількість однакових знаків (нулів), що дуже зручно для статистичного стиснення. Альтернативою MTF в інших реалізаціях методу може бути стиснення однорідних ланцюжків знаків за алгоритмом RLE;

- нарешті, на останньому етапі виконується статистичне стискання - наприклад, за методом Хаффмана.

Приклад виконання перетворення Барроуза-Віллера
Приклад виконання BWT показаний на рисунку 6.10.

Рисунок 6.10 Приклад виконання перетворення Барроуза-Віллера

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

Як видно в прикладі, тут виділяються повторювані елементи тексту: за буквою "У" часто слідують "-K", за "-" повторюються "КУ", а слідом за "K" - поєднання "У-". В результаті перетворення знаки "У", "-" і "K" зосереджуються в однорідні ланцюжки. Зрозуміло, в реальних повідомленнях різноманітність знаків в блоках набагато вище, однак і самі блоки зазвичай включають сотні знаків, так що ефект від перегрупування є істотним. Ще раз підкреслимо, що цей ефект тим більший, чим частіше зустрічаються повторювані групи символів.
Найважливішою особливістю BWT є його оборотність. Повний опис алгоритму відновлення є досить громіздким, так що ми обмежимося посиланням на [...], де цей підхід описаний докладно.

Приклад виконання перетворення MTF
На рис.6.11 показано виконання MTF для результатів попереднього етапу.

Рисунок 6.11 Приклад застосування перетворення MTF в сортувальному стисканні

- спочатку всі знаки отримують вихідні номери (в нашому прикладі для наочності використовуємо номери тільки чотирьох наявних в блоці знаків);

- при появі чергового знаку він кодується своїм поточним номером в алфавіті (в прикладі буква «У» замінюється на 3). Після цього його номер стає мінімальним, а коди всіх інших знаків збільшуються на «1» (наступні літери «У» кодуються як «0», а знак «-» при першій появі буде мати номер «1». Надалі ця процедура повторюється до кінця блоку).

Як видно, в результаті такого перетворення неоднорідність розподілу ймовірностей знаків суттєво зросла (перш за все за рахунок частого використання «0»). В результаті статистичне кодування по Хаффмену дає більше стиснення, ніж до застосування MTF.

Контрольні питання
1) Опишіть етапність сортувального стиснення в рамках алгоритму bzip2, спираючись на ріс.6.9.
2) Охарактеризуйте дію перетворення Барроуза-Віллера на блок даних, спираючись на приклад ріс.6.10.
3) Які саме дані необхідні для відновлення початкового вигляду блоку за допомогою перетворення Барроуза-Уиллера.
4) Опишіть виконання перетворення MTF, спираючись на ріс.6.11. Чому саме середня довжина коду при кодуванні по Хаффмену значно зменшується в результаті використання MTF.


6.4 Спеціалізовані методи стискання звуку без втрат

Підходи до стискання звуку без втрат
Як ми вже знаємо, оцифрований звук являє собою послідовність двійковій-кодованих чисел - значень амплітуд. При цьому важливими ресурсами стиснення є відносна плавність і передбачуваність зміни таких амплітуд, а також взаємозалежності їх значень для різних стереоканалов (рис.6.12):

Рисунок 6.12 Напрямки стискання звуку без втрат

- в силу плавності зміни амплітуд звуку різниці між їх сусідніми значеннями зазвичай значно менше, ніж самі вихідні амплітуди. Це означає, що кодування таких різниць (його також називають диференціальним або дельта-кодуванням) може бути більш компактним. У сучасній практиці різницевий принцип широко використовується для кодування звуку на двох стереоканалах. Зокрема, в стандартному режимі MS-Stereo замість двох значень амплітуд лівого і правого каналів (Li, Ri) зберігають Mi = (Li+Ri)/2, Si = (Li-Ri)/2, де величина Si в силу відносної малості може кодуватися економічно. Перед відтворенням значення Li і Ri відновлюються;

- розвитком разностного підходу є економічне кодування відхилення звукових амплітуд від їх прогнозних значень. В силу плавності зміни звукових амплітуд наступне значення, наприклад Mi може прогнозуватися за кількома попереднім значенням Mi-k (де k = 1, 2, ... n). Для прогнозування зазвичай використовується апроксимація поліномом. Зрозуміло, фактичне значення звукової амплітуди Mi буде часто буде відрізнятися від прогнозного Mi *. Саме така відмінність ΔMi і зберігається у вигляді компактного коду. Відзначимо, що такий спосіб називають ще адаптивним диференціальним кодуванням;

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

Використання коду Райса при стиканні звуку
Код Райса, який застосовується для компактного представлення малих чисел при кодуванні звуку, характеризується такими особливостями (ріс.6.13):

Рисунок 6.13 Механізм та приклади кодування за Райсом

- будь-яке число x може бути представлено у вигляді x = q * 2k + r, де r - залишок від ділення x на 22k, де значення k заздалегідь задано. Наприклад, при k = 4 число 45 = 2*24 + 13, 58 = 3 * 24 + 10, а 7 = 0 * 24 + 7. У такому поданні явно виділяються дві частини: перший параметр q "грубо" задає порядок числа (в нашому випадку з точністю до 24 = 16), а другий параметр r визначає його точне значення;

- код числа х будується за наступною схемою. Першими йдуть нулі, кількістю в q штук (наприклад, при x = 45 це [00]). Потім справа до нулях додається маркувальний біт [1], який вказує на кордон першої частини коду. Друга частина включає залишок r c з фіксованою довжиною в k біт (в разі x = 45 [1 101]). Таким чином код Райса для числа 45 буде мати вигляд [0011101], а для 58 - [00011010], а для 7 - [11010];

- як видно, довжина коду виходить змінної і убуває для менших значень x. При цьому умова префіксних (виділення меж кодових ланцюжків в загальному потоці бітів) призводить до додаткових накладних витрат. Так, мінімальна довжина двійкового коду для чисел 45, 58 і 7 становить відповідно 6, 6 і 3 розряду, а для коду Райса - 7, 8 і 5. Проте саме для малих значень x, які частіше зустрічаються для диференціального і особливо для адаптивного прогнозного кодування, такий код є ефективним;

- звернемо увагу, що при кодуванні по Райсу значення параметра k є заданим. При цьому його збільшення призводить до скорочення довжини першої половини коду і одночасно до зростання другої половини. Це може бути доцільний, якщо відносно часто з'являються великі значення x. Наприклад, для x = 100 при k = 4 число представляється як x = 6 * 24 + 4 (код [00000010100] - 11 розрядів), а при k = 5 - як x = 3 * 25 + 4 (код [000100100] - 9 розрядів). З іншого боку для x = 7 при k = 5 довжина коду в порівнянні з k = 4 збільшиться на один розряд - [101010] замість [11010]. На практиці вибір параметра k виконується програмою-кодером автоматично за результатами оцінки характеристик кодованого звуку.

Контрольні запитання
1) Які закономірності звукових даних використовуються для їх стиснення без втрат.
2) Поясніть принцип різницевого кодування для випадку послідовності амплітуд і для кодування стереоканалів.
3) Поясніть принцип адаптивного прогнозного методу стиснення звукових даних.
4) Поясніть алгоритм Райса економічного кодування різниць при стисненні звуку.
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2019 • Теория информации и кодирования
UP