3. Кодирование в отсутствие шумов

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

Пусть алфавит системы состоит из m символов. Средствами этого алфавита требуется представить любой из М возможных сигналов {u_k}, k=1, ... , M, вероятности которых {р(u_k)} заданы. Обычно М>т, поэтому каждый из сигналов, подлежащих передаче, невозможно обозначить только одним символом и приходится ставить им в соответствие некоторые последовательности символов; назовем их кодовыми словами. Так как возможна последовательная передача разных кодовых слов, то они не только должны различаться для разных u_k, но и не должны быть продолжением других, более коротких. Пусть сигналу u_k соответствует кодовое слово длиной l_k символов. При стационарной передаче сигналов с вероятностями {р(u_k)} средняя длина кодового слова равна L=_k l_kp(u_k).

Возникает вопрос о том, как выбирать L и {l_k}. Он не имеет смысла, пока не задан критерий выбора этих величин. Определим этот критерий так: L и {l_k} должны быть минимальными величинами, такими, при которых еще не происходит потери информации. Напомним, что в отсутствие шумов среднее количество информации на один элемент u_k ансамбля {u_k} равно энтропии этого ансамбля, т.е. H(U)=_k=1^Mp(u_k)logp(u_k), а индивидуальное количество информации в u_k есть i(u_k)=-logp(u_k). С другой стороны, на один символ придется максимальное количество информации, если символы равновероятны и независимы; при этом i = log m. Поскольку кодирование должно вестись без потерь информации, сразу получаем: H(U)log^-1mL; i(u_k)log^-1ml_k i(u_k)log^-1m + 1;

Так из общих соображений находим нижние границы для L и l_k. В теории информации доказываются теоремы об условиях достижимости этих границ. Мы не будем приводить эти теоремы; укажем лишь, что речь идет не только о принципиальной возможности: разработаны процедуры построения кодов, обеспечивающих безызбыточное кодирование (либо в случае невозможности этого - сколь угодно близкое к нему).

4. Кодирование при наличии шумов

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

Воспроизведем упрощенное доказательство указанного утверждения. Рассмотрим схему передачи по каналу с шумом. Будем считать, что на вход кодера сигналы поступают закодированными безызбыточно. Кодер вносит в сигналы избыточность, увеличивая длительность кодовых слов. Число возможных последовательностей сразу резко увеличивается, но избыточность и состоит в том, что к отправке предназначаются не все из них, а лишь разрешенные. Согласно фундаментальному свойству энтропии, число всевозможных последовательностей длины n равно 2^nH(X) а число разрешенных к отправке равно 2^nH<2^nH(X) (считаем, что энтропия исчисляется в битах); H-энтропия на символ во множестве разрешенных к отправке последовательностей ("энтропия источника", или "скорость создания информации"), Н(Х)-энтропия на символ во множестве всевозможных последовательностей. В результате воздействия шумов какие-то из символов отправленной последовательности подменяются другими и на приемный конец поступает другая, отличная от отправленной, последовательность. Поскольку p(x|y) считается известным, каждой принятой последовательности соответствует 2^nH(X|Y) возможно отправленных. Декодирование (т.е. принятие решения о том, какая последовательность была отправлена) можно выразить как разбиение всего множества К принимаемых последовательностей на 2^nH подмножеств, сопоставляемых с разрешенными к отправке: если, например, принят сигнал i-й группы, то считается, что был послан i-й разрешенный сигнал, который тут же выдается в "чистом" виде получателю.

Итак, в построенной модели проблема выбора кода (способа передачи) состоит в размещении разрешенных последовательностей среди множества всевозможных на передающем конце и в разбиении этого множества из 2^nH(X) последовательностей на 2^nH подмножеств на приемном конце. Идея Шеннона состоит не в том, чтобы указать некоторый регулярный способ кодирования со сколь угодно малой вероятностью ошибки, а в том, чтобы показать, что такой код вообще существует. Рассмотрим класс всевозможных кодов, которые получаются, если разрешенные последовательности размещать среди всевозможных случайным образом, а в качестве декодирующего подмножества брать 2^nH(X/Y) последовательностей высоковероятностной группы, соответствующей принятому сигналу.

Вероятность ошибки при этом равна вероятности того, что среди 2^nH(X/Y) последовательностей окажется более одной разрешенной. Так как код получается в результате случайного (равновероятностного) выбора 2^nH последовательностей среди 2^nH(X), то вероятность того, что данная последовательность окажется разрешенной, равна 2^nH/2^nH(X)=2^nH-nH(X). Средняя вероятность того, что в декодирующем подмножестве из 2^nH(X/Y) последовательностей имеется только одна разрешенная, выразится соотношением P=(1-2^n(H-H(X))^2nH(X/Y)-1; это и есть вероятность безошибочного приема. Поскольку H<C=H(Х)-Н(Х|Y), имеем H(Х)-Н(Х)=-Н(Х|Y)-, где  >0. Отсюда (пренебрегая единицей по сравнению с 2^nH(X/Y) ) находим P=(1-2^-n(H|Y)+)^2nH(X/Y).

Логарифмируя и применяя правило Лопиталя, легко показать, что lim|_{n } P=1, т.е. что при кодировании достаточно длинными блоками средняя вероятность ошибки может быть сделана сколь угодно малой. Доказательство завершается утверждением, что существуют коды с вероятностями ошибок меньше средней.