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

При наличии шума в канале невозможно передавать информацию с достоверностью. Вместе с тем введенное определение [6] характеризует пропускную способность канала с шумом. Очевидно, что, передавая информацию с избыточностью, можно снизить вероятность ошибок до приемлемого уровня. Можно ли, увеличивая избыточность кодирования источника, приблизить вероятность ошибки к нулю? Можно, но при этом скорость передачи будет также стремиться к нулю. С точки зрения эффективности передачи информации мы имеем ситуацию, когда, кажется, требования к источнику и каналу вошли в противоречие. В действительности определенная выражением [6] пропускная способность имеет вполне определенное значение. При надлежащем кодировании по каналу можно передавать информацию со скоростью С со сколь угодно малой частотой ошибок или при сколь угодно малой ненадежности. Это утверждение не верно, если скорость передачи больше С. При попытках передавать информацию со скоростью больше С (С+R’), неизбежно появится ненадежность, равная или больше R’. Проиллюстрируем сказанное рисунком 2. Скорость передачи отложена по горизонтали, ненадежность – по вертикали.

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

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

ТЕОРЕМА. Пусть дискретный канал обладает пропускной способностью С, а дискретный источник энтропией в секунду Н. Если Н ≤ С, то существует такая система кодирования, что сообщения источника могут быть переданы по каналу с произвольно малой частотой ошибок (или сколь угодно малой ненадежностью). Если Н > С, то можно закодировать источник таким образом, что ненадежность будет меньше, чем Н – С + ε, где ε сколь угодно мало. Не существует способа кодирования, обеспечивающего ненадежность, Н – С.

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

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

C =max[H(x) – H_у(x), [7]

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

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

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

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

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

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

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

В этих утверждениях все ”ε” и “δ” , подразумеваемые в словах “малый” и “примерно”, стремятся к нулю, когда Т возрастает и S₀ приближается к источнику, обеспечивающему предельную пропускную способность.

Сказанное иллюстрируется рисунком 2.2, где H(Z) соответствует → H(x), H(Z*) → H(y), H(Z/Z*) → H_y(x), H(Z*/Z) → H_x(y), Z – входные последовательности, Z* - выходные последовательности.

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

Предположим, имеется другой источник S, создающий информацию со скоростью R, причем R<C. За время Т этот источник будет создавать 2^TR высоковероятных сообщений. Требуется связать их с некоторым выбранным множеством возможных входных сигналов канала таким образом, чтобы получить малую частоту ошибок. Используя высоковероятностную группу входных сигналов, которая определяется источником S₀ , усредним частоту ошибок по этому большому классу возможных систем кодирования. Это равносильно вычислению частоты ошибок при случайном связывании сообщений и входных сигналов канала длительности Т. Предположим, что наблюдается некоторый выходной сигнал y₁. Какова вероятность того, что во множество возможных причин получения этого у₁ войдет более одного сообщения от источника S? Имеется 2^TR сообщений, распределенных по 2 ^TH(x) точкам. Вероятность того, что некоторая конкретная точка будет сообщением, равна 2^{T[R – H(x)]}. Вероятность того, что никакая другая точка веера (кроме действительно исходного сообщения) не будет сообщением, равна

[8]

Но R < H(x) – H_у(x), так что R – H(x) = - H_y(x) – η,

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

[9]

стремится (при Т → ∞) к 1 – 2^--Тη , из чего вполне очевидно, что ошибка стремится к нулю, и первая часть теоремы доказана.

Вторая часть теоремы легко доказывается из условия, что можно просто передавать С бит в секунду от источника, пренебрегая остатком создаваемой информации. В приемнике эта неучитываемая часть создает ненадежность H(x) – C, а передаваемая часть должна добавить лишь ε. Последнее утверждение теоремы является простым следствием принятого определения С. Предположим, что можно закодировать некоторый источник с энтропией H(x) = C + α таким образом, чтобы получить ненадежность H(x) = α – ε, где ε положительно. Тогда

Н(x) – H_y(x) = C + ε,

причем ε также положительно. Это, однако, противоречит определению С как максимума H(x) – H_y(x).