Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 86

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 80 81 82 83 84 85 < 86 > 87 88 89 90 91 92 .. 355 >> Следующая


Нахождение максимума Е ех (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 с указанной выше функцией при заданном р равна
Предыдущая << 1 .. 80 81 82 83 84 85 < 86 > 87 88 89 90 91 92 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed