Тема 3. Кодирование источника (Материалы лекций)

достаточным оказывается рассматри-вать данный раздел именно как развитие некоторого ма- тематического аппарата, доказывающего свойства этих специфических функций вероятност- ных распределений. 1 1 — 1оК „— Н(А) п Р(а'"') (6.40) где 8(А) — энтропия данного источника. Эскиз доказательства для стационарных источников без памяти имеет следующий вид. Согласно закону больших чисел при достаточно большом и частота п,/и события, состоящего в появлении символа а, в последовательности длины и, стремится к вероятности Р(а;), т.е.

П(п -+ Р(а,). (б.41) С другой стороны, если некоторая последовательность а1в~ содержит п, символов а„п, символов а, и т.д. п,, символов а... то вероятность ее появления Р(аИ) Р"а( ).Рч(, )..Р"к-а(а ) ' Тогда 1 1 и, 1 и, 1 п , 1 10К ы1 = 1ОК + 10К +...+ 10К п Р(аы') и Р(а,) п Р(а ) п Р(ак 1) (б.42) 235 6.2.3. ТЕОРЕМЫ КОДИРОВАНИЯ ШЕННОНА ДЛЯ ДИСКРЕТНОГО КАНАЛА СВЯЗИ Рассмотрим сначала теорему кодирования в канале без помех, который, очевидно, является частным случаем канала с помехами. Наилучшее кодирование состоит в том, что при заданном канале связи, который определяется объемом алфавита т и скоростью передачи канальных символов тк, а также при заданном источнике информации, определяемом вероятностным распределением р(а) последовательностей, составленных из символов, принадлежащих алфавиту источника А, обеспечить наибольшую возможную скорость передачи символов источника ти.

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

кодирование при неограниченных последовательностях символов источника и канала связи, сопоставляемых друг с другом. Для этого нам понадобится одна теорема, которая по существу является некоторой версией закона больших чисел, известного в теории вероятностей. Теорема о свойстве асимптотической равповероятпости (САР). Для любых заданных сколь угодно малых положительных чисел в и Б можно найти такое число и (зависящее от в, б и свойств источника), что с вероятностью большей, чем 1 — б, источник сообщений выдает последовательность а1л1 длины и, которая имеет вероятность Р(а'"'), удовлетворяющую неравенству 1 1 Подставляя (6.41) в (6.42), получаем, что величина — 1оя,,„,, будет стреи Р(а~"1) 1 1 и Р х'"'~у'"'') — 1оя -Н(Х~Ъ (6.44) 1 1 — 1оа ~,, ) — Н(Ъ~Х) (6.45) где е — сколь угодно малая величина.

Теперь мы подготовлены к формулировке и доказательству теорем кодирования. ТЕОРЕМА 1. О кодировании источника. Существует способ кодирования, при котором средняя длина последовательности канальных символов й, приходящаяся на один символ источника сообщений, ъ'„Н(А) и= — "= — +е, с>0. (6.46) ч„1одт Н(А) Не существует способа кодирования, при котором и меньше, чем 1оят Доказательство данной теоремы для источнИка без памяти будет дано в следующей главе. Прикладной смысл этой теоремы состоит в том, что при наилучшем кодировании в канале без помех мы можем передавать сообшения источника сообщений со скоростью ч„, сколь угодно близкой к величине 236 миться по вероятности к К 1 — ~ Р(а,) 1оя Р (а ) = Н(А) . ~ о (Аналогично, хотя и более громоздко, доказывается данная теорема и для стационарных источников с памятью). По существу теорема САР означает, что при достаточно большой величине и все последовательности, выдаваемые источником разбиваются на две группы, называемые соответственно типичными и нетипичными.

Первые последовательности примерно равновероятны, и количество их приблизительно (6.43) Р(а'"~) Что же касается нетипичных последовательностей, то они могут иметь разные вероятности, но вероятность появления хотя бы одной из них стремится к нулю при п-+се. Заметим, что число типичных последовательностей определенной длины оказывается значительно меньше общего возможного числа последовательностей такой же длины. Например, обшее число последовательностей букв русского языка длины и = 1О равно 32Ю ч 10'5, в то время как число типичных последовательностей такой же длины, если положить энтропию русского языка равной 1,5 бит/символ, оказывается всего лишь 2ю15 =33000, что примерно соответствует объему типичного словаря.

Теорема САР оказывается справедливой и для пар последовательностей х1т, у1П1, относительно которых утверждается, что при достаточно больших и с вероятностью 1-5 источник выдает пару последовательностей, для которых их условные вероятности будут удовлетворять неравенствам 1оят 6,47 ' н(А) ( ) и невозможно передавать сообщения со скоростью ря большей, чем (6.47). Видно, что скорость передачи оказывается тем большей, чем меньше энтропия источника или чем больше его избьггочность, что очевидно соответствует наей интуиции, подсказывающей возможность более быстрой передачи сообщений за счет устранения содержащейся в них избыточности.

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

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

ТЕОРЕМА 2. О кодировании в канале беэ помех. Существует способ кодирования и декодирования в канале без помех, при котором для длины и последовательности канальных символов, приходящихся на один символ источника, будет выполняться соотношение (6.46), причем вероятность ошибки не превосходит любой сколь угодно малой величины б > О. Заметим, что здесь под вероятностью ошибки понимается вероятность того, что последовательность символов, выданная получателю, будет отличаться от соответствующей ей последовательности символов, переданной источником сообщений. Несмотря на то, что мы имеем здесь дело с каналом без помех, ошибки в принятом сообщении появляются вследствие специального способа кодирования.

Доказательство. Как следует из (6.43), число типичных последовательностей источника длиной л„будет асимптотически (при больших аа) равно 2""~("). Условимся кодировать ка- нальными символами только эти типичные последовательности, а любую нетипичную после- довательность передавать при помощи одной и той же последовательности, что, очевидно, при декодировании на приеме и будет приводить к ошибкам. Однако поскольку при а„-+ с вероятность появления нетипичной последовательности будет стремиться к нулю, то это и означает, что вероятность ошибки может быть сделана сколь угодно малой величиной. Все типичные последовательности длины л„будем кодировать последовательностями длины л„, составленными из канальных символов, Для обеспечения однозначности декодиро- вания (отсутствия ошибок в этом случае) необходимо выполнение условия 2"""(Ы = т"" -1, откуда при больших значениях а„и п„получаем п„н(А) й= — "м —, и„)ояз т что и завершает доказательство теоремы.

Интерпретация этой теоремы для заданных скоростей источника и канала приводит так- же к соотношению (б.47). Разница состоит лишь в том, что возможна ошибка с некоторой малой вероятностью Ь, но зато кодирование оказывается равномерным, что не приводит к переполнению буферной памяти кодера. 237 ГЛАВА 7.

КОДИРОВАНИЕ ИСТОЧНИКОВ И КАНАЛОВ СВЯЗИ В предыдущей главе были установлены потенциальные возможности кодирования источников и каналов, которые определялись теоремами кодирования Шеннона. Однако ни формулировки, ни доказательства этих теорем не указывали прямо на способы кодирования и декодирования, которые обеспечивают эти потенциальные возможности. (Исключением было лишь кодирование в непрерывном канале с неограниченной полосой частот, когда постоянная скорость передачи при сколь угодно малой вероятности ошибок могла быть обеспечена при выборе ортогональных сигналов).

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