Теория передачи сигналов (2 часть)
.pdfСтатистическое кодирование источника при группировании символов
При кодировании блоков, содержащих по две буквы, получим коды:
|
|
|
Кодовые |
|
|||
|
|
|
комбинации |
|
|||
Блоки |
Вероятности |
|
|
|
|
|
|
номер разбиения |
|||||||
|
|
||||||
|
|
|
|
|
|
||
|
|
1 |
|
2 |
|
3 |
|
|
|
|
|
|
|
|
|
b1=а1а1 |
0.81 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
b2=а1а2 |
0.09 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
b3=а2а1 |
0.09 |
1 |
|
1 |
|
0 |
|
|
|
|
|
|
|
|
|
b4=а2а2 |
0.01 |
1 |
|
1 |
|
1 |
|
|
|
|
|
|
|
|
|
31
Статистическое кодирование источника при группировании символов
Так как буквы первичного алфавита статистически не связаны, вероятности блоков определяют как произведение вероятностей. Среднее число двоичных символов на блок:
ср = 1 1 + 2 2 + 3 3 + 4 4
ср = 0.81 ∙ 1 + 0.09 ∙ 2 + 0.09 ∙ 3 + 0.01 ∙ 3 = 1.29 бит/блок
На букву первичного алфавита приходится 1.29/2 = 0.645 бит. Остаточная избыточность после кодирования :
|
= |
ср − |
= |
0.645 − 0.47 |
= 0.27 − или 27%. |
|
|
||||
ост |
|
ср |
0.645 |
|
|
|
|
|
|||
Эффективность кодирования повысилась.
32
Статистическое кодирование источника при
группировании символов
Кодирование блоков, содержащих по три знака, даёт ещё больший эффект:
|
Вероятно |
|
кодовые комбинации |
|
||||
Блоки |
сть |
|
|
номер разбиения |
|
|
||
|
Pi |
1 |
2 |
|
3 |
|
4 |
5 |
b1=а1а1а1 |
0.729 |
0 |
|
|
|
|
|
|
b2=а2а1а1 |
0.081 |
1 |
0 |
|
0 |
|
|
|
b3=а1а2а1 |
0.081 |
1 |
0 |
|
1 |
|
|
|
b4=а1а1а2 |
0.081 |
1 |
1 |
|
0 |
|
0 |
|
b5=а2а2а1 |
0.009 |
1 |
1 |
|
0 |
|
1 |
|
b6=а2а1а2 |
0.009 |
1 |
1 |
|
1 |
|
0 |
|
b7=а1а2а2 |
0.009 |
1 |
1 |
|
1 |
|
1 |
0 |
b8=а2а2а2 |
0.001 |
1 |
1 |
|
1 |
|
1 |
1 |
8
ср = = 1.66 бит/блок
=1
33
Статистическое кодирование источника при группировании символов
Среднее число двоичных символов на букву первичного алфавита: 1.66/3=0.55.
Остаточная избыточность после кодирования с группировкой по три символа в блоке:
|
= |
ср − |
= |
0.55 − 0.47 |
= 0.14 − или 14%. |
|
|
||||
ост |
|
ср |
0.55 |
|
|
|
|
|
|||
Эффективность кодирования в два раза лучше, чем после группировки по два символа в блоке.
34
Префиксные коды
Эффект статистического кодирования связан с различием в числе символов кодовых комбинации. Это приводит к трудностям при декодировании. Для различения кодовых комбинаций можно ставить специальный разделительный символ, но при этом значительно снижается желаемый эффект, так как средняя длина кодовой комбинации увеличивается.
Более целесообразно обеспечить однозначное декодирование без введения дополнительных символов.
Для этого необходимо кодировать так, чтобы ни одна комбинация короткого кода не совпадала с началом более длинной комбинации. Коды, удовлетворяющие этому условию, называются префиксными.
35
Префиксные коды
Код
a1 |
a2 |
a3 |
a4 |
00 |
01 |
101 |
100 |
|
|
|
|
декодируется однозначно:
100 |
00 |
01 |
101 |
101 |
101 |
00 |
|
|
|
|
|
|
|
a4 |
a1 |
a2 |
a3 |
a3 |
a3 |
a1 |
36
Префиксные коды
Последовательность комбинаций не префиксного кода имеет вид:
a1 |
a2 |
a3 |
a4 |
00 |
01 |
101 |
010 |
|
|
|
|
(комбинация 01 является началом комбинации 010). Может быть декодирована по-разному:
00 |
01 |
01 |
01 |
010 |
101 |
|
|
|
|
|
|
a1 |
a2 |
a2 |
a2 |
a4 |
a3 |
37
Префиксные коды
00 |
010 |
101 |
010 |
101 |
|
|
|
|
|
a1 |
a4 |
a3 |
a4 |
a3 |
или
00 |
01 |
010 |
101 |
01 |
01 |
|
|
|
|
|
|
a1 |
a2 |
a4 |
a3 |
a2 |
a2 |
38
НЕРАВЕНСТВО КРАФТА
Теорема. Если целые числа q1 ..., qi, ..., qn удовлетворяют неравенству:
2− ≤ 1,
=1
то существует код, обладающий свойством префикса с двоичным алфавитом, длины кодовых слов в котором равны этим числам.
Теорема утверждает только о возможном существовании префиксного кода, но не указывает его конкретный вид.
39
НЕРАВЕНСТВО КРАФТА
С помощью неравенства Крафта определяется число двоичных символов, приходящихся на букву алфавита для того, чтобы код был префиксным.
A X |
1/2 |
B |
XX |
1/4 |
2−1 + 2−2 + 2−3 + 2−4 + 2−4 |
|
|
|
|
C |
XXX |
1/8 |
|
D |
XXXX |
1/16 |
|
E |
XXXX |
1/16 Сумма даёт 1. |
|
Т.е. количество символов для кодирования 5 букв выбрано правильно.
40