Теорема об оптимальном кодировании

Пусть имеется распределение вероятностей Р :

p₁ ≥ p₂ ≥… ≥ p_n-1; p_i =1.

И пусть имеется префиксная схема оптимального кодирования:

={}|. (3) И пусть существует p_j = q+ q, такое что p_n-1≥ q₁ ≥ q₂. (4) Тогда схема кодирования: ={;…; ; ;…; ; ; } (5)

где =0, =1, q₁ соответствует , q соответствует ,

является префиксной и оптимальной.

Разъяснение:

Эта теорема позволяет из оптимального кодирования алфавита, имеющего n- 1 букв, составить схему оптимального кодирования для другого алфавита, имеющего n букв, если выполнено условие (4). Смысл теоремы заключается в том, что для распределения вероятностей, состоящих из двух букв, мы можем произвести оптимальное кодирование. Например. р₁ = 0,6 ─ код 0, р ₂ = 0,4 ─ код 1.

Разобьем р ₁: р ₁ = 0,3 + 0,3. Каждое из слагаемых поместим в нижнюю часть распределения вероятностей, а имеющемуся коду первой буквы припишем 0 и 1. Получим оптимальную схему кодирования:.

р ₁=0,4 код 1

р P₂=0,3 код 00

р P₃=0,3 код 01.

Далее, продолжая разбивать вероятность р ₁ = 0,25 + 0,15, получим новую схему оптимального кодирования

р ₁ = 0,3 00

р ₂ = 0,3 01

р ₃ = 0,25 10

р ₄ = 0,15 11. и т.д.

Замечание:

Не всякая вероятность может быть разбита на два слагаемых, удовлетворяющих условию (4). Например: р ₁ = 0,6; р ₂ = 0,2; р ₃ = 0,2;

р ₁ не разбивается на два слагаемых, каждое из которых < 0,2.

Доказательство теоремы:

Схема кодирования (3) – префиксная. Цена кодирования

C = р ₁ l +…+ р _n-1.

Схема (5) тоже будет префиксной по построению.

Цена кодирования

C = р ₁l +…+ р _j-1+ р _j+1+…+ р _n-1+ q ||+ q || =

= р ₁ l +…+ р _n-1 + q (+ 1) + q (+1) =

= р ₁ l +…+ р _n-1+(q+ q) + q+q= р ₁ l +…+ р _n-1+ + р _j + p _j = C + p_j.

Рассмотрим теперь схему оптимального кодирования

={}|= {;…; } (6)

в которой = q , р _n = q , p_j = q+ q.

По лемме 2: =0, =1.

={;…;;;;…; }, следовательно, C = C + p_j (7) если p_j = q+q. (8)

Так как схема σ _n-1 ─ схема оптимального кодирования, то

C C (9)

Получим C = C + и в силу неравенства (9):

C = C + C += C . Так как ─ оптимальна, то оптимальна и .Что и требовалось доказать.

Дата добавления: 2014-01-06