13. Основная теорема для дискретного канала с шумом

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

Изложенное выше показано на рис. 9. Скорость информации в канале отложена по горизонтали, а ненадежность — по вертикали.

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

Эти положения являются основным оправданием предложенного определения С и будут сейчас доказаны.

Рис. 9. Ненадежность, возможная для энтропии входа канала.

Теорема 11. Пусть дискретный канал обладает пропускной способностью С, а дискретный источник — энтропией в секунду Н. Если то существует такая система кодирования, что сообщения источника могут быть переданы по каналу с произвольно малой частотой ошибок (или со сколь угодно малой ненадежностью). Если то можно закодировать источник таким образом, что ненадежность будет меньше чем где сколь угодно мало. Не существует способа кодирования, обеспечивающего ненадежность, меньшую чем

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

Пропускная способность канала с шумом была определена как

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

Пусть источник, на котором достигается максимальная пропускная способность С. Если максимум в действительности не достигается ни на каком источнике (но достигается лишь в пределе), то пусть источник, для которого пропускная способность достаточно близка к предельной.

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

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

2. Аналогично имеется высоковероятное множество принимаемых последовательностей, содержащее примерно членов, и маловероятное множество оставшихся последовательностей.

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

4. Каждая из высоковероятных входных последовательностей может создать примерно выходных последовательностей. Суммарная вероятность всех других исходов мала.

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

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

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

одного сообщения от источника Имеется сообщений, распределенных случайно по точкам. Вероятность того, что некоторая конкретная точка будет сообщением, поэтому равна

Рис. 10. (см. скан) Схематическое представление соотношений между входами и выходами в канале.

Вероятность того, что никакая другая точка веера (кроме действительного. исходного сообщения) не будет сообщением, равна

Но , так что

где положительно. Следовательно,

стремится (при к

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

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

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

причем положительно. Это противоречит определению С как максимума

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