Эффективное кодирование неравновероятных символов источника дискретных сообщений.

Цель работы. Ознакомление с алгоритмами эффективного кодирования неравновероятных символов источника дискретных сообщений и сравнение их эффективности.

Содержание работы. По номеру в списке группы ( k ) из Таблицы 1 выбрать закон распределения вероятности появления символов источника дискретных сообщений с объёмом алфавита М=8.

Произвести эффективное кодирование заданного источника дискретных сообщений по алгоритму Шеннона-Фено и по алгоритму Хафмена.

Рассчитать для построенных на основе этих алгоритмов кодов:

а). среднюю длину неравномерного кода (n_н);

б). избыточность неравномерного кода(R_нк);

в). энтропию элементов символов полученных кодов(H_1н);

Сравнить полученные результаты с соответствующими параметрами равномерного двоичного цифрового кода.

Таблица 1.

2. Произвести эффективное кодирование двоичным кодом соответствующего Вашему номеру (k) источника дискретных сообщений по алгоритму Хаффмена в программном средстве MathCad. Вычислить энтропию сообщений и среднюю длину nсркодового слова. Сравнить с минимально возможной длиной nср.min.и средней длиной кодового символа при кодировании равномерным кодом. Сравнить полученный результат с результатами «ручного» кодирования.

Ниже приведён пример программы, разработанной в программном средстве MathCad, для эффективного кодирования двоичным кодом источника дискретных сообщений по алгоритму Хаффмена в программном средстве MathCad.

Источник дискретных сообщений X (xi, i= 1,…, m), c объёмом алфавита равном m = 9, имеет следующие вероятности их появлений, заданные при вектор-строкой

,

где, например, и .

Предварительно определим единицы измерения количества энтропии и информации как и .

Составим матрицу, в которой вероятности выписываются в первый (основной) столбец в порядке их убывания, т.е.

;

.

Две последних вероятности P1 объединяются в одну вспомогательную вероятность Ps1:

.

; ; ;

Вероятности

снова располагаются в порядке их убывания в дополнительном столбце

;

.

Две последних вероятности P2 объединяются в одну вспомогательную вероятность Ps2:

.

; ; ;

Вероятности

снова располагаются в порядке их убывания в дополнительном столбце

;

.

Две последних вероятности P3 объединяются в одну вспомогательную вероятность Ps3:

.

; ; ;

Вероятности

снова располагаются в порядке их убывания в дополнительном столбце

;

.

Две последних вероятности P4 объединяются в одну вспомогательную вероятность Ps4:

.

; ; ;

Вероятности

снова располагаются в порядке их убывания в дополнительном столбце

;

.

Две последних вероятности P5 объединяются в одну вспомогательную вероятность Ps5:

.

; ; ;

Вероятности

снова располагаются в порядке их убывания в дополнительном столбце

;

.

Две последних вероятности P6 объединяются в одну вспомогательную вероятность Ps6:

.

; ; ;

Вероятности

снова располагаются в порядке их убывания в дополнительном столбце

;

.

Две последних вероятности P7 объединяются в одну вспомогательную вероятность Ps7:

.

; ; ;

Вероятности

снова располагаются в порядке их убывания в дополнительном столбце

;

.

Две последних вероятности P8 объединяются в одну вспомогательную вероятность Ps8:

.

; ; ;

Вероятности

снова располагаются в порядке их убывания в дополнительном столбце

;

.

На этом при получении дополнительного столбца с вероятностью, равной единице, процесс заканчивается. Матрица M, на основе которой проводится кодирование, принимает вид:

;

;

;

На основании данной таблицы строим кодовое дерево, ветки которого соответствуют вероятностям, согласно матрице M.

Каждой ветке дерева присваивается символ "1" при выходе из узла вверх и символ "0" при выходе из узла вниз. Движение по кодовому дереву из вершины с P=1.00 к сообщениям, определяемым соответствующими вероятностями, дает двоичные кодовые комбинации эффективного кода, приведенные в таблице.

Согласно таблице кодирования, длину кодовых символов можно описать вектор-строкой

.

Средняя длина кодового слова в битах

; .

Энтропия источника сообщений

; .

На основании (4.2) минимально возможная средняя длина кодового слова равна энтропии источника, т.е.

; .

В случае использования равномерного двоичного кодирования девяти символов сообщения требуется четырехразрядное кодовое слово для каждого сообщения, так как 23<9. При таком кодировании максимальная средняя длина кодового слова bit.

Таким образом, проведенное кодирование более эффективно, чем равномерное. Однако оно не достигает максимально возможной эффективности, так как ncp.min< ncp< ncp.max.

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

1. Какой вид кодирования называют эффективным и в чем его специфика?
2. Что такое избыточность кодов?
3. Какие коды называются равномерными?
4. На каких принципах основано построение эффективных кодов при неравновероятном появлении символов сообщения?
5. Принцип построения эффективного кода по алгоритму Шеннона-Фено.
6. Принцип построения эффективного кода по алгоритму Хафмена.