5.8. НИЖНИЕ ГРАНИЦЫ ДЛЯ ВЕРОЯТНОСТИ ОШИБКИ

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

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

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

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

Теорема 5.8.1. (Граница сферической упаковки). Для любого -кода в дискретном канале без памяти

где

и задается равенством (5.6.14). Величины стремятся к нулю с ростом N и могут быть взяты в виде

где является наименьшей ненулевой переходной вероятностью канала, объем входного алфавита.

Как будет показано, функция называемая показателем экспоненты сферической упаковки, определяется почти так же, как показатель экспоненты случайного кодирования и отличается только интервалом значений по которому производится максимизация. Следствием этого является то, что результаты, полученные в § 5.6, непосредственно применимы к В частности, будет положительной при убывающей с ростом R и выпуклой функцией. На рис. изображена для ряда каналов вместе с для сравнения. На рис. 5.8.1, а показано типичное поведение этих функций, а на других рисунках изображены в некотором смысле вырожденные случаи; на них обращается в бесконечность при всех скоростях,

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

как множество линейных функций в качестве параметра (см. рис. 5.6.3). Координата точки пересечения оси R с указанной выше функцией при заданном равна

Рис. 5.8.1. Сравнение показателей экспонент сферической упаковки и случайного кодирования.

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

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

где

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

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

Функция надежности канала определяется равенством

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

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

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

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

Тогда при любом положительном целом N и любой любой -код имеет вероятность ошибки, которая удовлетворяет неравенству

Это утверждение является теоремой 4 в работе Шеннона, Галлагера и Берлекэмпа (1967) и там же приведено ее доказательство. В формулировке теоремы 4 имеется небольшая ошибка, состоящая в том, что пропущено условие Однако приведенное там доказательство верно для сформулированной здесь теоремы. Прямолинейный отрезок показателя экспоненты вместе с показателем экспоненты сферической упаковки дают верхнюю границу для надежности при всех в пределе при больших Эти границы изображены на рис. 5.8.2 для тех же каналов, что и на рис. 5.8.1.

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

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

то общая вероятность правильного декодирования равна

Рис. 5.8.2. Границы для функции надежности (те же каналы, что и на рис. 5.8.1).

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

Используя равенство для биномиального распределения

находим, что вероятность ошибки будет равна

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

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

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

Минимум (5.8.14) при соблюдении этих ограничений достигается при и для всех когда

где выбирается так, что

Отдельные значения не существенны, если их сумма по удовлетворяет (5.8.18). Для того чтобы убедиться, что такой выбор приводит к минимуму (5.8.14), заметим, что при любом другом выборе можно найти такие, что для некоторого для некоторого При таком выборе можно увидеть, что (5.8.14) уменьшается при увеличении на 1 и уменьшении на 1. Подставляя (5.8.17) в (5.8.14) и замечая, что в результате

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

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

Эта граница называется границей сферической упаковки. Множество последовательностей, находящихся на расстоянии или меньше от кодового слова, можно интерпретировать как сферу радиуса вокруг этого кодового слова. Граница, представленная (5.8.19), является вероятностью ошибки, которая бы имела место, если бы можно было выбрать кодовые слова так, чтобы множество сфер радиуса описанных вокруг различных кодовых слов, исчерпывало все пространство двоичных последовательностей длины N и сферы имели бы пересечения друг с другом только по внешним слоям радиуса Такие коды называются сферически упакованными кодами и код, изображенный на рис. 5.2.1, дает пример такого кода (в этом случае нет пересечений даже на внешнем слое радиуса 1). Часто при выводе этой границы сначала находится вероятность ошибки для сферически упакованного кода и затем показывается, что сферически упакованный код имеет вероятность ошибки не большую, чем любой другой код с теми же самыми В таком выводе имеется логическая ошибка, состоящая в том, что для большинства значений не существует сферически упакованных кодов.

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

Теорема 5.8.3. (Граница сферической упаковки для ДСК.) Пусть задан двоичный симметричный канал с вероятностью ошибки и пусть произвольное число, Если число кодовых слов удовлетворяет неравенству

то

Доказательство. Как видно из (5.8.14), любое увеличение в какой-либо из сумм До значений, больших, чем указанные в (5.8.17) и (5.8.18), приводит к дальнейшему уменьшению нижней границы Пусть и выберем так, что Для всех выберем так, что выборы, очевидно, приводят к значениям сумм, большим, чем те, которые определяются из (5.8.17) и (5.8.18); подставляя эти выражения в (5.8.14), получаем

Используя границу Стерлинга для факториала, можно оценить снизу следующим образом (см. задачу 5.8(б)):

Если Так как

Так как то единственно возможное значение которое превышает равно В этом случае, используем специальную границу (см. задачу

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

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

Если найти [в соответствии с (5.8.2)], то, используя те же рассуждения, что и в примере 1 § 5.6, получим, что при

Рассмотрим теперь некоторый произвольный -код, для которого Если выбрать так, чтобы

удовлетворялось равенство

то должно удовлетворять (5.8.20), и из (5.8.21) вытекает результат, который эквивалентен теореме 5.8.1:

Для мы ниже выведем более сильную границу, чем граница в теореме 5.8.1.

Для того чтобы установить справедливость теоремы 5.8.2 для ДСК, нам понадобится несколько лемм, которые представляют самостоятельный интерес. В первой из них рассматривается концепция декодирования, называемая «декодирование списком». Предположим, что при заданном множестве кодовых слов длины N декодер отображает любую принятую последовательность в список, скажем, сообщений. Такое декодирование могло бы быть полезным, если бы планировалось использование обратной связи в системе передачи и при последующей передаче устранялась неопределенность в том, какое из декодированных сообщений было в действительности передано. Если переданное сообщение не принадлежит списку из декодируемых сообщений, то говорят, что произошла ошибка при декодировании списком. Пусть минимальная вероятность ошибки при декодировании списком по всем кодам с кодовыми словами, длиной блока N и списком из декодируемых сообщений. Можно повторить вывод границы сферической упаковки для схемы декодирования списком, обозначая через множество выходных последовательностей у, для которых принадлежит декодируемому списку. Равенство (5.8.14) остается справедливым, если понимать под число выходных последовательностей у, для которых принадлежит декодируемому списку и которые находятся на расстоянии от В этих условиях ограничение (5.8.16) для принимает вид

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

Лемма 1. Пусть задан ДСК с вероятностью ошибки и пусть произвольное число, Если

то

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

при всех

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

Лемма 2. (Граница Плоткина.) Минимальное расстояние любого двоичного кода с кодовыми словами и длиной блока N удовлетворяет неравенству

Доказательство. Расположим кодовые слова -кода в таблицу с N столбцами и строками двоичных символов; кодовое слово будет строкой таблицы. Рассмотрим теперь сумму всех расстояний в коде, т. е.

Пусть число нулей в столбце таблицы. Так как существует различных значений для которых то при

Поскольку существуют значений для которых то

Точно так же существуют значений для которых значений для которых так что

Правая часть (5.8.34) ограничена сверху числом которое является максимальным значением выражения рассматриваемого как функция Этот максимум достигается при Поэтому

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

Объединяя (5.8.35) и (5.8.36), получаем (5.8.31).

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

Лемма 3. В ДСК с вероятностью ошибки при имеет место неравенство

где

Отметим, что показатель экспоненты равен значению показателя экспоненты для процедуры с выбрасыванием при [см. (5.7.20)].

Доказательство. Так как должно быть целым числом, то легко проверить, что из (5.8.31) вытекает неравенство при Предположим, что в данном коде два кодовых слова находятся на расстоянии друг от друга. Имеем

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

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

При четных это выражение ограничено снизу следующим образом:

где было использовано неравенство (5.8.23). Это выражение представляет собой убывающую функцию при четных и так как то

При нечетном рассуждения почти совпадают; используется (5.8.25) при получении нижней границы для В результате получим неравенство

правая часть которого ограничена снизу выражением (5.8.40); это заканчивает доказательство.

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

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

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

Лемма 4. Для произвольных положительных целых чисел

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

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

При любом префиксе пусть будет множеством суффиксов для которых В канале без памяти и (5.8.42) можно переписать в виде

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

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

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

Изменяя порядок суммирования по в (5.8.43) и подставляя (5.8.45) в полученное выражение, имеем

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

Объединяя (5.8.47) и (5.8.46), завершаем доказательство леммы.

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

Для -кода с заданными определим число X с помощью равенства

Будем рассматривать лишь скорости из интервала

так, что Обозначим теперь

Заметим, что Используя (5.8.50), можно показать, что число

кодовых слов удовлетворяет неравенству

Теперь из леммы 1 следует, что

Согласно лемме 3, также имеем

Сочетая (5.8.54) и (5.8.55) с леммой 4, получаем

Наконец, используя (5.8.50), чтобы выразить X через и перенося коэффициент в показатель экспоненты, получаем

где

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

Теорема 5.8.4. Пусть задан ДСК с вероятностью ошибки и пусть обозначает при которой прямая линия, проходящая через точку является касательной к кривой Тогда при любом и любой R из интервала для любого -кода удовлетворяет (5.8.57).

Вероятность ошибки на блок при скоростях, больших пропускной способности

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

Теорема 5.8.5. [Вольфовиц В произвольном дискретном канале без памяти с пропускной способностью С (в натуральных единицах) для любого -кода при имеем

где А — конечная положительная постоянная, зависящая от канала и не зависящая от

Обсуждение. Как видно из (5.8.59), при любой фиксированной скорости значение должно стремиться к 1 при неограниченном возрастании Можно также заметить, что если выбрать при некотором фиксированном значении то будет строго больше чем 0 при всех

Доказательство. Пусть переходные вероятности канала, а объемы входного и выходного алфавитов соответственно. Пусть будут вероятностями на входе, на которых достигается пропускная способность, и пусть со соответствующие вероятности на выходе. Согласно теореме 4.5.1 имеем

Пусть

где и пусть

Определим

где

Рассмотрим теперь -код с кодовыми словами и областями декодирования Вероятность правильного декодирования для этого кода равна

Пусть будет произвольным числом; определим для

Обозначая через дополнение представляем (5.8.62) в виде

Для имеем и поэтому вторая сумма в (5.8.64) ограничена следующим образам:

где использовано то, что области декодирования не пересекаются и что является распределением вероятности.

Первую сумму в (5.8.64) можно оценить сверху с помощью суммирования при любом заданном по у а не по Получим

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

где

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

Отсюда при всех имеем

Подставляя (5.8.65) и (5.8.70) в (5.8.64), будем иметь

В силу того, что это справедливо для всех -кодов, имеем

Наконец, для заданной выбирая и используя равенство получаем (5.8.59), что завершает доказательство теоремы.

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