книги из ГПНТБ / Толстоусов, Г. Н. Прикладная теория информации учеб. пособие

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

Рассмотрим свойства выражения (12.I I ) . Воспользуемся нера­ венством

59

или

Среднее количество информации (12.10) как математическое ожидание неотрицательных величин также неотрицательно. Несмот­ ря на действие помех информация монет быть передана.

Условная энтропия системы не может быть больше априорной энтро­ пии. Этим доказано предположение (6 .10).

§13. Пропускная способность дискретного канала связи с помехами. Согласование источника

иканала связи

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

60

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

Рассмотрим другой пример. Пусть принятые сообщения о пара­

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

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

Каждый канал связи характеризуется своей скоростью передачи информации.

Пусть H'(Z)- скорость изменения энтропии передатчика. При сигналах передатчика равной длительности имеем

61

где Н(Ю- энтропия передатчика на один сигнал, определяе­ мая вероятностями состояний источника и системой кодирования;

“ZT - длительность одного сигнала.

Каждый сигнал передатчика передает согласно (12Л ) коли­ чество информации

ма кодирования, которая позволяет все сообщения источника пѳрет дать по каналу связи со сколь угодно малой ненадежностью///!^/}/.

Если Н'(Х) '"Сrit то не существует системы кодирования, обес­ печивающей ненадежность, меньшую, чем Н'(Х)~Сп. «

Эта теорема здесь приводится без доказательства, главным образом потому, что способ доказательства не указывает системы

62

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

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

н (х )< с ^/п £ и сн { г). (as)

Важно успеть принять все сообщения без искажения, а для этого необходимо соотношение

H 'fK j& C aBm aafc'fehH 'tè/vr)]' (*&

Из сравнения (13.5) и (13.б) видно, какую избыточность следует вводить для канала с помехами. Эта избыточность используется при построении системы кодирования.

Рассмотрим пример вычисления пропускной способности кана­ ла связи с помехами. Пусть имеется передатчик с двумя сигнала­

Wj

/ - /

Рис. 13.2

63

Модель помех описывается табл. 13.I условных вероятностей Pftij/Zi} . Найдем частные условные энтропии. Имеем

где оС(fil) - используемое далее обозначение.

При определении пропускной способности необходимо найти максимум выражения (13.7). Характеристика помехи ߣ считается заданной и не варьируется. Для энтропии приемника H(w) как системы с двумя состояниями имеем

rrubxH(W)- 1<fcr. (/3.9;

Следовательно, пропускная способность

05.10)

Скорость передачи информации равна пропускной способности, ког­

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

64

вероятно решение о правильном приеме, а при jic> 0,5 - о не­ правильном.

§ 14. Понятие об обнаруживающем и корректирующем кодах

Некоторые модели помех позволяют построить систему кодиро­ вания, обеспечивающую согласование источника и канала связи в полном соответствии с теоремой о пропускной способности. Рас­ смотрим следующий пример. В бинарном канале связи (передатчик передает два сигнала 0 и I ) помехи таковы, что из трех последо­ вательно передаваемых сигналов монет исказиться только одиіиТри вероятности искажения любого из трех сигналов и вероятность правильной передачи равны. Определим пропускную способность та­ кого канала. Для удобства в качестве сигнала передатчика примам трѳхраарядную кодовую комбинацию. Тогда будем иметь восемь пе­

65

H(wMc)= - £ р(г$/Ъ)6$рЩ /*г)=-4-~~Лу£=ЪГит .

P ( * /j/Z i)

Следовательно, средняя условная энтропия приеиника

H (w {zh ld U T .

Для определения пропускной способности необходимо найти m axH (W ). Учитывая, что принимается восемь разных сигналов,

имеем

fno*3e.H(w) = &xj£-d<fur .

Следовательно, пропускная способность канала

При отсутствии помех пропускная способность этого канала была

у, mcbX.H(W)_ з

66

Помехи втрое уменьшили пропускную способность. Хотя техни­

ческая скорость передачи сигналов от помех естественно не за­ висит, необходимо передавать сообщения источника втрое медлен­ нее. Избыточные сигналы передатчика используем следующим обра­ зом. Закодируем сообщения оптимальным неравномерным кодом. На­ зовем сигналы, необходимые для этого, информационными и обозна­ чим их через ct . При передаче по линии связи после каждого информационного сигнала будем передавать еще два контрольных сигнала еі и 6ХѣЭти сигналы выберем так, чтобы суммы

s ^ c , + e i t

Sj.—C1+

были четными.

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

ность. Ііы используем более длинные кодовые комбинации. Величи­ на избыточности кода

6?

случае помех, передавая только разрешенные комбинации, возмок-

ев перехода в другие разрешенные комбинации (пунктирные линии), что соответствует необнарукиваемым ошибкам; ~£к)спуча- ев перехода в запрещенные комбинации, что соответствует обна­ руживаемым ошибкам.

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

2 к(2'ь-2*) z Kz n-

корректирующим.

Некоторые элементарные понятия о построении кода могут быть показаны с помощью геометрической интерпретации. Любая

68