Оптимальное кодирование

Вариант 1

Лабораторная работа №2

Оптимальное кодирование

1. Мультимножество M строиться по следующему правилу. Берутся 8 букв из вашего ФИО, находятся их остатки при делении на 8 и к каждому из них прибавляется 1. Полученные числа и составляют 𝑀. Например для АААВВВББ 𝑀 = {2, 2, 2, 3, 3, 4, 4, 4}.

a. Для какого минимального D существует однозначно декодируемый код, длины слов которого составляют 𝑀.

b. Какое наименьшее число (возможно и 0) элементов из 𝑀 нужно выкинуть, чтобы существовал двоичный префиксный код с таким набором 𝑀’ длин слов.

c. Для набора 𝑀′ из b постройте префиксный код с такими длинами слов и его дерево.

2. Первый источник информации состоит из различных букв первых взятых из первых 12 букв вашего ФИО, вероятности их появления – частоты этих букв в первых 12 буквах ФИО. Второй источник информации состоит из всевозможных подпоследовательностей длины два последовательности П=‘N1990(30-N)’ (где N – номер варианта), вероятность появления подпоследовательности есть частота её встречаемости в П.

a. Закодируйте первый источник информации двоичными кодами Фано и Хаффмана.

b. Закодируйте второй источник информации троичным кодом Хаффмана.

c. Постройте деревья, соответствующие кодам из заданий a-b.

d. Найдите средние длины кодов из заданий a-b.

e. Найдите дины оптимальных кодов данных двух источников информации.

Решение.

1. Мультимножество M строиться по следующему правилу. Берутся 8 букв из вашего ФИО, находятся их остатки при делении на 8 и к каждому из них прибавляется 1. Полученные числа и составляют 𝑀.

Для А Р С Е Н Ь Е В

 𝑀 = {2,3,4,7,8,7,7,4} = {2,3,4,4,7,7,7,8} Чтобы найти минимальное D для которого существует однозначно декодируемый код, длины слов которого составляют M, воспользуемся неравенством Макмилана:

[pic 1]

Для 𝑀 оно будет иметь вид:

[pic 2]

Тогда: 𝐷−2 + 𝐷−3 + 2 ∙ 𝐷−4 + 3 ∙ 𝐷−7 + 𝐷−8 ≤ 1

Предположим, что 𝐷 = 2: [pic 3]

Так как неравенство выполняется, следовательно, предположение о том, что 𝐷 = 2 верно. Таким образом, минимальное 𝐷 при котором будет существовать однозначно декодируемый код, длины слов которого составляют 𝑀, равно 2.

Так как неравенство Макмилана выполняется для множества 𝑀 при 𝐷 = 2, то наименьшее число элементов из 𝑀 нужно выкинуть, чтобы существовал двоичный префиксный код с таким набором 𝑀’ длин слов равно 0. Т.е. 𝑀 = M′. Так как в 𝑀′ содержаться длины слов, то дерево, построенное на его основе будет иметь вид

[pic 4]

Тогда префиксный код будет иметь вид:

1. 110000
2. 11101
3. 1111
4. 10
5. 1110001
6. 111001
7. 0
8. 110

2. Первый источник информации: А Р С Е Н Ь Е В Р У С Л, а вероятности появления – частоты букв. Второй источник информации – всевозможные последовательности длины два последовательности П = 0 1 1 9 9 0 2 9, вероятность появления последовательности – частота её встречаемости в П.

а) Кодирование первого источника информации кодом Фано:

Кодирование первого источника информации двоичным кодом Хаффмана

Определим количество элементов, объединяемых на первом шаге: