Учебное пособие 1385

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

Такое кодирование называется статистическим. Если средняя длина ̅ кодового слова является минимально возможной, то код еще и оптимальный.

3.1. Метод кодирования Шеннона - Фано

Одним из наиболее простых и распространенных способов статистического кодирования является кодирование по методу Шеннона-Фано. Кодирование в соответствии с этим алгоритмом производится так:

-сначала все буквы из алфавита сообщения записывают в порядке убывания их вероятностей;

-затем всю совокупность букв разбивают на две примерно равные по сумме вероятностей группы; одной из них (в группе может быть любое число символов, в том числе – один) присваивают символ “1”, другой - “0”;

-каждую из этих групп снова разбивают (если это возможно) на две части и каждой из частей присваивают

“1” и “0” и т.д.

Метод Шеннона-Фано не всегда приводит к однозначному построению кода, так как при разбиении на подмножества можно сделать большей по вероятности как верхнюю, так и нижнюю часть, следовательно, такое кодирование хотя и является эффективным, но не всегда будет оптимальным.

Процедура кодирования по методу Шеннона-Фано иллюстрируется табл. 1.

21

Если величина среднего числа символов на знак оказывается значительно большей, чем энтропия, то это говорит об избыточности кода. Эту избыточность можно устранить, если перейти к кодированию блоками.

Рассмотрим простой пример кодирования двумя знаками z1, z2 с вероятностями их появления в сообщениях 0,1 и 0,9 соответственно. Если один из этих знаков кодировать, например, нулем, а другой единицей, т.е. по одному символу на знак, имеем соответственно

̅ = 0,1·1 + 0,9·1 = 1,0.

H (z) = - 0,1 · log2 0,1 - 0,9 · log2 0,9 = 0,47.

При переходе к кодированию блоками по два знака (табл. 2).

̅ = ̅бл / 2 = ½ (0,81 · 1 + 0,09 · 2 + 0,09 · 3 + 0,01 · 3) =

22

= 0,645.

Можно проверить, что при кодировании блоками по три символа среднее число символов на знак уменьшается и оказывается равным около 0,53.

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

lim ̅ = ( ) ,

∞

где n - число символов в блоке.

3.2. Метод кодирования Хаффмана

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

1.Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.

2.Последовательно объединяем два символа с

наименьшими вероятностями появления в новый

23

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

3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево – 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу.

Этот метод всегда дает оптимальное кодирование в отличие от предыдущего, так как получаемая средняя длина кодового слова является минимальной.

Буквы алфавита сообщения располагают в порядке убывания вероятностей. Две последние буквы объединяют в один составной символ, которому приписывают суммарную вероятность. Далее заново переупорядочивают символы и снова объединяют пару с наименьшими вероятностями. Продолжают эту процедуру до тех пор, пока все значения не будут объединены. Это называется редукцией. Затем строится кодовое дерево из точки, соответствующей вероятности 1 (это корень дерева), причем ребрам с большей вероятностью присваивают 1, а с меньшей – 0. Двигаясь по кодовому дереву от корня к оконечному узлу, можно записать кодовое слово для каждой буквы исходного алфавита.

Пример Расположим буквы алфавита А1 в порядке убывания

их вероятностей и подвергнем сжатию алфавит А1; при этом мы придём к алфавиту А2, который получается из первоначального алфавита А с помощью двукратного сжатия (а из алфавита А1 ─ с помощью простого или

24

однократного сжатия). Ясно, что алфавит А2 будет содержать уже всего n-2 буквы. Продолжая эту процедуру, мы будем приходить к всё более коротким алфавитам; после (n-2)-кратного сжатия мы придём к алфавиту Аn-2, содержащему уже всего две буквы.

Вот, например, как преобразуется с помощью последовательных сжатий рассмотренный выше алфавит,

Условимся теперь приписывать двум буквам последнего алфавита Аn-2 кодовые обозначения 1 и 0. Далее, если кодовые обозначения уже приписаны всем буквам алфавита Аj, то буквам «предыдущего» алфавита Аj- 1 (где, разумеется, А1-1 = А0 ─ это исходный алфавит А), сохранившимся и в алфавите Аj, мы пишем те же кодовые обозначения, которые они имели в алфавите Аj-1; двум же буквам а’ и а’’ алфавита Аj, «слившимся» в одну букву b

25

алфавита Аj-1, мы припишем обозначения, получившиеся из кодового обозначения буквы b добавлением цифр 1 и 0 в конце (табл. 4).

Таблица 4

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

Заметим ещё, что кодирование некоторого алфавита по методу Хаффмана (так же, впрочем, как и по методу Шеннона − Фано) не является однозначной процедурой.

Так, например, если на этапе построения кода заменить цифру 1 на цифру 0 и наоборот, то при этом мы получим два разных кода (отличающихся правда весьма несущественно друг от друга).

26

4. Порядок выполнения и оформления курсового проекта

1)Номер варианта курсового проекта соответствует номеру студента в групповом журнале.

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

-титульный лист;

-содержание;

-задание и исходные данные в соответствии с

номером варианта;

-введение;

-решение практических задач с подробным

расчетом основных характеристик и промежуточными результатами вычислений;

-выводы по проделанной работе;

-список использованных источников.

27

5. Варианты заданий для выполнения курсового проекта

ЗАДАНИЕ 1

Имеем Марковский источник с матрицей переходных вероятностей Р( хi / хj ) (в соответствии с вариантом).

сигналов:

- для вариантов 1 - 5:

р(х1) = 0,25; р(х2) = 0,15; р(х3) = 0,6;

- для вариантов 6 - 10:

р( х1 ) = 1/3; р( х2 ) = 1/3; р( х3 ) = 1/3; - для вариантов 11 - 15:

р( х1 ) = 0; р( х2 ) = 1; р( х3 ) = 0; - для вариантов 16 - 20:

р( х1 ) = 0,14; р( х2 ) = 0,36; р( х3 ) = 0,5.

29

Требуется:

1.1Построить граф состояний исходной системы

S[n].

1.2Найти энтропию Марковского источника Н1(Х) и избыточность Ки для состояния S[n].

1.3Найти энтропию Марковского источника Н2(Х) для состояния S[n+1].

1.4Построить предельную матрицу вероятностей перехода П∞.

1.5Найти предельную энтропию Н∞(Х) и избыточность Ки.

ЗАДАНИЕ 2

В системе связи используется двоичный источник с зависимыми элементами (буквами) x1 и x2, для которых заданы вероятности переходов.

Для разных вариантов

P(x1)=1/(1+N),

P(x2)=1-P(x1),

P(у1/х2)=1/(1+0,1·N),

P(у2/х1)=(N+4)/40,

где N – номер варианта.

30