Система стиснення відеоданих на основі аналізу ентропійності (стр. 4 из 17)
Асимптотичне поводження функції M (n) /n дозволяє зробити висновок:
 | (1.9) |
Таким чином, отримане узагальнення нерівності Макміллана на випадок внесків символів у результуючу довжину повідомлень.
Узагальнена нерівність (1.9) дозволяє обчислити точне значення величини внеску xaсимволу з індексом a для випадку оптимального кодування. Для обчислення точного значення необхідно вирішити задачу про мінімізацію суми
,яка визначає середню ефективність кодування, за умови виконання нерівності (1.9). У крапці мінімуму похідна від зазначеної суми звертається в нуль:
 | (1.10) |
Підстановка рішення задачі про мінімізацію в нерівність (1.9), мабуть, повинне перетворювати його в рівність. Звідси будь-який оптимальний внесок xkлегко виражається через внески інших символів:
Підставляючи вираження для xkу рівняння (1.10), одержуємо
Після узяття похідної рівняння здобуває наступний вид:
, або 
Індекс k може приймати одне з N значень, тобто реально для шкірного фіксованого індексу a є N рівнянь. Просумувавши ці рівняння, одержимо
що з урахуванням виконання рівності у вираженні (1.9) рівносильне
Звідси отримаємо формулу для xa:
 | (1.11) |
Таким чином, оптимальний внесок символу, що з'являється з імовірністю p: у довжину результуючого коду становить logm p одиниць інформації в системі подання з підставою m. - анный висновок може бути використаний для обчислення оптимальної довжини коду в рамках тієї або іншої імовірнісної моделі. Одержуючи оцінку ймовірності появи чергового символу на деякому етапі кодування, можна точно визначити оптимальну довжину відповідного інформаційного опису.
1.3 Методи генерації коду
1.3.1 Префіксне кодування
Серед кодів, що задовольняють нерівності Макміллана, особливе місце займають префіксні коди. Система кодів називається префіксною, якщо жоден з кодів, що належить системі, не є качаном (префіксом) іншого коду із цієї ж системи. Очевидне достоїнство префіксного кодування полягає в тім, що одержуваний код може бути легко декодований. Завдяки властивості префікса для того, щоб визначити черговий закодований символ (повідомлення), досить проаналізувати качан відповідної чергової порції коду. При цьому довжина аналізованої порції ніколи не перевищує довжину коду чергового закодованого символу (повідомлення).
Геометрична трактування систем префіксних кодів - m-арные дерева. Властивістьпрефікса гарантує відсутність циклів у графі, ребрам якого зіставлені різні значення інформаційної одиниці. Таким чином, граф є деревом зі ступенем розгалуження, що збігає з підставою системи подання інформації m. Слід зазначити, що нумерація ребер може бути здійснена довільним образом; значення має тільки конкретна структура дерева, а точніше - набір відстаней від кореневого вузла до листових вузлів. Ці відстані відповідають довжинам кодів префіксної системи. Крафт показав, що виконання нерівності (1.7) є гарантією існування кодового дерева зі структурою, що відповідає набору довжин
, що фігурують у нерівності. Інакше кажучи, якщо система довжин задовольняє нерівності (1.7), можна побудувати систему префіксних кодів з відповідними довжинами. Дане твердження дозволяє відмовитися від розгляду систем кодів, відмінних від префіксних. Будь-яка система дешифрованих кодів задовольняє нерівності (1.7), а виходить, вона може бути без шкоди для ефективності замінена системою префіксних кодів. Нерівність (1.7) стосовно до систем префиксних кодів називають також нерівністю Крафта.Розглянемо блокове кодування повідомлень довжини n, породжуваних деяким інформаційним джерелом. Як і раніше, позначимо через
імовірнісний розподіл появи j-ro символу повідомлення (sj - відповідний стан джерела), через pi1, i2,..., in - імовірність появи повідомлення "i1, i2,..., in". Відповідно до твердження Крафта, можна побудувати систему префіксних кодів із длинами
(Для доказу досить підставити ці довжини в нерівність Крафта й переконатися в тім, що воно виконується) Оцінимо ефективність кодування з розрахунку на один символ повідомлення:
Використовуючи альтернативне вираження для ентропії (1.5), одержуємо
Для випадку стаціонарного джерела з розподілом імовірностей
маємо:
Збільшуючи довжину повідомлення n, можна домогтися ефективності кодування як завгодно близької до ентропії джерела інформації. Таким чином, знаючи апріорі ймовірності появи різних символів на виході джерела в кожен конкретний момент часу, можна організувати кодування даного джерела, наближене до оптимального кодування на кожну наперед задану величину, за умови, що є достатній об'єм інформаційної вибірки.
1.3.2 Алгоритм Шеннона
Алгоритм побудови системи префиксних кодів з довжинами, що залежать від імовірностей по формулі
, був запропонований Шенноном. Алгоритм працює в такий спосіб. Імовірності появи повідомлень p1,p2,...,pnрозташовуються в порядку убування (тут N - потужність множини повідомлень). Не обмежуючи спільності, можна вважати 
.Як код повідомлення з індексом i беруться перші
m-ичных розрядів числа 
так називаної накопиченої ймовірності. Тому що довжини кодів у такій системі не убувають зі зменшенням імовірності й імовірності появи повідомлень із індексами i+1, i+2,...,N відрізняються від імовірності появи повідомлення з індексом i принаймні на 
, код повідомлення з індексом i не є початком кодів повідомлень із індексами i+1, i+2,...,N. Таким чином, система кодів є префіксною. Розглянемо геометричне трактування алгоритму Шеннона. Інтервал [0,1) може бути розбитий на N підінтервалів 
,відповідним повідомленням з індексами i = 1, 2,...,N. Для ідентифікації i-го повідомлення необхідно вибрати деяке число з підінтервалу [ai, bi),представиме як можна меншою кількістю m-ічних розрядів. Для цього потрібно побудувати на інтервалі [0,1) одномірну мережу з постійним періодом, що містить
крапок (місце розташування будь-якої крапки визначається li-розрядним числом), рівно одна з яких (ідентифікуюча) належить інтервалу [ai, bi). Ясно, що шукана мережа повинна мати період, що не перевищує pi, тобто 
. Звідки отримуємо 
.Алгоритм Шеннона дозволяє генерувати коди, довжина яких відрізняється від оптимальних значень, обумовлених по формулі (1.11), менш чим на одну інформаційну одиницю. Таким чином, різниця між ефективністю кодування й ентропією (так називана надмірність) не перевищує одиниці.
1.3.3 Алгоритм Хаффмана
Алгоритм Шеннона має досить високу ефективність, однак він не є оптимальним алгоритмом побудови системи префіксних кодів. Для знаходження оптимального алгоритму необхідно при фіксованому наборі ймовірностей {p1,p2,...,pn} вирішити задачу про мінімізацію суми
за умови виконання нерівності Крафта 
(тут li - довжина коду повідомлення з індексом i).