Файл: Бездудный, В. Г. Техника безопасности в шахтном строительстве.pdf

При укрупнении кодируемых блоков происходит не только де­ корреляция символов и снижение условной энтропии, вызванной взаимозависимостью между символами, но и уменьшение избыточности от округления. Природа избыточности от округления в том, что при передаче двоичным кодом максимально загруженными бывают только те символы вторичного алфавита, которые передают значение, являю­ щееся целыми степенями двойки. В остальных случаях тем же коли­ чеством символов может быть передано большее количество сообщений.

рядами можно передать и 65, и 128 сообщений. Фактически на пере­ дачу 65 сообщений необходимо L — log2 65 = 6,02 символа. Однако, как известно, 65 сообщений в двоичном коде не может быть передано менее чем семью символами, т. е. избыточность от округления D —

б02

=1 ------у - = 0,14. Аналогично для 100 сообщений

Совершенно очевидно, что избыточность от округления будет умень­ шаться по мере укрупнения блоков. Следовательно, код будет при­ ближаться к оптимальному.

Рассмотрим пример, иллюстрирующий преимущества укрупнения, или, как его часто называют, перекодирования символов.

Пример 6. Построим ОНК для передачи сообщения, алфавит которого состоит из двух букв — А и В с вероятностями рА — 0,89 и рд = 0,11, при кодировании пр

одному (I случай), два (II случай) и три (III случай) символа в блоке (табл. 13). Определяем средние числа двоичных знаков на букву кода и энтропии источни­

79

+ 3 ■0,011 log3 0,011 + 0,001 log2 0,001) = 0,3555 + 3 • 0,9065 +

+ 3 • 0,0716 + 0,0100 = 1,4998 бит/символ.

Таблица IS

Построение оптимального кода при блочном кодировании

Сравнивая полученные данные, убеждаемся, что с укрупнением кодируемых блоков разница значений L и Н быстро уменьшается, а полученный код приближает­ ся к оптимальному. Сравним эффективность ОНК в первом и третьем случаях. Для

этого определим:

TJ

80

"71 i ■

С увеличением числа символов в блоке эффективность кодирования

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

где N — число букв первичного алфавита; т — число букв вторичного алфавита.

81

Для передачи М-буквенного текста в двоичном коде (число букв вторичного алфавита т = 2) с равновероятным распределением букв русского алфавита (число букв первичного алфавита N = 32) надо затратить Л4Л0 = M log2 32 = М • 5 бит.

Оптимальным в этом случае будет равномерный код. Примером такого кода является телеграфный код Бодо, в котором каждая буква состоит из пяти двоичных символов (см. табл. 4).

Однако в действительности вероятности появления букв в русских текстах не одинаковы. Согласно табл. 3, вероятности появления от­ дельных букв значительно отличаются друг от друга. Чаще всего в русских текстах, как и в текстах на любом языке мира, встречается пробел между словами: вероятность его равна 0,175 (в английском языке 0,2); реже всего — буквы Э и Ф.

Естественно, что при неравновероятном распределении символов первичного алфавита равномерные коды не могут быть оптимальными. Эффективными в этом случае являются неравномерные коды, в кото­ рых наиболее часто встречающимся символам первичного алфавита соответствуют наиболее короткие комбинации символов вторичного алфавита. По такому принципу построен современный телеграфный код Морзе, хотя он и отличается от оптимального кода для троичного алфа­ вита (точка, тире и пауза), представленного в третьей колонке табл. 14.

Для определения значения п при передаче русских текстов с учетом вероятности распределения символов в выражении (55) зна­ чения Н следует находить по формуле

Н = — ^ P il o g p i . i

Так как для т = 21og2m = 1, то п = МП = М (—0,175 log3 0,175 —

— 0,09log2 0,09 — ... —0,02log2 0,02) » 4,36М.

Как видим, по сравнению с кодом Бодо достигнуто сокращение 0,64 бит на кодовое слово. Такого значения средней длины кодового слова для русского алфавита можно добиться при помощи оптималь­ ного кода, построенного методом Шеннона — Фано и представленного в табл. 15. Средняя длина кодового слова для кода табл. 15

L = ^ I (ОР( = 0,175 • 3 + 0,090 • 3 + 0,072 • 4 + • • • +

+ 0,002 - 9 « 4 ,4 .

Значение L отличается от значения Н, потому что вероятности рас­ пределения символов первичного алфавита (в данном случае — алфа­ вита русских букв) не являются целочисленными степенями двойки. Однако с ростом М среднее число знаков вторичного алфавита на кодовое слово будет сколь угодно приближаться к значению Я, что было проиллюстрировано примером 6. 4

При поблочном кодировании данный код будет еще ближе к опти­ мальному, так как в нем устранится избыточность, вызванная взаимо­ зависимостью между соседними буквами.

82