Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Нахождение максимума Е ех (R) по р в значительной мере похоже на аналогичную процедуру для показателя экспоненты случайного кодирования. Если ввести обозначение
Eex(R’ Q) = sup[ — pR'+Ex(p, Q)]. р» l
171
то получим параметрические соотношения
Евх (R, Q) = -р- +ЕХ (р, Q),
др
(5.7.17)
др p=i
(5.7.18)
(5.7.19)
При больших скоростях R эта граница эквивалента прямолинейному участку границы случайного кодирования, которая была рассмотрена ранее. Для типичного канала RXi ^ = 0 и, как показано в задаче 5.24, имеем
В настоящее время сравнительно немного известно о методах отыскания максимума этой границы по Q. Функция Ех (р, Q) не является выпуклой а по Q и может иметь несколько локальных максимумов по Q. И, что более удивительно, если попытаться оптимизировать выражение (5.7.7) для т по QN (х), не ограничиваясь произведением распределений, то иногда могут возникнуть случаи, в которых произведение распределений не оптимизирует границу (см. задачу 5.26). Джелинек (1968), однако, показал, что в случае произвольного дискретного канала с двоичным входом произведение распределений всегда оптимизирует границу и, на самом деле, оптимальное значение Q равно Q (0) = Q (1) = 1/2 (см. задачи 5.29 и и 5.30).
5.8. НИЖНИЕ ГРАНИЦЫ ДЛЯ ВЕРОЯТНОСТИ ОШИБКИ
В предыдущих параграфах были найдены верхние границы вероятности ошибочного декодирования, которые могут быть достигнуты в дискретном канале без памяти; эти границы были выражены через длину блока N и скорость R. Этот параграф посвящен отысканию минимальной вероятности ошибки, которая может быть достигнута на каком-либо (А\ /?)-коде. При изложении этого параграфа будем считать, что все кодовые слова являются равновероятными. В действительности без какого-либо такого предположения не существует ненулевая нижняя граница вероятности ошибки, так как если одно из кодовых слов посылается с вероятностью 1, то декодер может всегда декодировать сообщение, соответствующее этому кодовому слову и ошибки не будут происходить*’.
*> Можно, однако, построить нижнюю границу вероятности ошибки для наихудшего кодового слова в коде, т. е. для шах Ре,тt не рассматривая вероятностей кодовых слов (см. задачу 5.32).
lim?e3e(tf,Q) = - ^Q(k)Q(i) In f J VP (/1 k) P (/1 /)]. (5.7.20)
R-0 k, i L / J
172
Fr Для равновероятных сообщений вероятность ошибочного декодирования кода с М сообщениями равна
где Ре, т — вероятность ошибки при условии, что было передано сообщение т. В последнем параграфе было показано, что при любой длине блока N и любой скорости R > О существуют (N, Р)-блоковые коды, для которых одновременно Ре^ехр[—NET (R)] и Р е ^
< ехр [—NE ех (R +1п 4/N)].
Вывод известных нижних границ для Ре при заданных N и R значительно тоньше и сложнее, чем вывод верхних границ. Поэтому мы только сформулируем здесь относящиеся сюда теоремы. Доказательства могут быть найдены у Шеннона, Галлагера и Берлекэмпа (1967). Доказательства для частного случая двоичного симметричного канала (ДСК) будут представлены здесь. Большая часть идей, используемых при отыскании нижних границ для Р е, проявляется в этом частном случае, но при этом удается избежать многих деталей.
Теорема 5.8.1. (Граница сферической упаковки). Для любого (N, R)-кода в дискретном канале без памяти
и Е0 (р, Q) задается равенством (5.6.14). Величины Oj (N) и о2 (N) стремятся к нулю с ростом N и могут быть взяты в виде
где Pmin является наименьшей ненулевой переходной вероятностью канала, а К — объем входного алфавита.
Как будет показано, функция Esp (R), называемая показателем экспоненты сферической упаковки, определяется почти так же, как показатель экспоненты случайного кодирования S Er (R), и отличается только интервалом значений р, по которому производится максимизация. Следствием этого является то, что результаты, полученные в § 5.6, непосредственно применимы к Esp (R). В частности, Esp (R) будет положительной при 0 < R < С, убывающей с ростом R и выпуклой w функцией. На рис. 5.8.1 Esp (R) изображена для ряда каналов вместе с ЕТ (R) для сравнения. На рис. 5.8.1, а показано типичное поведение этих функций, а на других рисунках изображены в некотором смысле вырожденные случаи; на них Е8Р (R) обращается в бесконечность при всех скоростях,
Ре > ехр (— N {EiP [R—o, (N)} + о2 (N)}).
(5.8.1)
где
Esp (R) = sup ["max Е0 (р, Q) —рR
Р>0 L Q
(5.8.2)
(5.8.3)
(5.8.4)
173
меньших, чем заданная постоянная, обозначаемая через Rx. Для того чтобы найти эту постоянную, представим себе
jmaxfofa, Q) — рЯ|
как множество линейных функций R с р> 0 в качестве параметра (см. рис. 5.6.3). Координата точки пересечения оси R с указанной выше функцией при заданном р равна