алфавита Аj-1, мы припишем обозначения, получившиеся из кодового обозначения буквы b добавлением цифр 1 и 0 в конце (табл. 4).
Таблица 4
№ |
Вероятности |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
букв |
Исходный |
|
Сжатые алфавиты |
|
|
|
|
||||
ы |
алфавит А |
|
А1 |
|
А2 |
|
А3 |
|
А4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0,4 |
0 |
|
0,4 |
0 |
0,4 |
0 |
0,4 |
0 |
0,6 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
2 |
0,2 |
10 |
|
0,2 |
10 |
0,2 |
10 |
0,4 |
11 |
0,4 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
3 |
0,2 |
111 |
|
0,2 |
111 |
0,2 |
111 |
0,2 |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
0,1 |
1101 |
|
0,1 |
1101 |
0,2 |
110 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
0,05 |
11001 |
|
0,1 |
1100 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
0,05 |
11000 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Легко видеть, что из самого построения получаемого таким образом кода Хаффмана вытекает, что он удовлетворяет общему условию: никакое кодовое обозначение не является здесь началом другого, более длинного кодового обозначения, т.е. полученный код является префиксным.
Заметим ещё, что кодирование некоторого алфавита по методу Хаффмана (так же, впрочем, как и по методу Шеннона − Фано) не является однозначной процедурой.
Так, например, если на этапе построения кода заменить цифру 1 на цифру 0 и наоборот, то при этом мы получим два разных кода (отличающихся правда весьма несущественно друг от друга).
26
4. Порядок выполнения и оформления курсового проекта
1)Номер варианта курсового проекта соответствует номеру студента в групповом журнале.
2)Отчет должен содержать:
-титульный лист;
-содержание;
-задание и исходные данные в соответствии с
номером варианта;
-введение;
-решение практических задач с подробным
расчетом основных характеристик и промежуточными результатами вычислений;
-выводы по проделанной работе;
-список использованных источников.
27
5. Варианты заданий для выполнения курсового проекта
ЗАДАНИЕ 1
Имеем Марковский источник с матрицей переходных вероятностей Р( хi / хj ) (в соответствии с вариантом).
№ |
варианта |
х(Р |
х(Р |
х(Р |
х(Р |
х(Р |
х(Р |
х(Р |
х(Р |
х(Р |
|
|
) |
) |
) |
) |
) |
) |
) |
) |
) |
|
|
1 |
2 |
3 |
1 |
2 |
3 |
1 |
2 |
3 |
|
|
/ х |
/ х |
/ х |
/ х |
/ х |
/ х |
/ х |
/ х |
/ х |
|
|
1 |
1 |
1 |
2 |
2 |
2 |
3 |
3 |
3 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1/4 |
3/4 |
0 |
0 |
1/4 |
3/4 |
5/8 |
0 |
3/8 |
|
|
|
|
|
|
|
|
|
|
|
2 |
|
1/4 |
0 |
3/4 |
0 |
1/2 |
1/2 |
1/3 |
1/3 |
1/3 |
|
|
|
|
|
|
|
|
|
|
|
3 |
|
1/3 |
0 |
2/3 |
1/4 |
1/2 |
1/4 |
0 |
1/2 |
1/2 |
|
|
|
|
|
|
|
|
|
|
|
4 |
|
1/4 |
0 |
3/4 |
0 |
2/3 |
1/3 |
1/3 |
1/3 |
1/3 |
|
|
|
|
|
|
|
|
|
|
|
5 |
|
1/3 |
1/3 |
1/3 |
0 |
1/2 |
1/2 |
1/8 |
0 |
7/8 |
|
|
|
|
|
|
|
|
|
|
|
6 |
|
3/4 |
1/4 |
0 |
0 |
3/4 |
1/4 |
1/4 |
1/4 |
1/2 |
|
|
|
|
|
|
|
|
|
|
|
7 |
|
1/3 |
1/2 |
1/6 |
0 |
1/4 |
1/4 |
1/2 |
1/2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
8 |
|
1/3 |
1/2 |
1/6 |
0 |
3/4 |
1/4 |
1/2 |
1/2 |
0 |
|
|
|
|
|
|
|
|
|
|
|
9 |
|
1/4 |
3/4 |
0 |
0 |
1/4 |
3/4 |
3/4 |
0 |
1/4 |
|
|
|
|
|
|
|
|
|
|
|
10 |
|
3/4 |
1/4 |
0 |
0 |
1/2 |
1/2 |
3/4 |
0 |
1/4 |
|
|
|
|
|
|
|
|
|
|
|
11 |
|
1/3 |
1/3 |
1/3 |
0 |
1/2 |
1/2 |
3/4 |
0 |
1/4 |
|
|
|
|
|
|
|
|
|
|
|
12 |
|
1/3 |
0 |
2/3 |
1/4 |
1/2 |
1/4 |
1/2 |
0 |
1/2 |
|
|
|
|
|
|
|
|
|
|
|
13 |
|
1/4 |
3/4 |
0 |
0 |
1/2 |
1/2 |
1/3 |
1/3 |
1/3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
28 |
|
|
|
|
|
14 |
|
1/4 |
3/4 |
0 |
0 |
1/6 |
5/6 |
1/4 |
1/2 |
1/4 |
|
|
|
|
|
|
|
|
|
|
|
15 |
|
1/4 |
0 |
3/4 |
0 |
1/2 |
1/2 |
1/6 |
1/3 |
1/2 |
|
|
|
|
|
|
|
|
|
|
|
16 |
|
3/4 |
1/4 |
0 |
0 |
1/4 |
3/4 |
1/8 |
1/4 |
1/8 |
|
|
|
|
|
|
|
|
|
|
|
17 |
|
1/3 |
1/2 |
1/6 |
0 |
1/4 |
3/4 |
1/4 |
1/2 |
1/4 |
|
|
|
|
|
|
|
|
|
|
|
18 |
|
1/2 |
1/3 |
1/6 |
1/4 |
0 |
3/4 |
1/4 |
1/2 |
1/4 |
|
|
|
|
|
|
|
|
|
|
|
19 |
|
1/4 |
3/4 |
0 |
0 |
1/4 |
3/4 |
5/8 |
0 |
3/8 |
|
|
|
|
|
|
|
|
|
|
|
20 |
|
5/8 |
0 |
3/8 |
1/3 |
1/2 |
1/6 |
1/4 |
0 |
3/4 |
|
|
|
|
|
|
|
|
|
|
|
|
Начальные |
значения |
вероятности |
появления |
||||||
сигналов:
- для вариантов 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