Главная > Разное > Принципы цифровой связи и кодирования
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.2. Теорема кодирования для каналов и свойства показателя экспоненты вероятности ошибки в каналах без памяти

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

Лемма 3.2.1. (Галлагер [1965]). Пусть

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

отлична от нуля. Тогда функция обладает свойствами при

причем равенство в каждом случае достигается тогда и только тогда, когда и

причем равенство в (3.2.5а) достигается тогда и только тогда, когда

для всех таких, что

В соотношениях (3.2.2) и (3.2.56) фигурирует функция называемая средней взаимной информацией канала и введенная впервые в § 1.22, где было показано, что она неотрицательна. Непосредственная подстановка значения в (3.2.1) дает а следовательно, неравенства (3.2.3) суть следствия неравенства (3.2.4). Доказательство неравенств (3.2.4) и (3.2.5а) основано на некоторых фундаментальных неравенствах математического анализа. В приложении 3А приведены упомянутые неравенства и даны доказательства (3.2.4) и (3.2.5а).

Таким образом, во всех случаях, кроме тех, когда выполняется равенство (3.2.56), представляет собой положительную возрастающую выпуклую функцию для положительных причем ее наклон вначале координат равен (пример приведен на рис. 3.1). Если выполняется равенство (3.2.56), вторая производная по равна нулю при всех следовательно, в этом случае Хотя можно построить нетривиальные примеры дискретных каналов, для которых выполняется равенство (см. задачу (3.2), практического интереса они не представляют.

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

видим, что в силу леммы 3.2.1 этот показатель экспоненты имеет единственный максимум. Для малых (рис. 3.2а) максимум достигается при следовательно, максимум на единичном интервале имеет место при Для больших (рис. 3.26) максимум достигается при таком значении о, для которого

Рис. 3.1. Функция

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

а при больших скоростях параметрическими соотношениями

Рис. 3.2. Функция при

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

вторая производная задается равенством

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

Рис. 3.3. Примеры функции при

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

В этом случае, как показано на рис. 3.36, криволинейный участок типичной функции пропадает и остается только линейный участок.

Показатель экспоненты в неравенстве (3.1.20), взятый со знаком минус, получается непосредственно при максимизации по всем возможным векторам распределения. Имеем

где

Отметим, что вследствие этих ограничений множество допустимых представляет собой выпуклое замкнутое множество. Для некоторых каналов, включая весьма важные с физической точки зрения (см. § 3.4), максимум достигается на единственном векторе распределения при всех скоростях; для других каналов (см. задачу 3.3В) число распределений, максимизирующих на непересекающихся интервалах равно двум и более; наконец, для некоторых каналов (см. задачу 3.5) максимизирующее распределение непрерывно меняется с

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

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

Теорема 3.2.1. (Шеннон [1948] и др.). Для любого канала без памяти с дискретным входом существует -символьный код (набор сигналов) со скоростью нат на символ; для которого вероятность ошибки при декодировании по максимуму правдоподобия ограничена неравенством

где определена соотношениями (3.1.20) и (3.1.18) и представляет собой выпуклую убывающую, положительную функцию при а С определена в (3.2.13)

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

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

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

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

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

ибо в противном случае среднее по кодовым векторам с наибольшими вероятностями ошибки уже превысило бы границу (3.2.16). Подставив неравенство (3.1.20) в показатель экспоненты, для скорости получим неравенство

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

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

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

В заключение остановимся на задаче отыскания вектора весов доставляющего максимум взятому со знаком минус показателю экспоненты в границе для вероятности ошибки. Для получения аналитического выражения удобнее всего переписать показатель экспоненты в виде

Необходимо максимизировать или, что то же самое, минимизировать по величину

где

Ключевой оказывается следующая лемма.

Лемма 3.2.2. Величина представляет собой выпуклую функцию на множестве вероятностных распределений при всяком фиксированном

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

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

Лемма 3.2.3. Функция выпукла на множестве вероятностных распределений

Доказательство. Начнем доказательство с определения (3.2.2) для переписав его в виде

Первый член — линейная функция по следовательно, выпуклая. Второй член можно записать в виде

где

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

Минимизация (максимизация) выпуклых функций в пространстве распределений рассматривается в приложении 3Б, где приводятся принадлежащие Куну и Таккеру [1951] необходимые и достаточные условия минимума (максимума) и где применительно к рассматриваемым здесь задачам доказаны следующие теоремы.

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

где определено соотношением (3.2.21), причем при всех х таких, что должно выполняться равенство

Теорема 3.2.3. Средняя взаимная информация. Для того чтобы существовал максимум функции по вектору распределения равный С, необходимо и достаточно выполнение неравенства

которое переходит в равенство при х таких, что

Явных формул для и С приведенные теоремы не дают. Однако неравенства (3.2.23) и (3.2.24) могут служить для принятия или отклонения интуитивных соображений об оптимизирующем распределении. Вот очень простой пример: для симметричного по выходу канала с двоичным входом определенного в § 2.9, приведенные необходимые и достаточные условия подтверждают очевидный факт, что оптимизирующим всегда будет равномерное распределение В частном случае, когда выходное пространство совпадает со входным и когда матрица переходов размерами невырождена, можно показать (см. задачу 3.4), что условия обеих теорем выполняются, а в их формулировках неравенства можно заменить на равенства. Кроме того, для оптимизирующего и оптимизируемых величин можно получить явные формулы. В общем случае, однако, максимизацию (минимизацию) приходится проводить численно. Дело существенно упрощается при выпуклости функций, гарантирующей сходимость к максимуму (минимуму) любого алгоритма в классе алгоритмов наискорейшего спуска. В приложении приводится эффективный вычислительный алгоритм для нахождения пропускной способности. Аналогичные алгоритмы для вычисления были найдены Аримото [1976] и Лешем [1976].

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

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

введенная формулой (3.2.7), будучи максимизированной по дает значение показателя экспоненты при малых скоростях. Для любого канала с двоичным входом этот максимум легко вычисляется, так как оптимизирующее распределение равномерно, что приводит к равенству

где

Для частного случая ДСК и АБГШ канала 1 параметр легко вычисляется:

Применив неравенство Шварца (см. приложение 3А) к (3.2.27а), получим, что

Допустим теперь, что скорость достаточно мала, так что применима линейная оценка (3.2.7). Для канала с двоичным входом имеем

В § 2.9 было показано, что для линейных кодов, используемых в этом классе каналов,

где веса ненулевых кодовых слов, задано в (3.2.27а). В частности, как было показано в § 2.10, если ограничиться случаем (так что при N-уоо), то окажется, что для всех существует ортогональный код такой, что при всех В этом случае получаем границу

Поскольку здесь скорость асимптотически стремится к нулю с ростом ясно, что границу (3.2.29) следует сравнивать с верхней границей среднего по ансамблю (3.2.28), взяв обе границы при Легко видеть, что показатель экспоненты в (3.2.29) больше, чем в (3.2.28), т. е.

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

Оба показателя экспоненты (3.2.28) и (3.2.29) приведены на рис. 3.4. Из формул (3.2.27а, б) видно, что случай описывает каналы без шума и что с увеличением шума растет монотонно

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

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

Рис. 3.4. Отрицательные показатели экспоненты из соотношений (3.2.28) и (3.2.29)

<< Предыдущий параграф Следующий параграф >>
Оглавление