3.7. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КАНАЛА С ПОМЕХАМИ

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

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

то таких способов не существует.

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

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

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

при сколь угодно малом положительном

Поскольку код (3.71) обеспечит при безошибочный прием, однако одновременно при этом и скорость передачи информации по каналу стремится к нулю, тогда как согласно теореме К. Шеннона существуют коды, которые, в отличие от кода (3.71), обеспечивают сколь угодно малую вероятность ошибки при конечной скорости передачи информации.

Заметим, что условие (3.69) можно записать так:

где число сообщений, поступающих от источника в секунду.

Поэтому можно дать и другую формулировку основной теоремы К. Шеннона: если среднее число символов канала на одно сообщение источника удовлетворяет неравенству

то существует способ кодирования и декодирования, обеспечивающий сколь угодно малую вероятность ошибки, если же

такого способа нет. Как следует из (3.74) с учетом 3.57, при двоичиом симметричном канале без памяти минимальное значение

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

Конечно, при можно передавать такие сигналы, что достигнет значения Но — это скорость передачи информации о сигнале В, а не о сообщении А. Поэтому вопрос сводится к тому, можно ли установить такое соответствие (код) между сообщением А и сигналом В, чтобы вся информация, полученная на выходе канала о сигнале В, была в то же время и информацией о сообщении А?

Положительный ответ на этот воцрос очевиден только в тривиальном случае, когда в канале нет помех и сигнал В принимается безошибочно. При этом и если между установлено взаимно однозначное соответствие, то по принятому сигналу можно однозначно восстановить сообщение. В общем же случае в канале имеются помехи и сигнал В принимается с ошибками, так что С учетом (3.54) и (3.69) отсюда следует, что

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

Теорема Шеннона дает на этот вопрос почти положительный ответ, с той лишь поправкой, что скорость «утечки информации» (или ненадежность) не равна в точности нулю, но может быть сделана сколь угодно малой. Соответственно сколь угодно малой может быть сделана вероятность ошибочного декодирования. Как будет видно из доказательства, чем меньше допустимая вероятность ошибочного декодирования, тем сложнее должен быть код.

Идея доказательства основной теоремы кодирования Шеннона для дискретного канала основана на случайном кодировании. Рассмотрим некоторое множество кодов и определим среднюю (по всему этому множеству кодов) вероятность ошибочного декодирования, которая в условиях теоремы окажется меньше наперед заданной величины Отсюда следует, что в рассмотренном множестве кодов содержатся такие, для которых вероятность ошибочного декодирования также меньше чем и будет завершено доказательство.

Пусть при некотором ансамбле входных сигналов дискретного канала обеспечивается пропускная способность канала:

В соответствии с теоремой об асимптотической равновероятности (см. § 2.8) число типичных последовательностей входных сигналов достаточно большой длительности (содержащих достаточно большое число символов равно

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

Рис. 3.12. (см. скан) Иллюстрация идеи случайного кодирования типичных последовательностей источника и возможных переходов типичных входных последовательностей в канале с шумами

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

Выполним указанное кодирование (сопоставление последовательностей источника и канала) всеми возможными способами. Очевидно, что число возможных кодов равно числу размещений элементов по Каждому из них соответствует своя вероятность ошибки Средняя по всем этим способам вероятность ошибки

Средняя вероятность ошибочного приема типичной последовательности источника может быть получена в предположении случайного выбора типичной кодовой последовательности сообщений той же длительности.

При достаточно большом вероятность того, что какая-то типичная последовательность канальных сигналов использована при кодировании, в силу равновероятности выбора, с учетом (3.76)

Пусть принят некоторый выходной сигнал (последовательность символов) длительностью Он мог, в принципе, получиться при передаче любого входного сигнала Среди них существует типичных, а вероятность того, что в действительности передавался некоторый сигнал, не входящий в число этих «условно типичных», при достаточно большом меньше любого наперед заданного положительного числа

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

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

Таким образом, среднюю по всем кодам вероятность ошибочного декодирования сигнала длительностью можно оценить неравенством Буля

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

На основании (3.77) и

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

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

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

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

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

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

Подчеркнем важный результат, непосредственно следующий из формул (3.79) и (3.80): верность связи тем выше, чем больше т. е. чем длиннее кодируемый отрезок сообщения (а следовательно, и больше задержка при приеме информации), и чем менее эффективно используется пропускная способность канала (чем больше разность определяющая «запас пропускной способности» канала). Итак, существует возможность обмена между верностью, задержкой и эффективностью системы. С увеличением существенно возрастает сложность кодирования и декодирования (число операций, число элементов и стоимость аппаратуры). Поэтому практически чаще всего предпочитают иметь умеренное значение задержек которые, кстати, не во всех системах связи можно произвольно увеличивать, и добиваются повышения верности за счет менее полного использования пропускной способности канала.

Примеры практического применения кодирования для повышения верности передачи информации будут приведены в последующих главах.