Кодирование с минимальной избыточностью.

При равномерном кодировании общая длина кода зависит от длины сообщения. Возникает необходимость произвести неравномерное кодирование так, чтобы избыточность была минимальной.

Пусть задан алфавит А, и мы назначили неравномерные коды этому алфавиту. Например, букве А – 4 – битный код; Б – 6 – битный код; Ъ – 2 – битный код; О – 7 – битный код и так далее. Ясно, что в обычном тексте Ъ встречается реже буквы О, следовательно, если мы переназначим коды: О – 2 – битный код, Ъ – 7 – битный код, то общая длина кода уменьшится.

Алгоритм для сообщения S:

1) Находим частоту появления каждой буквы в заданном сообщении.

2) Элементарный код наименьшей длины ставим в соответствие букве с наибольшей частотой и так далее.

Замечание:

Этот кодирование применимо для данного сообщения S. Для другого сообщения частота появления букв может быть другой, следовательно, элементарные коды могут быть другими.

Префиксное кодирование.

Пусть имеется алфавит А. Таблица соответствия буквам алфавита А элементарных кодов, называется схемой кодирования.

Схема кодирования  называется префиксной, если не один элементарный код не является префиксом другого элементарного кода.

Например:

А={a,b}; B={0,1};

={ а 0; b 01} – не префиксная схема.

={ a 0; b 10} - префиксная схема.

Схема кодирования называется разделимой, если любой код однозначным образом разбивается на элементарные коды, то есть если код = , ,…, = , ,…, , то =  и k= , т.е. возможно однозначное декодирование.

Теорема. Префиксные схемы разделимы.

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

Пусть схема ={α_i β_i}|  префиксная, но неразделима. Это значит, что существует некоторое t такое, что = , = … = . Так как схема неразделима, то . А это значит, что есть такое , что или = , то есть элементарный код  содержит  и , а значит, является префиксом, следовательно, кодирование – не префиксное. Пришли к противоречию, означающее, что наше утверждение о неразделимости схемы  неверно, следовательно, схема разделима.

Что и требовалось доказать.

Замечание: утверждение о том, что если схема разделима, то она префиксная, неверно.

Пример:

А={a,b}; B={0,1};

: а 0; b 01 – схема не префиксная. Покажем, что она разделима.

 Сообщение ab 001. Будем декодировать. Первая цифра 0 может быть кодом буквы а, а может быть префиксом буквы b. Но следующая цифра тоже 0. Значит, первый 0 не является префиксом буквы b, т.е. это код буквы а. Если предположить, что второй 0. это код буквы а, то следующий код начинается с 1, а таких кодов у нас нет, и мы вынуждены признать, что имеем код 01, т.е. букву b. Таким образом, получили 001 ab;

Декодирование можно начать и с конца. Если последний символ 1, то рассмотрим предпоследний. Если он 0, то эти два символа соответствуют букве b. Если он 1, то кодирование произведено неверно. Исключаем из рассмотрения эти два символа. Следующий символ конца 0. А 0 – это а. Если у нас есть еще символы – продолжаем.

Еще пример. aabbaba 0001010010.

Первый символ 0. Это значит, что он может соответствовать а или являться префиксом b. Рассмотрим следующий. Если он 1, то первые два символа являются элементарным кодом b. После этого рассматриваем третий аналогично первому. Так как 2 – ой символ у нас 0, то первый символ – это элементарный код буквы а. Рассматриваем второй аналогично первому. И т.д. Замечание: кодирование произведено неверно, если код начинается с 1 или две 1 стоят подряд внутри кода.

Неравенство Макмиллана.

Пусть имеется разделимая схема ={ }|  и  - длина элементарного кода. =| |. Тогда        (1)

Неравенство Макмиллана позволяет установить будет ли имеющаяся схема кодирования разделимой (необходимое условие).

Пример:

Имеется схема кодирования – Азбука Морзе.

А – 01(точка, тире);                    =2;

Е – 0 (точка);                                =1;

Т – 1(тире);                                  =1 и так далее.

Проверим неравенство Макмиллана:

 +  +  + … =  + 1+…>1.

Вывод: схема кодирования неразделима. При фактическом использовании азбуки Морзе радист после каждой буквы делает паузу.

В некотором смысле условие (1) является достаточным. Если существует набор чисел  (i=1,…,n), удовлетворяющий условию (1), то существует разделимая схема кодирования ={ }| , для которой | |= .

Понятие вероятности.

 

Рассмотрим некоторое событие А. Пусть при выполнении комплекса условий возможно n исходов, из которых m – благоприятных для А. Тогда вероятностью события А р (А) назовем отношение числа исходов, благоприятствующих А, к общему числу исходов:

 р (А) = .

Ра практике часто пользуются статистической вероятностью. Если в n испытаниях событие А произошло m раз, то статистическая вероятность р (А) = . Отличие от предыдущей формулы заключается в том, что здесь n m фактические, а не гипотетические.

Пример.

 Пусть в алфавите А буква ю занимает третью позицию. Сообщение содержит n = 100 букв. Буква ю встречается в этом сообщении m₃ = 10 раз. Тогда вероятность появления буквы ю равна р₃ = m_{3 /} n = 10 / 100 = 0,01.

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

Пусть имеется некоторый алфавит А, и имеется некоторая схема кодирования , ={ }| . Пусть  - длина i – того элементарного кода. Пусть известны вероятности  вхождения i – той буквы алфавита А в сообщении, причем =1.

 Тогда ценой кодирования называется сумма произведений вероятностей на соответствующую длину кода:

С= .

 Цена кодирования выражает среднюю длину элементарного кода.

Пример: пусть заданы коды букв и вероятности их вхождения в сообщение.

а 0;     =0,6;

в 10;   =0,3;

с 11;   =0,1;

Заметим, что =1. Тогда С=0,6*1+0,3*2+0,1*2=1,4.