книги из ГПНТБ / Бовбель, Е. И. Элементы теории информации

Разложение каждого Qt продолжается до тех пор, пока число членов разложения \ц не окажется в пределах

Iog Р(хі) ^ w ^ 1 + 1о§ Р{Хі) *

Остальные члены разложения отбрасываются. Таким об­ разом, каждому сообщению xt сопоставляется двоичное число (код) у 1г содержащее ^ членов: Qi~q__x<7_2?_3 ...

q = уі, где Рі определяется выражением (*).

Поясним процедуру коди розап ия на предложейиом выше примере. Результаты расчетов сведем в табл. 15.

Задача 1. Независимые сообщения Х\, х% ,ѵ3, Х\ появ­ ляются соответственно с вероятностями 1/2, 1/4, 1/8, 1/8 и кодируются по методу Шеннона — Фано: 0,10, ПО, 111. Показать, что в получающейся последовательности кодо­ вых слов символы «0» и «1» встречаются с равными ве­ роятностями.

Р е ш е н и е . Вероятность символа «0» определим как отношение среднего числа сим-волов «0» в кодовых словах к средней длине кодового слова:

£ «оР(хі)

Аналогично Р (1)'=1/2, что и требовалось-показать. Задача 2. Источник независимо друг от друга выраба­

тывает два различных сообщения Х\ и х<і с вероятностями

80

Р(х\) = 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

Пусть на выходе кодера I появляются двоичные кодо­ вые слова одинаковой длины (х, соответствующие пере­ даваемым сообщениям. Чтобы декодер I имел возмож­ ность'обнаруживать и исправлять ошибки, 2-е кодиру­ ющее устройство по некоторому правилу добавляет |хЛ корректирующих двоичных символов к каждому кодово­ му слову, поступающему на его вход. В результате полу­ чаются кодовые слова длиной символов, которые затем .передаются по линии связи с шумами, где некото­ рые символы искажаются (символ «1» подменяется сим­ волом «О», а символ «О»— символом «1»).

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

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

Таким образом, корректирующий код, удовлетворя­ ющий условию (4.1), способен в N(N0— N) случаях обна­ руживать ошибки из общего числа NqN. Однако если іѴ < < іѴ0, разрешенные комбинации могут быть выбраны с учетом вероятностных свойств шума так, чтобы вероят­ ность получения ошибочной разрешенной комбинации была очень мала. Другими словами, при Лгс<С-Ѵ0 в ре­ зультате ошибочного приема отдельных символов приня­ тое кодовое слово, как правило, окажется запрещенным, что и укажет на ошибку.

Для принятия однозначного решения о том, какое ко­ довое слово было отправлено, в общем случае все мно­ жество принимаемых кодовых слов No разбивается по не­ которому правилу на N подмножеств. Каждое подмноже­ ство отождествляется с одним из разрешенных кодовых слов. Если, например, принятое кодовое слово попало в і-е подмножество, считается, что было передано і-е кодо-

88