12. Надежность и пропускная способность канала

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

Предположим, что имеются два возможных символа 0 и 1, и мы ведем передачу со скоростью 1000 символов в секунду с вероятностями Таким образом, наш источник создает

информацию со скоростью 1000 бит в секунду. В процессе передачи шум вносит ошибки, так что в среднем один из ста символов принимается неправильно (0 вместо 1 или 1 вместо 0). Какова скорость передачи информации? Ясно, что она меньше 1000 бит в секунду, так как около принятых сигналов неправильны. Первое желание состоит в том, чтобы сказать, что эта скорость составляет 990 бит в секунду, т. е. просто вычесть среднее число ошибок. Однако это не совсем правильно, так как при этом не учитывается, что получатель не знает, где именно произошла ошибка. Можно рассмотреть крайний случай и предположить, что шум настолько велик, что принятые символы полностью не зависят от переданных. Вероятность принять 1 (0) равна 1/2, какой бы символ не был передан (1 или 0). Тогда благодаря одной случайности около половины принятых символов будут правильными, и нам пришлось бы считать, что система способна передавать 500 бит в секунду. Однако в действительности никакой передачи информации нет вовсе. Можно было бы получить столь же «хорошую» передачу, обойдясь вообще без канала и подбрасывая монету в точке приема.

Очевидно, истинная поправка к количеству переданной информации равна той части этой информации, которая отсутствует в принятом сигнале, или иначе той неопределенности относительно переданного сигнала, которая имеет место, когда известен принятый сигнал. Исходя из проведенного нами обсуждения понятия энтропии как меры неопределенности, представляется рациональным использовать условную энтропию сообщения (при известном сигнале) как меру этой недостающей части информации. Как будет видно ниже, такое определение действительно является подходящим. Следуя этой идее, было бы можно получить скорость действительной передачи информации вычитая из скорости создания информации (т. е. энтропии источника) среднюю скорость Условной энтропии

Условная энтропия для удобства будет называться ненадежностью. Она является мерой средней неопределенности принятого сигнала.

В рассмотренном выше примере, если принят символ 0, то апостериорная вероятность того, что был передан символ 0, равна 0,99, а того, что была передана единица — 0,01. Если же была принята единица, то эти цифры поменяются местами. Следовательно,

или 81 бит в секунду. Мы можем сказать, что система передает информацию со скоростью бит в секунду. В том крайнем случае, когда при передаче символа 0 равновероятен прием как 0, так и 1, и аналогично для символа 1, апостериорные вероятности равны 1/2, 1/2 и тогда:

или 1000 бит в секунду. В этом случае скорость передачи равна 0, как и следовало ожидать.

Следующая теорема дает непосредственную интуитивную интерпретацию ненадежности, а также служит тому, чтобы оправдать ее как единственную подходящую меру. Рассмотрим систему связи и наблюдателя (или вспомогательный прибор), который может видеть как то, что передается, так и то, что принимается (с ошибками из-за шума). Этот наблюдатель отмечает ошибки в принятом сообщении и передает эти данные в точку приема через «коррекционный канал», чтобы дать возможность в точке приема исправить ошибки. Схематически это показано на рис. 8.

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

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

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

Вторая часть теоремы может быть доказана, если заметить, что для любых дискретных случайных переменных х, у, z

Разлагая дальше левую часть, получим

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

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

Рис. 8. Схема корректирующей системы.

Эти ошибки могут быть исправлены, если известны их положения. Таким образом, по коррекционному каналу нужно посылать информацию только об этих позициях. Это сводится к передаче информации от источника, который создает двоичные цифры, причем 1 имеет вероятность (неправильно) и -вероятность (правильно). Для этого требуется канал с пропускной способностью

что равно ненадежности исходной системы.

Исходя из упомянутых выше тождеств, скорость передачи может быть записана в двух других формах. А именно:

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

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

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