ВУЗ:
Составители:
55
T
s
Δ
f
k
f
c
ln 1
P
u
S
0
Δ
f
k
.
ln 1
P
u
S
0
f
c
.
.
T
k
.
;
=T
s
6.617 sec
4. ЭФФЕКТИВНОЕ КОДИРОВАНИЕ
4.1. Основные сведения
Идея эффективного двоичного кодирования основывается на теореме Шенно-
на о кодировании для дискретных каналов без помех. Согласно этой теореме,
путем кодирования скорость передачи можно сделать максимальной
ν
k
C
HX
max
()
= .
Для этого нужно статистически согласовать источник и канал. Это достигается
так − наиболее вероятные сообщения кодируются более короткими кодовыми
комбинациями, а менее вероятные − более длинными. В этом случае средняя
длительность кодовой комбинации
∑
=
τ=τ=τ
n
1i
ii0cp0x
)x(npn , (4.1)
где
τ
0
− длительность двоичного символа;
cp
n
− среднее число символов в
сообщении;
)x(n
i
− число кодовых символов для i-го сообщения x
i
; p
i
− веро-
ятность этого сообщения.
Источник будет согласован с двоичным каналом, когда
~
()IX C=
. Отсю-
да следует
)X(Hn
min.cp
=
и
min.cp0
maxk
n
1
τ
=ν
. (4.2)
Код, обеспечивающий равенство (4.2), имеет наибольшую эффектив-
ность
maxkk
ν
ν
=
η и соответственно наименьшую избыточность
cp
min.cp
n
n
1R −=
. (4.3)
Известны две методики построения эффективного кода: алгоритм Шен-
нона-Фано и алгоритм Хаффмена. Последний алгоритм обеспечивает одно-
значное построение кода.
Рассмотрим алгоритм Хаффмена. Составляется таблица. В таблице со-
общения выписываются в основной столбец в порядке убывания их вероятно-
.
Страницы
- « первая
- ‹ предыдущая
- …
- 53
- 54
- 55
- 56
- 57
- …
- следующая ›
- последняя »
