На бирже курсовых и дипломных проектов можно найти готовые бесплатные и платные работы или заказать написание уникальных курсовых работ, дипломов, лабораторных работ, контрольных работ, диссертаций, рефератов по самым низким ценам. Добавив заявку на написание требуемой для вас работы, вы узнаете реальную стоимость ее выполнения.

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Быстрая помощь студентам

 

Работа № 100161


Наименование:


Контрольная Найти H (X ), H(X X? ), H2 (X). Построить коды Хаффмена для ансамблей X , X2 .

Информация:

Тип работы: Контрольная. Предмет: Математика. Добавлен: 03.11.2016. Сдан: 2015. Страниц: 5. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Задание №1

1. Имеем Марковский источник с матрицей переходных вероятностей

Р=[¦(1/3&1/2&1/6@0&1/4&3/4@1/2&1/2&0)]
Найти H (X ), H(X |X? ), H2 (X). Построить коды Хаффмена для ансамблей X , X2 . Указать наилучший алгоритм кодирования для данного источника.

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

Это стохастическая матрица с суммой вероятностей строк равной 1.


Найдем вероятности появления каждого состояния

Рассмотрим частоты появления каждого символа (сумма по столбцам матрицы):

X1= 1/3+1/2=5/6
Р(Х1)=5/18
X2= 1/2+1/4+1/2=5/4
Р(Х2)=5/12
X3= 1/6+3/4=11/12
Р(Х3)=11/36


H(X)=-?-?p(X_i )*log_2?p(X_i ) ?=-5/18*log_2??5/18?-5/12*log_2??5/12?-11/36*log_2??11/36?=1,562


Найдем H2 (X).
Рассчитаем вероятности получение каждого состояния на втором шаге. Для этого перемножим строки матрицы состояний на соответствующие вероятности состояний Р(Х).

Р=[¦(1/3*5/18&1/2*5/18&1/6*5/18@0*5/12&1/4*5/12&3/4*5/12@1/2*11/36&1/2*11/36&0*11/36)]=[¦(5/54&5/36&3/65@0&5/48&5/16@11/72&11/72&0)]
Вероятности появления состояний на втором шаге соответственно 0,245; 0,396;0,359.

H_2 (X)=-0,245*log_2?0,245-0,396*log_2?0,396-0,359*log_2?0,359=1,557

По сравнению с Н(Х) энтропия немного уменьшилась.


Н(Х)?Н_2 (Х)?Н_? (Х)=1,56


Код Хаффмана для Х будет

X1= 01
X2= 1
X3= 00


Для построения кода для ансамбля Х2 рассчитаем таблицу
22 0,104 0,243 0,382 1,000
12 0,139
11 0,093 0,139
13 0,046
23 0,313 0,618
31 0,153 0,306
32 0,153


Код Хаффмана для Х2 будет

11 = 011
12=100
13=010
21 -отсутствует
22=000
23=11
31=101
32=001
33- отсутствует


Задача 2.
Определить частоты появления букв в поговорке, построить для заданных частот код Хаффмена, найти среднюю длину кодовых слов, определить затраты на передачу поговорки при заранее известных частотах появления букв.
На острую косу много и покосу! покоси-ка, коса!


Алгоритм Хаффмана — адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.

Этот метод кодирования состоит из двух основных этапов:
Построение оптимального кодового дерева.
Построение отображения код-символ на основе построенного дерева.

Идея алгоритма состоит в следующем: зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством префиксности (т.е. ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать.
Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.
2. Выбираются два свободных узла дерева с наименьшими весами.
3. Создается их родитель с весом, равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Этот процесс можно представить как построение дерева, корень которого — символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n0 потомков — символы из предыдущего шага и т. д.

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

Рассчитаем количество повторений букв в сообщении

а 3
г 1
и 2
к 5
м 1
н 2
о 9
п 2
р 1
с 5
т 1
у 3
ю 1

По описанному алгоритму строим таблицу:
н 2
4 9
18
36
п 2
к 5
о 9
с 5
11 18

а 3
6
у 3
г 1 2 4 7
м 1
р 1 2
т 1
ю 1 3
и 2

Итого получаем коды (красные стрелочки - 1, синие - 0).
Буква Частота Код Длина кода Частота*Длину
а 3 0101 4 12
г 1 00111 5 5
и 2 0000 4 8
к 5 110 3 15
м 1 00110 5 5
н 2 1111 4 8
о 9 10 2 18
п 2 1110 4 8
р 1 00101 5 5
с 5 011 3 15
т 1 00100 5 5
у 3 0100 4 12
ю 1 0001 4 4
Сумма 120


Показателем экономичности или эффективности неравномерного кода является не длина отдельных кодовых слов, а "средняя" их длина, определяемая равенством:

где - кодовое слово, которым закодировано сообщение , а - его длина, - вероятность сообщения , - общее число сообщений источника
Необходимые вычисления проведены в таблице.
Затраты на передачу вычислений = 120 бит.
Средняя длинна кодовых слов L=120/36=3,33.





Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть похожие работы