Білоруський державний університет інформатики і радіоелектроніки
Кафедра РЕЗ
Реферат на тему:
«Ентропія складних повідомлень, надмірність джерела. Мета стиснення даних і типи систем стиснення »
МІНСЬК, 2009
Ентропія складних повідомлень, надмірність джерела
Розглянуті вище характеристики джерела - кількість інформації та ентропія - ставилися до одного джерела, який виробляє потік незалежних чи простих повідомлень, або до джерела без пам'яті.
Однак у реальних умовах незалежність елементарних повідомлень, вироблюваних джерелом, - явище досить рідкісне. Частіше буває як раз зворотне - сильна детермінована або статистичний зв'язок між елементами повідомлення одного або декількох джерел.
Наприклад, при передачі тексту ймовірності появи окремих букв залежать від того, які букви їм передували. Для російського тексту, наприклад, якщо передана літера "П", ймовірність того, що наступною буде "А", набагато вище, ніж "Н", після букви "'" ніколи не зустрічається "H" і т.д. Подібна ж картина спостерігається при передачі зображень - сусідні елементи зображення мають зазвичай майже однакові яскравість і колір.
При передачі та зберігання даних часто також мають справу з кількома джерелами, що формують статистично пов'язані один з одним повідомлення. Повідомлення, що виробляються такими джерелами, називаються складними повідомленнями, а самі джерела - джерелами з пам'яттю.
Очевидно, що при визначенні ентропії і кількості інформації в повідомленнях, елементи яких статистично пов'язані, не можна обмежуватися тільки безумовними ймовірностями - необхідно обов'язково враховувати також умовні ймовірності появи окремих повідомлень.
Визначимо ентропію складного повідомлення, що виробляється двома залежними джерелами (подібним же чином визначається ентропія складного повідомлення, що виробляється одним джерелом з пам'яттю).
Нехай повідомлення першого джерела приймають значення x 1, x 2, x 3 ,.... x k з ймовірностями, відповідно, P (x 1), P (x 2 ),..... P (x k), повідомлення другого - y 1, y 2 ,..... y m з імовірностями P (y 1), P (y 2 ),..... P (y m).
Спільну ентропію двох джерел X і Y можна визначити наступним чином:
де P (x i, y j) - ймовірність спільного появи повідомлень x i і y j. Оскільки спільна ймовірність P (x i, y j) за формулою Байєса визначається як
то вираз для спільної ентропії можна записати в наступному вигляді:
Так як передачі повідомлення x i обов'язково відповідає передача одного з повідомлень (будь-якого) з ансамблю Y, то
і спільна ентропія H (X, Y) визначиться як
де H (Y / x i) - так звана приватна умовна ентропія, що відображає ентропію повідомлення Y за умови, що мало місце повідомлення x i. Другий доданок в останньому виразі представляє собою усереднення H (Y / x i) по всім повідомленням x i і називається середньої умовної ентропія джерела Y за умови передачі повідомлення X. І остаточно:
H (X, Y) = H (X) + H (Y / X). (6)
Таким чином, спільна ентропія двох повідомлень дорівнює сумі безумовної ентропії одного з них і умовної ентропії другого.
Можна відзначити наступні основні властивості ентропії складних повідомлень:
1. При статистично незалежних повідомленнях X і Y спільна ентропія дорівнює сумі ентропій кожного з джерел:
H (X, Y) = H (X) + H (Y), (7)
так як H (Y / X) = H (Y).
2. При повній статистичної залежності повідомлень X і Y спільна ентропія дорівнює безумовній ентропії одного з повідомлень. Друге повідомлення при цьому інформації не додає. Дійсно, при повній статистичної залежності повідомлень умовні ймовірності P (y j / x i) і P (x i / yj) рівні або нулю, або 1, тоді
P (x i / y j) * log P (x i / y j) = P (y j / x i) * log P (y j / x i) = 0 (8)
і, отже, H (X, Y) = H (X) = H (Y).
3. Умовна ентропія змінюється в межах
0 <H (Y / X) <H (Y). (9)
4. Для спільної ентропії двох джерел завжди справедливе співвідношення
H (X, Y) ≤ H (X) + H (Y), (0)
при цьому умова рівності виконується тільки для незалежних джерел повідомлень.
Отже, за наявності зв'язку між елементарними повідомленнями ентропія джерела знижується, причому в тим більшою мірою, чим сильніше зв'язок між елементами повідомлення.
Таким чином, можна зробити наступні висновки щодо ступеня інформативності джерел повідомлень:
1. Ентропія джерела і кількість інформації тим більше, чим більше розмір алфавіту джерела.
2. Ентропія джерела залежить від статистичних властивостей повідомлень. Ентропія максимальна, якщо повідомлення джерела різновірогідні і статистично незалежні.
3. Ентропія джерела, що виробляє неравновероятние повідомлення, завжди менше максимально досяжною.
4. При наявності статистичних зв'язків між елементарними повідомленнями (пам'яті джерела) його ентропія зменшується.
В якості прикладу розглянемо джерело з алфавітом, що складається з букв російського мови а, б, в ,....., ю, я. Будемо вважати для простоти, що розмір алфавіту джерела К = 2 5 = 32.
Якщо б всі літери російського алфавіту мали однакову ймовірність і були статистично незалежні, то середня ентропія, яка припадає на один символ, склала б
H (λ) max = log лютого 1932 = 5 біт / літеру.
Якщо тепер врахувати лише різну ймовірність літер у тексті (а неважко перевірити, що так воно і є), розрахункова ентропія складе
H (λ) = 4,39 біт / літеру.
З урахуванням кореляції (статистичного зв'язку) між двома і трьома сусідніми літерами (після букви "П" частіше зустрічається "A" і майже ніколи - "Ю" і "Ц") ентропія зменшиться, відповідно, до
H (λ) = 3,52 біт / букву і H (λ) = 3,05 біт / літеру.
Нарешті, якщо врахувати кореляцію між вісьмома і більше символами, ентропія зменшиться до
H (λ) = 2,0 біт / букву
і далі залишається без змін.
У зв'язку з тим, що реальні джерела з одним і тим же розміром алфавіту можуть мати зовсім різну ентропію (а це не лише тексти, а й мова, музика, зображення і т.д.), вводять таку характеристику джерела, як надмірність
ρ і = 1 - H (λ) / H (λ) max = 1 - H (λ) / log K, (11)
де H (λ) - ентропія реального джерела, log K - максимально досяжна ентропія для джерела з об'ємом алфавіту в К символів.
Тоді, приміром, надмірність літературної російської тексту складе
ρ і = 1 - (2 біта / букву) / (5 біт / букву) = 0,6.
Іншими словами, при передачі тексту по каналу зв'язку кожні шість літер з десяти переданих не несуть ніякої інформації і можуть без жодних втрат просто не передаватися.
Такий же, якщо не більш високою (ρ і = 0,9 ... 0,95) надмірністю володіють і інші джерела інформації - мова, і особливо музика, телевізійні зображення і т.д.
Виникає законне питання: чи потрібно займати носій інформації або канал зв'язку передачею символів, практично не несуть інформації, або ж можливе таке перетворення вихідного повідомлення, при якому інформація "втискувалася" б в мінімально необхідний для цього кількість символів?
Виявляється, не тільки можна, а й необхідно. Сьогодні багато хто з існуючих радіотехнічних систем передачі інформації і зв'язку просто не змогли б працювати, якби в них не проводилося такого роду кодування. Не було б цифрового стільникового зв'язку стандартів GSM і CDMA. Не працювали б системи цифрового супутникового телебачення, дуже неефективною була б робота Internet, а вже про те, щоб подивитися відеофільм чи послухати гарну музику з лазерного диска, не могло бути й мови. Все це забезпечується ефективним або економним кодуванням інформації в даних системах.
Вивченню цього розділу сучасної радіотехніки - основ теорії і техніки економного, або безнадлишкових, кодування - і присвячена наступна частина нашого курсу.
Мета стиснення даних і типи систем стиснення
Передача, зберігання і обробка інформації потребують досить великих витрат. І чим з великою кількістю інформації нам доводиться мати справу, тим дорожче це коштує. На жаль, велика частина даних, які потрібно передавати по каналах зв'язку і зберігати, має не найкомпактніше подання. Швидше, ці дані зберігаються у формі, що забезпечує їх найбільш просте використання, наприклад: звичайні книжкові тексти, ASCII коди текстових редакторів, двійкові коди даних ЕОМ, окремі відліки сигналів у системах збору даних і т.д. Однак таке найбільш просте у використанні подання даних вимагає вдвічі - втричі, а іноді і в сотні разів більше місця для їх збереження і смугу частот для їх передачі, ніж насправді потрібно. Тому стиснення даних - це одне з найбільш актуальних напрямків сучасної радіотехніки.
Таким чином, мета стиснення даних - забезпечити компактне представлення даних, що виробляються джерелом, для їх більш економного збереження і передачі по каналах зв'язку.
Враховуючи надзвичайну важливість процедури економного кодування даних при їх передачі, виділимо її з узагальненої схеми РТС ПІ і докладно розглянемо в цьому розділі нашого курсу.
Нижче наведена умовна структура системи стиснення даних:
Дані джерела ® Кодер ® Стислі дані ® Декодер ® Відновлені дані
У цій схемі виробляються джерелом дані визначимо як дані джерела, а їх компактне подання - як стислі дані. Система стиснення даних складається з кодера і декодера джерела. Кодер перетворює дані джерела в стислі дані, а декодер призначений для відновлення даних джерела з стиснених даних. Відновлені дані, що виробляються декодером, можуть або абсолютно точно збігатися з вихідними даними джерела, або незначно відрізнятися від них.
Існують два типи систем стиснення даних:
· Системи стиснення без втрат інформації (неруйнуюче стиснення);
· Системи стиснення з втратами інформації (руйнівний стиснення).
Вектор даних X ® Кодер ® B (X) ® Декодер ® X
Вектор даних джерела X, що підлягають стисненню, являє собою послідовність X = (X 1, x 2, ... x n) кінцевої довжини. Відліки x i - Складові вектора X - вибрані з кінцевого алфавіту даних A. При цьому розмір вектора даних n обмежений, але він може бути як завгодно великим. Таким чином, джерело на своєму виході формує в якості даних X послідовність довжиною n з алфавіту A.
Вихід кодера - стислі дані, відповідні вхідному вектору X, - представимо у вигляді двійкової послідовності B (X) = (b 1, b 2, ... b k ), розмір якої k залежить від X. Назвемо B (X) кодовим словом, присвоєним вектору X кодером (або кодовим словом, в яке вектор X перетворений кодером). Оскільки система стиснення - неруйнівний, однаковим векторах X l = X m повинні відповідати однакові кодові слова B (X l ) = = B (X m ).
При вирішенні задачі стиснення природним є питання, наскільки ефективна та чи інша система стиснення. Оскільки, як ми вже відзначали, в основному використовується тільки двійкове кодування, то таким заходом може бути коефіцієнт стиснення r, який визначається як відношення
розмір даних джерела в бітах n log 2 (dim A) (12)
r =
=,
розмір стиснених даних в бітах k
де dim A - розмір алфавіту даних A.
Таким чином, коефіцієнт стиснення r = 2 означає, що обсяг стиснутих даних становить половину від обсягу даних джерела. Чим більше коефіцієнт стиснення r, тим краще працює система стиснення даних.
Поряд з коефіцієнтом стиснення r ефективність системи стиснення може бути охарактеризована швидкістю стиснення R, що визначається як відношення
R = k / n (13)
і вимірюється в "кількості кодових біт, що припадають на відлік даних джерела". Система, яка має більший коефіцієнт стиснення, забезпечує меншу швидкість стиснення.
X ® квантователь ® X q ® Неруйнівний кодер ® B (X q) ® Декодер ® X *
Як і в попередній схемі, X = (x 1, x 2, ... x n) - вектор даних, що підлягають стисненню. Відновлений вектор позначимо як X * = (x 1, x 2, ... x n). Відзначимо наявність у цій схемі стиснення елемента, який був відсутній при неруйнівному стиску, - квантователя.
Квантователь стосовно до вектора вхідних даних X формує вектор X q, досить близький до X в сенсі середньоквадратичного відстані. Робота квантователя заснована на зниженні розміру алфавіту (найпростіший квантователь виробляє округлення даних до найближчого цілого числа).
Далі кодер піддає неруйнівного стисненню вектор квантованих даних X q таким чином, що забезпечується однозначна відповідність між X q і B (X q) (для X l q = X m q виконується умова B (X l q) = B (X m q)). Однак система в цілому залишається руйнує, оскільки двом різним векторам X може відповідати один і той же вектор X *.
Руйнівний кодер характеризується двома параметрами - швидкістю стиснення R і величиною спотворень D, що визначаються як
Параметр R характеризує швидкість стиснення в бітах на один відлік джерела, величина D є мірою середньоквадратичного відмінності між X * і X.
Якщо є система руйнує стиснення зі швидкістю і спотвореннями R 1 і D 1 відповідно і друга система зі швидкістю R 2 і спотвореннями D 2, то перша з них краще, якщо R 1 < R 2 і D 1 <D 2. Однак, на жаль, неможливо побудувати систему руйнівного стиснення, що забезпечує одночасно зниження швидкості R і зменшення спотворень D, оскільки ці два параметри пов'язані зворотною залежністю. Тому метою оптимізації системи стиснення з втратами може бути або мінімізація швидкості при заданій величині спотворень, або одержання найменших спотворень при заданій швидкості стиснення.
Вибір системи неруйнівного або руйнуючої стиснення залежить від типу даних, що підлягають стисненню. При стисненні текстових даних, комп'ютерних програм, документів, креслень і т.п. цілком очевидно, що потрібно застосовувати руйнівні методи, оскільки необхідно абсолютно точне відновлення вихідної інформації після її стиснення. При стисненні мови, музичних даних і зображень, навпаки, частіше використовується руйнує стиснення, оскільки при практично непомітних спотвореннях воно забезпечує на порядок, а іноді і на два меншу швидкість R. У загальному випадку руйнує стиснення забезпечує, як правило, істотно більш високі коефіцієнти стиснення, ніж неруйнуюче.
Нижче наведено ряд прикладів, які ілюструють необхідність процедури стиснення, найпростіші методи економного кодування і ефективність стиснення даних.
Приклад 1. Припустимо, що джерело генерує цифрове зображення (кадр) розміром 512 * 512 елементів, що містить 256 кольорів. Кожен колір представляє собою число з множини {0,1,2 ... 255}. Математично це зображення являє собою матрицю 512х512, кожен елемент якої належить безлічі {0,1,2 ... 255}. (Елементи зображення називають пікселями).
У свою чергу, кожен піксел з множини {0,1,2 ... 255} може бути представлений у двійковій формі з використанням 8 біт. Таким чином, розмір даних джерела в бітах складе 8х512х512 = 2 21, або 2,1 Мегабіта.
На жорсткий диск об'ємом в 1 Гігабайт поміститься приблизно 5000 кадрів зображення, якщо вони не стискаються (відеоролик тривалістю приблизно в п'ять хвилин). Якщо ж це зображення піддати стисненню з коефіцієнтом r = 10, то на цьому ж диску ми зможемо зберегти вже майже годинний відеофільм!
Припустимо далі, що ми хочемо передати вихідне зображення по телефонній лінії, пропускна здатність якої становить 14000 біт / с. На це доведеться витратити 21000000 біт/14000 біт / с, або приблизно 3 хвилини. При стисненні ж даних з коефіцієнтом r = 40 на це піде всього 5 секунд!
Кафедра РЕЗ
Реферат на тему:
«Ентропія складних повідомлень, надмірність джерела. Мета стиснення даних і типи систем стиснення »
МІНСЬК, 2009
Ентропія складних повідомлень, надмірність джерела
Розглянуті вище характеристики джерела - кількість інформації та ентропія - ставилися до одного джерела, який виробляє потік незалежних чи простих повідомлень, або до джерела без пам'яті.
Однак у реальних умовах незалежність елементарних повідомлень, вироблюваних джерелом, - явище досить рідкісне. Частіше буває як раз зворотне - сильна детермінована або статистичний зв'язок між елементами повідомлення одного або декількох джерел.
Наприклад, при передачі тексту ймовірності появи окремих букв залежать від того, які букви їм передували. Для російського тексту, наприклад, якщо передана літера "П", ймовірність того, що наступною буде "А", набагато вище, ніж "Н", після букви "'" ніколи не зустрічається "H" і т.д. Подібна ж картина спостерігається при передачі зображень - сусідні елементи зображення мають зазвичай майже однакові яскравість і колір.
При передачі та зберігання даних часто також мають справу з кількома джерелами, що формують статистично пов'язані один з одним повідомлення. Повідомлення, що виробляються такими джерелами, називаються складними повідомленнями, а самі джерела - джерелами з пам'яттю.
Очевидно, що при визначенні ентропії і кількості інформації в повідомленнях, елементи яких статистично пов'язані, не можна обмежуватися тільки безумовними ймовірностями - необхідно обов'язково враховувати також умовні ймовірності появи окремих повідомлень.
Визначимо ентропію складного повідомлення, що виробляється двома залежними джерелами (подібним же чином визначається ентропія складного повідомлення, що виробляється одним джерелом з пам'яттю).
Нехай повідомлення першого джерела приймають значення x 1, x 2, x 3 ,.... x k з ймовірностями, відповідно, P (x 1), P (x 2 ),..... P (x k), повідомлення другого - y 1, y 2 ,..... y m з імовірностями P (y 1), P (y 2 ),..... P (y m).
Спільну ентропію двох джерел X і Y можна визначити наступним чином:
де P (x i, y j) - ймовірність спільного появи повідомлень x i і y j. Оскільки спільна ймовірність P (x i, y j) за формулою Байєса визначається як
то вираз для спільної ентропії можна записати в наступному вигляді:
Так як передачі повідомлення x i обов'язково відповідає передача одного з повідомлень (будь-якого) з ансамблю Y, то
і спільна ентропія H (X, Y) визначиться як
де H (Y / x i) - так звана приватна умовна ентропія, що відображає ентропію повідомлення Y за умови, що мало місце повідомлення x i. Другий доданок в останньому виразі представляє собою усереднення H (Y / x i) по всім повідомленням x i і називається середньої умовної ентропія джерела Y за умови передачі повідомлення X. І остаточно:
H (X, Y) = H (X) + H (Y / X). (6)
Таким чином, спільна ентропія двох повідомлень дорівнює сумі безумовної ентропії одного з них і умовної ентропії другого.
Можна відзначити наступні основні властивості ентропії складних повідомлень:
1. При статистично незалежних повідомленнях X і Y спільна ентропія дорівнює сумі ентропій кожного з джерел:
H (X, Y) = H (X) + H (Y), (7)
так як H (Y / X) = H (Y).
2. При повній статистичної залежності повідомлень X і Y спільна ентропія дорівнює безумовній ентропії одного з повідомлень. Друге повідомлення при цьому інформації не додає. Дійсно, при повній статистичної залежності повідомлень умовні ймовірності P (y j / x i) і P (x i / yj) рівні або нулю, або 1, тоді
P (x i / y j) * log P (x i / y j) = P (y j / x i) * log P (y j / x i) = 0 (8)
і, отже, H (X, Y) = H (X) = H (Y).
3. Умовна ентропія змінюється в межах
0 <H (Y / X) <H (Y). (9)
4. Для спільної ентропії двох джерел завжди справедливе співвідношення
H (X, Y) ≤ H (X) + H (Y), (0)
при цьому умова рівності виконується тільки для незалежних джерел повідомлень.
Отже, за наявності зв'язку між елементарними повідомленнями ентропія джерела знижується, причому в тим більшою мірою, чим сильніше зв'язок між елементами повідомлення.
Таким чином, можна зробити наступні висновки щодо ступеня інформативності джерел повідомлень:
1. Ентропія джерела і кількість інформації тим більше, чим більше розмір алфавіту джерела.
2. Ентропія джерела залежить від статистичних властивостей повідомлень. Ентропія максимальна, якщо повідомлення джерела різновірогідні і статистично незалежні.
3. Ентропія джерела, що виробляє неравновероятние повідомлення, завжди менше максимально досяжною.
4. При наявності статистичних зв'язків між елементарними повідомленнями (пам'яті джерела) його ентропія зменшується.
В якості прикладу розглянемо джерело з алфавітом, що складається з букв російського мови а, б, в ,....., ю, я. Будемо вважати для простоти, що розмір алфавіту джерела К = 2 5 = 32.
Якщо б всі літери російського алфавіту мали однакову ймовірність і були статистично незалежні, то середня ентропія, яка припадає на один символ, склала б
H (λ) max = log лютого 1932 = 5 біт / літеру.
Якщо тепер врахувати лише різну ймовірність літер у тексті (а неважко перевірити, що так воно і є), розрахункова ентропія складе
H (λ) = 4,39 біт / літеру.
З урахуванням кореляції (статистичного зв'язку) між двома і трьома сусідніми літерами (після букви "П" частіше зустрічається "A" і майже ніколи - "Ю" і "Ц") ентропія зменшиться, відповідно, до
H (λ) = 3,52 біт / букву і H (λ) = 3,05 біт / літеру.
Нарешті, якщо врахувати кореляцію між вісьмома і більше символами, ентропія зменшиться до
H (λ) = 2,0 біт / букву
і далі залишається без змін.
У зв'язку з тим, що реальні джерела з одним і тим же розміром алфавіту можуть мати зовсім різну ентропію (а це не лише тексти, а й мова, музика, зображення і т.д.), вводять таку характеристику джерела, як надмірність
ρ і = 1 - H (λ) / H (λ) max = 1 - H (λ) / log K, (11)
де H (λ) - ентропія реального джерела, log K - максимально досяжна ентропія для джерела з об'ємом алфавіту в К символів.
Тоді, приміром, надмірність літературної російської тексту складе
ρ і = 1 - (2 біта / букву) / (5 біт / букву) = 0,6.
Іншими словами, при передачі тексту по каналу зв'язку кожні шість літер з десяти переданих не несуть ніякої інформації і можуть без жодних втрат просто не передаватися.
Такий же, якщо не більш високою (ρ і = 0,9 ... 0,95) надмірністю володіють і інші джерела інформації - мова, і особливо музика, телевізійні зображення і т.д.
Виникає законне питання: чи потрібно займати носій інформації або канал зв'язку передачею символів, практично не несуть інформації, або ж можливе таке перетворення вихідного повідомлення, при якому інформація "втискувалася" б в мінімально необхідний для цього кількість символів?
Виявляється, не тільки можна, а й необхідно. Сьогодні багато хто з існуючих радіотехнічних систем передачі інформації і зв'язку просто не змогли б працювати, якби в них не проводилося такого роду кодування. Не було б цифрового стільникового зв'язку стандартів GSM і CDMA. Не працювали б системи цифрового супутникового телебачення, дуже неефективною була б робота Internet, а вже про те, щоб подивитися відеофільм чи послухати гарну музику з лазерного диска, не могло бути й мови. Все це забезпечується ефективним або економним кодуванням інформації в даних системах.
Вивченню цього розділу сучасної радіотехніки - основ теорії і техніки економного, або безнадлишкових, кодування - і присвячена наступна частина нашого курсу.
Мета стиснення даних і типи систем стиснення
Передача, зберігання і обробка інформації потребують досить великих витрат. І чим з великою кількістю інформації нам доводиться мати справу, тим дорожче це коштує. На жаль, велика частина даних, які потрібно передавати по каналах зв'язку і зберігати, має не найкомпактніше подання. Швидше, ці дані зберігаються у формі, що забезпечує їх найбільш просте використання, наприклад: звичайні книжкові тексти, ASCII коди текстових редакторів, двійкові коди даних ЕОМ, окремі відліки сигналів у системах збору даних і т.д. Однак таке найбільш просте у використанні подання даних вимагає вдвічі - втричі, а іноді і в сотні разів більше місця для їх збереження і смугу частот для їх передачі, ніж насправді потрібно. Тому стиснення даних - це одне з найбільш актуальних напрямків сучасної радіотехніки.
Таким чином, мета стиснення даних - забезпечити компактне представлення даних, що виробляються джерелом, для їх більш економного збереження і передачі по каналах зв'язку.
Враховуючи надзвичайну важливість процедури економного кодування даних при їх передачі, виділимо її з узагальненої схеми РТС ПІ і докладно розглянемо в цьому розділі нашого курсу.
Нижче наведена умовна структура системи стиснення даних:
Дані джерела ® Кодер ® Стислі дані ® Декодер ® Відновлені дані
У цій схемі виробляються джерелом дані визначимо як дані джерела, а їх компактне подання - як стислі дані. Система стиснення даних складається з кодера і декодера джерела. Кодер перетворює дані джерела в стислі дані, а декодер призначений для відновлення даних джерела з стиснених даних. Відновлені дані, що виробляються декодером, можуть або абсолютно точно збігатися з вихідними даними джерела, або незначно відрізнятися від них.
Існують два типи систем стиснення даних:
· Системи стиснення без втрат інформації (неруйнуюче стиснення);
· Системи стиснення з втратами інформації (руйнівний стиснення).
Стиснення без втрат інформації
У системах стиску без втрат декодер відновлює дані джерела абсолютно точно, таким чином, структура системи стиснення виглядає наступним чином:Вектор даних X ® Кодер ® B (X) ® Декодер ® X
Вектор даних джерела X, що підлягають стисненню, являє собою послідовність X = (X 1, x 2, ... x n) кінцевої довжини. Відліки x i - Складові вектора X - вибрані з кінцевого алфавіту даних A. При цьому розмір вектора даних n обмежений, але він може бути як завгодно великим. Таким чином, джерело на своєму виході формує в якості даних X послідовність довжиною n з алфавіту A.
Вихід кодера - стислі дані, відповідні вхідному вектору X, - представимо у вигляді двійкової послідовності B (X) = (b 1, b 2, ... b k ), розмір якої k залежить від X. Назвемо B (X) кодовим словом, присвоєним вектору X кодером (або кодовим словом, в яке вектор X перетворений кодером). Оскільки система стиснення - неруйнівний, однаковим векторах X l = X m повинні відповідати однакові кодові слова B (X l ) = = B (X m ).
При вирішенні задачі стиснення природним є питання, наскільки ефективна та чи інша система стиснення. Оскільки, як ми вже відзначали, в основному використовується тільки двійкове кодування, то таким заходом може бути коефіцієнт стиснення r, який визначається як відношення
розмір даних джерела в бітах n log 2 (dim A) (12)
r =
розмір стиснених даних в бітах k
де dim A - розмір алфавіту даних A.
Таким чином, коефіцієнт стиснення r = 2 означає, що обсяг стиснутих даних становить половину від обсягу даних джерела. Чим більше коефіцієнт стиснення r, тим краще працює система стиснення даних.
Поряд з коефіцієнтом стиснення r ефективність системи стиснення може бути охарактеризована швидкістю стиснення R, що визначається як відношення
R = k / n (13)
і вимірюється в "кількості кодових біт, що припадають на відлік даних джерела". Система, яка має більший коефіцієнт стиснення, забезпечує меншу швидкість стиснення.
Стиснення з втратою інформації
У системі стиснення з втратами (або з руйнуванням) кодування здійснюється таким чином, що декодер не в змозі відновити дані джерела в первісному вигляді. Структурна схема системи стиснення з руйнуванням виглядає наступним чином:X ® квантователь ® X q ® Неруйнівний кодер ® B (X q) ® Декодер ® X *
Як і в попередній схемі, X = (x 1, x 2, ... x n) - вектор даних, що підлягають стисненню. Відновлений вектор позначимо як X * = (x 1, x 2, ... x n). Відзначимо наявність у цій схемі стиснення елемента, який був відсутній при неруйнівному стиску, - квантователя.
Квантователь стосовно до вектора вхідних даних X формує вектор X q, досить близький до X в сенсі середньоквадратичного відстані. Робота квантователя заснована на зниженні розміру алфавіту (найпростіший квантователь виробляє округлення даних до найближчого цілого числа).
Далі кодер піддає неруйнівного стисненню вектор квантованих даних X q таким чином, що забезпечується однозначна відповідність між X q і B (X q) (для X l q = X m q виконується умова B (X l q) = B (X m q)). Однак система в цілому залишається руйнує, оскільки двом різним векторам X може відповідати один і той же вектор X *.
Руйнівний кодер характеризується двома параметрами - швидкістю стиснення R і величиною спотворень D, що визначаються як
R = k / n,
D = (1 / n) Σ (x i - x i) 2. (14)Параметр R характеризує швидкість стиснення в бітах на один відлік джерела, величина D є мірою середньоквадратичного відмінності між X * і X.
Якщо є система руйнує стиснення зі швидкістю і спотвореннями R 1 і D 1 відповідно і друга система зі швидкістю R 2 і спотвореннями D 2, то перша з них краще, якщо R 1 < R 2 і D 1 <D 2. Однак, на жаль, неможливо побудувати систему руйнівного стиснення, що забезпечує одночасно зниження швидкості R і зменшення спотворень D, оскільки ці два параметри пов'язані зворотною залежністю. Тому метою оптимізації системи стиснення з втратами може бути або мінімізація швидкості при заданій величині спотворень, або одержання найменших спотворень при заданій швидкості стиснення.
Вибір системи неруйнівного або руйнуючої стиснення залежить від типу даних, що підлягають стисненню. При стисненні текстових даних, комп'ютерних програм, документів, креслень і т.п. цілком очевидно, що потрібно застосовувати руйнівні методи, оскільки необхідно абсолютно точне відновлення вихідної інформації після її стиснення. При стисненні мови, музичних даних і зображень, навпаки, частіше використовується руйнує стиснення, оскільки при практично непомітних спотвореннях воно забезпечує на порядок, а іноді і на два меншу швидкість R. У загальному випадку руйнує стиснення забезпечує, як правило, істотно більш високі коефіцієнти стиснення, ніж неруйнуюче.
Нижче наведено ряд прикладів, які ілюструють необхідність процедури стиснення, найпростіші методи економного кодування і ефективність стиснення даних.
Приклад 1. Припустимо, що джерело генерує цифрове зображення (кадр) розміром 512 * 512 елементів, що містить 256 кольорів. Кожен колір представляє собою число з множини {0,1,2 ... 255}. Математично це зображення являє собою матрицю 512х512, кожен елемент якої належить безлічі {0,1,2 ... 255}. (Елементи зображення називають пікселями).
У свою чергу, кожен піксел з множини {0,1,2 ... 255} може бути представлений у двійковій формі з використанням 8 біт. Таким чином, розмір даних джерела в бітах складе 8х512х512 = 2 21, або 2,1 Мегабіта.
На жорсткий диск об'ємом в 1 Гігабайт поміститься приблизно 5000 кадрів зображення, якщо вони не стискаються (відеоролик тривалістю приблизно в п'ять хвилин). Якщо ж це зображення піддати стисненню з коефіцієнтом r = 10, то на цьому ж диску ми зможемо зберегти вже майже годинний відеофільм!
Припустимо далі, що ми хочемо передати вихідне зображення по телефонній лінії, пропускна здатність якої становить 14000 біт / с. На це доведеться витратити 21000000 біт/14000 біт / с, або приблизно 3 хвилини. При стисненні ж даних з коефіцієнтом r = 40 на це піде всього 5 секунд!
Приклад 2. В якості даних джерела, що підлягають стисненню, виберемо фрагмент зображення розміром 4х4 елемента і містить 4 кольори: R = = "червоний", O = "помаранчевий", Y = "синій", G = "зелений":
R | R | O | Y |
| R | O | O | Y |
| O | O | Y | G |
| Y | Y | Y | G |
Для стиснення даних візьмемо кодер, що використовує таку таблицю перекодування даних джерела в кодові слова (питання про вибір таблиці залишимо на майбутнє):
| Кодер | |
| Відлік | Кодове слово |
| 3 | 001 |
| 2 | 01 |
| 1 | 1 |
| 0 | 000 |
B (X) = (0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,1,1,0,1,0,1,1, 0,0,0,1,1,1,0,0,0).
Коефіцієнт стиснення при цьому складе r = 32/31, або 1,03. Відповідно швидкість стиснення R = 31/16 біт на відлік.
Приклад 3. Порівняємо два різних кодера, здійснюють стиснення одного і того ж вектора даних
X = ABRACADABRA.
Перший кодер - кодер без пам'яті, аналогічний розглянутому в попередньому прикладі (кожен елемент вектора X кодується незалежно від значень інших елементів - кодер без пам'яті). Таблиця кодування для нього виглядає наступним чином:
| Кодер 1 | |
| Символ | Кодове слово |
| A | 0 |
| B | 10 |
| R | 110 |
| C | 1110 |
| D | 1111 |
| Кодер 2 | |
| Символ, попередній символ | Кодове слово |
| (A, -) | 1 |
| (B, A) | 0 |
| (C, A) | 10 |
| (D, A) | 11 |
| (A, R) | 1 |
| (R, B) | 1 |
| (A, C) | 1 |
| (A, B) | 1 |
B 1 (X) = 01011001110011110101100,
B 2 (X) = 10111011111011.
Таким чином, швидкість стиснення при використанні кодера 1 (без пам'яті) складе 23/11 = 2,09 біта на символ даних, тоді як для кодера 2 - 13/11 = = 1,18 біта на символ. Використання другого кодера, отже, є кращим, хоча він і більш складний.
ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для вузів. / В.І. Нефедов, В.І. Халкин, Є.В. Федоров та ін - М.: Вища Школа,
3. Цапенко М.П. Вимірювальні інформаційні системи. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок,
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс»,