Файл: Бовбель, Е. И. Элементы теории информации.pdf

Р(х\) = 0,9 и Р(х2) =0,1.- Произвести кодирование по ме­ тоду Хаффмана: а) отдельных сообщений; б) сообщений, составленных по два в группе; в) сообщений, составлен­ ных по три в группе. Сравнить коды по экономности (L), по скорости передачи (I) и по избыточности (R). Длитель-

мости кодовых символов одинаковы и равны т0 = 10~ с. Р е ш е ін и е. Энтропия источника сообщений

Н(Х) = —0,91og0,9 0,1 logO, 1 = 0,469 (бит).

а) При кодировании отдельных сообщений методом Хаффмана сообщению Х\ сопоставляется кодовый символ «1», а сообщению х2 «0». Средняя длина кодового симво­ ла при этом L= 0,9*1+0,1 • 1 = 1. Скорость передачи

что составляет 46,9% от пропускной способности С = 1/т. Избыточность кода равна избыточности источника сооб­ щений:

Средняя длина кодового слова, приходящегося на од­ но сообщение:

L = у (1- 0,81+2-0,09+3-0,09+3-0,01) =0,645.

Скорость передачи при этом

00000

82

что составило 72,7% от максимально возможной скоро­ сти передачи (10б бит/с).

Чтобы найти избыточность кода, вычислим вероят­ ность появления кодового символа «О»:

0,09-2 4- 0,09-1 0,01-2 0,645-2

Р( 1) = 1 — Р(0) = 0,77.

Энтропия кода

Нк= —0,23 logO,23—0,77 log 0,77 = 0,778 (бит);

избыточность Rk = 1 — Hk —0,222.

в) Наконец, перейдем к кодированию групп сообще­ ний, содержащих три сообщения в группе (табл. 17).

Средняя длина кодового слова, приходящаяся на од­ но сообщение, в этом случае будет

L = у (0,729+0,081 -9+0,009-15+0,001-5) =0,533.

При этом скорость передачи

0,469

880000 (бит/с),

0,533-10-6

что составляет 88% от С. Вероятность появления симво­ ла «0»

0,08Ь5+0,009-11+0,001-5

0,533-3

Р( 1) = 1 - Р ( 0 ) = 0,68. .

Найдем энтропию и избыточность кода в этом случае:

Я* = —0,32 log 0,32—0,68. log 0,68=0,904; '

Rk = 1 - Hk = 0,096.

Сведем полученные результаты в табл. 18.

83

‘ Если кодировать группы по четыре и более сообщений, мы еще более приблизимся к предельным значениям вы­ числяемых величин. • •

Задача 3. Закодировать методом Хаффмана сообще­ ния источника, описываемого схемой вида

в кодовом алфавите, содержащем три различных символа уи Уъ Уъ- Вычислить экономичность полученного кода.

Ре ш е и и е. Энтропия источника

Н(Х) = 0 ,4 lo g 0,4+0,4 log 0,2+0,2 lo g 0,05 = 2,322 (бит).

Процедура составления кода Хаффмана в этом случае иллюстрируется табл. 19.

Задача 4. Проверить, что выписанная наугад произволь­ ная последовательность кодовых символов легко декоди­ руется, если кодирование производится методами Шен­ нона — Фано и Хаффмана.

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

Р е ш е н и е. Так как число сообщений (лг = 15) боль- ше числа кодовых символов (л г = 3 ), то каждому сооб-

84

щеншо необходимо ставить в соответствие более одного кодового символа.

Первое сообщение (х\) можно закодировать любым кодовым символом, к примеру, символом а. Таким обра­

для кодирования сообщений Х\ и х 2 только т ( т — 1\) =

= 3(3— 1) = 6 следующих;

bc, ba, cb, ca, bb, сс.

число использованных для кодирования кодовых слов, со­ держащих два кодовых символа, l2 = 2<ijn(m — 1\) — 6. Для кодирования оставшихся сообщений используем ко­ довые слова, содержащие по три кодовых символа. Число их равно 33= 2 7 . Выпишем их;

Для последующего кодирования мы не должны использо­ вать в таблице (3.37) те последовательности, которые со­ держат в начале себя символ а (х\) и кодовые слова Ьс (х2) и Ьа (хг). Оставшихся последовательностей (3.37)

/:{ = [т(чп — Іі)— /2]/?г = 12

оказывается достаточно для кодирования сообщений лг4, х$, ..., Хіз. Тогда кодовая таблица будет выглядеть так:

85

Легко видеть, что произвольная последовательность кодо­ вых символов

aacccbcccccbbababccbacaaacbc

декодируется без разделительных символов:

Х\Х\Х\ QX2X1qX1 3 Х1 X1 3 ХIX3 Х2 Х5 Х1 1 ^ 1 ^ 1 5

Задача 6. Источник вырабатывает 16 различных сооб­ щений. Энтропия источника Н ( Х ) = 2 (бит). Показать, что равномерное двоичное кодирование сообщений не яв­ ляется оптимальным.

Р е ш е н и е . При равномерном кодировании каждому сообщению сопоставляется одинаковое число кодовых символов. Минимальное число их находится из уравнения

2^-— 16, откуда- (X= 4 . Таким образом, каждому из 16 сообщений сопоставляется кодовое слово, состоящее из 4 двоичных чисел. Очевидно, при этом средняя длина ко­ дового слова L = 4 .

Из теоремы (Шеннона) о кодировании следует, что средняя длина кодового слова (при подходящем кодиро­ вании) может быть

что и доказывает неоптимальность равномерного кода.

I

Г Л А В А 4

§ 1. Модель канала связи, в котором действуют шумы

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

Для ослабления действия шумов в информационную систему приходится вводить два дополнительных устрой­ ства— кодер II и декодер I (рис. 4). Назначение второго

Рис. 4

кодера состоит в реализации помехоустойчивого кодиро­ вания сигналов, В простейшем случае 2-е кодирующее устройство многократно повторяет те сигналы кодера I, которые наиболее сильно подвержены, действию шума в линии связи; последующее сличение многократно пере­ данных сигналов уменьшает вероятность их неправильно­ го приема. Однако такой метод помехоустойчивого коди­ рования резко увеличивает необходимое время передачи; Заметим, что во всех случаях кодер вносит ту или иную избыточность’в сигналы, выдаваемые кодером I, благода­ ря чему помехоустойчивость системы растет.

Назначение декодера I состоит в том, чтобы восста­ навливать по принятому сигналу соответствующий сигнал ііа выходе кодера I.

Функции, выполняемые кодером I и декодером II, та­ кие же, как в схеме на рис. 3.

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

87