Основы эффективного кодирования

Задача статистического кодирования, которую часто приходится решать в технике документальной электросвязи формулируется следующим образом. Пусть имеется сообщение, записанное с помощью букв некоторо­го алфавита A={a₁,a₂,...,a_к}, содержащего К букв. Алфавит А назовем входным. Требуется закодировать это сообщение, т. е. указать правило, которое сопоставляет каждой букве алфавита последовательность из символов «0» и «1». Выбранный код, во-первых, должен обеспечивать возможность однозначного декоди­рования, т. е. позволять по принятой последовательности симво­лов «0» и «1» однозначно восстановить переданное сообщение (букву). Во-вторых, на передачу сообщения в среднем должно быть затрачено минимальное число нулей и единиц, что позволит передать за единицу времени максимальное число сообщений.

 

Таблица 2.1.

A	Код 1	Код 2	Код З
a1
a2
a3

 

Пример 1. Пусть A={a₁, а₂, a₃}. Некоторые возможные коды для букв алфавита А представлены в табл.1.

Код 1 не является однозначно декодируемым кодом. Для доказательства этого рассмотрим, например, двоичную последовательность 0101. Она может быть декодирована одним из сообщений: а₂а₁а₂a₁; а₃a₃; а₂a₁а₃; a₃a₂a₁. Код 2 де­кодируется однозначно, поскольку все кодовые слова этого кода имеют равные длины и различны. Код 3 также однозначно декодируемый, поскольку никакое его кодовое слово не является началом {префиксом} другого кодового слова.

Код, обладающий тем свойством, что никакое более короткое слово не является началом другого более длинного слова кода, называют префиксным. Префиксные коды всегда однозначно де­кодируемы.

Кодовое дерево для множества кодовых слов. Наглядное гра­фическое изображение множества кодовых слов можно получить, установив соответствие между сообщениями и концевыми узлами двоичного дерева. Пример двоичного дерева изображен на рис. 1. Две ветви, идущие от корня дерева к узлам первого по­рядка, соответствуют выбору между «0» и «1» в качестве перво­го символа кодового слова: левая ветвь соответствует «0», а пра­вая—«1». Две ветви, идущие из узлов первого порядка, соот­ветствуют второму символу кодовых слов, левая означает «0», а правая—«1» и т. д. Ясно, что последовательность символов каждого кодового слова определяет необходимые правила про­движения от корня дерева до концевого узла, соответствующего рассматриваемому сообщению.

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

Рис.2.1 Пример двоичного кодового дерева	Рис.2.2 Кодовые деревья для кодов 2(а) и 3 (б)

Требование, чтобы только концевые узлы сопоставлялись со­общениям, эквивалентно условию, чтобы ни одно из кодовых слов не совпало с началом (префиксом) более длинного кодового сло­ва. Любой код, кодовые слова которого соответствуют различным концевым вершинам некоторого двоичного дерева, является пре­фиксным, т. е. декодируемым.

На рис. 2.2 изображены кодовые деревья, соответствующие кодам 2 и 3 (см. табл. 2.1).

Вернемся к рассмотренному ранее примеру 1. Пусть веро­ятность появления в сообщении буквы a₁ равна 0,2; буквы a₂ — 0,3; a₃—0,5. Тогда среднее число двоичных символов, приходя­щихся на одну букву для кода 3 составляет 0,2*1+0,3*2+0,5*3=2,3, а для кода 2-0,2*2+0,3*2+0,5*2= 2,0, т. е. код 2 в сред­нем экономичнее кода 3.

Рассмотрим еще один код—код 4, который букве a₁ ставит в соответствие 10; a₂ — 11; a₃—0. Среднее число двоичных сим­волов, приходящихся на одну букву этого кода: 0,2*2+0,3*2+0,5*1 =1,5, т. е. код 4 экономичнее и кода 3, и кода 2. Спра­шивается, можно ли предложить код, который будет экономичнее кода 4? Как построить самый экономичный код для данного со­общения? Ответы на эти и многие другие вопросы дает основная теорема кодирования, сформулированная и доказанная впервые К. Шенноном.

Пусть буквы a _i, i= , входного алфавита А порождаются независимо с вероятностью p_i, т. е. р(а_i)=р_i, некоторым источни­ком сообщений. Количество информации, приходящееся на сооб­щение a_i, равно—log₂p_i. Среднее количество информации в битах на одно сообщение (букву) обозначается Н(А) и называет­ся энтропией источника сообщений

(2.1)

Энтропию Н(А) можно рассматривать как меру «неопределенно­сти» сообщения до того, как оно было принято.

В приведенной ниже основной теореме кодирования устанав­ливается связь между Н(А) и средним числом символов «0» и «1» в кодовом слове.

Теорема 1. Для любого однозначно декодируемого кода всег­да выполняется неравенство ³H(A) и существует однозначно декодируемый код, для которого выполняется неравенство <H(A)+1.

Теорема 1 имеет глубокий смысл. В частности, из нее сле­дует, что нельзя закодировать сообщение таким образом, чтобы средняя длина кодовых слов была меньше, чем энтропия сообще­ний. Кроме того, теорема утверждает, что существует кодирова­ние, при котором средняя длина кодового слова немногим отли­чается от энтропии сообщения. Покажем, что среднее число сим­волов на сообщение можно уменьшить, если кодировать не каждую букву в отдельности, а блоки по п букв из алфавита А. Пусть буквы алфавита А появляются независимо с вероятностя­ми р₁,...,р_K. Множество всех блоков длины п в алфавите А обо­значим Aⁿ. Как хорошо известно,

H(Aⁿ)=nH(A). (2.2)

Обозначим среднее число «0» и «1», приходящихся на один блок из п букв, взятых из алфавита A, через _n. Тогда среднее число символов, приходящихся на одну букву алфавита, опреде­ляется формулой

= _n/n (2.3)

Теорема 2. При любом сколь угодно малом положительном eможно найти натуральное число N, такое, что среднее число сим­волов на одно сообщение при n >N удовлетворяет неравенству

<H(A)+e (2.4)

Наоборот невозможно найти натуральное число N и одно­значно декодируемый код, такие, чтобы выполнялось неравенство

<H(A). (2.5)

Доказательство. Эта теорема вытекает из теоремы 1. Под­ставляя в нее _n вместо , получаем

_n£H(Aⁿ)+1. (2.6)

Разделив (6) на n и учитывая (2) и (3), получим

H(A)£ <H(A)+1/n (2.7)

Из неравенства (7) следует неравенство (4), если положить n= 1/e.

В то же время неравенство (5) несовместимо с неравенством (7). Теорема доказана.

Из теоремы 2 следует, что, используя кодирование блоков, можно получить среднее число символов на сообщение (букву), сколь угодно мало отличающееся от энтропии, но при этом уве­личивается сложность кодирования.