Код поступового відмови l; інший усічений двійковий код Connect - Diamond Editions
Коди поступового відмови походять від кодів поступового введення, які були запропоновані мені в 2003 році Стівеном Пайдженом [1], автор дисертації (французькою мовою) про двійкове кодування [2] (див., зокрема, розділ 5.3.4.2 “Коди введення”). Вони вирішують невелику проблему, з якою стикаються при використанні класичних двійкових кодів: коли ви знаєте межу, яку може приймати число, до половини кодів може бути невикористано. Малюнок 1 показує, що в середньому втрачається чверть простору кодування, що становить до половини біта на число.
Рис. 1: Невикористаний простір кодування в класичному двійковому кодуванні представлений білими трикутниками.
1. Деякі орієнтири
Щоб встановити контекст, давайте спочатку уточнимо, що ми хочемо створити потік даних, який у нашому випадку представляє дискретизовані сигнали, такі як звуки або зображення. Кожен зразок перетворюється у послідовність бітів, яка потім буде об'єднана в двійковий потік, щоб бути записаною у файл або переданою.
Спорт тут полягає у зменшенні загального розміру, який займає цей бітовий потік, без втрати будь-якої інформації: кожне закодоване число повинно давати однаковий результат після декодування. Існує багато методів з більш-менш складною обробкою, але тут ми розглянемо, що кожне число, яке кодується (зване n), не залежить від сусідів. Таким чином, ми обробляємо кожну вибірку, не турбуючись про попередню чи наступну, що робить n дещо абстрактним числом, але для цілей експерименту це завжди ціле число, більше або рівне нулю.
Де експеримент починає ставати цікавим, полягає в тому, що для декодування бітів нашого числа n потрібно так чи інакше знати заздалегідь допоміжну інформацію: межа (називається L), яка вказує, яке максимальне значення може прийняти наше число n. Тому ми можемо записати таке рівняння:
Мистецтво ентропіста (чи ентрополога?) Полягає у тому, щоб передати цю межу, не займаючи більше місця, ніж оригінал, але ця стаття зосереджена на тому, як ці два значення n та L можуть поєднуватися, так що n просто використовувати ідеал кількість бітів.
Класичний двійковий код використовує k бітів для представлення числа від 0 до 2 k -1. Наприклад, з k = 4, ми можемо представити 24 = 16 символів, які найчастіше асоціюються з числами від 0 до 15. Якщо наше обмеження становить 15, тоді наше число n буде використовувати 4 біти, ні більше, ні менше. Як загальне правило, якщо межа L дорівнює 2 k -1, тоді використовується k біт. І навпаки, коли ми знаємо L, тоді ми можемо розрахувати кількість бітів k = log2 (L) .
Але межа, рівно дорівнює степеню двох, є досить рідкісним випадком. Здебільшого наша межа L буде між двома степенями двох: 2k -1k. Потім ми повинні завжди виділяти k біт, але залишатимуться 2 k -L невикористаних кодів, коди, які займуть віртуальний простір, частка біта, яка в кінцевому підсумку зважує всі дані. Цей втрачений простір кодування представлений білими трикутниками на малюнку 1, оскільки біт не ділиться.
Існують методи, близькі до ідеалу, такі як арифметичні коди [3] та інтервальне кодування [4] з яким знайдено символ, змішаний з попередніми, що звільняє числа від довільного обмеження окремих бітів. Недоліком є те, що цей тип коду є відносно складним і складним у реалізації. Зокрема, арифметичні коди виконують обчислення цілих чисел із множеннями, що займає значні матеріальні ресурси у випадку матеріальної реалізації. І оскільки я розробляю КОДЕК, призначений використовувати якомога менше логічних входів, такий тип підходу виключається.
Іншим популярним класом двійкових кодів, які не потребують множення, є коди Хаффмана (див. Вікіпедію). Вони також здатні управляти складними ймовірностями за допомогою таблиці, яку потрібно зберігати та будувати. Отже, щоб використовувати класичний код Хаффмана, спочатку потрібно зібрати, закодувати та реконструювати статистику та гістограми, перш ніж ви навіть зможете почати передавати корисні дані. В іншому випадку існують також адаптивні або динамічні коди Хаффмана.
Тут ми дослідимо поступові коди, які іноді також називають усіченими двійковими кодами: це особливий випадок кодів Хаффмана, на півдорозі між арифметичними кодами та класичними двійковими кодами. Як і коди Хаффмана, поступові коди не змішуються між послідовними словами, тому кожне двійкове слово завжди залишається досить чітким. Щоб зменшити розмір, числа представляються у вигляді бітового рядка змінної довжини, тоді як довжина фіксується у звичайному двійковому кодуванні.
Простота - це і перевага, і недолік. Кодування не є оптимальним, оскільки воно не моделює ймовірності, тому передбачається, що всі числа однаково ймовірні. Натомість алгоритм не вимагає управління таблицями в пам'яті, які є джерелом складності, затримки та помилок. Поступове кодування використовує лише кілька додань або віднімань, що обіцяє прості і дуже швидкі досягнення як в програмному, так і в апаратному забезпеченні.
На малюнку 2 показано різницю в поведінці із звичайним двійковим кодом. Більше не відбувається різких змін розміру коду залежно від межі, навпаки, довжина слова змінюється лінійно, слідуючи по діагоналі, що дозволяє уникнути будь-якого безладу в коді.
Рис. 2: Використання бітів та прогресивного розміру слів із запрограмованим кодом.
Як видно на малюнку 2, коди, що відповідають числу, поділяються на дві області, залежно від межі:
- половина кодів використовує k біт;
- друга половина використовує біти k-1.
Ці дві половини (які не обов'язково мають однаковий розмір) розділені значенням, яке називається тут стрижнем, що дозволяє вирішити, чи можна двійковий код n скоротити на один біт. На малюнку 2 стержні - це паралельні діагональні лінії, які розділяють дві сусідні сірі області.
Таким чином, у гіршому випадку коди введення не збільшують кількість використовуваних бітів. У кращому випадку зберігається один біт. На практиці виграш не є величезним, але оскільки немає ризику марно витрачати простір, а оскільки відповідний алгоритм дуже простий, його можна без ризику додати до системи стиснення. За цілий блок даних накопичені таким чином частки бітів накопичуються і можуть докласти приблизно (залежно від даних) декількох відсотків від загального розміру файлу, докладаючи невеликих зусиль, тому це завжди вітається.
Як і всі коди, їх не можна використовувати поодинці, їм потрібен контекст, тобто допоміжна інформація, що дозволяє їх декодування. Вони в ідеалі є частиною такого алгоритму, як 3R (представлений в [5] [6] [7]) та будь-яка система, що використовує цілі додатні числа, межі яких відомі неявно або явно.
Ідея поступового введення кодів, схоже, викристалізувалася приблизно в 1995 році, в той час, коли статті, розкопані Стівеном Голубом ([2] стор.104):
[Автори] Ачар'я та Я Я [8] [9] посилання на коди поступового введення під назвою коди економіки. Це одне з удосконалень, які вони пропонують щодо кодування індексів в алгоритмі стиснення LZW.
Документація щодо кодів поступового та рекурсивного введення, крім статей Ачар'ї та Я Я, є переважно анекдотичною.
Отже, це робить три назви для однієї і тієї ж техніки: метод поступового кодування Вікіпедією також називає "усічений двійковий код" [10], але ми будемо використовувати терміни поступового та поступового відмови, оскільки вони дозволяють виділити конкретний підметод.
2. Чисельний приклад
Для кодування та декодування чисел алгоритм повинен спочатку обчислити опорну точку, а потім встановлене значення коду. Просто потрібно трохи лінійної арифметики. Нічого дуже складного, як ми побачимо на простому прикладі, коли кодируємо числа від 0 до 10.
Число 10 представлене у двійковому вигляді 1010, тому потрібні чотири біти. Однак 4 біти дозволяють кодувати числа від 0 до 15, а числа від 11 до 15 не використовуються, що є втратою 5 кодів або майже третиною простору кодування. З іншого боку, 3 біти дозволяють представляти лише 8 кодів (від 0 до 7), чого недостатньо. Ось класична таблиця двійкового кодування: