LAB36 Антон. Лабораторная работа 36 эффективное кодирование на примере кода хаффмана выполнил студент группы рт0701 Ольхин Антон Владимирович
![]()
|
Кафедра передачи дискретных сообщений и телеграфии Лабораторная работа №36 ЭФФЕКТИВНОЕ КОДИРОВАНИЕ НА ПРИМЕРЕ КОДА ХАФФМАНА Выполнил студент группы РТ0701 Ольхин Антон Владимирович Москва 2011 Цель работы: Изучение принципов эффективного кодирования источников дискретных сообщений. Схема лабораторного макета. ![]() Индивидуальное задание.Изучить принцип эффективного кодирования алфавита источника дискретных сообщений (ИДС) по методу Хаффмана. Сформировать кодовые комбинации для передачи заданной последовательности знаков алфавита при кодировании алфавита ИДС равномерным кодом; при кодировании алфавита ИДС кодом Хаффмана. Определить значения Нmax , Нреал и nсред для анализируемого варианта. Оценить значение Коэ и Ксж. p(z1)=0.18 p(z2)=0.14 p(z3)=0.03 p(z4)=0.24 p(z5)=0.05 p(z6)=0.36 Закодируем этот алфавит равномерным кодом. N=6 ![]() , нам потребуются 3-х разрядные кодовые комбинации. Допустим: z1->001 z2->010 z3->011 z4->100 z5->101 z6->110 Слово алфавита z1z2z3z4z5z6 будет кодировано следующим образом: 001010011100101110 Найдем значение энтропии. ![]() Найдем значение максимальной энтропии (при вероятности появления символа 1/N) ![]() Избыточность источника равна: ![]() Найдем кодовые комбинации для того же алфавита по методу Хаффмана. Построим таблицу перехода вероятностей. Д ![]() алее построим дерево кодовых слов. ![]() В соответствии с ним находим кодовые комбинации для каждого символа алфавита. z1->00 n1=2 z2->011 n2=3 z3->0100 n3=4 z4->10 n4=2 z5->0101 n5=4 z6->11 n6=2 Выбранный код обладает свойством префиксности. Комбинация z1z2z3z4z5z6 кодируется: 00011010010010111 Найдем среднее число двоичных символов на знак алфавита. ![]() Очевидно, неравномерный код Хаффмана более компактен, чем равномерный код. Найдем коэффициенты относительной эффективности и сжатия. ![]() ![]() Пункт 1.2 Наблюдение и анализ статистики сообщения и процесса кодирования и декодирования (приотсутствии ошибок). ![]() ![]() ![]() Код Хаффмана: Таблица переходных вероятностей ![]() Дерево кодовых слов. ![]() ![]() ![]() ![]() П ![]() ункт 1.3 Наблюдение и анализ процесса декодирования при наличии ошибок. Вывод: Исходя из результатов лабораторной работы, можно сделать вывод, что неравномерный код Хаффмана более компактный, но равномерный код более устойчив к помехам. Контрольные вопросы: 2) Принцип построение кодовой комбинации при кодировании неравномерным кодом. Построение кода Хаффмана начинается с упорядочивания указанных знаков по убыванию значений Рi. Затем по результатам таблицы строится кодовое дерево. ![]() Из точки Рi=1,0 направляем две ветви, и той, у которой в соответствии с колонкой 5 таблицы 1 вероятность больше (Рi =0,58), присваиваем символ 1, другой — 0. Код висячей вершины и будет кодом при последовательном прохождении от начала дерева к ней. 4) Показатели количественной оценки эффективности неравномерного кодирования, Эффективность неравномерных кодов оценивается коэффициентом относительной эффективности ![]() который показывает степень использования статистической избыточности. Для оптимальных кодов Коэ=1. Отношение среднего числа двоичных символов, приходящихся на один знак алфавита, при кодировании заданного источника неравномерным кодом к длине кодовой комбинации в случае кодирования источника равномерным кодом называется коэффициентом сжатия Ксж. ![]() 6) Принцип декодирования последовательности префиксного кода. При декодировании последовательности комбинаций префиксного кода определение кода каждого знака производится однозначно. В противном случае, т.е. для комбинаций непрефиксного кода характерна неоднозначность декодирования. Пусть, например, некоторый код удовлетворяет требованию префиксности, т.е. знакам алфавита соответствуют кодовые комбинации вида: А-00 Б-01 B-101 Г-100. Составим произвольно комбинацию передаваемых знаков алфавита и соответствующую ей кодовую последовательность: БАБВГВГЕГААБ. 01000110110010101100000001.() Эта последовательность декодируется однозначно: 01 00 01 101 100 101 01 100 00 00 01 Б А Б В Г В Б Г А А Б Рассмотрим другой случай, когда кодирование ансамбля знаков проведено по кодовой таблице вида А-00; Б-01; В-001; Г-010. Тогда последовательность кодовых комбинаций того же сообщения будет иметь вид 01000100101000101010000001. В этом случае возможны различные варианты декодирования: 01 00 01 001 01 00 01 01 010 00 00 01 Б А Б В Б А Б Б Г А А Б или 010 001 001 010 001 01 010 00 00 01 Г В В Г В Б Г А А Б |