Тема 2.6. Теорема К. Шеннона

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

(A)<C , (12.38)

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

Рассмотрим содержание теоремы Шеннона.

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

Но является ли это условие достаточным?

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

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

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

Если бы двоичный канал был без помех и допускал передачу двоичных символов со скоростью символ/с, то пропускная способность в расчёте на секунду была бы

(2.39)

В этом случае данная теорема свелась бы к теореме о кодировании источника.

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

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

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