Коды Шеннона-Фано и Хаффмена. Достоинства и недостатки эффективного кодирования

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

Код по своему построению удовлетворяет свойству префикса. Поэтому вышеприведенная последовательность двоичных символов L декодируется однозначно . Средняя длина сообщения с учетом их вероятностей , т.е. незначительно превышает энтропию источника сообщений. На рис.4.2 приведен соответствующий граф кодового дерева.

Коды Хаффмапа

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

Лемма 4.1. Для любого заданного источника с буквами существует оптимальный двоичный код, в котором два наименее вероятных кодовых слова и имеют одну и ту же длину и отличаются лишь последним символом: оканчивается на 1, а - на 0, -множество двоичных кодовых слов

источника с вероятностями и для простоты

обозначений буквы упорядочены так, что -длины кодовых слов).

Для нахождения кодовой комбинации, соответствующей i-му знаку, необходимо проследить путь перехода знака по строкам и столбцам таблицы. Это наиболее наглядно осуществимо по кодовому дереву (рис. 4.3). Из точки, соответствующей вероятности 1. направляются две ветви, причем ветви с большей вероятностью присваиваем символ 1. ас меньшей - 0. Такое последовательное ветвление продолжается до тех пор. пока не дойдем до вероятности каждой буквы. Кодовое дерево для алфавита сообщений (табл. 4.4) приведено на рис. 4.3. Двигаясь по кодовому дереву сверху вниз, можно записать для каждого сообщения соответствующие ему кодовые комбинации (табл.4)

16. Сверточные коды: основные понятия и параметры, классификация

Сверточный кодер обычно представляется в виде регистра сдвига, и многие основные определения могут быть введены с использованием такой схемы. Рассмотрим кодер, представленный на рис.7.1. Информационная последовательность вводится в кодер, начиная с нулевого момента времени и до бесконечности. Поток входящих информационных символов разбивается на сегменты, которые содержат no k0 символов и называются кадрами ин-

формационных символов. Кадр информационных символов может, в частности, состоять из единственного символа, что нередко имеет место на практике. В кодере может храниться m кадров. Втечение каждого временного кадра в регистр сдвига вводится новый кадр информационных символов, а кадр информационных символов, дольше остальных хранившийся в нем, выводится из него и сбрасывается. В конце каждого временного кадра в кодере

хранятся последние m из поступивших в него кадров (всего mk0 информационных символов). В начале каждого временного кадра кодер по введенному кадру информационных символов и m хранящимся в нем кадрам вычисляет один кадр кодового слова, имеющий длину n0 символов. Этот кадр кодового слова выводится из кодера, как только поступает следующий кадр информационных символов. Следовательно, каждым k0 информационным символам

соответствуетпередачапоканалуn0 кодовых символов. Бесконечное множество всех бесконечно длинных кодовых слов, получаемых при поступлении в этот кодер всех возможных входных последовательностей, называется древовидным (n, k)-кодом.

Основными характеристиками сверточных кодов являются:

- k₀ – размер кадра информационных символов;

- n₀ – размер кадра кодовых символов;

- m – длина памяти кода;

- k = (m+1) ⋅ k₀ – информационная длина слова;

- n = (m+1) ⋅ n₀ – кодовая длина блока – это длина кодового слова, на которой сохраняется влияние одного кадра информационных символов;

- R = k/n – скорость, которая характеризует степень избыточности кода, вводимой для обеспечения справляющих свойств кода.

На рис.7.1. изображен кодер, у которого k₀ =3, n₀ =5,v=21, n=40. Кодовая длина блока - это длина кодового слова, на которой сохраняется влияние одного кадра информационных символов. Из соображений удобства реализации на практике значения n₀ и k₀ для древовидных кодов выбираются равными небольшим целым числам; в типичном случае k₀ равно единице. Это означает, что выбор скорости кода ограничен. Невозможно построить практический древовидный код со скоростью, очень близкой к единице.

17. Кодирование длин повторений

Кодирование длин участков (или повторений) может быть достаточно эффективным при сжатии двоичных данных, например, черно-белых факсимильных изображений, черно-белых изображений, содержащих множество прямых линий и однородных участков, схем и т.п. Кодирование длин повторений является одним из элементов известного алгоритма сжатия изображений JPEG.

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

Пример. Предположим, что нужно закодировать двоичное (двухцветное) изображение размером 8×8 элементов, приведенное на рис. 3.3. Просканируем это изображение по строкам (двум цветам на изображении будут соответствовать 0 и 1), в результате получим двоичный вектор данных

Х=(0011111000000100000010000001000000100000001000000010000000100000) длиной 64 бита (скорость исходного кода составляет 1 бит на элемент изображения).

Выделим в векторе X участки, на которых данные сохраняют неизменное значение, и определим их длины. Результирующая последовательность длин участков – положительных целых чисел, соответствующих исходному вектору данных X, - будет иметь вид r = (2,5,6,1,6,1,6,1,6,1,7,1,7,1,7,1,5).

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