2.4. Основная теорема Шеннона для дискретного канала

Определенную в разделе 2.3 скорость передачи I^!(X,Y) от X к Y можно интерпретировать и как скорость передачи информации по дискретному каналу, если под ансамблями X и Y понимать ансамбли сообщений на его входе и выходе

. (2.18)

Из четырех энтропий, фигурирующих в этом выражении, только H(X) - собственная информация передаваемого сообщения, определяемая источником дискретного сообщения и не зависящая от свойств канала. Остальные три энтропии в общем случае зависят как от источника, так и от канала. Отсюда следует, что такой параметр, как скорость передачи не может характеризовать канал как средство передачи.

Представим, что на вход канала можно подавать сообщения от разных источников, характеризуемых разными распределениями вероятностей p(X). Для каждого такого источника количество информации, передаваемое в канал, будет разным.

Максимальное количество информации, передаваемое в единицу времени, взятое по всем возможным источникам, называется пропускной способностью канала

бит/с. (2.19)

В качестве примера определим пропускную способность дискретного симметричного канала без памяти, через который в единицу времени передаются  символов из алфавита с объемом m.

Можно записать с учетом (2.18) и (2.19)

. (2.20)

Величина H(Y/X) в данном случае легко находится, поскольку условная вероятность p(y_j/x_i) принимает только два значения

, (2.21)

где p - вероятность того, что при передаче символа x_i будет принят любой другой символ, кроме y_j, т.е. вероятность ошибки. Первое из этих значений возникает с вероятностью p, а второе - 1-p возникает с вероятностью 1-p. К тому же, поскольку рассматривается канал без памяти, результаты приема отдельных символов независимы. Поэтому в соответствии с полученной ранее формулой (2.8) и с учетом (2.21) можно записать .

Следовательно, при этих условиях H(Y/X) не зависит от распределения вероятностей в ансамбле X, а определяется только переходными вероятностями канала.

Таким образом, поскольку в выражении (2.20) только член H(Y) зависит от распределения вероятностей p(X), то максимизировать необходимо именно его.

Максимальное значение H(Y) реализуется тогда, когда все выходные символы y_j равновероятны и независимы, а это условие, в свою очередь, выполняется, когда равновероятны и независимы входные символы x_i. При этом в соответствии с (2.4) . Отсюда пропускная способность канала в расчете на единицу времени

.

Для двоичного (m=2) симметричного канала пропускная способность бит/с.

При p=0,5 пропускная способность двоичного канала C=0, поскольку при такой вероятности ошибки последовательность выходных двоичных символов можно получить, совсем не передавая сигналы по каналу (канал не нужен), а просто выбирая их наудачу (например, бросая монету), т.е. при p=0,5 последовательности символов на входе и на выходе канала независимы. То, что пропускная способность при p=0 (канал без шумов) равна пропускной способности при p=1, объясняется тем, что p=1 означает, что все входные символы при прохождении через канал обязательно преобразуются под воздействием помех в противоположные. Следовательно, чтобы правильно восстановить на выходе входное сообщение, достаточно инвертировать все выходные символы.

Пусть, например, по каналу передается сообщение, формируемое из 8 символов x_i с вероятностями их появления p_i.

xi	x1	x2	x3	x4	x5	x6	x7	x8
pi	0,20	0,15	0,20	0,15	0,10	0,10	0,05	0,05

Канал имеет полосу пропускания, позволяющую передавать элементы сообщения со средней длительностью _и = 0,5 мс. Шум в канале отсутствует.

Тогда, поскольку шум отсутствует, энтропия шума H(Y/X) из формулы (2.18) равна нулю. Тогда из этой же формулы . В соответствии с (2.4) , т.е. . Канал способен пропускать в единицу времени символов. Следовательно С = 3*2000 = 6000 бит/с. Скорость передачи определяется по формуле (2.18) . Величина H(Y) находится по определению энтропии (2.3)

=0,464+0,411+0,464+0,411+0,332+0,332+

+0,216+0,216=2,846 бит/символ.

Тогда скорость передачи = 2000*2,846 = 5692 бит/с.

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

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

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

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

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

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

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

В общем случае в канале имеются помехи, сигнал Y принимается с ошибками, так что скорость передачи информации по каналу меньше производительности кодера . Отсюда с учетом подчеркнутого выше (2.22) утверждения следует, что . (2.23)

Это значит, что производительность кодера, на выходе которого формируется сигнал Y, должна быть выше производительности источника, на выходе которого формируется сообщение X. Следовательно, Y содержит кроме информации об X дополнительную собственную информацию. Часть информации о сигнале Y в канале теряется. Вопрос сводится к следующему: можно ли осуществить кодирование так, чтобы терялась только дополнительная, избыточная часть собственной информации Y, а информация об X сохранялась? Теорема Шеннона дает на этот вопрос почти положительный ответ, с той лишь поправкой, что скорость потери информации не равна в точности нулю, но может быть сделана сколь угодно малой. Соответственно, сколь угодно малой может быть сделана вероятность ошибочного декодирования. При этом, чем меньше допустимая вероятность ошибочного декодирования, тем сложнее должен быть код.

Верхняя граница средней вероятности ошибочного декодирования по всем возможным кодам определяется выражением

, (2.24)

где Т - длительность последовательности кодируемых сообщений или длительность последовательности сигналов, соответствующей последовательности сообщений.

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

Подчеркнем, что чем больше запас пропускной способности, тем легче реализуется система передачи, но одновременно падает ее эффективность.

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