62523 (Коды без памяти. Коды Хаффмена. Коды с памятью), страница 2

Объединяя эти кодовые слова вместе, имеем выходную последовательность кодера:

B(X) = ( 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0 ).

Можно проверить, что энтропия H(X) исходного вектора X равна 0.9887 бит/букву, а степень сжатия, получаемая в результате использования блочного кода R(X) = 12/16 = 0.75 бит на выборку данных, оказалась меньше нижней границы энтропии. Полученный результат, казалось бы, противоречит теореме Шеннона, утверждающей, что невозможно достичь средней длины кода, меньшей энтропии источника. Однако на самом деле это не так. Если внимательно посмотреть на вектор данных X, то можно заметить закономерность: за символом 0 чаще следует 1, то есть условная вероятность Р(1/0) существенно больше, чем просто Р(0). Следовательно, энтропию этого источника нужно считать как энтропию сложного сообщения, а она, как известно, всегда меньше, чем для источника простых сообщений.

Код с конечной памятью при кодировании вектора данных ( X₁, X₂, ..., X_n ) использует кодовую книгу, состоящую из нескольких различных кодов без памяти. Каждая выборка данных кодируется кодом без памяти из кодовой книги, определяемым значением некоторого числа предыдущих выборок данных.

В качестве примера кодирования кодом с памятью рассмотрим уже упоминавшийся ранее классический пример X = ABRACADABRA. В этой последовательности совершенно очевидна сильная статистическая зависимость между ее очередными символами, которая должна обязательно учитываться при выборе метода кодирования.

Кодер с памятью при кодировании текущего символа учитывает значение предшествующего ему символа. Таким образом, кодовое слово для текущего символа A будет различным в сочетаниях RA, DA и CA (иными словами, код обладает памятью в один символ источника) (табл. 2).

Таблица 2

Результат кодирования - вектор B(X) = (10111011111011) длиной в 11 бит и скоростью сжатия R = 13/11=1,18 бита на символ данных, тогда как при кодировании равномерным трехразрядным кодом с R = 3 понадобилось бы 33 бита.

ЛИТЕРАТУРА

1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с.

2. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Федоров и др. – М.: Высшая школа, 2001 г. – 383с.

3. Цапенко М.П. Измерительные информационные системы. – М.: Энергоатом издат, 2005. - 440с.

4. Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с.

5. Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.