Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

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

Автор:   •  Ноябрь 17, 2023  •  Лабораторная работа  •  768 Слов (4 Страниц)  •  75 Просмотры

Страница 1 из 4

Вариант 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, вероятность появления последовательности – частота её встречаемости в П.

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

А

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

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

...

Скачать:   txt (11 Kb)   pdf (186.6 Kb)   docx (648.9 Kb)  
Продолжить читать еще 3 страниц(ы) »
Доступно только на Essays.club