Выбор и обоснование информационных характеристик канала связи (стр. 6 из 16)

Принцип построения оптимального кода Шеннона-Фано следующий.

Для заданного сообщения необходимо составить вспомогательную таблицу вероятностей появления букв в сообщении.

Таблица 5.1

А	К	С	Е	Н	Е	Н	К	О	_	И
0.062	0.028	0.045	0.072	0.053	0.072	0.053	0.028	0.09	0.175	0.062

Все символы сообщения, входящие в ансамбль, располагаются в порядке убывания вероятности их появления, определяется сумма всех вероятностей. Чтобы кодирование было оптимальным, необходимо выполнение условия нормировки:

(5.1)

Это означает, что необходимо ввести паузу, вероятность которой будет рассчитана, как:

P₁ = 0.26

Т.к. код Шеннона-Фано двоичный, следовательно, основание кода k = 2.

Далее все символы ансамбля разбиваются на k групп с таким расчетом, чтобы суммарные вероятности в группах были приблизительно одинаковы. Каждая из групп делится на подгруппы, чтобы в каждой из k подгрупп суммарные вероятности были бы равны. Такое разбиение осуществляется до тех пор, пока в подгруппах не останется по одному символу.

В подгруппах каждый символ или группа кодируется следующим образом. Всем символам первой подгруппы присваивается 0, всем символам второй подгруппы – 1, третьей – 2, и т.д. до k-ой группы, которой присваивается (k – 1).

По этим данным можно составить таблицу разработки кода:

Таблица 5.2

Буква	Символ	Pi	1	2	3	4	5	аi	n
пауза	а1	0.26	0	0	а1	2
_	а2	0.175	0	1	0	а2	3
О	а3	0.09	0	1	1	а3	3
Е	а4	0.072	1	0	0	0	а4	4
Е	а5	0.072	1	0	0	1	а5	4
А	а6	0.062	1	0	1	0	а6	4
И	а7	0.062	1	0	1	1	а7	4
Н	а8	0.053	1	1	0	0	а8	4
Н	а9	0.053	1	1	0	1	а9	4
С	а10	0.045	1	1	1	0	а10	4
К	а11	0.028	1	1	1	1	0	а11	5
К	а12	0.028	1	1	1	1	1	а12	5

Таким образом, можно окончательно записать сообщение, закодированное методом Шеннона-Фано:

0010101111011101000110010011101111110110101011

Процесс кодирования методом Шеннона-Фано обеспечивает оптимальность кода засчет того, что символам с более высокой вероятностью появления ставится в соответствие более короткая кодовая комбинация.

Обычно после разработки системы кодирования определяют среднее количество разрядов, необходимое для передачи одного символа, следующим образом:

(5.2)

5.2.3. Оценка кода по показателям эффективности

Для оценки качества кода необходимо знать энтропию, рассчитывающуюся по формуле Шеннона:

(5.3)

Н = 3.241 бит/символ

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

(5.4)

1. Расчет показателя избыточности сообщения

Расчет показателя избыточности сообщения будет осуществляться по следующей формуле:

(5.5)

где Н – энтропия сообщения, написанного на алфавите, в котором буквы распределяются со своей вероятностью

Н_max – энтропия сообщения, написанного на алфавите, в котором буквы распределяются с равной вероятностью

Н_max = log₂ n (5.6)

В таком случае, подставив формулу (5.7) в (5.6), получим:

R = 0.096

2.Расчет показателя избыточности кода

Расчет показателя избыточности кода осуществляется по следующей формуле:

Rk

(5.7)

Rk = 0.009

3. Расчет показателя недогруженности кода

Расчет показателя недогруженности кода осуществляется по следующей формуле:

D

(5.8)

D = 0.03

5.3. Кодирование сообщения методом Хаффмана

Код Хаффмана строится на базе кодового дерева – специального графа, отображающего запись всех возможных k-ичных n-разрядных чисел. Дерево представляет собой совокупность узлов, которые располагаются на разных уровнях.

Рис. 5.1. Кодовое дерево

5.3.1. Разработка кода сообщения

Для построения оптимального кода на базе кодового дерева необходимо учитывать следующее:

1) символ ансамбля с наибольшей вероятностью появления должен находиться в узле наименьшего порядка.

2) по крайней мере, два сообщения с минимальной вероятностью появления должны кодироваться в узлах максимального порядка.

3) если выбран узел порядка i, то все узлы более высокого порядка, связанные с ним, не могут быть использованы для кодирования.