Порядок выполнения лабораторной работы

Пример декодирования сообщения

Рассмотрим пример сообщения, созданного из имеющихся символов. Пусть передано сообщение a1, a5, a3, a7, a2, a3.

При кодировании, используя табл.1 получим следующую последовательность:

1100101100001101011

Получив сообщение подобного вида, необходимо её декодировать, чтобы прочитать сообщение. Считаем, что получатель имеет таблицу кодировки символов, идентичную с отправителем.

Возможный способ декодирования представлен на таблице 3:

Таблица 3

шаг комбинация кол-во символов символ
a1
-
a5
-
a3
     

Декодирование производиться с наименьшей длины кодового слова — в нашем случае — 2, — получается таблица (см.выше), с итоговым результатом, аналогичным закодированному:

 

Лабораторная работа №5 «Кодирование дискретных источников информации по методики Д.Хаффмана»

Цель работы

Освоить метод построения кодов дискретного источника информации используя методику Д.Хаффмана. На примере показать однозначность раскодирования имеющегося сообщения.

Исходными данными для данной лабораторной работы являются результаты статистической обработки текста, выполненной в лабораторной работе «Кодирование дискретных источников информации методом Шеннона-Фано». Из лабораторной работы «Определение количества информации, содержащегося в сообщении» для данной работы необходимо взять:

1) список символов данного текста;

2) оценку вероятностей появления символов в тексте;

3) значение энтропии источника.

Из лабораторной работы «Кодирование дискретных источников информации методом Шеннона-Фано» для данной работы необходимо взять вычисленное значение средней информации.

Расчеты рекомендуется выполнять в табличной форме, используя MS Excel.

1. Отсортировать символы в порядке убывания их вероятности появления в тексте.

2. Построить таблицу по правилу Д. Хаффмана для посимвольного кодирования заданного текста (См. Табл.1).

3. Определить энтропию и среднее количество двоичных разрядов, необходимых для передачи текста при использовании эффективных кодов.

4. Построить кодовое дерево (См.рис.1).

5. Создать таблицу кодов.

6. Проверить возможность однозначного декодирования полученных кодов, рассмотрев пример передачи слова, состоящего из не менее 10 символов.

Содержание отчёта

1. Название и цель работы.

2. Таблица, содержащая

Ø список символов;

Ø значения вероятностей;

Ø 49 шагов суммирования вероятностей.

3. Значение средней информации в битах, вычисленное по составленной таблице кодов.

4. Описание применяемых формул.

5. Рисунок кодового дерева, с полученными значениями и подписанными символами.

6. Таблица полученных кодов.

7. Составленное сообщение, содержащее не менее 10 символов и кодовая строка.

8. Описание декодирования данного сообщения. (Пример оформления декодирования дан в предыдущей лабораторной работе, описанной выше).

9. Выводы по работе соответственно цели лабораторной работы.

Приложение к лабораторной работе «Кодирование дискретных источников информации по методики Д.Хаффмана»