Описание лабораторного макета. Лабораторная работа выполняется на компьютере с использованием виртуального макета, структурная схема которого приведена на рис
Лабораторная работа выполняется на компьютере с использованием виртуального макета, структурная схема которого приведена на рис. 7.
Макет является универсальным модулятором сигналов цифровой модуляции. В состав макета входит генератор цифрового сигнала длительностью 8Тб, значения символов сигнала можно изменять. Установлена длительность бита Тб = 50 мс. Модулятор состоит из следующих блоков: кодера модуляционного кода, формирующих фильтров, генераторов несущих колебаний, двух перемножителей и сумматора. Установка вида модуляции действует на кодер модуляционного кода и генераторы несущих колебаний и позволяет установить следующие виды модуляции: АМ-2, АМ-4, ФМ-2, ФМ-4 и ЧМ-2. Сигналы от двух выходов кодера поступают на входы фильтров, формирующие огибающую радиоимпульсов в виде импульса Найквиста. Схема содержит переключатель, позволяющий выключить формирующие фильтры из схемы, и тогда радиоимпульсы имеют П-образную огибающую. Сформированные импульсы перемножаются с несущими колебаниями. Частота несущей установлена в макете f0 = 40 Гц. Разнос частот Df в макете устанавливается в случае ЧМ-2 согласно формуле (9), а в случае ММС Df = 0,5/T. Макет содержит осциллографы и анализатор спектра.
Требования к отчету
7.1 Название лабораторной работы.
7.2 Цель работы.
7.3 Результаты выполнения домашнего задания.
7.4 Структурные схемы для выполнения каждого из лабораторных заданий.
7.5 Результаты выполнения лабораторных заданий по пунктам (осциллограммы и спектрограммы, каждая из которых должны иметь подпись).
7.6 Выводы по каждому пункту задания, в которых предоставить анализ полученных результатов (совпадение теоретических и экспериментальных данных, проявление свойств сигналов и т.п.).
7.7 Дата, подпись студента, виза преподавателя с оценкой в 100-балльной шкале.
ЛР 2.1 Исследование алгоритмов эффективного
кодирования источников дискретных сообщений
Цель работы
1.1 Изучение информационных характеристик источников дискретных сообщений и принципов эффективного кодирования сообщений.
1.2 Изучение и исследование особенностей алгоритмов эффективного кодирования Хаффмана и Шеннона-Фано.
Ключевые положения
2.1 В основу определения количества информации в сообщениях в теории и технике связи положены вероятностные характеристики сообщений, которые показывают их степень неопределенности. Количество информации I(a) в сообщении a, вероятность появления которого P(a), определяется как
I(a) = 
= – log2P(a). (1)
Логарифмическая мера имеет свойство аддитивности (количество информации, содержащейся в нескольких независимых сообщениях, равна сумме количеств информации в каждом сообщении). Поскольку 0 < P(a) 
1, то величина I(a) является неотрицательной и конечной. Если P(a) = 1, то количество информации равно нулю (сообщение об известном событии никакой информации не несет).
Единицей измерения количества информации является двоичная единица (дв. ед.) или бит (1 дв. ед. определяется как количество информации в сообщении, вероятность которого P(a) = 0,5).
Источник сообщений А использует МА знаков (МА называют объемом алфавита). Знаки ak обычно имеют разные вероятности P(ak), и количества информации I(ak) в знаках согласно формуле (1) разные. Для описания источника в среднем введено понятие энтропия. Энтропия источника H(A) – это среднее количество информации в одном знаке (измеряется в дв. ед.). Если знаки независимые, то среднее количество информации определяется как математическое ожидание значений I(ak):
H(A) = 
= 
= – 
. (2)
Физически энтропия является мерой неопределенности состояния источника сообщений, она является объективной информационной характеристикой источника.
Из выражения (2) вытекает, что энтропия неотрицательная. При этом энтропия равняется нулю только тогда, когда вероятность одного из знаков равна 1, а вероятности остальных знаков равны нулю. Энтропия достигает максимального значения в случае, когда все знаки на выходе источника сообщений равновероятные и независимые:
Hmax(A) = log2MA. (3)
В общем случае для энтропии справедливо выражение H(A) £ log2MA.
Очень часто MA = 2. Тогда Hmax(A) = 1 дв. ед. Итак, при передаче информации двоичными символами, каждый символ не может переносить больше чем 1 дв. ед. информации.
Другой важной характеристикой источника является избыточность. Это свойство источника сообщений выдавать информацию бóльшим количеством знаков, чем можно было б. Избыточность источника уменьшает его энтропию в сравнении с максимальной энтропией. Основные причины избыточности:
- разные вероятности отдельных знаков;
- имеется статистическая зависимость между знаками источника.
Количественно избыточность источника оценивается коэффициентом избыточности
Kизб = 
= 1 – 
. (4)
Производительность источника Rи, дв. ед./с – это количество информации, выдаваемой источником в среднем за единицу времени
Rи = 
, (5)
где Tср – средняя длительность одного знака и определяется как
Tср = 
, (6)
где Tk – длительность k-го знака.
2.2 Согласно теореме кодирования Шеннона для канала без помех дискретное сообщений с алфавитом {ak} и вероятностями знаков {P(ak)} может быть закодированное эффективным префиксным кодом таким образом, что
H(A) £ 
£ H(A) + 1, (7)
где – средняя длина кодовых комбинаций, определяемая как
= 
, (8)
где nk – длина кодовой комбинации, которая соответствует знаку ak.
Теорема кодирования Шеннона для канала без помех указывает на возможность создания алгоритмов эффективного кодирования дискретных сообщений, при которых средняя длина кодовой комбинации может приближаться к энтропии источника как угодно близко, но не может быть меньшей энтропии.
Поскольку в большинстве случаев знаки имеют разные вероятности, то кодовые комбинации должны иметь разные длины с целью уменьшения избыточности передаваемых сообщений. Такое кодирование называется эффективным или сжатием информации.
Для оценки эффективности выбранного алгоритма кодирования вводится коэффициент эффективности кодирования
m = 
. (9)
Также можно рассчитать коэффициент сжатия сообщения (в сравнении с равномерным кодом)
h = 
, (10)
где n ³ log2MA – минимальное целое число, при котором выполняется равенство-неравенство.
Основной принцип эффективного кодирования заключается в том, что более вероятным знакам должны соответствовать более короткие кодовые комбинации, а знакам с малой вероятностью – более длинные.
Префиксным называется кодирование, в результате которого ни одна из коротких кодовых комбинаций не является началом более длинных комбинаций. Тем самым префиксное кодирование обеспечивает однозначное разбиение последовательности символов на кодовые комбинации при декодировании.
2.3 Для кодирования независимых знаков используется алгоритм Хаффмана. Для его реализации необходима таблица частот (вероятностей) знаков в кодируемом сообщении. На основании этой таблицы строится дерево кодирования Хаффмана по следующему правилу.
1. Все знаки располагаются в порядке убывания их вероятностей сверху вниз (каждому знаку соответствует свой исходный узел дерева).
2. От двух знаков с наименьшими вероятностями выходят ветки, которые сходятся в узел, соответствующий составному знаку с суммарной вероятностью объединяемых знаков (далее эти два знака не рассматриваются, а составной знак рассматривается наравне с остальными).
3. Одной ветке, например верхний, присваивается символ “1”, другой ветке – “0” (или наоборот).
4. Шаги, начиная со второго, повторяются до тех пор, пока в списке знаков не останется только один. Он и будет считаться корнем дерева.
Для определения кодовой комбинации каждого из знаков, которые входят в алфавит, необходимо пройти путь от корня дерева к исходному узлу (знаку), накапливая символы 0 или 1 при перемещении по веткам дерева.
Пример 1. Задан источник независимых дискретных сообщений с объемом алфавита MA = 6 с вероятностями знаков: P(А) = 0,3; P(Е) = 0,25; P(В) = 0,22; P(Г) = 0,1; P(Д) = 0,08; P(Б) = 0,05. Построить дерево кодирования Хаффмана и определить кодовые комбинации знаков сообщения.
Построим дерево кодирования Хаффмана (рис. 1).
На основании кодового дерева запишем соответствующим знакам кодовые комбинации: А – 11; Е – 10; В – 00; Г – 010; Д – 0111; Б – 0110.
 |
2.4 Для кодирования независимых знаков используется также алгоритм Шеннона-Фано. Для его реализации необходимая таблица частот (вероятностей) знаков в сообщении. Алгоритм Шеннона-Фано следующий.
1. Все знаки располагаются в порядке убывания их вероятностей сверху вниз.
2. Все знаки делятся на две подгруппы, в которых суммарные вероятности знаков приблизительно равны.
3. Всем знакам верхней подгруппы присваивается “0”, а знакам нижней подгруппы – “1”.
4. Шаги, начиная со второго (относительно подгрупп, которые образовались), повторяются до тех пор, пока в подгруппах останется по одному знаку.
Кодовая комбинация создается, как последовательность двоичных символов, соответствующим группам, в которых принимал участие при разбивке данный знак, и выписывается слева направо.
Пример 2. Задан источник независимых дискретных сообщений с объемом алфавита MA = 6 и вероятностями знаков: P(А) = 0,3; P(Е) = 0,25; P(В) = 0,22; P(Г) = 0,1; P(Д) = 0,08; P(Б) = 0,05. Построить таблицу разбивок на подгруппы по алгоритму Шеннона-Фано и определить кодовые комбинации знаков сообщения. Табл. 1 иллюстрирует алгоритм Шеннона-Фано.
Таблица 1 – Алгоритм Шеннона-Фано
| Знаки ak | Вероятности P(ak) | Разбивка на подгруппы | Кодовые комбинации | ||
| I | II | III | IV | ||
| А | 0,3 | ||||
| Е | 0,25 | ||||
| В | 0,22 | ||||
| Г | 0,1 | ||||
| Д | 0,08 | ||||
| Б | 0,05 |
Особенности алгоритмов Хаффмана и Шеннона-Фано:
- если к началу кодирования сообщений не известны вероятности знаков, то необходимо два прохождения по кодируемому сообщению: одно для составления таблицы вероятностей знаков и кода, а второе для кодирование;
- необходимость передачи таблицы кодовых комбинаций (кода) вместе со сжатым сообщением приводит к уменьшению суммарного эффекта от сжатия;
- для двоичного источника сообщений непосредственное применение кода Хаффмана или Шеннона-Фано не дает эффекта;
- избыточность закодированного сообщения равна нулю только в случае, когда вероятности знаков алфавита являются целыми отрицательными степенями двойки (1/2; 1/4; 1/8 и т.д.);
- сжатие по алгоритму Хаффмана является оптимальным и в большинстве случаев средняя длина кодовой комбинации при сжатии по алгоритму Шеннона-Фано такая же, как и при сжатии по алгоритму Хаффмана; при некоторых распределениях вероятностей знаков кодирование по алгоритму Шеннона-Фано не будет оптимальным.
Ключевые вопросы
3.1 Что такое информация и как определяется ее количество?
3.2 Что такое энтропия источника? При каких условиях она максимальная?
3.3 Что такое избыточность источника и каковы ее причины?
3.4 Сформулировать теорему кодирования Шеннона для канала без помех.
3.5 В чем заключается основной принцип эффективного кодирования?
3.6 Что такое префиксный код?
3.7 Описать алгоритм кодирования Хаффмана.
3.8 Описать алгоритм кодирования Шеннона-Фано.
3.9 Перечислить недостатки алгоритмов эффективного кодирования Хаффмана и Шеннона-Фано.
Домашняя задача
4.1. Изучить раздел “Эффективное кодирование дискретных сообщений” по конспекту лекций и ключевым положениям. Рекомендуется воспользоваться литературой [2, с. 16...27; 3, с. 307...310; 4, с. 257...262; 5, с. 876...887]. Изучить описание лабораторного макета в разд. 6.
4.2. Задан источник независимых дискретных сообщений с объемом алфавита MA = 5. Количество появлений знаков дано в табл. 2. Построить дерево Хаффмана и таблицу разбивок на подгруппы алгоритмом Шеннона-Фано, записать кодовые комбинации кодов Хаффмана и Шеннона-Фано, определить:
– энтропию источника сообщений H(A);
– коэффициент избыточности источника Kизб;
– среднюю длину кодовых комбинаций ;
– коэффициент эффективность кодирования μ;
– коэффициент сжатия сообщения h.
4.3. Подготовиться к обсуждению по ключевым вопросам.
Таблица 2 – Количество появлений знаков алфавита дискретного источника
| Номер бригады | Количество появлений знаков | ||||
| А | Б | В | Г | Д | |
| 1, 7 | |||||
| 2, 8 | |||||
| 3, 9 | |||||
| 4, 10 | |||||
| 5, 11 | |||||
| 6, 12 |
Лабораторное задание
5.1 Ознакомиться с виртуальным макетом на рабочем месте. Для этого запустить программу 2.1 Исследование алгоритмов эффективного кодирования источников дискретных сообщений, используя иконку Лабораторные работы на рабочем столе, а затем папки ТЭС и Модуль 2. Изучить схему макета на дисплее компьютера, пользуясь разд. 6. Уточнить с преподавателем план выполнения лабораторного задания.
5.2 Исследовать источник дискретных равновероятных сообщений. Установить объем алфавита равным 5, затем создать поля, и оставить знаки равновероятными. Запустить программу на выполнение. Наблюдать пошагово процесс кодирования. Записать кодовые комбинации, значение энтропии и рассчитать среднюю длину кодовых комбинаций. Сравнить среднюю длину с длиной равномерного кода.
Провести аналогичные исследования для источника равновероятных сообщений с объемом алфавита МА = 8. Сделать выводы.
5.3 Исследовать источник дискретных неравновероятных сообщений. Установить объем алфавита равным 5, затем создать поля, в которые записать количество появлений знаков из домашнего задания. Наблюдать пошагово процесс кодирования. Сравнить с результатами выполнения домашнего задания. Сделать выводы.
Установить объем алфавита произвольным от 10 до 16. Создать поля со случайным количеством появлений знаков, нажав кнопку “Случайные”. Запустить программу на выполнение. Зафиксировать в тетради процесс кодирования и значение энтропии. Записать кодовые комбинации, рассчитать среднюю длину кодовых комбинаций, эффективность кодирования и коэффициент сжатия. Сделать выводы о возможности декодирования сообщений без разделительных знаков.
5.4 Исследовать источник дискретных сообщений с максимальной эффективностью кодирования. Установить объем алфавита равным 6. Установить вероятности знаков равные отрицательным степеням двойки (для этого можно установить количество появлений: 16; 8; 4; 2; 1; 1). Запустить программу на выполнение. Записать кодовые комбинации и рассчитать их среднюю длину. Сравнить ее с энтропией. Сделать выводы.