Основная теорема Шеннона для дискретных каналов с шумом

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

V_{к max} [ log₂m – H(B/B’)] > V_и * H(A),(4.1)

где H(A) – энтропия источника.

Здесь обозначения соответствуют схеме, изображенной на рис. 4.6.

4.6. Схема системы передачи информации через дискретный канал связи с помехами и сопутствующие обозначения.

Доказательство

Согласно полученной ранее формуле, число типичных последовательностей длительностью Т равно:

N_тип(А) = 2^Vи*T*H(A) (4.2)

Максимально возможное число различных последовательностей на выходе кодера, которое сможет иметь ту же длительность, Т равна:

N(B) = m^Vк*T,

где m – объем вторичного алфавита.

Эту формулу можно записать также в виде:

(4.3)

Предположим, что условие теоремы V_к [ log₂m – H(B/B’)] > V_и * H(A) выполняется. Тогда, поскольку H(B/B’)>0, неравенство условия теоремы только усилится, если его записать в виде: V_к log₂m > V_и * H(A).

Домножим левую и правую части неравенства на Т и сделаем их показателями двойки:

.

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

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

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

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

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

По условной энтропии H(B/B’) можно найти количество возможных типичных последовательностей на входе канала, которые после искажения в нем могли бы дать определенную последовательность на выходе канала:

N_тип(B/B’) = 2^{T Vк H(B/B’) .} (4.4)

Вывод аналогичен сделанному ранее при исследовании свойств типичных последовательностей. Только в данном случае энтропия символа на выходе канала – функция того, какой символ получен на входе канала – H(B/B’).

Правильный прием возможен только тогда, когда на [N_тип(B/B’)-1] не разрешенных кодовых слов приходится одно разрешенное, т.е. число возможных кодовых слов вообще должно быть в N_тип(B/B’) раз больше числа типичных N_тип(A) последовательностей, которые может выдать источник.

Предположим теперь, что соответствия между типичными последовательностями, выдаваемыми источником, и кодовыми словами устанавливаются равновероятно. Тогда вероятность p_разр того, что определенное кодовое слово среди N_тип(А) является разрешенным, равна: p_разр=N_тип(А)/N(B) (кодируются только типичные последовательности).

Соответственно, вероятность того, что кодовое слово является запрещенным равна 1- p_разр= 1 - N_тип(А)/N(B).

Правильное декодирование возможно только тогда, если среди N_тип(B/B’) кодовых слов только одно выбрано в качестве разрешенного.

Вероятность этого равна:

.

Так как основание степени , то, увеличивая показатель степени с N_тип(B/B’)-1 до N_тип(B/B’), получим неравенство:

. (4.5)