Методы эффективного кодирования при неизвестной статистике сообщений

Коды, экономичные одновременно для некоторого класса источников, называют универсальными кодами. Сформулируем постановку задачи универсального кодирования источников. Предположим, что алфавит состоит из двух букв a₁ и a₂, появляющихся независимо с вероятностями p, q=1- p. Однако величина pзаранее неизвестна. Требуется построить код, для которого среднее число символов «0» и «1» на одну букву алфавита приближалось бы к H(A) при любом p, 0<= p <=1. Этот код строится так. Множество всех блоков длины n в алфавите A разбиваем на группы, которые имеют одинаковые вероятности при любом р. Таких групп будет ровно n+1. В нулевой группе отсутствует буква a₂, она состоит из единственного блока а₁а₁... а₁, вероятность появления которого рⁿ.

Первая группа состоит из всех блоков длины n, содержащих одну букву а₂. Эта группа состоит из С_п¹=п блоков, вероятность каждого из которых равна р^n-1 q. Группа с номером k состоит из всех блоков длины п, содержащих k букв a₂. Эта группа содержит п блоков, вероятность каждого из которых р^n-k <q^k.

Универсальный код для k -й группы состоит из двух частей: префикса и суффикса. Префикс содержит log₂(n +1) двоичных знаков. Префикс указывает, к какой группе сообщений при­надлежит кодируемый блок, суффикс содержит log C_n ^k двоичных символов и указывает номер блока в группе. Построенный таким образом код будет однозначно дешифруем. На приемном конце первоначально по log(n +1) элементам кода определяют, к какой группе принадлежит переданное сообщение, а затем по следующим log C_n ^k элементам определяют, какое именно сообщение передавалось.

Код 1 в таблице 7 построен описанным выше способом. Здесь выделены штриховой линией префиксы. Этот метод кодирования называется комбинаторным.

Префикс каждой из групп при комбинаторном кодировании содержит ровно log(n +1) символов «0» и «1». Еще большего эффекта можно достичь, если префикс кодировать неравномерным кодом (Рисунок 1). Код 2 в таблице 7 построен именно этим методом. Универсальные методы кодирования хороши не только тем, что они экономичны для любого распределения вероятностей, но и достаточно просто реализуются. Для универсального кодирования на передающем и приемном концах не обязательно знать таблицу, которая определяет кодирование.

Код каждого блока вычисляется по мере поступления на кодирующее устройство букв а₁ и а₂. На приемном конце также можно декодировать, не прибегая к таблицам. При этом число операций на кодирование и декодирование блока длины п не превосходит п³.

Таблица 7 - Кодирование при неизвестной статистике сообщений

Из приведенного выше описания метода кодирования видно, наиболее трудоемкой частью кодирования является нахождение суффикса. Опишем алгоритм нахождения суффикса. Пусть в блоке А длины п буква а₁ встречается на местах i₁, i₂, …, i_r, тогда суффиксом для А назовем число N(A), вычисляемое по пра­вилу:

(9)

Очевидно, что блоки с разными наборами (i₁, …, i_r) получают разные номера. При этом максимальное значение номера равно

(10)

Таким образом, двоичная запись номера (суффикса) должна иметь длину | log C_n^r |.

Для нахождения N(A) воспользуемся таблицей биноминальных коэффициентов (треугольником Паскаля):

Элементы этой таблицы вычисляются по мере надобности либо размещаются в памяти кодирующего устройства.

Приведем фрагмент этой таблицы, в которой на пересечении i-й строки и j-го столбца стоит .

Пример 3. Пусть n =8, A=a₂a₁a₁a₂a₁a₁a₂a₁ тогда r =5; i₁ =2, i₂ =3, i₃ =5, i₄ =6, i₅ =8.
Тогда номер блока N(A) =С₁¹+С₂²+С₄³+С₅⁴+С₇⁵. Слагаемые в N(А) находим, используя таблицу дополнительных коэффициентов. Они выделены жирным шрифтом. Таким образом, N (А) =1+1+4+5+21=32 или в двоичной записи N(А) =100000.

Декодирование производится с помощью этой же таблицы.

Пример 4. Пусть нам известно, что длина передаваемого блока равна 8, и что в блоке пять букв а₁ (количество букв в блоке находим по префиксу). Находим максимальное число в 5-м столбце, не превосходящее 32, это 21=С⁵_8-1, следовательно, i₅=8, находим разность 32—21=11. Находим далее ма­ксимальное число 4-го столбца, не превосходящее 11. Это 5=C⁴_6-1 т. е. i₄ =6. Аналогично находим i₃ =5, i₂ =3, i₁ =2. Следовательно, декодированное сообщение имеет вид

A=a₂a₁a₁a₂a₁a₁a₂a₁, т.е. совпадает с переданным.

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

Метод Хаффмена

Одним из часто используемых методов кодирования является так называемый метод Хаффмена. Данный метод кодирования, позволяющий значительно сжимать информацию и построенный на основе двоичных кодирующих деревьев был предложен Д. А. Хаффменом в 1952 году задолго до появления современного цифрового компьютера. Метод обладает высокой эффективностью, он и его многочисленные адаптивные версии лидируют среди методов, используемых в алгоритмах кодирования.

Пусть сообщения входного алфавита А = {а₁, а₂, …, а_k} имеют соответственно вероятности их появления р₁, р₂,..., р_k.

Тогда алгоритм кодирования Хаффмена состоит в следующем.

1) Сообщения располагаются в столбец в порядке убывания вероятности их появления.

2) Два самых маловероятных сообщения a_k-1, и а_k объединяем в одно сообщение b, которое имеет вероятность, равную сумме вероятностей сообще­ний a_k-1, а_k, т. е. p_k-1+p_k. В результате получим сообщения a₁, a₂, …, a_k-2, b, вероятности которых p₁, p₂, …, p_k-2, (p_k-1+p_k). Полученные сообщения вновь располагаем в порядке убывания вероятностей.

3) Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1.

4) Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые комбинации можно определить, приписывая левым ветвям объединения символ «1», а правым - «0». Впрочем, понятия «левые» и «правые» ветви в данном случае относительны.

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

Построение кода Хаффмена для восьми сообщений, появляющихся с вероятностями 0.2; 0.2; 0.15; 0.13; 0.12; 0.1; 0.07; 0.03, иллюстрируется таблицей 8 и рисунком 5.

Таблица 8 - Кодирование методом Хаффмена

Из точки, соответствующей сумме всех вероятностей (в данном случае она равна 1), направляются две ветви. Ветви с большей вероятностью присваивается единица, с меньшей - нуль. Продолжая последовательно разветвлять дерево, доходим до вероятности каждого символа (Рисунок 3).

		Рисунок 3 – Кодовое дерево кода Хаффмена

Из таблицы 9 видно, что полученный код является неравномерным, причем сообщению с максимальной вероятностью появления соответствует минимальная длина кодовой комбинации (2 бита), а сообщению с минимальной
вероятностью - максимальная (4 бита).

Таблица 9 - Полученный код

Пусть переданная последовательность сообщений а₁, а₂, а₃, а₄, а₈ отображается двоичной последовательностью

Рассмотрим влияние одиночной ошибки во втором разряде принятой кодовой последовательности на результат декодирования. При этом получим

Полученная последовательность расшифровывается следующим образом

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

Среднее число двоичных символов l на одно сообщение алфавита объемом К, для неравномерных двоичных кодов, определяется выражением

(14)

Эффективность неравномерных кодов оценивается следующими параметрами:

1) коэффициентом статистического сжатия, который характеризует уменьшение числа двоичных символов на знак при применении методов эффективного кодирования по сравнению с применением равномерного кода:

(15)

где l_p.k - средняя длина кодовой комбинации при равномерном кодировании;

2) коэффициентом относительной эффективности, который показывает степень близости средней длины кодовой комбинации к теоретически возможному пределу Н(А):

(16)

Поиск по сайту: