7.2. ОТСУТСТВИЕ ОГРАНИЧЕНИЙ НА ВХОДЕ

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

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

Определим фикцию с помощью равенства

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

Верхняя грань берется по всем конечным выборам входных букв, всем распределениям вероятностей входных букв, всем разбиениям выходного пространства и всем Аналогично определяется пропускная способность канала (в натуральных единицах):

где верхняя грань определяется как и выше.

Теорема 7.2.1. (Теорема кодирования.) Пусть для дискретного по времени канала без памяти и С определены равенствами (7.2.3) и (7.2.4). Для любых существует блоковый код длины кодовыми словами, для которого

Здесь

- средняя вероятность ошибки; вероятность передачи шло кодового слова; вероятность ошибки для кодового слова. Кроме того,

(Замечания. Неравенство (7.2.5) утверждает, что для заданных можно либо найти коды, для которых либо, по крайней мере, найти коды, для которых сколь угодно близко к Альтернативное утверждение состоит в том, что для заданных имеем где нижняя грань берется по всем кодам с заданными

Доказательство. Для заданных выберем так, что

Это всегда возможно, так как строго меньше, чем верхняя грань левой части (7.2.7) по Из теоремы 5.6.2 следует, что для дискретного канала, соответствующего существует код с заданными для которого

Так как эта вероятность ошибки также быть достигнута для общего дискретного по времени канала, то из (7.2.7) и (7.2.8) получаем (7.2.5). Для того чтобы установить справедливость (7.2.6), примем выберем число и выберем удовлетворяющие неравенству

Из теоремы 5.6.4 следует, что показатель экспоненты случайного кодирования для канала, соответствующего положителен при следовательно, также положительно для данного

Использование в (7.2.5) вместо вызывает некоторое раздражение, однако следующий пример (рис. 7.2.1) показывает, что этого нельзя избежать. Легко видеть, что при использовании такого канала любой код будет иметь ненулевую вероятность ошибочного декодирования. Вместе с тем при любых если использовать только входы то при достаточно больших вероятность ошибки можно уменьшить до сколь угодно малого

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

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

Рис. 7.2.1. Канал со стиранием и с бесконечным алфавитом.

Тогда в пределе при вероятность ошибки на букву источника удовлетворяет соотношению

Доказательство. Формулировка этой теоремы совпадает с формулировкой теоремы 4.3.4. Однако она применима к .более широкому классу каналов. В доказательстве теоремы 4.3.4 канал рассматривается лишь при установлении следующих двух соотношений:

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

Доказательство соотношения (7.2.11). Для любого заданного значения и для любых заданных источника и кодера число кодовых слов конечно. Следовательно, только конечное множество входных букв канала может быть использовано в соответствующем ансамбле

таким образом, дискретный ансамбль. Аналогично, любой заданный декодер разбивает пространство не более чем на областей декодирования, соответствующих элементам пространства Обозначим разбиение выходного пространства через Теорема 4.3.3 устанавливает, что

Далее, по определению (2.5.1),

где верхняя грань берется по всем разбиениям Сравнивая (7.2.13) и (7.2.14), получаем (7.2.11).

Доказательство соотношения (7.2.12). Выражение может быть переписано следующим образом:

Повторно применяя соотношение (2.2.29) к правой части (7.2.15) и замечая, что все члены конечны, получаем

Используя (2.5.4) и (2.5.5), имеем

Согласно теореме 2.3.3 последнее слагаемое в (7.2.18) равно нулю; сопоставляя эти соотношения, получаем

Так как дискретно, то определяется как верхняя грань по всем разбиениям соответствии с определением С в (7.2.4) имеем а отсюда непосредственно следует (7.2.12).

Устанавливая справедливость теоремы кодирования и ее обращения при большой степени общности, представленные выше результаты дают слабое указание на то, как вычислять или С. В § 2.5 было показано, что не убывает при измельчании разбиения пространства Теперь установим тот же самый результат для Пусть разбиение с событиями и пусть подразбиение с событиями где

По неравенству Мипковского (см. задачу 4.15.3) для имеем

Суммируя обе части (7.2.20) по и беря минус логарифм от результата, получаем

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

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

То что правая часть (7.2.22) действительно является верхней гранью по всем разбиениям следует из тех же соображений, которые были использованы при рассмотрении (7.2.20); при этом применяется интегральная форма неравенства Минковского

Суммируя обе части по получаем желаемый результат.

Это сводит проблему нахождения для канала с переходной плотностью вероятности к проблеме вычисления выражения

где определено (7.2.22). Очень мало можно сказать в общем случае о нахождении верхней грани по всем дискретным входам. В некоторых случаях (см. задачу 7.5) достигает максимума на дискретных входах и в этом случае условия

В приведенных выше выражениях произвольны, а определено в (7.3.15) и оценено в (7.3.29).

Теперь можно применить эти результаты к произвольному дискретному по времени каналу без памяти с ограничением на входе Как в § 7.2, пусть конечное множество входных букв канала с заданными вероятностями удовлетворяющими ограничению Пусть разбиение выходного пространства на события Пусть задаются соотношениями

Определим для рассматриваемого канала показатель экспоненты случайного кодирования и показатель экспоненты для процедуры с выбрасыванием равенствами

Верхняя грань в обоих приведенных выше равенствах берется по всем конечным наборам входных букв; всем вероятностям, удовлетворяющим ограничению; всем разбиениям на выходе; всем и всем удовлетворяющим для (7.3.36) и для (7.3.37).

Теорема 7.3.2. (Теорема кодирования.) Для произвольного дискретного по времени канала без памяти с ограничением на входе пусть и С определеныв (7.3.36), (7.3.37) и (7.3.1). Пусть и произвольны. Тогда для всех достаточно больших N существует блоковый код длины кодовыми словами каждое из которых удовлетворяет ограничению

и для каждого из которых удовлетворяется неравенство

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

Другая разумная интерпретация состоит в задании вероятностной меры на сообщениях и требовании, чтобы

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

Используя обозначения последнего параграфа, пропускную способность дискретного по времени канала без памяти с ограничением на входе определим следующим образом:

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

Заметим, что при этом определении функция и присутствующее! в ограничении значение рассматриваются как неотъемлемые части описания канала.

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

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

Тогда, в пределе при вероятность ошибки на букву источника удовлетворяет соотношению

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

Доказательство. Доказательство теоремы 7.2.2 применимо здесь в той части, где оно касается установления справедливости неравенств

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

Пусть множество входных букв канала, используемых для какого-либо кода, вероятность появления входной буквы при использовании канала. Согласно (7.3.3) имеем

Введем вероятности

Подставляя (7.3.7) в (7.3.6), получаем

Пусть средняя взаимная информация между входом и выходом канала при использовании букв а с вероятностями Так как (7.3.8) эквивалентно (7.3.2), то

В теореме 4.4.2 было показано, что средняя взаимная информация в канале с дискретным входом является выпуклой функцией входных вероятностей. Из (4.4.5) (если положить равным следует

Сочетая (7.3 9) и (7.3.10), получаем (7.3 5), что и доказывает теорему. Передаем как приступить к формулировке и доказательству теоремы кодирования для дискретного по времени канала без памяти с ограничением на входе, следует рассмотреть влияние ограничения на входе на дискретный канал без памяти. Так же как и в гл. 5, обозначим через переходные вероятности для дискретного канала без памяти с входным алфавитом и выходным алфавитом Пусть функция, определенная на входных буквах; рассмотрим класс кодов, для которых каждое кодовое слово удовлетворяет ограничению

где заданная постоянная.

Построим теперь ансамбль кодов, в котором каждое кодовое слово удовлетворяет (7.3.11). Пусть вероятности входных букв, удовлетворяющие неравенству

Пусть распределение вероятностей на последовательностях N входов канала, задаваемое соотношением

где

произвольное положительное число, определенное ниже.

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

Рассмотрим ансамбль кодов с кодовыми словами блоковой длины в котором кодовые слова выбраны независимо с вероятностями Из теоремы 5.6.1 следует, что для каждого сообщения, вероятность ошибки, усредненная по ансамблю кодов, ограничена сверху при всех выражением

Неравенство (7.3.16) не очень удобно по форме, так как при больших N трудно иметь дело с входящими в него суммами. Если оценить сверху и упростить получившееся выражение, то можно получить более удобный результат. Для любого 0 можно построить верхнюю границу для [см. (7.3.14)]:

Неравенство (7.3.17), очевидно, справедливо, когда Когда выражение, стоящее в скобках в (7.3.17), неотрицательно и правая часть (7.3.17) больше или равна 1. Сочетая (7.3.13) и (7.3.17), имеем для любого

Мажорируя в (7.3.16) выражением (7.3.18) и повторяя выкладки, проведенные при переходе от (5.6.11) к (5.6.13), получаем

где связаны равенством Используя соображения следствия 2 теоремы 5.6.2, можно заметить, что существует также код, для которого при любом и любом

Приведенная выше граница записана с помощью некоторых произвольных параметров, а именно и 60. Прежде чем попытаться оптимизировать выражение по этим параметрам, полезно исследовать поведение границы при и сколь угодно большом В этом случае (7.3.19) упрощается следующим образом:

где показатель экспоненты, знакомый по теореме 5.6.2, за исключением множителя эквивалентно теореме 5.6.2.

Так как теперь вероятность того, что при независимом выборе букв с распределением последовательность х удовлетворяет неравенству

то из центральной предельной теоремы следует, что стремится к 1/2 при возрастании если стремится к 1, если Таким образом, множитель не отражается на экспоненциальной зависимости границы от

Пропускная способность этого канала в натах задается как частный случай формулы (7.3.1):

где максимум берется по всем заданиям вероятностей удовлетворяющих (7.3.12). Используя рассуждения теоремы 5.6.4, можно показать, что для максимизирующем (7.3.23) при условии (7.3.12), выражение

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

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

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

вероятностью ошибки. Вероятность ошибки, обусловленная этими немногими словами, определяет границу вероятности ошибки при действительности эти слова не принадлежат ансамблю, однако они появляются в границе, поскольку граница для имеет вид (7.3.18)]. Смысл выбора состоит в том, чтобы уменьшить влияние этих немногих плохих слов на границу.

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

Используя "К и у как множители Лагранжа, находим стационарную точку функции

Взяв частные производные по всем получаем условия

с равенством при где определяется формулой

Неравенство в (7.3.25) соответствует тому, что максимум может достигаться на границе, когда некоторые точно так же как и в теореме 4.4.1. Взяв частные производные функции (7.3.24) по получаем условие

Умножая (7.3.25) на и суммируя по находим, что

Аналогично, умножив (7.3.25) на просуммировав по и сравнив с (7.3.27), находим, что Таким образом, (7.3.25) преобразуется в

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

надежности канала с ограничением при скоростях, лежащих между где определена в § 5.8.

Для величины из (7.3.19) трудно найти хорошую границу, однако она может быть точно оценена для больших Предположим, что удовлетворяет соотношению рассмотрим

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

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

Граница вероятности ошибки для процедуры с выбрасыванием § 5.7 может быть распространена на случай, когда имеются ограничения на входе, точно так же как и граница случайного кодирования. Рассмотрим (5.7.7), которое справедливо для любого ансамбля кодов, и верхние границы (7.3.18) для Раскрывая произведения, находим, что для всех существует блоковый код длины кодовыми словами, каждое кодовое слово которого удовлетворяет ограничению

а также удовлетворяет границе

где

В приведенных выше выражениях произвольны, а определено в (7.3.15) и оценено в (7.3.29).

Теперь можно применить эти результаты к произвольному дискретному по времени каналу без памяти с ограничением на входе в § 7.2, пусть конечное множество входных букв канала с заданными вероятностями удовлетворяющими ограничению Пусть разбиение выходного пространства на события Пусть задаются соотношениями

Определим для рассматриваемого канала показатель экспоненты случайного кодирования и показатель экспоненты для процедуры с выбрасыванием равенствами

Верхняя грань в обоих приведенных выше равенствах берется по всем конечным наборам входных букв; всем вероятностям, удовлетворяющим ограничению; всем разбиениям на выходе; всем и всем удовлетворяющим для (7.3.36) и для (7.3.37).

Теорема 7.3.2. (Теорема кодирования.) Для произвольного дискретного по времени канала без памяти с ограничением на входе пусть и С определены в (7.3.36), (7.3.37) и (7.3.1). Пусть и произвольны. Тогда для всех достаточно больших N существует блоковый код длины кодовыми словами каждое из которых удовлетворяет ограничению

и для каждого из которых удовлетворяется неравенство

Кроме того, для всех

Доказательство. Выберем удовлетворяющее условию Если выберем так, что

Из (7.3.21) следует, что для любого и каждого существует код для этих кодовыми словами, каждое из которых удовлетворяет ограничению и удовлетворяет неравенству

Так как для достаточно больших выражение возрастает как и так как для достаточно больших N имеем

Эти же рассуждения применимы и в случае, когда за исключением того, что должно стоять вместо Далее примем, что и выберем так, чтобы Из соображений, следующих за (7.3.23), видно, что для

и, следовательно,

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

Если верхняя грань достигается в пределе на распределениях, сходящихся к плотности вероятности то можно

положить по определению

Показатели экспонент могут теперь быть найдены прямо из (7.3.43) и (7.3.44) после максимизации лишь по . В этом случае можно получить в некотором смысле более точные результаты, повторяя выводы теорем 5.6.1 и 5.7.1 и используя при этом плотности вместо вероятностей и интегралы вместо сумм. Упрощая результаты, так же как при переходе от (7.3.16) к (7.3.2), находим, что существует код, для которого каждое кодовое слово удовлетворяет как ограничению, так и следующим границам вероятности ошибки:

где R определено в (7.3.33), произвольно и задается приближенно равенством (7.3.29), в котором Ограничения при выводе этих соотношений состоят в том, что плотности и интегралы существуют; конечен. Ясно, что (7.3.45) и (7.3.46) справедливы, независимо от того, максимизирует ли входная плотность величины или нет.