Наиболее интересные и важные результаты были получены при рассмотрении передачи информации по каналам связи с шумами. В этом случае безизбыточное кодирование приведет к безвозвратным потерям информации: искаженный символ нельзя ни обнаружить, ни исправить. Для борьбы с влиянием помех необходимо ввести избыточность в сигнал. Основываясь на интуитивных соображениях, легко прийти к выводу, что при неограниченном повышении требований к малости вероятности ошибки избыточность (при любом способе кодирования) должна неограниченно возрастать, а скорость передачи — стремиться к нулю. Здесь мы имеем яркий пример того, как интуиция может привести к сильному заблуждению. К.Шеннон показал, что «существуют такие способы введения избыточности, при которых обеспечиваются одновременно и сколь угодно малая вероятность ошибки и конечная (отличная от нуля) скорость передачи информации. Причем эта скорость может быть сколь угодно близкой к пропускной способности канала». Это замечательное открытие и привлекло столь большое внимание к теории информации. Воспроизведем упрощенное доказательство указанного утверждения.
Рис.11.1 — Схема передачи по каналу с шумом
Будем считать, что на вход кодера сигналы поступают закодированными безизбыточно. Кодер вносит в сигнал избыточность, увеличивая длительность кодовых слов. Число возможных последовательностей сразу резко увеличивается. Но избыточность и состоит в том, что к отправке предназначаются не все из них, а лишь «разрешенные» (на рис. отмечены черными кружками). Согласно фундаментальному свойству энтропии, число всевозможных последовательностей длины n равно 2n⋅H(X), а число разрешенных к отправке равно 2n⋅H < 2n⋅H(X) (считаем, что энтропия исчисляется в битах); Н — энтропия на символ во множестве разрешенных к отправке последовательностей (»энтропия источника», или «скорость создания информации»), H(X) — энтропия на символ во множестве всевозможных последовательностей. В результате воздействия шумов какие-то из символов отправленной последовательности подменяются другими и на приемный конец поступает другая, отличная от отправленной, последовательность. Поскольку p(x/y) считается известной, каждой принятой последовательности соответствует 2n⋅H(X/Y) возможно отправленных. Декодирование, (т.е. принятие решения о том, какая последовательность была отправлена) можно выразить как разбиение всего множества Y принимаемых последовательностей на 2n⋅H подмножеств, сопоставляемых с разрешенными к отправке. Если, например, принят сигнал i-й группы, то считается, что был послан i-й разрешенный сигнал, который и выдается в «чистом» виде получателю. Итак, в построенной модели проблема выбора кода (способа передачи) состоит в размещении разрешенных последовательностей среди множества всевозможных на передающем конце и в разбиении этого множества из 2n⋅H(X) последовательностей на 2n⋅H подмножеств на приемном конце.
Идея Шеннона состоит не в том, чтобы указать некоторый регулярный способ кодирования со сколь угодно малой вероятностью ошибки, а в том, чтобы показать, что такой код вообще существует.
Рассмотрим класс всевозможных кодов, которые получаются, если разрешенные последовательности размещать среди всевозможных случайным образом, а в качестве декодирующего подмножества брать 2n⋅H(X/Y) последовательностей высоковероятной группы, соответствующей принятому сигналу. Вероятность ошибки при этом равна вероятности того, что среди 2n⋅H(X/Y) последовательностей окажется более одной разрешенной. Так как код получается в результате случайного (равновероятного) выбора 2n⋅H последовательностей среди 2n⋅H(X), то вероятность того, что данная последовательность окажется разрешенной, равна
2n⋅H/2n⋅H(X) = 2n⋅(H-H(X)).
(6)
Средняя вероятность того, что в декодирующем подмножестве из 2n⋅H(X/Y) последовательностей имеется только одна разрешенная, выразится соотношением
P = {1 - 2n⋅(H-H(X))}2n⋅H(X/Y) - 1.
(7)
Это и есть вероятность безошибочного приема. Поскольку
H < C = H(X) - H(X/Y), H - H(X) = -H(X/Y) - ν, где ν > 0
Отсюда (пренебрегая единицей по сравнению с 2n⋅H(X/Y) находим
P = {1 - 2n⋅(H-H(X))}2n⋅H(X/Y) - 1.
Логарифмируя и применяя правило Лопиталя, легко показать, предел Р = 1, при n стремящемся к бесконечости, т.е. при кодировании достаточно длинными блоками средняя вероятность ошибки может быть сделана сколь угодно малой. Доказательство завершается утверждением, что существуют коды с вероятностями ошибок меньше средней.
