<< Предыдущая

стр. 12
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

0

100 9/41 10 18/41
2
о
liL
0

17
010 8/41 3
0 010 24/41
i
по
15
110 4/41 3 12/41
0
0- 1
8
111 4/41 111 12/41
3
1
Of
оно
Oil 4/41 16/41
4
7
°1
101 3/41 0111 12/41
4
1
000 0
л _ 1 112_
0,911
бит" 3 41 ˜


2. Найдите энтропию источника.

3. Проведите кодирование Хаффмана для блоков, состоящих из
трех двоичных символов.

4. Какой эффективностью обладает кодирование?

Решение.
1. Переходные вероятности рис. 5.9 равны

тг(А/А)=0,9 ir{B/A)=0,l
(5.106)
тф4/В)=0,3 IT{B/B) = 0,7.

Стационарное значение вероятности состояния А определяется, ис-
ходя из следующих равенств

Р(А) = 1 - Р{В)
(5.107)
Р(А) = 0,9 -Р(А)+ 0,3 -Р{В),
поэтому,
Р{А) = 0,9 • Р{А) + 0,3 • (1 - Р(А))
Р(А)-[1 -0,9 + 0,3] = 0,3 (5.108)
Р(А) = 3/4.
Из этого следует, что
Р{В) = 1/4. (5.109)
5.5. Кодирование стационарных марковских источников
Таблица 5.2. Кодирование Хаффмана для марковского ис-
точника с памятью г = 2 и длиной блока 4.


1:
pt Кодо вая конструкция Кодовое слово
Гимволы п,Р,

2
1001 9/41 00 18/41
°
з
n

0010 100
6/41 18/4]
n ' °
о
з
0100 110 18/4]
6/41 °
n
0
4
17 0
ООП 3/41 1010 12/41
11
0
4
1100 3/41 0 12/41
1110
'—т. 4
0101 2/41 0100 8/41
0 ]j
>1 4
2/41 0101 8/41
1110
1 оно 4
i 8/41
2/41
1111
J
l__J
0111 4 8/41
ОНО 2/41
7
0
10110 5
I
O—j 4
0111 10/41
2/41

ют 5
1
1010 10/41
2/41
°-t
5
11110 5
1101 1/41 5/41
°˜П2
inn 5 5/41
1011 1/41

-
1000 -
0

-
0000 -
0

0001 0


-=- = 4 4 1 .0.744
!.!»
бит



2. Энтропия источника определяется как
Н{А)
= -0,9 log2 0,9-0,1 log2 0,1 = 0,469
бит
Н{В) (5.110)
= -0,71og2 0,7 - 0,31og20,3 = 0,811
бит
НХ(Х) = Р{А) • Н(А) + Р(В) • Н(В) = 0,572 бит.

3. Вероятности блоков, состоящих из трех двоичных символов, равны

-7г(А/А) • ж(А/А) = 0,6075
Р(ААА) = Р(А)
• ж{А/А) • ж{В/А) = 0,0675
Р(ААВ) = Р(А)
• ж{В/А) • IT(A/B) = 0,0225
Р(АВА) = Р(А)
= Р(А) • к(В/А) • ж{В/В) = 0,0525
Р(АВВ)
(5.111)
• тг{А/В) • -п{А/А) = 0,1225
Р(ВАА) = Р(В)
• п(А/В) • тг{В/А) = 0,0525
Р(ВАВ) = Р(В)
• п(В/В) • п(А/В) = 0,0075
Р(ВВА) = Р{В)
• п(В/В) • ж(В/В) = 0,0675.
Р(ВВВ) = Р(В)

Кодирование Хаффмана представлено на рис. 5.10.
Глава 5. Стационарные дискретные источники с памятью


Вероятность Кодовое
Блок состояния слово


0
0,6075
ААА 0

0
ВВВ 0,1225 100
0 0 22 1
45 , 0
0 0675
ААВ 110
0095
,2
3
02
.
1
ВАЛ 0,0675 1010

05
,
1 1
ABB 0,0525 O-jJ 1011


03 085
, ,2
00
1110
0,0525
ВВА


°п
0,0225 11110
ABA

1
1
ППП7Ч
RAR



Рис. 5.10. Кодирование Хаффмана.

4. Средняя длина кодового слова определяется как

п = 1/3(0,6075 + 3(0,1225 + 0,0675)+
+ 4(0,0675 + 0,0525 + 0,0525)+ (5.112)
+ 5(0,0225 + 0,0075)) = 0,6725,

следовательно, эффективность кодирования равна
0,572 _п
Нж(х)
(5.113)
ос
•п 0,6725


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

Таблица 5.3. Марковские цепи.


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


Дискретный по времени и состояниям марковский процесс называет-
ся марковской цепью. Его реализацией является последовательность
состояний
S, €S = {SI,S2,...,SN].



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

n(j/i) = P(Sj/Si) для j,i = 0,1,2,3,..., N.



• Гомогенная марковская цепь полностью определяется матрицей пе-
реходных вероятностей П

<< Предыдущая

стр. 12
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>