|
Слово
|
Вероятность
|
КК
|
Длина КК
|
|
АА
|
0,6577
|
1
|
1
|
|
АВ
|
0,0324
|
00111
|
5
|
|
АD
|
0,1208
|
01
|
2
|
|
ВА
|
0,0324
|
00110
|
5
|
|
ВВ
|
0,0016
|
0010111
|
7
|
|
ВD
|
0,0060
|
0010110
|
7
|
|
DA
|
0,1208
|
000
|
3
|
|
DB
|
0,0060
|
001010
|
6
|
|
DD
|
0,0222
|
00100
|
5
|
Для получения кодов для кодирования
по три символа используем методику Хаффмена, предварительно рассчитав частоты
появления слов, которые состоят из трех символов:
Р(ААА) = Р(А)*Р(А)*Р(А) =
0,811*0,811*0,811 = 0,5334
Р(ААВ) = Р(А)*Р(А)*Р(B) = 0,811*0,811*0,040 = 0,0263
Р(ААD) = Р(А)*Р(А)*Р(D) = 0,811*0,811*0,149 = 0,0980
Р(АBА) = Р(А)*Р(B)*Р(А) = 0,811*0,040*0,811 = 0,0263
Р(АBB) = Р(А)*Р(B)*Р(B) = 0,811*0,040*0,040 = 0,0013
Р(АBD) = Р(А)*Р(B)*Р(D) = 0,811*0,040*0,149 = 0,0048
Р(АDА) = Р(А)*Р(D)*Р(А) = 0,811*0,149*0,811 = 0,0980
Р(АDB) = Р(А)*Р(D)*Р(B) = 0,811*0,149*0,004 = 0,0048
Р(АDD) = Р(А)*Р(D)*Р(D) = 0,811*0,149*0,149 = 0,0180
Р(BАА) = Р(B)*Р(А)*Р(А) = 0,040*0,811*0,811 =
0,0263
Р(BАВ) = Р(B)*Р(А)*Р(B) = 0, 040*0,811*0,040 = 0,0013
Р(BАD) = Р(B)*Р(А)*Р(D) = 0, 040*0,811*0,149 = 0,0048
Р(BBА) = Р(B)*Р(B)*Р(А) = 0, 040*0,040*0,811 = 0,0013
Р(BBB) = Р(B)*Р(B)*Р(B) = 0, 040*0,040*0,040 = 0,0001
Р(BBD) = Р(B)*Р(B)*Р(D) = 0, 040*0,040*0,149 = 0,0002
Р(BDА) = Р(B)*Р(D)*Р(А) = 0, 040*0,149*0,811 = 0,0048
Р(BDB) = Р(B)*Р(D)*Р(B) = 0, 040*0,149*0,004 = 0,0002
Р(BDD) = Р(B)*Р(D)*Р(D) = 0, 040*0,149*0,149 = 0,0009
Р(DАА) = Р(D)*Р(А)*Р(А) = 0,149*0,811*0,811 =
0,0980
Р(DАВ) = Р(D)*Р(А)*Р(B) = 0, 149*0,811*0,040 = 0,0048
Р(DАD) = Р(D)*Р(А)*Р(D) = 0, 149*0,811*0,149 = 0,0180
Р(DBА) = Р(D)*Р(B)*Р(А) = 0, 149*0,040*0,811 = 0,0048
Р(DBB) = Р(D)*Р(B)*Р(B) = 0, 149*0,040*0,040 = 0,0002
Р(DBD) = Р(D)*Р(B)*Р(D) = 0, 149*0,040*0,149 = 0,0009
Р(DDА) = Р(D)*Р(D)*Р(А) = 0, 149*0,149*0,811 = 0,0180
Р(DDB) = Р(D)*Р(D)*Р(B) = 0, 149*0,149*0,004 = 0,0009
Р(DDD) = Р(D)*Р(D)*Р(D) = 0, 149*0,149*0,149 = 0,0033
|
Слово
|
Вероятность
|
КК
|
Длина КК
|
|
ААA
|
0,5334
|
1
|
1
|
|
АAВ
|
0,0263
|
010111
|
6
|
|
АAD
|
0,0980
|
001
|
3
|
|
AВА
|
0,0263
|
010110
|
6
|
|
AВВ
|
0,0013
|
0100011011
|
10
|
|
AВD
|
0,0048
|
01010011
|
8
|
|
ADA
|
0,0980
|
011
|
3
|
|
ADB
|
0,0048
|
01010010
|
8
|
|
ADD
|
0,0180
|
00011
|
5
|
|
ВАA
|
0,0263
|
010101
|
6
|
|
ВAВ
|
0,0013
|
0100011010
|
10
|
|
ВAD
|
0,0048
|
01010001
|
8
|
|
ВВА
|
0,0013
|
0101000011
|
10
|
|
ВВВ
|
0,0001
|
0101000010111
|
13
|
|
ВВD
|
0,0002
|
0101000010110
|
13
|
|
ВDA
|
0,0048
|
01000111
|
8
|
|
ВDB
|
0,0002
|
0101000010101
|
13
|
|
ВDD
|
0,0009
|
01010000100
|
11
|
|
DАA
|
0,0980
|
000
|
3
|
|
DAВ
|
0,0048
|
01000101
|
8
|
|
DAD
|
0,0180
|
010010
|
6
|
|
DВА
|
0,0048
|
01000100
|
8
|
|
DВВ
|
0,0002
|
0101000010100
|
13
|
|
DВD
|
0,0009
|
0101000001
|
10
|
|
DDA
|
0,0180
|
010000
|
6
|
|
DDB
|
0,0009
|
010100000
|
9
|
|
DDD
|
0,0033
|
010001100
|
9
|
2. Сравним между
собой построенные коды и их эффективность
Рассчитаем среднюю длину кодовой
комбинации в расчете на один символ источника.
l ср (1) = 0,811*1 + 0,040*2 + 0,149*2 = 1,189
l ср (2) = [0,6577*1 + (0,0324 + 0,0324 + 0,0060 + 0,0222)*5 +
(0,0016 + 0,0060)*7 + 0,128*3]/2 = 0,8929
l ср (3) = 2,5296/3 = 0,8432
Найдем относительную разницу между
средней длиной кодовой комбинации и энтропией источника.
Н(х) = 0,8126
Видим, что наиболее
эффективным будет код при кодировании по три символа.
3. Построенными
кодами закодируем фрагмент текста
AAAAAAAAAAADDAAAAAAAAAAABADAAA
Для кодирования по одному символу:
Длина двоичной последовательности: L = 34.
Для кодирования по два символа:
Длина двоичной последовательности: L = 24.
Для кодирования по три символа:
Длина двоичной последовательности: L = 21.
Для источника с памятью
1. Построим двоичные
неравномерные эффективные коды для кодирования слов длиной в два символа,
предварительно рассчитав вероятности их появления.
Р(А) = 0,604
Р(В) = 0,175
Р(D) = 0,220
Р(АА) = Р(А)*Р (А/A) = 0,604*0,809 = 0,4886
Р(АВ) = Р(А)*Р (В/A) = 0,604*0,039 = 0,0236
Р(АD) = Р(А)*Р (D/A) = 0,604*0,152 = 0,0918
Р(BА) = Р(B)*Р (А/B) = 0,175*0,375 = 0,0656
Р(BB) = Р(B)*Р (B/B) = 0,175*0,534 = 0,0935
Р(BD) = Р(B)*Р (D/B) = 0,175*0,091 = 0,0159
Р(DА) = Р(D)*Р (А/D) = 0,220*0,226 = 0,0497
Р(DB) = Р(D)*Р (B/D) = 0,220*0,262 = 0,0576
Р(DD) = Р(D)*Р (D/D) = 0,220*0,512 = 0,1126
Неравномерные двоичные
эффективные коды построим по методике Хаффмена.
|
Слово
|
Вероятность
|
КК
|
Длина КК
|
|
АА
|
0,4886
|
1
|
1
|
|
АВ
|
0,0236
|
011011
|
6
|
|
АD
|
0,0918
|
0111
|
4
|
|
ВА
|
0,0656
|
0101
|
4
|
|
ВВ
|
0,0935
|
001
|
3
|
|
ВD
|
0,0159
|
011010
|
6
|
|
DA
|
0,0497
|
01100
|
5
|
|
DB
|
0,0576
|
0100
|
4
|
|
DD
|
0,1126
|
000
|
3
|
2. Разработаем марковские
процедуры для кодирования слов по одному символу:
Для состояния А:
Р (А/А) = 0,809
Р (В/А) = 0,039
Р (D/А) = 0,152
|
Символ, что ожидается
|
Условная вероятность
|
КК
|
Длина КК
|
|
А
|
0,809
|
1
|
1
|
|
В
|
0,039
|
01
|
2
|
|
D
|
0,152
|
00
|
2
|
Для состояния В:
Р (А/В) = 0,375
Р (В/В) = 0,534
Р (D/В) = 0,091
|
Символ, что ожидаетсяУсловная вероятностьККДлина КК
|
|
|
|
|
А
|
0,375
|
11
|
2
|
|
В
|
0,534
|
0
|
1
|
|
D
|
0,091
|
10
|
2
|
Для состояния D:
Р (А/D) = 0,226
Р (В/D) = 0,262
Р (D/D) = 0,512
|
Символ, что ожидаетсяУсловная вероятностьККДлина КК
|
|
|
|
|
А
|
0,226
|
11
|
2
|
|
В
|
0,262
|
10
|
2
|
|
D
|
0,512
|
0
|
1
|
Разработаем марковские процедуры для
кодирования слов по два символа:
двоичный
неравномерный код марковский
Р (АА/А) = Р (А/A)*Р (А/A) = 0,809*0,809 = 0,6545
Р (АВ/А) = Р (А/A)*Р (В/A) = 0,809*0,039 = 0,0316
Р (АD/А) = Р (А/A)*Р (D/A) = 0,809*0,152 = 0,1230
Р (BА/А) = Р (B/A)*Р (А/B) = 0,039*0,375 = 0,0146
Р (BB/А) = Р (B/A)*Р (B/B) = 0,039*0,534 = 0,0208
Р (BD/А) = Р (B/A)*Р (D/B) = 0,039*0,091 = 0,0035
Р (DА/А) = Р (D/A)*Р (А/D) = 0,152*0,226 = 0,0343
Р (DB/А) = Р (D/A)*Р (B/D) = 0,152*0,262 = 0,0398
Р (DD/А) = Р (D/A)*Р (D/D) = 0,152*0,512 = 0,0778
|
Слово
|
Вероятность
|
КК
|
Длина КК
|
|
АА
|
0,6545
|
1
|
1
|
|
АВ
|
0,0316
|
0111
|
4
|
|
АD
|
0,1230
|
001
|
3
|
|
ВА
|
0,0146
|
000111
|
6
|
|
ВВ
|
0,0208
|
00010
|
5
|
|
ВD
|
0,0035
|
000110
|
6
|
|
DA
|
0,0343
|
0110
|
4
|
|
DB
|
0,0398
|
0000
|
4
|
|
DD
|
0,0778
|
010
|
3
|
Для состояния B:
Р (АА/B) = Р (А/B)*Р (А/A) = 0,375*0,809 = 0,3034
Р (АВ/B) = Р (А/B)*Р (В/A) = 0,375*0,039 = 0,0146
Р (АD/B) = Р (А/B)*Р (D/A) = 0,375*0,152 = 0,0570
Р (BА/B) = Р (B/B)*Р (А/B) = 0,534*0,375 = 0,2003
Р (BB/B) = Р (B/B)*Р (B/B) = 0,534*0,534 = 0,2852
Р (BD/B) = Р (B/B)*Р (D/B) = 0,534*0,091 = 0,0486
Р (DА/B) = Р (D/B)*Р (А/D) = 0,091*0,226 = 0,0206
Р (DB/B) = Р (D/B)*Р (B/D) = 0,091*0,262 = 0,0238
Р (DD/B) = Р (D/B)*Р (D/D) = 0,091*0,512 = 0,0466
|
СловоВероятностьККДлина КК
|
|
|
|
|
АА
|
0,3034
|
11
|
2
|
|
АВ
|
0,0146
|
001011
|
6
|
|
АD
|
0,0570
|
0011
|
4
|
|
ВА
|
0,2003
|
01
|
2
|
|
ВВ
|
0,2852
|
10
|
2
|
|
ВD
|
0,0486
|
0001
|
4
|
|
DA
|
0,0206
|
001010
|
6
|
|
DB
|
0,0238
|
00100
|
5
|
|
DD
|
0,0466
|
0000
|
4
|
Для состояния D:
Р (АА/D) = Р (А/D)*Р (А/A) = 0,226*0,809 = 0,1828
Р (АВ/D) = Р (А/D)*Р (В/A) = 0,226*0,039 = 0,0088
Р (АD/D) = Р (А/D)*Р (D/A) = 0,226*0,152 = 0,0344
Р (BА/D) = Р (B/D)*Р (А/B) = 0,262*0,375 = 0,0983
Р (BB/D) = Р (B/D)*Р (B/B) = 0,262*0,534 = 0,1399
Р (BD/D) = Р (B/D)*Р (D/B) = 0,262*0,091 = 0,0238
Р (DА/D) = Р (D/D)*Р (А/D) = 0,512*0,226 = 0,1157
Р (DB/D) = Р (D/D)*Р (B/D) = 0,512*0,262 = 0,1341
Р (DD/D) = Р (D/D)*Р (D/D) = 0,512*0,512 = 0,2621
|
СловоВероятностьККДлина КК
|
|
|
|
|
АА
|
0,1828
|
11
|
2
|
|
АВ
|
0,0088
|
011111
|
6
|
|
АD
|
0,0344
|
01110
|
5
|
|
ВА
|
0,0983
|
0110
|
4
|
|
ВВ
|
0,1399
|
010
|
3
|
|
ВD
|
0,0238
|
011110
|
6
|
|
DA
|
0,1157
|
101
|
3
|
|
DB
|
0,1341
|
100
|
3
|
|
DD
|
0,2621
|
00
|
2
|
3. Сравним между собой
разработанные коды и оценим их эффективность.
Для кодирования по одному символу:
Для кодирования по два
символа:
4. Разработанными кодами и
процедурами закодируем фрагмент текста:
АААААААААААААААААААDBBAAAAAAAA
При кодировании кодами по два
символа:
Длина кодовой комбинации: L = 20
Кодирование процедурами будем выполнять в порядке справа налево, считая, что
перед появлением первого символа на выходе источника был символ А.
При кодировании процедурами по
одному символу:
Длина кодовой комбинации: L = 33
При кодировании процедурами по два
символа:
Длина кодовой комбинации: L = 24