ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ»

Кафедра МСИБ

Методическая разработка к лабораторной работе № 60

СОПРЯЖЕНИЕ ИСТОЧНИКА ИЗБЫТОЧНЫХ

ДИСКРЕТНЫХ СООБЩЕНИЙ С ДИСКРЕТНЫМ

КАНАЛОМ (ЭФФЕКТИВНОЕ КОДИРОВАНИЕ)

Составитель: к.т.н., доц. Крыжановский А.В.

Редактор: к.т.н., доц. Казаченко Ю.М.

Рецензент: к.т.н., доц. Соколов В.Ф.

САМАРА

2011

Цель работы

Изучить особенности и методы построения эффективных кодов и расчет их характеристик с использованием ПЭВМ.

Рекомендуемые источники

1. Передача дискретных сообщений. Учебник для вузов /В.П. Шувалов, Н.В. Захарченко, В.О. Шварцман и др. Под редакцией В.П. Шувалова. – М.: Радио и связь, 1990, с. 146-155.

2. Кловский Д.Д. Теория передачи сигналов. – М.: Связь, 1973, с. 207-208.

3. Цымбал В.П. Теория информации и кодирование. – Киев: Вища школа, 1977, с.110-137.

Подготовка к работе

1. Изучить методы построения эффективных кодов по одному из рекомендованных источников [1,2,3].

2. Ознакомиться с содержанием данной методической разработки.

3. Подготовить бланк отчета, который должен содержать:

   • цель работы;

   • заготовки таблиц кодирования по методикам Шеннона-Фано (Табл. 1) и Хаффмена (Табл. 3);

   • расчетные формулы средней длины кодовой комбинации эффективного кода, энтропии источника дискретных сообщений, коэффициентов статистического сжатия и относительной эффективности.

Контрольные вопросы

1. В каких условиях целесообразно использовать эффективное кодирование?

2. Преимущества и недостатки эффективных кодов.

3. До какого предела может быть уменьшена средняя длина кодовой комбинации эффективного кода?

4. Как определяется средняя длина кодовой комбинации эффективного кода?

5. Сущность кодирования по методике Шеннона-Фано.

6. Кодирование по методу Хаффмена.

7. Какой эффективный код называется префиксным?

8. Дайте определение коэффициента статистического сжатия.

9. Что называется коэффициентом относительной эффективности?

10. Чему равна минимальная длина двоичных кодовых комбинаций для 32-х буквенного алфавита, если буквы в тексте встречаются с равными вероятностями?

11. Алфавит источника содержит шесть сообщений, передаваемых независимо друг от друга с вероятностями ; ; ; ; ; . До какого предела может быть уменьшена средняя длина кодовой комбинации эффективного кода?

12. Первичный алфавит состоит из четырех равновероятных символов. Рассчитать коэффициент относительной эффективности.

13. Какой код позволяет минимизировать среднюю длину передаваемой кодовой комбинации?

Содержание работы

1. Ознакомиться с постановкой задачи сопряжения источника дискретных сообщений с дискретным каналом.

2. Освоить практические методики построения эффективных кодов.

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

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

Отчет должен содержать:

1. Цель работы.

2. Таблицы кодирования по методикам Шеннона-Фано и Хаффмена.

3. Построенное на ПЭВМ кодовое дерево.

4. Расчетные формулы и численные значения средней длины кодовой комбинации эффективного кода, энтропии источника дискретных сообщений, коэффициентов статистического сжатия и относительной эффективности.

5. Выводы об особенностях, преимуществах и областях применения эффективного кодирования.

Методические указания к выполнению работы

Лабораторная работа выполняется на ПЭВМ в диалоговом режиме. После ввода программы в память ЭВМ все необходимые указания, вопросы и пояснения выводятся на дисплей.

Перед выполнением лабораторной работы на экране дисплея выводится ее название и текст «Нажмите пробел». После этого нужно ввести номер варианта, который совпадает с номером бригады. После ввода числа здесь и в дальнейшем, если не оговорено особо, нужно нажать клавишу «Enter». После этого ЭВМ задает контрольные вопросы и принимает решение о допуске к работе. Для допуска к работе допускается совершить не более трех ошибок. В случае возникновения конфликта между ЭВМ и студентом он может быть разрешен преподавателем.

1. Кодирование по методу Шеннона-Фано

В соответствии с выбранным вариантом ЭВМ устанавливает значения вероятностей букв первичного алфавита, сведенные в таблицу. Необходимо произвести кодирование и заполнить таблицу. Перед заполнением таблицы следует убедиться, что сумма вероятностей букв первичного алфавита равна 1.

Во избежание чрезмерного количества ошибок и, как следствие, конфликтов с ЭВМ, предлагается вначале заполнить таблицу без привлечения ЭВМ по методике, изложенной на с. 5-6 настоящей методической разработки (Табл. 1). Затем правильность заполнения таблицы проверяется на ЭВМ, при этом следует пользоваться клавишами «1», «0», «-», клавишу «Enter» в данном случае нажимать не следует.