4.1  Теоретичні границі стиснення інформації

 

Стиснення даних не може бути більше деякої теоретичної границі. Сформульована раніше теорема Шеннона про кодування каналу без шуму встановлює верхню границю стиснення інформації як ентропію джерела H(X).

Позначимо через L(X) функцію, що повертає довжину коду повідомлень

L(X)=len(code(X)),

де code(X) кожному значенню X ставить у відповідність деякий бітовий код; len( ) - повертає довжину цього коду.

Оскільки L(X) - функція від д. в. в. X, тобто також є д. в. в., то її середнє значення обчислюється як математичне сподівання:

 

.                                              (2.3)

 

Наслідком теореми Шеннона про кодування джерела у відсутності шуму є те, що середня кількість бітів коду, що припадає на одне значення д. в. в., не може бути менше її ентропії, тобто

 

                                                  (2.4)

 

для будь-якої д. в. в. X і будь-якого її коду.

Нехай - вектор даних завдовжки n;  - вектор частот символів у .

Тоді середня кількість бітів коду на одиницю повідомлення обчислюється так:

 

     ,                                         (2.5)

 

де  - довжина коду повідомлення : ;  - вектор Крафта для .

Ентропія повідомлення  обчислюється так:

 

.                                                  (2.6)

 

Розглянемо функцію y=ln(x), яка є опуклою вниз, тобто її графік лежить не вище своєї дотичної y=x-1. Тоді можна записати таку нерівність:

 

ln(x)  x-1, x>0.                                   (2.7)

 

Підставимо в (2.7)  і помножимо обидві частини цієї нерівності на :

 

.                              (2.8)

 

Запишемо суми за i обох частин нерівності (2.8), і з урахуванням того, що для оптимального кодування Хаффмена нерівність Крафта (2.1) переходить в строгу рівність, дістанемо в правій частині (2.8) нуль, отже,

.

Перейдемо від натурального логарифма до двійкового і з урахуванням виразу (2.6) дістанемо

,

тобто приходимо до виразу (2.4), що визначає верхню границю стиснення даних.

                Припустимо, що у векторі Крафта  довжини кодових слів пов'язані з частотами символів у повідомленні так:

.

При виконанні цієї умови нерівність Крафта (2.1) обертається у строгу рівність, і код буде компактним, тобто матиме найменшу середню довжину. Тоді, оскільки для оптимальних кодів Шеннона-Фано і Хаффмена довжина кожної кодової комбінації округлюється до більшої цілої кількості бітів, маємо  

,

звідси

.

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

 

.                                       (2.9)