Кодирование целых чисел

Рассмотрим семейство методов кодирования, не учитывающих вероятности появления символов источника. Поскольку все символы алфавита источника можно пронумеровать, то в будем считать, что алфавит источника состоит из целых чисел. Каждому целому числу из определенного диапазона ставится в соответствие свое кодовое слово, поэтому эту группу методов также называют представлением целых чисел (representation of integers).

Основная идея кодирования состоит в том, чтобы отдельно кодировать порядок значения числа («экспоненту» ) и отдельно – значащие цифры числа («мантиссу» ). Значащие цифры мантиссы начинаются со старшей ненулевой цифры, а порядок числа определяется позицией старшей ненулевой цифры в двоичной записи числа. Как и при десятичной записи, порядок равен числу цифр в записи числа без предшествующих незначащих нулей.

Пример. Порядок двоичного числа 000001101 равен 4, а мантисса – 1101.

В этой главе будут рассмотрены две группы методов кодирования целых чисел. Условно их можно обозначить так:

· Fixed + Variable (фиксированная длина экспоненты + переменная длина мантиссы)

· Variable + Variable (переменная длина экспоненты + переменная длина мантиссы)

1.1 Коды класса Fixed + Variable

В кодах класса Fixed + Variable под запись значения порядка числа отводится фиксированное количество бит, а значение порядка числа определяет, сколько бит потребуется под запись мантиссы. Для кодирования целого числа необходимо произвести с числом две операции: определение порядка числа и выделение бит мантиссы (можно хранить в памяти готовую таблицу кодовых слов). Рассмотрим процесс построения кода данного класса на примере.

Пример. Пусть R = 15 – количество бит исходного числа. Отведем E = 4 бита под экспоненту (порядок), т.к. R≤2⁴. При записи мантиссы можно сэкономить 1 бит: не писать первую единицу, т.к. это всегда будет только единица. Таким образом, количество бит мантиссы меньше на один бит, чем количество бит для порядка.

Таблица 1 Код класса Fixed + Variable

1.2 Коды класса Variable + Variable

В качестве кода числа берется двоичная последовательность, построенная следующим образом: несколько нулей (количество нулей равно значению порядка числа), затем единица как признак окончания экспоненты переменной длины, затем мантисса переменной длины (как в кодах Fixed + Variable). Рассмотрим пример построения кода этого класса.

Таблица 2 Код класса Variable + Variable

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

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

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

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

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

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

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

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

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

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

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

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

000000 1 00000 1 0000000 1 1 00000000 1

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

7 6 8 1 9 Þ 00111 00110 0001000 1 0001001

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

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

2. Некоторые теоремы ПОБУКВЕННОГО кодирования

В этом параграфе приведены некоторые теоремы о свойствах побуквенного кодирования.

Пусть даны алфавит источника , кодовый алфавит . Обозначим множество всевозможных последовательностей в алфавите А (В). Множество всех сообщений в алфавите А обозначим S. Кодирование может сопоставлять код всему сообщению из множества S как единому целому или строить код сообщения из кодов его частей (побуквенное кодирование).

Пример 1 А={a₁,a₂,a₃}, B={0,1} Побуквенное кодирование символов источника a₁ ®1001 a₂ ®0 a₃®010

позволяет следующим образом закодировать сообщение

a₂a₁a₂a₃ ® 010010010

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

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

Побуквенное кодирование задается таблицей кодовых слов: , , . Множество кодовых слов V={β_i} называется множеством элементарных кодов. Используя побуквенное кодирование, можно закодировать любое сообщение следующим образом ,т.е. общий код сообщения складывается из элементарных кодов символов входного алфавита.

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

Побуквенный код называется разделимым (или однозначно декодируемым), если любое сообщение из символов алфавита источника, закодированное этим кодом, может быть однозначно декодировано, т.е. если β_i1 …β_ik=β_j1…β_jt , то k=t и при любых s=1,…,k i_s=j_s . При разделимом кодировании любое кодовое слово единственным образом разлагается на элементарные коды.

Пример. 3 Код из примера 1 не является разделимым, поскольку кодовое слово 010010 может быть декодируемо двумя способами: a₃a₃ или a₂a₁a₂.

Побуквенный код называется префиксным, если в его множестве кодовых слов ни одно слово не является началом другого, т.е. элементарный код одной буквы не является префиксом элементарного кода другой буквы.

Пример 4. Код из примера 1 не является префиксным, поскольку элементарный код буквы a₂является префиксом элементарного кода буквы a₃.

Утверждение. Префиксный код является разделимым.

Доказательство(от противного). Пусть префиксный код не является разделимым. Тогда существует такая кодовая последовательность β, что она представлена различными способами из элементарных кодов: (побитовое представление одинаковое) и существует L такое, что при любом следует (β_is=β_js) и (β_it≠β_jt), т.е. начало каждого из этих представлений имеет одинаковую последовательность элементарных кодов. Уберем эту часть. Тогда , т.е. последовательности элементарных кодов разные и существует β^/, что β_iL=β_jLβ^/ или β_jL=β_iLβ^/ , т.е. β_iL – начало β_jL, или наоборот. Получили противоречие с префиксностью кода.

Заметим, что разделимый код может быть не префиксным.

Пример 5.Разделимый, но не префиксный код: A={a,b}, B={0,1},

Приведем основные теоремы побуквенного кодирования.

Теорема (Крафт). Для того, чтобы существовал побуквенный двоичный префиксный код с длинами кодовых слов L₁,…,L_n необходимо и достаточно, чтобы

.

Доказательство.Докажем необходимость. Пусть существует префиксный код с длинами L₁,…,L_n. Рассмотрим полное двоичное дерево. Каждая вершина закодирована последовательностью нулей и единиц (как показано на рисунке).

Рисунок 2 Полное двоичное дерево с помеченными вершинами

В этом дереве выделим вершины, соответствующие кодовым словам. Тогда любые два поддерева, соответствующие кодовым вершинам дерева, не пересекаются, т.к. код префиксный. У i-того поддерева на r-том уровне – 2^r-Li вершин. Всего вершин в поддереве 2^r. Тогда , , .

Докажем достаточность утверждения. Пусть существует набор длин кодовых слов такой, что . Рассмотрим полное двоичное дерево с помеченными вершинами. Пусть длины кодовых слов упорядочены по возрастанию L₁≤ L₂≤ … ≤ L_n. Выберем в двоичном дереве вершину V₁ на уровне L₁. Уберем поддерево с корнем в вершине V₁. В оставшемся дереве возьмем вершину V₂ на уровне L₂и удалим поддерево с корнем в этой вершине и т.д. Последовательности, соответствующие вершинам V₁, V₂,…, V_n образуют префиксный код. Теорема доказана.

Пример 6. Построить префиксный код с длинами L₁=1, L₂=2, L₃=2 для алфавита A={a₁,a₂,a₃}. Проверим неравенство Крафта для набора длин

.

Неравенство выполняется и, следовательно, префиксный код с таким набором длин кодовых слов существует. Рассмотрим полное двоичное дерево с 2³ помеченными вершинами и выберем вершины дерева, как описано выше. Тогда элементарные коды могут быть такими: a₁ ®0, a₂®10, a₃ ®11.

Рисунок 3 Построение префиксного кода с заданными длинами

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

Теорема (МакМиллан). Для того чтобы существовал побуквенный двоичный разделимый код с длинами кодовых слов L₁,…,L_n , необходимо и достаточно, чтобы .

Доказательство.Покажем достаточность. По теореме Крафта существует префиксный код с длинами L₁,…,L_n, и он является разделимым.

Докажем необходимость утверждения. Рассмотрим тождество

Положим . Тогда тождество можно переписать следующим образом

,

где , – число всевозможных представлений числа j в виде суммы . Сопоставим каждому представлению числа j в виде суммы последовательность нулей и единиц длины j по следующему правилу

,

где b_s – элементарный код длины s. Тогда различным представлениям числа j будут соответствовать различные кодовые слова, поскольку код является разделимым. Таким образом, и . Используя предельный переход получим при . Теорема доказана.

Пример 7. Азбука Морзе – это схема алфавитного кодирования

A®01, B®1000, C®1010, D®100, E®0, F®0010, G®110, H®0000, I®00, J®0111, K®101, L®0100, M®11, N®10, O®111, P®0110, Q®1101, R®010, S®000, T®1, U®001, V®0001, W®011, X®1001, Y®1011, Z®1100.

Неравенство МакМиллана для азбуки Морзе не выполнено, поскольку

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

3. оптимальное ПОБУКВЕННОЕ кодирование

3.1 Основные понятия

При кодировании сообщений считается, что символы сообщения порождаются некоторым источником информации. Источник считается заданным полностью, если дано вероятностное описание процесса появления сообщений на выходе источника. Это означает, что в любой момент времени определена вероятность порождения источником любой последовательности символов Р(x₁x₂x₃...x_L), L≥1. Такой источник называется дискретным вероятностным источником.

Если вероятностный источник с алфавитом А={a₁, a₂, ..., a_n}порождает символы алфавита независимо друг от друга, т.е. знание предшествующих символов не влияет на вероятность последующих, то такой источник называется бернуллиевским. Тогда для любой последовательности x₁x₂...x_L, L≥1, порождаемой источником, выполняется равенство:

P(x₁x₂...x_L ) = P(x₁)·P(x₂)·...·P(x_L),

где P(x) – вероятность появления символа х, Р(x₁x₂x₃...x_L) – вероятность появления последовательности x₁x₂x₃...x_L.

Для другого класса источников (марковских) существует статистическая взаимосвязь между порождаемыми символами. В дальнейшем мы будем рассматривать кодирование стационарных (с неизменным распределением вероятностей) бернуллиевских дискретных источников без памяти.

Пусть имеется дискретный вероятностный источник без памяти, порождающий символы алфавита А={a₁,…,a_n} с вероятностями , . Основной характеристикой источникаявляется энтропия, которая представляет собой среднее значение количества информации в сообщении источника и определяется выражением (для двоичного случая)

.

Энтропия характеризует меру неопределенности выбора для данного источника.

Пример. Если А={a₁,a₂}, p₁=0, p₂ =1, т.е. источник может породить только символ a₂, то неопределенности нет, энтропия H(p₁,p₂)=0.

Источник с равновероятными символами А={a₁,a₂}, p₁ =1/2, p₂ =1/2, будет иметь максимальную энтропию H(p₁,p₂)=1.

Величина называется энтропией на символ последовательности длины L, где A^L - множество всех последовательностей длины Lв алфавитеA, x=(x₁,x₂,...,x_L)-последовательность Lбукв дискретного cтационарного источника. Обозначим через предел энтропии H_Lпри L® ¥. Эту величину называют предельной энтропией источника.Показано, что для стационарного бернуллиевского источника

.

Для практических применений важно, чтобы коды сообщений имели по возможности наименьшую длину. Основной характеристикой неравномерного кода является количество символов, затрачиваемых на кодирование одного сообщения. Пусть имеется разделимый побуквенный код для источника, порождающего символы алфавита А={a₁,…,a_n} с вероятностями p_i =P(a_i), состоящий из n кодовых слов с длинами L₁,…,L_n в алфавите {0,1}. Средней длиной кодового слова называется величина , которая показывает среднее число кодовых букв на одну букву источника.

Пример. Пусть имеются два источника с одним и тем же алфавитом А={a₁,a₂,a₃} и разными вероятностными распределениями P₁={1/3, 1/3, 1/3}, P₂={1/4, 1/4, 1/2}, которые кодируются одним и тем же кодом

.

Средняя длина кодового слова для разных источников будет различной

L_ср(P₁)=1/3^.2 + 1/3^.3 + 1/3^.2= 7/3 ≈2.33

L_ср(P₂)=1/4^.2 + 1/4^.3 + 1/2^.2= 9/4 =2.25

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

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

.

Избыточность кода является показателем качества кода, оптимальный код обладает минимальной избыточностью. Задача эффективного неискажающего сжатия заключается в построении кодов с наименьшей избыточностью, у которых средняя длина кодового слова близка к энтропии источника. К таким кодам относятся классические коды Хаффмана, Шеннона, Фано, Гилберта-Мура и арифметический код.

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

Теорема 1(Шеннон). Для источника с алфавитом А={a₁,…,a_n} и вероятностями p_i =P(a_i), и любого разделимого побуквенного кода средняя длина кодового слова всегда не меньше энтропии

L_cp ≥ H(p₁,…,p_n)

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

L_cp < H(p₁,…,p_n)+1

Можно получить более сильные результаты, если кодовые слова приписывать не отдельными буквами, а блоками из L букв источника. Так, для неравномерных блоковых кодов справедлива следующая теорема.

Теорема 2. Пусть H_L - энтропия на букву в блоке длины L дискретного источник. Тогда существует префиксный код для кодирования блоков длины L, такой, что средняя длина кодового слова L_cp будет удовлетворять неравенствам:

.

Кроме того, в случае бернуллиевского стационарного источника для любогоe>0 можно выбрать достаточно большое L, чтобы величина L_cp удовлетворяла неравенствам:

,

и левое неравенство для L_cp никогда не нарушается для разделимого кода.

Приведем некоторые свойства, которыми обладает любой оптимальный побуквенный код.

Лемма 1. Для оптимального кода с длинами кодовых слов L₁,…,L_n: верно соотношение L₁≤L₂≤…≤L_{n ,} если p₁≥p₂≥…≥p_n.

Доказательство (от противного): Пусть есть i и j, что L_i>L_j при p_i>p_j. Тогда

L_ip_i+L_jp_j=

=L_ip_i+L_jp_j+L_ip_j+L_jp_i-L_ip_j-L_jp_i=

=p_i(L_i-L_j)-p_j(L_i-L_j)+L_jp_i+L_ip_j=

=(p_i-p_j)(L_i-L_j) +L_ip_j+L_jp_i>L_ip_j+L_jp_i,

т.е. если поменяем местами L_i и L_j, то получим код, имеющий меньшую среднюю длину кодового слова, что противоречит с оптимальности кода. Лемма 1 доказана.

Лемма 2 Пусть – схема оптимального префиксного кодирования для распределения вероятностей Р, . Тогда среди элементарных кодов, имеющих максимальную длину, существуют два, которые различаются только в последнем разряде.

Доказательство. Покажем, что в оптимальной схеме кодирования всегда найдется два кодовых слова максимальной длины. Предположим обратное. Пусть кодовое слово максимальной длины одно и имеет вид , . Тогда длина любого элементарного кода не больше длины b, т.е. , . Поскольку схема кодирования префиксная, то кодовые слова не являются префиксом b. С другой стороны, b не является префиксом кодовых слов . Таким образом, новая схема кодирования также является префиксной, причем с меньшей средней длиной кодового слова , что противоречит оптимальности исходной схемы кодирования. Пусть теперь два кодовых слова и максимальной длины отличаются не в последнем разряде, т.е. , , , . Причем , не являются префиксами для других кодовых слов и наоборот. Тогда новая схема также является префиксной, причем , что противоречит оптимальности исходной схемы кодирования. Лемма 2 доказана.

3.2 Оптимальный код Хаффмана

Метод оптимального побуквенного кодирования был разработан в 1952 г. Д. Хаффманом. Оптимальный код Хаффмана обладает минимальной средней длиной кодового слова среди всех побуквенных кодов для данного источника с алфавитом А={a₁,…,a_n} и вероятностями p_i =P(a_i).

Рассмотрим алгоритм построения оптимального кода Хаффмана, который основывается на утверждениях лемм предыдущего параграфа.

1. Упорядочим символы исходного алфавита А={a₁,…,a_n} по убыванию их вероятностей p₁≥p₂≥…≥p_n.

2. Если А={a₁,a₂}, то a₁®0, a₂®1.

3. Если А={a₁,…,a_j,…,a_n} и известны коды <a_j ® b_j >, j = 1,…,n, то для алфавита {a₁,…a_j^/, a_j^//…,a_n} с новыми символами a_j^/ и a_j^// вместо a_j, и вероятностями p(a_j)=p(a_j^/)+ p(a_j^//), код символа a_j заменяется на коды a_j^/ ® b_j0, a_j^// ®b_j1.

Пример. Пусть дан алфавит 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.

Здесь символы источника уже упорядочены в соответствии с их вероятностями. Будем складывать две наименьшие вероятности и включать суммарную вероятность на соответствующее место в упорядоченном списке вероятностей до тех пор, пока в списке не останется два символа. Тогда закодируем эти два символа 0 и 1. Далее кодовые слова достраиваются, как показано на рисунке 4.

a₁ 0.36 0.36 0.36 0.36 0.64 0

a₂ 0.18 0.18 0.28 0.36 0.36 1

a₃ 0.18 0.18 0.18 0.28 00

a₄ 0.12 0.16 0.18 000 01

a₅0.09 0.12 010 001

a₆0.07 0100 011

0101

Рисунок 4 Процесс построения кода Хаффмана

Таблица 5 Код Хаффмана

Посчитаем среднюю длину, построенного кода Хаффмана

L_ср(P)=1^.0.36 + 3^.0.18 + 3^.0.18 + 3^.0.12 + 4^.0.09 + 4^.0.07 =2.44,

при этом энтропия данного источника

H(p₁,…,p₆)= − 0.36^.log0.36 − 2^.0.18^.log0.18 −

− 0.12^.log0.12 − 0.09^.log0.09 − 0.07log0.07=2.37

Рисунок 5 Кодовое дерево для кода Хаффмана

Код Хаффмана обычно строится и хранится в виде двоичного дерева, в листьях которого находятся символы алфавита, а на «ветвях» – 0 или 1. Тогда уникальным кодом символа является путь от корня дерева к этому символу, по которому все 0 и 1 собираются в одну уникальную последовательность (рис. 5).