yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->2.2.4  Метод блокирования сообщения. Блочный код Хаффмена

Теория информации

2.2.4  Метод блокирования сообщения. Блочный код Хаффмена

 

         В отличие от предыдущих методов кодирования информации блочные коды относятся к так называемым кодам с памятью, так как в данном случае при кодировании текущего символа учитываются значения одного или нескольких предыдущих символов.

         Блочный код делит вектор данных на блоки заданной длины и затем каждый блок заменяет кодовым словом из префиксного множества кодовых слов. Полученную последовательность кодовых слов объединяют в результирующую двоичную строку на выходе кодера.

         О блочном коде говорят, что он блочный код k-го порядка, если все блоки имеют длину k.

 

         Метод блокирования сообщений заключается в следующем.     

         По заданному e > 0 можем выбрать такое k, что если разбить все сообщения на блоки длиной k (всего будет n/k блоков), то, используя оптимальное статистическое кодирование таких блоков, принимаемых за единицу сообщения, можно добиться средней длины кода больше энтропии менее чем на e.

         Пусть X1, X2, …, Xn – независимые д.с.в., имеющие одинаковое распределение.  - кодируемое сообщение, где ,  ,  …,  - блоки сообщения.

         Тогда

 

                      .                                          (2.10)

 

         При использовании оптимального кодирования Шеннона-Фано и Хаффмена для векторной д.с.в.  справедливо неравенство

 

                      .                                             (2.11)

 

         Среднее количество битjd на единицу сообщения определяется как

 

                      .                                        (2.12)

 

         Тогда с учетом (2.10) и (2.12) неравенство (2.11) можно записать следующим образом:

 

                      .                                  (2.13)

 

Разделив обе части (2.13) на k, получаем

 

                      ,                                     (2.14)

 

т.е. достаточно брать .

 

Пример 1  Сожмем вектор данных X=(0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1), используя блочный код 2-го порядка.

 

         Разобьем вектор на блоки длины 2:  (01, 10, 10, 01, 11, 10, 01, 01).

         Будем рассматривать эти блоки как элементы нового «гипералфавита» {01, 10, 11}.

         Определим вектор частот появления блочных элементов в заданной последовательности. Получаем (4, 3, 1), т.е. наиболее часто встречается блок 01, затем 10 и наименее часто – блок 11; всего 8 блоков.

         Построим код Хаффмена для блоков символов, встречающихся в сообщении. Кодовое дерево данного кода представлено на рис. 2.8, таблица кодера – в таблице 2.5.

 

                                                                                                                                                                                        Таблица 2.5

Блок сообщения

Кодовое слово

01

0

10

10

11

11

                 

                  Рисунок 2.8                                  

 

         Заменяя каждый блок ему  соответствующим кодовым словом из таблицы кодера, получаем выходную последовательность

         Code(01, 10, 10, 01, 11, 10, 01, 01)= 010100111000.

        

         Энтропия исходного сообщения

 

                   (бит/сим).

          

         Скорость сжатия определяется как 

 

                  (бит/сим).

 

         Полученный результат оказывается меньше энтропии, что, казалось бы, противоречит теореме Шеннона. Однако это не так. Как видим из вектора исходных данных, символ 1 чаще следует 0, т.е. условная вероятность p(1/0) больше безусловной вероятности p(1), таким образом, прослеживается явно выраженная корреляция между этими двумя символами. Следовательно, энтропию этого источника нужно считать как энтропию статистически взаимосвязанных сообщений, а она меньше безусловной энтропии.   

 

Пример 2  Пусть д.с.в. X1, X2 Xn независимы, одинаково распределены и могут принимать только два значения 0 и 1 со следующими вероятностями: p(Xi=0)=3/4 и p(Xi=1)=1/4i=1…n.

 

         Тогда энтропия единицы сообщения

          (бит/сим).

Минимальное префиксное кодирование – это коды 0 или 1 длиной 1 бит.

Среднее количество битjd на единицу сообщения (бит/сим).

         Разобьём сообщение на блоки длины 2. Распределение вероятностей и кодирование двумерной д.с.в. будет следующим (табл2.6).

Таблица 2.6

00

01

10

11

P

9/16

3/16

3/16

1/16

Префиксный код

0

10

110

111

1

2

3

3

 

         Среднее количество битов на единицу сообщения

 (бит/сим), т.е. меньше, чем при неблочном кодировании.

         Для блоков длины 3 количество битов в среднем на единицу сообщения  (бит/сим), для блоков длины 4 –   (бит/сим) и т.д.

 

         Формулы теоретических пределов сжатия задают предел для средней длины кода на единицу сообщения, на некоторых же сообщениях длина кода может быть меньше энтропии сообщения.

 

 

 

10