Кодирование информации. Шикина В.Е. - 9 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

6
Среднее число символов на блок равно 1,59, а на букву 0,53, что всего
на 12% больше энтропии. Теоретический минимум Н(z)=0,47 может быть
достигнут при кодировании блоков, включающих бесконечное число букв:
(
)
zHllim
ср
n
=
∞→
. (1.3)
Следует подчеркнуть, что увеличение эффективности кодирования при
укрупнении блоков не связано с учетом все более далеких статистических
связей, так как нами рассматривались алфавиты с некоррелированными
буквами. Повышение эффективности определяется лишь тем, что набор
вероятностей, получающийся при укрупнении блоков, можно делить на более
близкие по суммарным вероятностям подгруппы.
1.4. Методика Хаффмена
Рассмотренная нами методика Шеннона – Фэно не всегда приводит к
однозначному построению кода. Ведь при разбиении на подгруппы можно
сделать большей по вероятности как верхнюю, так и нижнюю подгруппу.
Множество вероятностей, приведенных в табл. 1.2, можно было бы разбить
иначе, например, так, как это показано в табл. 1.5.
Табл. 1.5
Буквы Вероятности
Кодовые
комбинации
Ступень
разбиения
z
1
0,22 11
z
2
0,20 10 II
z
3
0,16 011 I
z
4
0,16 010 IV
z
5
0,10 001 III
z
6
0,10 0001 V
z
7
0,04 00001 VI
z
8
0,02 00000 VII
При этом среднее число символов на букву оказывается равным 2,80.
Таким образом, построенный код может оказаться не самым лучшим. При
построении эффективных кодов с основанием m>2 неопределенность становится
еще больше.
От указанного недостатка свободна методика Хаффмена. Она гарантирует
однозначное построение кода с наименьшим для данного распределения
вероятностей средним числом символов на букву.
Для двоичного кода методика сводится к следующему. Буквы алфавита
сообщений выписываются в основной столбец в порядке убывания
вероятностей. Две последние буквы объединяются в одну вспомогательную

Страницы