Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
7.2. ОТСУТСТВИЕ ОГРАНИЧЕНИЙ НА ВХОДЕКак было 1 оказано, если ограничиться конечным множеством букв на входе и произвести разбиения на выходе, то общий дискретный по времени капал без памяти можно использовать как дискретный капал без памяти. Таким образом, любая вероятность ошибки, которая могут быть достш пугз с помощью кодирования в любом таком дискретном канале без памяти, может быть достигнута и в общем канале при использовании его как соответствующего дискретного канала. Для заданного дискретного по времени канала без памяти пусть
Определим фикцию
Согласно теореме (5.6.2) существует блоковый код длины
Верхняя грань берется по всем конечным выборам входных букв, всем распределениям вероятностей входных букв, всем разбиениям выходного пространства и всем
где верхняя грань определяется как и выше. Теорема 7.2.1. (Теорема кодирования.) Пусть для дискретного по времени канала без памяти
Здесь
- средняя вероятность ошибки;
(Замечания. Неравенство (7.2.5) утверждает, что для заданных Доказательство. Для заданных
Это всегда возможно, так как
Так как эта вероятность ошибки также
Из теоремы 5.6.4 следует, что показатель экспоненты случайного кодирования для канала, соответствующего Использование положительного значения. Наконец, с помощью разбиения выходного пространства на множества, сопоставления одного множества разбиения каждому Теорема 7.2.2. (Обращение теоремы кодирования.) Пусть дискретный стационарный источник с алфавитом объема
Рис. 7.2.1. Канал со стиранием и с бесконечным алфавитом. Тогда в пределе при
Доказательство. Формулировка этой теоремы совпадает с формулировкой теоремы 4.3.4. Однако она применима к .более широкому классу каналов. В доказательстве теоремы 4.3.4 канал рассматривается лишь при установлении следующих двух соотношений:
Таким образом, здесь достаточно установить справедливость этих двух соотношений для дискретного по времени канала без памяти. Доказательство соотношения (7.2.11). Для любого заданного значения
Далее, по определению (2.5.1),
где верхняя грань берется по всем разбиениям Доказательство соотношения (7.2.12). Выражение
Повторно применяя соотношение (2.2.29) к правой части (7.2.15) и замечая, что все члены конечны, получаем
Используя (2.5.4) и (2.5.5), имеем
Согласно теореме 2.3.3 последнее слагаемое в (7.2.18) равно нулю; сопоставляя эти соотношения, получаем
Так как Устанавливая справедливость теоремы кодирования и ее обращения при большой степени общности, представленные выше результаты дают слабое указание на то, как вычислять По неравенству Мипковского (см. задачу 4.15.3) для
Суммируя обе части (7.2.20) по
С физической точки зрения этот результат не удивителен. При более тонком разбиении выхода канала декодер имеет большую информацию о принятой последовательности и вероятность ошибочного декодирования будет меньше. Если выходное пространство канала — действительная прямая и канал описывается плотностью вероятности
То что правая часть (7.2.22) действительно является верхней гранью
Суммируя обе части по Это сводит проблему нахождения
где
В приведенных выше выражениях Теперь можно применить эти результаты к произвольному дискретному по времени каналу без памяти с ограничением на входе Как в § 7.2, пусть
Определим для рассматриваемого канала показатель экспоненты случайного кодирования и показатель экспоненты для процедуры с выбрасыванием равенствами
Верхняя грань в обоих приведенных выше равенствах берется по всем конечным наборам входных букв; всем вероятностям, удовлетворяющим ограничению; всем разбиениям на выходе; всем Теорема 7.3.2. (Теорема кодирования.) Для произвольного дискретного по времени канала без памяти с ограничением на входе пусть
и для каждого из которых удовлетворяется неравенство
из разумных интерпретаций этого ограничения состоит в том, что каждое кодовое слово удовлетворяет этому ограничению, т. е. для каждого кодового слова
Другая разумная интерпретация состоит в задании вероятностной меры на сообщениях
Заметим, что класс кодов, для которого каждое кодовое слово удовлетворяет ограничению, содержится в классе кодов, для которых удовлетворяется ограничение при усреднении по кодовым словам. Таким образом, любая вероятность ошибочного декодирования, которая может быть достигнута на некотором коде первого класса, может быть также достигнута на коде (в частности, на том же коде) последнего класса. Обратно, любая нижняя граница вероятности ошибки последнего класса также будет нижней границей первого класса. Поэтому теорема кодирования будет доказываться при ограничении на каждое кодовое слово, а ее обращение — когда удовлетворяется ограничение только при усреднении по множеству кодовых слов. Таким образом, каждая теорема будет применима к обоим случаям, и будет показано, что нет существенной разницы в том, какой из двух случаев рассматривается. Начнем с изучения обращения теоремы кодирования, так как она почти не отличается от соответствующей теоремы для случая без ограничений. Используя обозначения последнего параграфа, пропускную способность дискретного по времени канала без памяти с ограничением на входе
где верхняя грань берется по всем разбиениям выходного пространства, всем дискретным множествам входов
Заметим, что при этом определении функция Теорема 7.3.1. (Обращение теоремы кодирования.) Пусть дискретный стационарный источник с алфавитом объема которому передается последовательность N символов
Тогда, в пределе при
(Замечания. Заметим, что условие (7.3.3) означает, что ограничение удовлетворяется при усреднении по кодовым словам. Допускается нарушение ограничения для отдельных кодовых слов, а также для отдельных букв в последовательности N посылок по каналу. Другими словами, при ограничении на энергию допускается распределение энергии, приходящейся на блок, любым желаемым образом между N посылками по каналу.) Доказательство. Доказательство теоремы 7.2.2 применимо здесь в той части, где оно касается установления справедливости неравенств
В конце доказательства теоремы 7.2.2 было показано, что
Пусть
Введем вероятности
Подставляя (7.3.7) в (7.3.6), получаем
Пусть
В теореме 4.4.2 было показано, что средняя взаимная информация в канале с дискретным входом является выпуклой функцией входных вероятностей. Из (4.4.5) (если положить
Сочетая (7.3 9) и (7.3.10), получаем (7.3 5), что и доказывает теорему.
где Построим теперь ансамбль кодов, в котором каждое кодовое слово удовлетворяет (7.3.11). Пусть
Пусть
где
Можно заметить, что Рассмотрим ансамбль кодов с
Неравенство (7.3.16) не очень удобно по форме, так как при больших N трудно иметь дело с входящими в него суммами. Если оценить сверху
Неравенство (7.3.17), очевидно, справедливо, когда
Мажорируя
где
Приведенная выше граница записана с помощью некоторых произвольных параметров, а именно
где Так как теперь
то из центральной предельной теоремы следует, что Пропускная способность этого канала в натах задается как частный случай формулы (7.3.1):
где максимум берется по всем заданиям вероятностей
положительно при Как побочный результат приведенного выше рассмотрения находим, что если максимум Обратимся теперь к более интересной ситуации, в которой при заданном вероятностью ошибки. Вероятность ошибки, обусловленная этими немногими словами, определяет границу вероятности ошибки при Простейшим способом максимизации
Используя "К и у как множители Лагранжа, находим стационарную точку функции
Взяв частные производные по всем
с равенством при
Неравенство в (7.3.25) соответствует тому, что максимум
Умножая (7.3.25) на
Аналогично, умножив (7.3.25) на
для всех надежности канала с ограничением при скоростях, лежащих между Для величины
как сумму независимых случайных величин, выбранных в соответствии с вероятностной мерой
Из (7.3.26) можно увидеть, что для фиксированных Граница вероятности ошибки для процедуры с выбрасыванием § 5.7 может быть распространена на случай, когда имеются ограничения на входе, точно так же как и граница случайного кодирования. Рассмотрим (5.7.7), которое справедливо для любого ансамбля кодов, и верхние границы (7.3.18) для
а также удовлетворяет границе
где
В приведенных выше выражениях Теперь можно применить эти результаты к произвольному дискретному по времени каналу без памяти с ограничением на входе
Определим для рассматриваемого канала показатель экспоненты случайного кодирования и показатель экспоненты для процедуры с выбрасыванием равенствами
Верхняя грань в обоих приведенных выше равенствах берется по всем конечным наборам входных букв; всем вероятностям, удовлетворяющим ограничению; всем разбиениям на выходе; всем Теорема 7.3.2. (Теорема кодирования.) Для произвольного дискретного по времени канала без памяти с ограничением на входе пусть
и для каждого из которых удовлетворяется неравенство
Кроме того, Доказательство. Выберем
Из (7.3.21) следует, что для любого
Так как для достаточно больших
Эти же рассуждения применимы и в случае, когда
и, следовательно, Теорема 7.3.2 обладает большой общностью, однако часто ее трудно применить ввиду трудности вычисления верхних граней, введенных при определении
Если верхняя грань положить по определению
Показатели экспонент
где R определено в (7.3.33),
|
1 |
Оглавление
|