Оптимальное кодирование
Автор: Анна Пищик • Ноябрь 17, 2023 • Лабораторная работа • 768 Слов (4 Страниц) • 80 Просмотры
Вариант 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. Найдите дины оптимальных кодов данных двух источников информации.
Решение.
- Мультимножество 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]
Тогда префиксный код будет иметь вид:
- 110000
- 11101
- 1111
- 10
- 1110001
- 111001
- 0
- 110
2. Первый источник информации: А Р С Е Н Ь Е В Р У С Л, а вероятности появления – частоты букв. Второй источник информации – всевозможные последовательности длины два последовательности П = 0 1 1 9 9 0 2 9, вероятность появления последовательности – частота её встречаемости в П.
а) Кодирование первого источника информации кодом Фано:
А | 1 | 100 |
Р | 2 | 010 |
С | 2 | 011 |
Е | 2 | 000 |
Н | 1 | 1011 |
Ь | 1 | 110 |
В | 1 | 1010 |
У | 1 | 1110 |
Л | 1 | 1111 |
Кодирование первого источника информации двоичным кодом Хаффмана
Р | 2 |
С | 2 |
Е | 2 |
А | 1 |
Н | 1 |
Ь | 1 |
В | 1 |
У | 1 |
Л | 1 |
Определим количество элементов, объединяемых на первом шаге:
...