2.6. Обратная теорема кодирования

Обратная теорема Шеннона для кодирования в дискретных каналах без памяти может быть сформулирована следующим образом:

Если скорость создания информацииR больше пропускной спо­собности канала С, то никакой код не может обеспечить сколь угод­но малой ошибки.

Общие методы доказательства обратной теоремы основаны на ис­пользовании неравенства Фано. Здесь мы ограничимся частным случаем передачи по симметричному каналу без памяти с мощностью алфавита кодовых символов n. Скорость передачи информации (на символ) определяется как , где носит название апостериорной энтропии отправленного сигнала на символ, или рассеяния информации в канале. Чтобы снять неопределенность оставшуюся после приема из-за возможных ошибок, необ­ходимо дополнительное количество информации, равное на каждый символ. Для установления, какой именно символ был пере­дан, если принят символ , необходимо:

1. Установить, была ли совершена ошибка при передаче данного символа. Если вероятность ошибки равна р, то количество информации, связанное с фактом наличия ошибки,

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

Таким образом, оказывается справедливым следующее неравенство:

Это неравентсво можно принимать в более общем смысле, отнеся его не только к отдельным кодовым символам, но и к кодовым словам и блокам любой длины; рассматривая код как множество пар , понимая под вероятность ошибочного декодирования i-ого кодового слова при обнаружении его в j-й, j≠Iрешающей области и рассматривая в качестве апостериорной неопределенности отправленного слова . Тогда можно записать следующую последовательность неравенств:

Далее в силу теоремы о высоковероятных множествах при больших n, следует: , поэтому

В условиях прямой теоремы следовательно

.

Поскольку , то , откуда видно, что не может быть сколь угодно малым при любом n. Более того, можно показать, что при увеличении n стремиться к 1. Действительно, при R>Cвеличина μ становится отрицательной. При этом , и вероятность безошибочного приема стремится к нулю.

Следует сделать следующие замечания:

- теоремы Шеннона носят характер теорем существования; четких и конструктивных алгоритмов кодирования и декодирования в них не дается;

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

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