1 Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. – М.: Айрис-пресс, 2007. – 176 с.
2 Таран, Т. А. Сборник задач по дискретной математике / Т.А. Таран, Н.А. Мыценко, Е.Л. Темникова. – 2-е изд., перераб. и доп. – Киев: Инрес, 2005. – 64 с.
3 Таран, Т. А. Основы дискретной математики / Т. А. Таран. – Киев: Просвiта, 2003. – 288 с.
Лабораторная работа №3
Эффективное кодирование неравновероятных символов источника дискретных сообщений
Цель работы. Ознакомление с алгоритмами эффективного кодирования неравновероятных символов источника дискретных сообщений.
Теоретическая часть.
Алгоритм Шеннона-Фено. Суть этого алгоритма, при использовании двоичного кода (объем алфавита элементов символов кода равен 2), заключается в следующем.
Все символы алфавита источника сообщений ранжируют, т. е. располагают в порядке убывания вероятностей их появления. Затем символы алфавита делятся на две группы приблизительно равной суммарной вероятности их появления. Все символы первой группы получают «0» в качестве первого элемента кодового символа, а все символы второй группы — «1». Далее группы делятся на подгруппы, по тому же правилу примерно равных суммарных вероятностей, и в каждой подгруппе присваивается вторая позиция кодовых символов. Процесс повторяется до закодирования всех символов алфавита кодируемого источника сообщений. В кодовый символ, соответствующий последней группе, добавляется в качестве последнего элемента «0» для того, чтобы начальный элемент символов кода не совпадал с конечным, что позволяет исключить разделительные элементы между символами кода.
Таблица 1 иллюстрирует процесс построения кода Шеннона–Фено на примере источника сообщений, алфавит которого состоит из восьми символов.
Таблица 1
| Номер | Символы | Вероятности | Номера | Кодовые |
| символа. (i) | алфавита. (mi) | (Рi ). | Разбиений. | Символы. |
| 1 | m1 | 1/2 |
I
II III
IV
V
VI VII | 0 |
| 2 | m2 | 1/4 | 10 | |
| 3 | m3 | 1/8 | 110 | |
| 4 | m4 | 1/16 | 1110 | |
| 5 | m5 | 1/32 | 11110 | |
| 6 | m6 | 1/64 | 111110 | |
| 7 | m7 | 1/128 | 1111110 | |
| 8 | m8 | 1/256 | 11111110 |
Представляет интерес сравнение эффективного кодирования равномерным кодом и неравномерным кодом по алгоритму Шеннона–Фено.
В качестве примера рассмотрим предложенный выше (Табл. 1) источник сообщений с объемом алфавита равным 8 и соответствующими вероятностями появления отдельных символов (Pi). Для кодирования используем двоичный код ( k = 2).
Энтропия рассмотренного источника сообщений (H и) определяется по формуле Шеннона:
(бит/символ).
Максимально же возможное значение энтропии источника сообщений (H u.max), при условии равновероятного и взаимно независимого появления символов, находится по формуле Хартли:
.
Следовательно, избыточность рассматриваемого источника сообщений (R и) может быть найдена из соотношения:
Средняя длина неравномерного кода (п Н) определяется выражением:
, (2.7)
где пi — значность i - го кодового символа, соответствующего символу алфавита m i .
Избыточность неравномерного кода ( R НК ) определим из соотношения:
Энтропия элементов символов эффективного неравномерного кода 
может быть легко найдена:
(бит/элемент символа кода). (2.8)
Алгоритм Хаффмена. Суть этого алгоритма, при использовании двоичного кода, состоит в следующем. Все символы алфавита источника сообщений ранжируют, т.е. выписывают в столбец в порядке убывания вероятностей их появления. Два последних символа объединяют в один вспомогательный символ, которому приписывают суммарную вероятность.
Вероятности символов, не участвовавших в объединении, и вероятность вспомогательного символа вновь ранжируют, т.е. располагают в порядке убывания вероятностей в дополнительном столбце и два последних символа объединяются. Процесс продолжается до тех пор, пока не получим единственный вспомогательный символ с вероятностью равной единице. Пример кодирования по алгоритму Хаффмена приведен в таблице 2.
Таблица 2
На рис. 1 показан граф кодирования (кодовое дерево), который иллюстрирует ранжирование символов на группы и отдельные символы, причем из точки, соответствующей вероятности 1, направляем две ветви: одной из них (с большей вероятностью) присваиваем символ 1, а второй – символ 0.
|
Рис 1. Граф кодирования по алгоритму Хаффмена
Различные символы, генерируемые источником сообщения, и соответствующие им кодовые символы представлены в таблице 3.
Таблица 3.
| m1 | m2 | m3 | m4 | m5 | m6 | m7 | m8 |
| 01 | 00 | 111 | 110 | 100 | 1011 | 10101 | 10100 |
Этот алгоритм можно использовать и при ином числовом основании кода, а также использовать блоки, как это рассмотрено в алгоритме Шеннона-Фено.
Эффективность рассмотренных алгоритмов достигается благодаря присвоению более коротких кодовых комбинаций (кодовых символов) символам источника сообщений, вероятность которых более высока, и более длинных кодовых комбинаций - символам источника сообщений с малой вероятностью. Это ведет к различиям в длине кодовых символов и, как следствие, к трудностям при их декодировании. Для разделения отдельных кодовых символов можно использовать специальный разделительный элемент, но при этом существенно снижается эффективность кода, т.к. средняя длина кодового символа фактически увеличивается на один элемент символа кода.
Целесообразнее обеспечить декодирование без введения дополнительных элементов символов. Этого можно добиться, если в эффективном коде ни одна кодовая комбинация не будет совпадать с началом более длинной кодовой комбинации. Коды, удовлетворяющие этому условию, называют префиксными кодами (префиксом или началом называют первый элемент в кодовом символе, а последний элемент – окончанием или постфиксом).
Легко заметить, что коды, построенные по алгоритмам Шеннона–Фено или Хаффмена, являются префиксными.
Содержание работы. По номеру в списке группы ( k ) из Таблицы 4 выбрать закон распределения вероятности появления символов источника дискретных сообщений с объёмом алфавита М=8.
Произвести эффективное кодирование заданного источника дискретных сообщений по алгоритму Шеннона-Фено и по алгоритму Хафмена.
Рассчитать для построенных на основе этих алгоритмов кодов:
а). среднюю длину неравномерного кода (n н);
б). избыточность неравномерного кода(R нк);
в). энтропию элементов символов полученных кодов(H 1н);
Сравнить полученные результаты с соответствующими параметрами равномерного двоичного цифрового кода.
Таблица 4.
| mi | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| m1 | 0.10 | 0.18 | 0.07 | 0.65 | 0.55 | 0.60 | 0.01 | 0.15 | 0.30 | 0/01 |
| m2 | 0.51 | 0.10 | 0.03 | 0.05 | 0.05 | 0.06 | 0.02 | 0.10 | 0.20 | 0.05 |
| m3 | 0.02 | 0.47 | 0.11 | 0.06 | 0.16 | 0.02 | 0.02 | 0.30 | 0.10 | 0.03 |
| m4 | 0.10 | 0.07 | 0.33 | 0.03 | 0.03 | 0.10 | 0.15 | 0.35 | 0.05 | 0.02 |
| m5 | 0.02 | 0.03 | 0.25 | 0.02 | 0.02 | 0.02 | 0.02 | 0.02 | 0.15 | 0.10 |
| m6 | 0.20 | 0.02 | 0.01 | 0.15 | 0.02 | 0.15 | 0.45 | 0.02 | 0.10 | 0.14 |
| m7 | 0.01 | 0.04 | 0.17 | 0.02 | 0.02 | 0.03 | 0.30 | 0.01 | 0.07 | 0.25 |
| m8 | 0.04 | 0.09 | 0.03 | 0.02 | 0.15 | 0.05 | 0.03 | 0.05 | 0.03 | 0.40 |
Контрольные вопросы.
- Какой вид кодирования называют эффективным и в чем его специфика?
- Что такое избыточность кодов?
- Какие коды называются равномерными?
- На каких принципах основано построение эффективных кодов при неравновероятном появлении символов сообщения?
- Принцип построения эффективного кода по алгоритму Шеннона-Фено.
- Принцип построения эффективного кода по алгоритму Хафмена.
Лабораторная работа № 4
Дата: 2019-02-02, просмотров: 392.
