Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 59
Текст из файла (страница 59)
По существу теорема САР означает, что при достаточно большой величине и все последовательности, выдаваемые источником разбиваются на две группы, называемые соответственно типичными и нетипичными. Первые последовательности примерно равновероятны, и количество их приблизительно тип РР( ~л) 1 (6.43) Что же касается нетипичных последовательностей, то они могут иметь разные вероятности, но вероятность появления хотя бы одной из них стремится к нулю при и — ь со. Заметим, что число типичных последовательностей определенной длины оказывается значительно меньше общего возможного числа последовательностей такой же длины. Например, общее число последовательностей букв русского языка длины и = 10 равно 32Ю м 10'5, в то время как число типичных последовательностей такой же длины, если положить энтропию русского языка равной 1,5 бит/символ, оказывается всего лишь 2Ю' 5 м33000, что примерно соответствует объему типичного словаря.
Теорема САР оказывается справедливой и для пар последовательностей х1"1, у1 "1, относительно которых утверждается, что при достаточно больших и с вероятностью 1-5 источник выдает пару последовательностей, для которых их условные вероятности будут удовлетворять неравенствам у =у 1оят " Н(А) (6.47) и невозможно передавать сообщения со скоростью уи большей, чем (6.47). Видно, что скорость передачи оказывается тем большей, чем меньше энтропия источника или чем больше его избыточность, что очевидно соответствует наей интуиции, подсказывающей возможность более быстрой передачи сообщений за счет устранения содержащейся в них избыточности.
Такой метод кодирования называется также кодированием источников сообщений или иногда — статистическим или экономным. кодированием (сжатием) сообщений. Поскольку теорема 1 дает условие лишь для средней длины блока канальных символов, то очевидно, что в отдельные моменты времени эти длины могуг оказаться значительно больше средней длины, а это потребует для источников с фиксированной скоростью использования специального буферного устройства для поглощения задержки поступающих сообщений.
Можно показать, что с вероятностью единица накопитель любой конечной емкости рано или поздно будет переполнен, т.е. произойдет потеря информации. Заметим, что указанное выше кодирование является обычно неравномерным. Поэтому для источников сообщений с фиксированной скоростью имеет смысл следующее видоизменение теоремы 1, в котором используется равномерное кодирование. ТЕОРЕМА 2.
О кодировании в канале без помех. Существует способ кодирования и декодирования в канале без помех, при котором для длины и последовательности канальных символов, приходящихся на один символ источника, будет выполняться соотношение (6.46), причем вероятность ошибки не превосходит любой сколь угодно малой величины б > О. Заметим, что здесь под вероятностью ошибки понимается вероятность того, что последовательность символов, выданная получателю, будет отличаться от соответствующей ей последовательности символов, переданной источником сообщений.
Несмотря на то, что мы имеем здесь дело с каналом без помех, ошибки в принятом сообщении появляются вследствие специального способа кодирования. Доказательство. Как следует из (6.43), число типичных последовательностей источника длиной «„ будет асимптотически (при больших «„) равно 2"" 1"). Условимся кодировать канальными символами только эти типичные последовательности, а любую нетипичную последовательность передавать при помоши одной и той же последовательности, что, очевидно, при декодировании на приеме и будет приводить к ошибкам.
Однако поскольку при «„-+о~ вероятность появления нетипичной последовательности будет стремиться к нулю, то это и означает, что вероятность ошибки может быть сделана сколь угодно малой величиной. Все типичные последовательности длины «„ будем кодировать последовательностями длины «„, составленными из канальных символов. Для обеспечения однозначности декодирования (отсутствия ошибок в этом случае) необходимо выполнение условия 2ч «~") = т~ — 1, откуда при больших значениях «„и «к получаем и н(А) «„)ек е что и завершает доказательство теоремы. Интерпретация этой теоремы для заданных скоростей источника и канала приводит также к соотношению (б.47).
Разница состоит лишь в том, что возможна ошибка с некоторой малой вероятностью Ь, но зато кодирование оказывается равномерным, что не приводит к переполнению буферной памяти кодера. 237 Перейдем к рассмотрению теорем кодирования Шеннона в канале с помехами. Пусть сообщения некоторого источника информации передаются по каналу с помехами, заданному входным Х и выходным х" алфавитами, условным распределением Р(у[х) и скоростью передачи тю Будем осуществлять кодирование, сопоставляя с различными последовательностями символов источника различные последовательности (комбинации) символов канала длины п.
Назовем последние разрешенными кодовыми комбинациями блочного кода, обозначив их через х["', [= 1,2, ..., М, где М вЂ” полное число таких комбинаций. Если бы в канале не было помех, то принятые комбинации совпадали бы в точности с разрешенными кодовыми комбинациями. В канале же с помехами принятая комбинация может стать с некоторой вероятностью любой из п[л последовательностей длины п, составленных из выходных канальных символов.
Разобьем все множество таких последовательностей Ъ'" на М непересекаюшихся подмножеств У,", У,", „., У„", и установим следуюШее правило декодирования. Если принятая последовательность у'"' аУ,", то принимается решение о том, что передавалась кодовая комбинация х["'. Такое разбиение будем называть также (см. гл. 5) решаюшей схемой. В этом случае можно определить вероятность правильного приема (или правильного декодирования) как вероятность Р)у[ "[ еУ,"~х["[) того, что при передаче комбинации х["' принятая комбинация уья попадает в соответствующее подмножество У,". Кратко будем записывать эту вероятность как Р[У,"~х["[).
Теперь мы в состоянии сформулировать теорему кодирования для канала с помехами. Теорема кодирования в дискретном канале с помехами. Если канал имеет пропускную способность С бит/симв. и заданы любые числа Ю > О, Н < С, то всегда найдется такое целое число по, что при всяком п > по существует блочный код х,'"',х["',...,х'"' длиной п, состоящий из М=2 комбинаций, и решающая схема г',", у,", ..., У„"„которые обеспечивают выполнение неравенств Р(У" ~х[")) > 1 — 8, 1 = 1, 2, ..., М . (6.48) Если Н > С, то неравенство (6.48) при произвольном б не выполняется, как бы ни было велико по Данная теорема, вообше говоря, справедлива для достаточно широкого класса (хотя и не для всех) каналов с памятью, но мы ее докажем лишь для канала без памяти и для совпадающих входных и выходных алфавитов канала, поскольку в противном случае доказательство заметно усложняется (см., например, 1161).
Доказательство. Докажем сначала прямую часть теоремы, т.е, факт, что (б.48) выполняется при М = 2"", где пН<С. Пусть пропускная способность канала достигается при некотором распределении вероятностей входных символов Р(хь~ = Р,, „,, Р(х,) = Р„,. Будем тогда называть последовательность длиной а, составленную из входных символов канала, а-типичной, если неравенство (б.40) (с очевидной заменой а[ь[ на х["[ и Н(А) на Н(Х)) выполняется для нее при входном распределении Р,,,Р,. Аналогично будем называть последовательность выходных символов а-условной типичной последовательностью для а-типичной входной последовательности, если для нее выполняется неравенство (б.45), в котором входное распределение задается как Р,, ...,Р„„а переходные вероятности определяются каналом связи.
Предпо- 238 ложим, что уже построены блочный код х!"1,х!"1, ..., хф и решающая схема 1;!, у", ..., я, удовлетворяющие следующим условиям: 1. Все комбинации кода являются в-типичными последовательностями. 2. Множества 1;", 1=1,2,..., М содержат все в-условные типичные последовательности для каждого из х!"1, которые не входят в объединение предыдуших множеств, т.е. в у,"ат..оуД.
3. Вероятности правильного декодирования при выборе данного кода и данной решающей схемы ограничены снизу неравенствами Р(К" ~х1"1) а,1 — Ь, ! = 1, 2, ..., М 4. Выбранный код не может быть расширен путем присоединения к нему еще одной комбинации х1Ы1„и множества ум„, для которых выполняется условие 1-3. Покажем, что при достаточно большом и число комбинаций такого кода, удовлетворяющего условиям 1 — 4, оказывается больше, чем 2, где Хг«я< С (см. рис.
6.4). . Заметим. прежде всего, что существует такой код и решающая схема хотя бы для М= 1, Действительно, для этого достаточно выбрать одну в-типичную последовательность х!"! и е-условные типичные в-тнпичные входные х!,"! х«« Р(У,"/хЦ, ~ ~1-б !.
Для любой е-типичной (относительно Р„..., Р,) входной последовательности х'"', Д,дх(.) >. !=! 0УР > аб 3. Р (у — е-условная типичная выходная последовательности)~2 М 4 ОУ« ~об2"( ! !'=! )У« ~ 2«(н(ъ )х)!е) аб2 «(н(у)-н(у!х). ) «(Н(У)-в) 2 (н(ъ'!х) а) Рнс.6,4. Пояснение доказательства теоремы кодирования 239 Р(ут")х( )) = 6=1 род ~=./ (6.49) где р,д вероятность ошибки декодирования блока символов. (Если условие (6.49) не выполняется, то всегда можно изменить решающую схему так, чтобы уменьшить максимальную вероятность ошибки и выполнить это условие для некоторой величины р.,). Теперь код вместе с решающей схемой можно рассматривать как расширенный ИСК с вероятностями переходов (6.49) и обьемами входного и выходного алфавитов равными М.
Тогда количество информации, передаваемой по такому каналу, не может превосходить его пропускной способности, равной )ая м + а )ав а+ р )аа р " . Если это количество информации отнести к одному симвои — ) лу и„то оно, очевидно, не может превзойти пропускной способности С исХодного канала„так 240 такое и, чтобы неравенство (6.48) выполнялось с вероятностью, большей 1 — 5. Пусть х~,"), — любая е-типичная последовательность, не входящая в код, тогда вероятность того, что при передаче х(„",), на выходе появится а-типичная условная последовательность х'("), которая попадает в У1" 0Т"...0У,", будет не меньше 5.
Действительно, если это не так, то х("1, можно присоединить к коду и выбрать У",,, как множество выходных а- условных типичных последовательностей для х'~) „не вошедших в 1;" 0У~"...0У,",. В этом случае Р(у,"~,ф,)>1-5, т.е. расширенный код удовлетворяет условиям 1-3, что противоречит условию 4. Если же передается кодовая комбинация х("), то из условий 1-3 видно, что вероятность появления на выходе а-типичной условной последовательности, попадающей в У1" 0Т". 0У"~, будет не менее чем 1 — 5 и, таким образом, при достаточно больших и (малых 5) также не менее чем 5. Следовательно, какая бы а-типичная последовательность относительного входного распределения Р„...,Р, ни передавалась, вероятность того, что на выходе канала появится последовательность, принадлежащая 1;" 0Ут ...0У,",, будет не менъше 5.
В соответствии с теоремой САР с увеличением длин блоков и вероятность появления атипичной входной последовательности приближается к единице и, таким образом, начиная с некоторого и > ио, становится не меньше постоянной о > О. Поэтому при достаточно больших и безусловная вероятность появления на выходе последовательности, попадающей в 1;" 0Т". 0у,", будет не меньше чем а5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
