Система стиснення відеоданих на основі аналізу ентропійності (стр. 3 из 17)
 | (1.1) |
Формула (1.1) дозволяє визначити ентропію джерела, що перебуває в деякому конкретному стані. Ентропія джерела в цілому - безвідносно до конкретного стану - може бути визначена далеко не завжди. Можливість визначення ентропії залежить від імовірностей тихнув або інших станів і відповідних цих станів ансамблів перехідних імовірностей (перехід зі стану в стан здійснюється при породженням джерелом чергового символу). Розглянемо окремий випадок, коли інформаційне джерело S може перебувати в одному з T станів, причому чітко відомі всі ймовірності переходів джерела з будь-якого стану i у стан j (pij). Якщо існує межа
, де Р - матриця з компонентами pi,j, величина ентропії джерела S може бути обчислена по формулі  | (1.2) |
Отут pi - імовірність знаходження джерела S в i-м стані (pi є значення i - елемента будь-якого рядка матриці P∞), a m - підстава системи подання інформації.
Множина станів інформаційного джерела в сукупності з ансамблем перехідних імовірностей прийнято називати моделлю станів або марковской моделлю. Для визначення ентропії джерела інформації в рамках даної моделі необхідно правильно підібрати її структуру й параметри, які повинні повною мірою відповідати джерелу. На практиці це досить важко, тому що параметри інформаційних джерел, як правило, апріорі не відомі1. Визначити їх можна тільки приблизно, тому при рішенні практичних задач доводити прибігати до емпіричних способів оцінки ентропії. Як правило, мова йде про усереднення величини ентропії за годиною.
Нехай джерело послідовно перебуває в станах s1, s2,..., sn, які відповідають розподілу ймовірностей появи символів
Через рі1, і2, іn позначимо ймовірність появи на виході джерела послідовності символів з індексами i1, i2,..., in (символ ik породжується джерелом у стані sk). Очевидно, що
 | (1.3) |
Напівемпіричною ентропією джерела назвемо величину
 | (1.4) |
З урахуванням тотожності (1.3) формула (1.4) приводитися до більше зручного для обчислення виду
Приставка "напів" означає, що для отримання ентропії частино використовуються апріорні дані про імовірнісні характеристики джерела (відомий розподіл імовірностей появи символів у різних станах), а частина, що залишилася, інформації - конкретна послідовність станів - виходить емпіричним шляхом. У реальних задачах, як правило, подібної апріорної інформації ні, тому доцільно ввести поняття емпіричної ентропії, визначивши її величину по формулі:
 | (1.6) |
У цьому випадку ri (sj) - емпірична оцінка ймовірності появи символу з індексом i при породженні j-й вибірки джерела інформації1. Причина, по якій особлива увага приділяється способах обчислення ентропії, полягає в тім, що величина ентропії є чисельною границею ефективності ощадливого кодування вибірки інформаційного джерела. Знаючи ентропію, можна оцінити ефективність того або іншого методу або алгоритму. В ідеалі ефективність винна збігатися з величиною ентропією. При цьому, якщо природа інформаційного джерела не є імовірнісної, тобто чітко виділити ті або інші імовірнісні стани не можна, мова може йти тільки про ентропію, що обчислює частково на емпіричній основі. В силу останньої обставини, надалі при вживанні терміна ентропія найчастіше буде матися на увазі напівемпірична ентропія.
Обчислення ентропії на практиці можна здійснювати в процесі послідовного аналізу станів інформаційного джерела, що безпосередньо треба з формул (1.5) і (1.6). Як видно з наведених формул, величина ентропії складається з величин ентропії в станах, у яких послідовно перебуває джерело інформації. Таким чином, задача оптимального моделювання послідовної інформаційної вибірки зводиться до задачі створення оптимальної моделі породження символів у шкірному конкретному стані, що є істотним спрощенням. Як буде показаний нижче, подібне спрощення припустиме й відносно механізму генерації коду, тобто воно фактично припустимо відносно методу кодування в цілому.
1.2.2 Дешифровані коди
Найпростіший варіант кодування вибірки інформаційного джерела - установлення відповідності між конкретними символами алфавіту й кодами, що мають цілу довжину в одиницях подання інформації. Природно зажадати, щоб код, отриманий у результаті такого кодування, був дешифрованим, тобто по будь-якій комбінації кодів символів можна було б відновити закодоване повідомлення. Необхідна умова дешифруємості було запропоновано й доведене Макмілланом. Формулювання виглядає в такий спосіб: якщо система кодів із цілими довжинами {li}Ni=1 дешифровані, те виконується нерівність
 | (1.7) |
де m - підстава системи подання інформації.
Виконання нерівності (1.7) спричиняє виконання більше важливої нерівності:
 | (1.8) |
Для доказу досить скористатися опуклістю функції logm (x). Таким чином, ефективність дешифрованого посимвольного кодування обмежена величиною ентропії імовірнісного розподілу появи символів на виході інформаційного джерела.
Більше складний й у той же час найбільше ефективний варіант кодування має на увазі одержання кодів не для окремих символів, а для цілих повідомлень. Коди декодуємих повідомлень, мабуть, також повинні задовольняти нерівності Макміллана. При цьому оцінка ефективності з розрахунку на один символ повідомлення ускладнюється необхідністю проведення усереднення по довжині повідомлення. Покажемо, що ефективність кодування вибірки інформаційного джерела зазначеним способом також обмежується величиною ентропії.
Будемо використати раніше уведені позначення. Джерело, що послідовно перебуває в станах s1, s2,..., sn, як і раніше, характеризується імовірнісними розподілами
.Через pi1, i2,..., in позначається ймовірність появи повідомлення "i1, i2,... in", через li1, i2,..., in - довжина коду повідомлення. Ефективність кодування повідомлень довжини n з розрахунку на один символ визначається по формулі
Коди для повідомлень довжини n повинні бути дешифрованими, тому можна скористатися нерівністю (1.8):
Права частина нерівності являє собою вираження для ентропії. Таким чином, ефективність кодування з розрахунку на один символ не може перевершувати величину ентропії повідомлення, що доводити на один символ. Використовуючи формулу (1.5), одержуємо більше зручну з обчислювальної крапки зору оцінку:
Якщо джерело, що породжує повідомлення, є стаціонарним (імовірнісний розподіл 
не залежить від позиції символу в повідомленні), нерівність здобуває спрощений вид:
1.2.3 Оптимальна довжина коду
Тому що код виходить для повідомлення в цілому, не можна говорити про коди для конкретних символів, що становлять повідомлення. Проте виникає необхідність визначати деякий внесок у результуючу довжину коду повідомлення, внесень кожним вхідної в нього символом. Фізичний зміст такого внеску - середнє збільшення довжини коду повідомлення, обумовлене входженням у нього даного символу. Позначимо через xiвнесок, внесень символом з індексом i (у загальному випадку величина внеску являє собою речовинне число). Через xi1, i2,..., inпозначимо внесок, внесень повідомленням s = i1, i2,..., in - Виходячи зі змісту поняття "внесок", для випадку стаціонарної незалежної вибірки логічно зажадати виконання наступних властивостей:
(адитивність)
,де li1, i2,..., in - довжина реального коду повідомлення (ціле число), а M (n) - ненегативна функція, така що M (n) /n - > 0 при n - > оо