Лабораторная работа 2
Построение оптимального кода
Цели работы:
изучение основных принципов эффективного кодирования;
приобретение практических навыков построения оптимальных кодов (на примере кодов Шеннона-Фано и Хаффмана) и оценка их эффективности;
программная реализация оптимального кодирования.
Теоретические сведения
Оптимальным кодированием называется процедура преобразования символов первичного алфавита m1 в кодовые слова во вторичном алфавите m2, при которой средняя длина сообщений во вторичном алфавите имеет ми нимально возможную для данного m2 длину.
Оптимальными именуются коды, представляющие кодируемые поня тия кодовыми словами минимальной средней длины. Оптимальные коды от носятся к классу префиксных кодов, т. е. каждая кодовая комбинация имеет свою длину и ни одна не является началом другой, более длиной.
В сообщениях, составленных из кодовых слов оптимального кода, ста тистическая избыточность сведена к минимуму, в идеальном случае – к нулю.
Основная теорема кодирования для каналов связи без шумов доказыва ет принципиальную возможность построения оптимальных кодов. Из нее од нозначно вытекают методика построения и свойства оптимальных кодов.
Одно из основных положений этой теории заключается в том, что при кодировании сообщения, разбитого на N-буквенные блоки, можно, выбрав N достаточно большим, добиться, чтобы среднее число двоичных элементар ных сигналов, приходящихся на одну букву исходного сообщения, было сколь угодно близким к H / log m. Разность будет тем меньше, чем больше Н, а Н достигает максимума при равновероятных и взаимонезависимых символах. Отсюда вытекают основные свойства оптимальных кодов:
– минимальная средняя длина кодового слова оптимального кода обеспечи вается в случае, когда избыточность каждого кодового слова сведена к мини муму (в идеальном случае – к нулю);
– кодовые слова оптимального кода должны строиться из равновероятных и взаимонезависимых символов.
Из свойств оптимальных кодов вытекают принципы их построения:
– выбор каждого кодового слова необходимо производить так, чтобы содержа щееся в нем количество информации было максимальным;
– буквам пер вичного алфавита, имеющим большую вероятность, присваиваются более ко роткие кодовые слова во вторичном алфавите.
Принципы оптимального кодирования определяют методику построе ния оптимальных кодов. Построение оптимального кода по методу Шеннона-Фано для ансамбля из М сообщений сводится к следующей процедуре:
множество из М сообщений располагают в порядке убывания вероят ностей;
первоначальный ансамбль кодируемых сигналов разбивают на две группы таким образом, чтобы суммарные вероятности сообщений обеих групп были по возможности равны;
первой группе присваивают символ 0, второй – символ 1;
каждую из групп делят на две подгруппы так, чтобы их суммарные вероятности были по возможности равны;
первым подгруппам каждой из групп вновь присваивают 0, а вторым – 1, в результате получают вторые цифры кода;
каждую из четырех подгрупп вновь делят на равные (с точки зрения суммарной вероятности) ча сти до тех пор, пока в каждой из них не останется одна буква.
Пример. Построим оптимальный код для передачи сообщений, в кото рых вероятности появления букв первичного алфавиты равны:
А1 = 1/4, А2 = 1/4, А3 = 1/8, А4 = 1/8, А5 = 1/16, А6 = 1/16, А7 = 1/16, А8 = 1/16.
Решение. Построение ведем по общей методике. Оптимальный код для данных условий представлен в табл. 1.
Таблица 1
Бу ква
|
Вероят ность
появле ния буквы
|
Кодовое слово
после разбиения
|
Число
знаков в кодовом слове
|
L(i) pi
|
|
|
1-го
|
2-го
|
3-го
|
4-го
|
|
|
A1
|
1/4
|
0
|
0
|
|
|
2
|
0,5
|
A2
|
1/4
|
0
|
1
|
|
|
2
|
0,5
|
A3
|
1/8
|
|
0
|
0
|
|
3
|
0,375
|
|
1/8
|
|
0
|
1
|
|
3
|
0,375
|
|
1/16
|
|
1
|
0
|
0
|
4
|
0,25
|
A6
|
1/16
|
|
1
|
0
|
1
|
4
|
0,25
|
|
1/16
|
|
1
|
1
|
0
|
4
|
0,25
|
A8
|
1/16
|
|
1
|
1
|
1
|
4
|
0,25
|
Проверка оптимальности кода осуществляется путем сравнения энтро пии кодируемого (первичного) алфавита со средней длиной кодового слова во вторичном алфавите.
Для рассматриваемого примера энтропия источника сообщений:
 бит/символ
Среднее число двоичных знаков на букву кода:
 бит/символ,
где l(i) – длина i-й кодовой комбинации;
pi – вероятность появления i-го символа комбинации длиной в l(i).
Таким образом, H = L, т. е. код оптимален для данного ансамбля сооб щений.
Коды, представляющие первичные алфавиты с неравномерным распре делением символов, имеют минимальную среднюю длину кодового слова во вторичном алфавите. Максимально эффективными будут те оптимальные неравномерные коды, у которых:
где m и N – символы соответственно вторичного и первичного алфавитов.
Эффективность ОНК оценивают при помощи коэффициента стати стического сжатия, характеризующего уменьшение количества двоичных знаков на символ сооб щения при применении ОНК по сравнению с применением методов нестати стического кодирования:
А также с помощью коэффициента относительной эффективности, показывающего, насколько используется статистическая избы точность передаваемого сообщения:
Метод Шеннона-Фано не единственный способ построения оптималь ных кодов. Хорошо известна и широко применяется методика построения ОНК при помощи кодовых деревьев. Впервые она была описана Хаффменом.
Хаффмен показал, что для получения минимально возможной длины кода основания m с числом взаимонезависимых букв первичного алфавита N:
необходимо и достаточно выполнение следующих условий:
если выписать символы в порядке убывания вероятностей pi > pj, то при i < j, l(i) < l(j);
2) два последних (но не больше чем m) кодовых слова равны по длительности и различаются лишь значениями последнего символа. При этом:
где m – число качественных признаков вторичного алфавита, а n0 – число наименее вероятных сообщений, объединяемых на первом этапе построения кодового дерева; кроме того а – целое положительное число;
3) любая возможная последовательность N–1 кодовых слов должна сама быть кодовой комбинацией.
Исходя из данных условий, Хаффмен предложил следующий метод по строения ОНК. Символы первичного алфавита выписываются в порядке убы вания вероятностей. Последние n0 символов, где 2 ≤ n0 ≤ m и N – n0 / m–1, це лое число, объединяют в некоторый новый символ с вероятностью, равной сумме вероятностей объединяемых символов. Последние символы с учетом образованного символа вновь объединяют и получают новый, вспомогатель ный символ. Опять выписывают символы в порядке убывания вероятностей с учетом вспомогательного – и так до тех пор, пока вероятности m оставшихся символов после (N–n0 / m–1)-го выписывания не дадут в сумме 1.
На практике обычно не производят многократного выписывания веро ятностей символов, а обходятся геометрическими построениями, суть кото рых для кодов с числом качественных признаков m = 2 сводится к тому, что символы кодируемого алфавита попарно объединяются в новые, начиная с символов, имеющих наименьшую вероятность, а затем, с учетом вероятно стей вновь образованных символов, опять производят попарное объединение символов с наименьшими вероятностями и таким образом строят двоичное кодовое дерево, в вершине которого стоит символ с вероятностью 1.
Пример. Используя методику Хаффмена, осуществить эффективное кодирование ансамбля знаков с вероятностями соответственно: z1 = 0,22; z2 = 0,20; z3 = 0,16; z4 = 0,16; z5 = 0,10; z6 = 0,10; z7 = 0,04; z8 = 0,02.
Решение
Знаки
|
Вероят ности
|
Вспомогательные столбцы
|
|
|
I
|
II
|
III
|
IV
|
V
|
VI
|
VII
|
Zi
|
0,22
|
0,22
|
0,22
|
0,26
|
0,32
|
0,42
|
0,58
|
1
|
Z2
|
0,20
|
0,20
|
0,20
|
0,22
|
0,26
|
0,32
|
0,42
|
|
Z3
|
0,16
|
0,16
|
0,16
|
0,20
|
0,22
|
0,26
|
|
|
Z4
|
0,16
|
0,16
|
0,16
|
0,16
|
0,20
|
|
|
|
Z5
|
0,10
|
0,10
|
0,16
|
0,16
|
|
|
|
|
Z6
|
0,10
|
0,10
|
0,10
|
|
|
|
|
|
Z7
|
0,04
|
0,06
|
|
|
|
|
|
|
Z8
|
0,02
|
|
|
|
|
|
|
|
Для наглядности построим кодовое дерево. Из точки соответствующей вероятности 1 направляем две ветви, причем ветви с большей вероятностью присваиваем символ 1, а с меньшей – 0. Такое последовательное ветвление продолжаем до тех пор, пока не дойдем до вероятности каждой буквы.
Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каж дой буквы соответствующую ей кодовую комбинацию:
Z1 Z2 Z3 Z4 Z5 Z6 Z7 Z8
01 00 111 110 100 1011 10101 10100
При построении ОНК для вторичных алфавитов с m = 2 методы Шеннона-Фано и Хаффмена дают в большинстве случаев одинаковые результаты.
Задание
Получить у преподавателя вариант задания и ознакомиться с ним.
Построить код по методу Шеннона-Фано и проверить его оптимальность.
Построить код по методу Хаффмана и кодовое дерево.
Провести программный контроль выполнения 2, 3 пунктов на при мере случайных сообщений.
Подготовить отчет и сдать работу.
Контрольные вопросы
1. Какой код называется оптимальным?
2. Способы построения оптимальных кодов.
3. В чем заключается сущность оптимального кодирования и практический результат его применения?
4. Как оценивается эффективность ОНК?
5. Какие коды называются оптимальными неравномерными кодами?
|
