Файл: Методы кодирования данных.pdf

Если в рассмотренном выше коде исключить кодовое слово для нуля, то можно уменьшить длины кодовых слов на 1 бит, убрав первый нуль. Таким образом строится гамма-код Элиаса (γ-код Элиаса).

Таблица 3. Гамма-код Элиаса

Другим примером кода класса Variable + Variable является омега-код Элиаса (ω-код Элиаса). В нем первое значение (кодовое слово для единицы) задается отдельно. Другие кодовые слова состоят из последовательности групп длиной L₁,L₂.,…,L_m, начинающихся с единицы. Конец всей последовательности задается нулевым битом. Длина первой группы составляет 2 бита, длина каждой следующей группы равна двоичному значению битов предыдущей группы плюс 1. Значение битов последней группы является итоговым значением всей последовательности групп, то есть первые m-1 групп служат лишь для указания длины последней группы.

Таблица 4. Омега-код Элиаса

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

Рассмотренные типы кодов могут быть эффективны в следующих случаях

1. Вероятности чисел убывают с ростом значений элементов и их распределение близко к такому: Р(х)≥ Р(х+1), при любом x, то есть маленькие числа встречаются чаще, чем большие^[5].

2. Диапазон значений входных элементов не ограничен или неизвестен. Например, при кодировании 32-битовых чисел реально большинство чисел маленькие, но могут быть и большие.

3. При использовании в составе других схем кодирования, например, кодировании длин серий.

2.3. Кодирование длин серий

Метод кодирования информации, известный как метод кодирования длин серий и предложенный П.Элиасом, при построении использует коды целых чисел. Входной поток для кодирования рассматривается как последовательность из нулей и единиц^[6]. Идея кодирования заключается в том, чтобы кодировать последовательности одинаковых элементов (например, нулей) как целые числа, указывающие количество элементов в этой последовательности. Последовательность одинаковых элементов называется серией, количество элементов в ней – длиной серии.

Пример. Входную последовательность (общая длина 31 бит) можно разбить на серии, а затем закодировать их длины.

00000 1

Используем, например, γ-код Элиаса. Поскольку в коде нет кодового слова для нуля, то будем кодировать длину серии +1, то есть последовательность: Þ 00

Длина полученной кодовой последовательности равна 25 бит.

Метод длин серий актуален для кодирования данных, в которых есть длинные последовательности одинаковых бит. В нашем примере, если Р(0)>>Р(1).

3. НЕКОТОРЫЕ ТЕОРЕМЫ ПОБУКВЕННОГО КОДИРОВАНИЯ

Пусть даны алфавит источника А={а₁, а₂, …а_n}, кодовый алфавит В={b₁, b₂, …b_n}. Обозначим А^*(В^*) множество всевозможных последовательностей в алфавите А(В). Множество всех сообщений в алфавите А обозначим S. Кодирование F:S→ В^* может сопоставлять код всему сообщению из множества S как единому целому или строить код сообщения из кодов его частей (побуквенное кодирование).

Пример.

А={a1,a2,a3}, B={0,1}. Побуквенное кодирование символов источника a1 ®1001 a2 ®0 a3®010 позволяет следующим образом закодировать сообщение a2a1a2a3 ®

Пример.

Азбука Морзе. Входной алфавит – английский. Наиболее часто встречающиеся буквы кодируются более короткими словами:

А ® 01, В ® 1000, С ® 1010, D ® 100, E ® 0, …

Побуквенное кодирование задается таблицей кодовых слов: α_iєA, β_iєВ^*. Множество кодовых слов V={βi} называется множеством элементарных кодов. Используя побуквенное кодирование, можно закодировать любое сообщение α= α_il…α_ikєS следующим образом F(α)=F(α_il)…F(α_ik)=β_il…β_ik, то есть общий код сообщения складывается из элементарных кодов символов входного алфавита.

Количество букв в слове α=α1…αk называется длиной слова. (Обозначение |αا|=k) Пустое слово, то есть слово, не содержащее ни одного символа обозначается Λ. Если α=α1α2, то α1 – начало (префикс) слова α, α2 – окончание (постфикс) слова α.

4. ОПТИМАЛЬНОЕ ПОБУКВЕННОЕ КОДИРОВАНИЕ. КОД ХАФФМАНА

Предложенный Хаффманом алгоритм построения оптимальных неравномерных кодов – одно из самых важных достижений теории информации как с теоретической, так и с прикладной точек зрения. Трудно поверить, но этот алгоритм был придуман в 1952 г. студентом Дэвидом Хаффманом в процессе выполнения домашнего задания.

Рассмотрим ансамбль сообщений X={1,…,N} с вероятностями сообщений {P₁,…,P_N}. Без потери общности мы считаем сообщения упорядоченными по убыванию вероятностей, то есть P₁≤P₂≤ …≤P_N. Наша задача состоит в построении оптимального кода, то есть кода с наименьшей возможной средней длиной кодовых слов^[7]. Понятно, что при заданных вероятностях такой код может не быть единственным, возможно существование семейства оптимальных кодов. Мы установим некоторые свойства всех кодов этого семейства. Эти свойства подскажут нам простой путь к нахождению одного из оптимальных кодов.

Пусть двоичный код С={ć₁,Кć_n} с длинами кодовых слов {m₁,…,m_N} оптимален для рассматриваемого ансамбля сообщений.

Свойство 1. Если P_i<P_j, то m_i>m_j.

Свойство 2. Не менее двух кодовых слов имеют одинаковую длину m_max=max_k m_k.

Свойство 3. Среди кодовых слов длины m_max = max_k m_k найдутся 2 слова, отличающиеся только в одном последнем символе.

Прежде, чем сформулировать следующее свойство, введем дополнительные обозначения^[8]. Для рассматриваемого ансамбля X={1,…,N} и некоторого кода C, удовлетворяющего свойствам 1–3, введем вспомогательный ансамбль X’={1,…,N-1}, сообщениям которого сопоставим вероятности {P’₁,…,P’_N} следующим образом P₁¢=P₁K, P_N¢₂=P_N-2, P_N¢₁=P_N-1+P_N

Из кода C построим код C' для ансамбля X', приписав сообщениям {х₁¢К, х_N-2¢} те же кодовые слова, что и в коде C, а сообщению х_N-2¢ – слово ć_N-1, представляющее собой общую часть слов ć_N-1 и ć_N (согласно свойству 3 эти два кодовых слова отличаются только в одном последнем символе).

Свойство 4. Если код C' для X' оптимален, то код C оптимален для X.

Итак, сформулированные свойства оптимальных префиксных кодов сводят задачу построения кода объема N к задаче построения кодов объема N'=N-1. Это означает, что мы получили рекуррентное правило построения кодового дерева оптимального неравномерного кода.

5. ПОЧТИ ОПТИМАЛЬНОЕ КОДИРОВАНИЕ

5.1. Код Шеннона

Код Шеннона позволяет построить почти оптимальный код с длинами кодовых слов L_i<-log p_i+1. Тогда по теореме Шеннона L_cp<H(p₁,..., p_n)+1.

Код Шеннона, удовлетворяющий этому соотношению, строится следующим образом:

1. Упорядочим символы исходного алфавита А={a₁,a₂,…,a_n} по убыванию их вероятностей: p₁≥p₂≥p₃≥…≥p_n.
2. Вычислим величины Q_i, которые называются кумулятивные вероятности Q₀=0, Q₁=p₁, Q₂=p₁+p₂, Q₃=p₁+p₂+p₃, … , Q_n=1.
3. Представим Q_i в двоичной системе счисления и возьмем в качестве кодового слова первые /-log p_i / знаков после запятой^[9].

Для вероятностей, представленных в виде десятичных дробей, удобно определить длину кодового слова L_i из соотношения 1/2^L_i ≤ p_i<1/2^L_i-1, i=1,…n

Пример.

Пусть дан алфавит A={a₁,a₂,a₃,a₄,a₅,a₆} с вероятностями p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07. Построенный код приведен в таблице 5.

Таблица 5. Код Шеннона

Построенный код является префиксным. Вычислим среднюю длину кодового слова и сравним ее с энтропией. Значение энтропии вычислено при построении кода Хаффмана (H=2.37), сравним его со значением средней длины кодового слова кода Шеннона

L_ср= 0.36^.2+(0.18+0.18)^.3+(0.12+0.09+0.07)^.4=2.92< 2.37+1,

что полностью соответствует утверждению теоремы Шеннона.

5.2. Код Фано

Метод Фано построения префиксного почти оптимального кода, для которого L_cp<H(p₁,..., p_n)+1, заключается в следующем. Упорядоченный по убыванию вероятностей список букв алфавита источника делится на две части так, чтобы суммы вероятностей букв, входящих в эти части, как можно меньше отличались друг от друга^[10]. Буквам первой части приписывается 0, а буквам из второй части – 1. Далее также поступают с каждой из полученных частей. Процесс продолжается до тех пор, пока весь список не разобьется на части, содержащие по одной букве.

Пример.

Пусть дан алфавит A={a₁, a₂, a₃, a₄, a₅, a₆} с вероятностями p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07. Построенный код приведен в таблице 6 и на рисунке 2.

Таблица 6. Код Фано

Рисунок 2. Кодовое дерево для кода Фано

Полученный код является префиксным и почти оптимальным со средней длиной кодового слова L_ср=0.36^.2+0.18^.2+0.18^.2+0.12^.3+0.09^.4+0.07^.4=2.44