Розділ 1. Аналіз існуючих кодерів стиску інформаційних потоків

1.1. Розгляд основних положень теорії стиснення

Основна проблема, яку необхідно вирішити|рішати| при побудові|шикуванні| системи комунікації, була вперше|уперше| сформульована Клодом Шенноном в 1948 році:

«Головна властивість системи зв'язку полягає в тому, що вона повинна точно або наближено відтворити в певній точці простору|простір-час| і часу деяке повідомлення|сполучення|, вибране в іншій точці.

Зазвичай|звично|, це повідомлення| якийсь зміст, проте|однак| це абсолютно не має значення для рішення поставленої інженерної| задачі. Найголовніше полягає в тому, що відправлене повідомлення|сполучення| обирається з| деякого сімейства можливих повідомлень|сполучень|.»

Така точна і ясна постановка проблеми комунікації зробила|робила| величезну дію на розвиток засобів|коштів| зв'язку. Виникла нова наукова галузь, яка почала|стала| називатися теорією інформації.

Головна ідея, обгрунтована Шеноном, полягає в тому, що надійні комунікації мають бути цифровими, тобто задачу зв'язку слід розглядати|розглядувати| як передачу двійкових цифр (бітів).

На рис. 1.1 приведена загальна|спільна| схема передачі цифрової інформації [1].

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

(1.1)

Тобто, як значення функції, так і значення аргументу для таких повідомлень безперервні.

Форматування джерела повідомлень – це процес аналого-цифрового перетворення інформаційного сигналу джерела повідомлення в цифровий сигнал за допомогою дискретизації й квантування сигналу та його представлення в двійковій системі числення.

Аналого-цифровий перетворювач здійснює одночасно процедуру дискретизації сигналу за часом, квантування за рівнем та формує значення вихідного сигналу представляючи його в цифровому коді.

Рис. 1.1. Структурна схема цифрової інформаційної мережі передачі даних

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

Крім того, Шенон довів, що завдання|задачу| надійного зв'язку можна розкласти|розкладати| на дві підзадачі без применшення її ефективності. Ці дві підзадачі називаються кодуванням джерела і кодуванням каналу.

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

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

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

Передача і зберігання інформації вимагають достатньо великих витрат. Велика частина даних, які потрібно передавати по каналах зв'язку і зберігати, має не найкомпактніше представлення. Зазвичай дані зберігаються у формі, що забезпечує їх найбільш просте використання, наприклад: звичайні книжкові тексти, ASCII коди текстових редакторів, двійкові коди даних ЕОМ, окремі відліки сигналів в системах збору даних і т.д. Проте таке найбільш просте у використанні представлення даних вимагає удвічі - втричі, а іноді і в сотні разів більше місця для їх збереження і смугу частот для їх передачі, ніж насправді потрібно. Тому стиснення даних – це один з найбільш актуальних напрямків сучасної теорії інформації.

Завданням|задачею| кодування джерела є|з'являється| створення|створіння| кодера джерела, яке проводить|виробляє| компактний (укорочене) опис початкового|вихідного| сигналу, який необхідно передати|передавати| адресатові. Джерелом сигналів може служити текстовий файл, цифрове зображення, оцифрована музика або телепередача. Це стислий опис сигналів джерела може бути неточним, тоді слід говорити про розбіжність|розходження| між відновленим після|потім| прийому і декодування сигналом і його оригіналом. Це зазвичай|звично| відбувається|походить| при перетворенні (квантуванні) аналогового сигналу в цифрову форму.

Таке кодування називають економним, безнадлишковим, ефективним кодуванням або стисненням даних.

Нижче приведена умовна структура [1] системи стиснення даних (рис.1.2.) :

Рис.1.2. Блок-схема алгоритму стиснення даних

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

Оскільки метою|ціллю| кодування джерел є|з'являється| створення|створіння| компактного, стислого опису цифрової інформації, цю техніку також прийнято називати стиском або компресією цифрових даних.

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

Якщо алгоритм компресії є неадаптивним, то він не здатен змінювати свої операції та параметри в залежності від даних, що стискаються.

Адаптивні алгоритми спочатку тестують вихідні дані, а потім підлаштовують свої параметри та/або операції у відповідності до результату перевірки.

Локально адаптивні алгоритми, можуть змінювати свої параметри, пересуваючись від області до області вхідних даних, виходячи з локальних особливостей файла.

Деякі методи компресії використовують двопрохідні алгоритми, коли при першому проході файлом збирається певна статистика даних, що стискаються, а на другому – проходить безпосередньо стиснення з використанням параметрів, отриманих на першому етапі. Такі алгоритми є напівадаптивними.

Метод компресії, при якому дані на виході декомпресора завжди тотожно співпадають з вихідними даними називається методом компресії без втрат.

Метод компресії, при якому дані на виході декомпресора відрізняються від вихідних даних, стиснених компресором, але результат, тим не менш, влаштовує користувача, називається компресією з втратами.

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

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

Для оцінки продуктивності стиснення використовується ряд величин.

Коефіцієнт стиснення розраховується за формулою [1]:

(1.2)

Таким чином, коефіцієнт стиснення означає, що об'єм стиснення даних складає половину від об'єму даних джерела. Чим більше коефіцієнт стиснення , тим краще працює система стиснення даних.

Коефіцієнт стиснення прийнято вимірювати в bpb (bit per bit). При стисненні графічних зображень використовується величина bpp (bit per pixel), текстових – bpc (bit per character).

Разом з коефіцієнтом стиснення ефективність системи стиснення може бути охарактеризована швидкістю стиснення , що визначається як відношення

(1.3)

де - кількість біт повідомлення.

Величина, обернена коефіцієнту стиснення, називається фактором стиснення :

(1.4)

Головна причина| використання стиснення даних в комунікаціях полягає в бажанні передавати або зберігати інформацію з|із| найбільшою ефективністю.

Бітовий бюджет (bit budget) визначає певний додаток до кожного біта стиснених даних.

Наприклад, якщо в стиснутому файлі 90% займають коди змінної довжини, а 10% використовуються для зберігання деяких таблиць, які будуть використовуватися декомпресором для відновлення вихідних даних, то бітовий бюджет в даному випадку складає 10%.

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

Звернемося|обертатимемося| до кодування джерел. Як і в звичайному|звичному| тексті в різних джерелах цифрових даних є|наявний| надлишкові дані. Тому виникає питання: що є найбільш компактним представленням даних джерела? На це питання відповідь була дана| Шеноном. У своїй роботі по теорії інформації він ввів|запроваджував| числову характеристику джерела, яка називається ентропією. Фундаментальне значення цієї величини полягає в тому, що вона задає нижню межу|кордон| можливого стиснення. Крім того, є|наявний| теорема, яка стверджує, що до цієї межі|кордону| можна наблизитися скільки завгодно близько за допомогою відповідного|придатного| методу кодування джерела. Наприклад, відомо, що ентропія усередненого англійського тексту дорівнює приблизно 3.2 біт/букву|літеру|. У комп'ютерному уявленні|виставі| одна буква|літера| займає|позичає| 8 бітів. Значить, при стисненні типового текстового файлу англійською мовою досягається стиснення приблизно в 2.5 раз.

Під ентропією символа , ймовірність появи якого в повідомленні , розуміється кількість інформації, що міститься в і чисельно дорівнює [2]:

(1.5)

Якщо символи певного алфавіту мають ймовірності відповідно , то ентропія всього алфавіту дорівнює:

(1.6)

Ентропія строки символів цього алфавіту визначається аналогічно.

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

Якщо при кодуванні розмір коду завжди в точності виходить рівним бітам, то в цьому випадку довжина закодованої послідовності буде мінімальною для всіх можливих способів кодування.

Як вже згадувалося вище всі методи стиснення поділяються на два великі класи [3]:

• методи стиснення без втрат інформації (не руйнуюче стиснення);

• методи стиснення з втратами інформації (руйнуюче стиснення).

Якщо ентропія стислих даних збігається з|із| ентропією початкового|вихідного| джерела, то передбачається|припускається|, що за стислими даними можна повністю|цілком| відновити початкову|вихідну| інформацію. Такий підхід прийнято називати стисненням без втрат. Це стиснення, наприклад, застосовується в дистрибутивах програмних продуктів. Це найбільш вивчена область стиснення даних. Вона є|з'являється| дуже важливою|поважною|, оскільки більшість методів компресії самих різних типів цифрової інформації часто використовують на певних стадіях алгоритми стиснення без втрат. Таке стиснення ще називається ентропійним| стисненням. Надмірністю даних можна назвати|накликати| різницю між їх об'ємом|обсягом| і ентропією. Можна сказати, що компресія без втрат є|з'являється| екстремальним випадком стиснення, при якому ентропія даних залишається незмінною.

Блок-схема алгоритму кодування без втрат зображена на рис. 1.3.

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

Рис.1.3. Блок-схема алгоритму кодування без втрат

На виході кодера отримуємо стиснені дані, що відповідають вхідному вектору , представимо у вигляді двійкової послідовності розмір якої k залежить від . Назвемо кодовим словом, привласненим вектору кодером (або кодовим словом, в яке вектор перетворений кодером). Оскільки система стиснення неруйнуюча, однаковим векторам повинні відповідати однакові кодові слова .

Стиснення з|із| втратами припускає|передбачає| зменшення ентропії початкової|вихідної| інформації. У системі стиснення з втратами (або з руйнуванням) кодування проводиться таким чином, що декодер не в змозі відновити дані джерела в первинному вигляді. Структурна схема системи стиснення з руйнуванням зображена на рис. 1.4.

Рис. 1.4. Блок-схема алгоритму кодування з втратами

Як і в попередній схемі, – вектор даних, що підлягає стисненню. Відновлений вектор позначимо як Відзначимо наявність в цій схемі стиснення елементу, який був відсутній при неруйнуючому стисненні – руйнуючий кодер.

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

Руйнуючий кодер додатковим параметром – величиною спотворень , яка визначається як:

(1.7)

Величина є мірою середньоквадратичної відмінності між .

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

Міра, що зараз використовується на практиці, називається мірою відношення сигналу до шуму (peak-to-peak signal-to-noise ratio - PSNR).

(1.8)

Дана міра, по суті, аналогічна середньоквадратичному відхиленню, однак користуватися нею трохи зручніше за рахунок логарифмічного масштабу шкали. Їй властиві ті ж недоліки, що й середньоквадратичному відхиленню.

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