Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Свяжем теперь значения N \\ L с помощью интервала времени между двумя последовательными буквами источника т, и интервалом времени между двумя последовательными буквами канала тс. Предположим, что число возможных использований канала задается величиной N = [_ Lxjxc J, где [_ л: j означает наибольшее целое число,
меньшее или равное х.
Теорема 4.3.4. (Обращение теоремы кодирования.) Пусть дискретный стационарный источник с алфавитом объема М имеет энтропию
Hx (U) = lim Hl (U) и производит буквы со скоростью одна буква
L-+0O
за ге секунд. Пусть дискретный канал без памяти имеет пропускную способность С и передача по нему ведется со скоростью одна буква за тс секунд. Пусть последовательность источника длины L связана
с адресатом каналом, используемым N раз, 'где N — |_________Lxjxc____|.
Тогда для любого L вероятность ошибки на букву источника (Р е> удовлетворяет неравенству
<Ре) log (М— 1) + Ж «Ре» > Их, (U)------— С. (4.3.22)
1с
Доказательство. Согласно теореме 3.5.1 (U) ^ Hl (U), и
(4.3.22) является непосредственным следствием (4.3.21). |
Для того чтобы дать соответствующую интерпретацию доказанной теореме, рассмотрим Lxs как общее время, в течение которого проис-98
KoAHf передача. В течение этого бремени кодер MO>Kef использовав кодирование с фиксированной длиной или неравномерное кодирование для источника и блоковое или неблоковое кодирование для канала. Независимо от того, какое кодирование и какая обработка данных производились, средняя вероятность ошибки на символ источника должна удовлетворять (4.3.22) и, таким образом, она отлична от нуля, если Я^ (U) (скорость источника) больше, чем (т8/тс) С (пропускная способность канала на букву источника). Следует заметить, что теорема ничего не говорит о вероятностях ошибок отдельных букв Ре г. С помощью подходящего выбора кодера и декодера мы можем сделать Ре г малым для одних значений I и большим для других.
Хотя теорема в том виде, как она здесь сформулирована, приложима лишь к дискретным каналам без памяти, можно заметить, что это ограничение было использовано только при переходе от (4.3.20) к (4.3.21). Для того чтобы доказать справедливость теоремы для более общих каналов, нужно найти способ определения совместного ансамбля XN\N, а также определить С таким образом, чтобы Cs~(\IN) I (Xw; \N) в пределе при N->- оо. Эта задача будет рассмотрена в § 4.6.
В частном случае канала без шума с D буквами во входном и выходном алфавитах условие (4.3.22) является просто обращением теоремы кодирования для источника. Оно отличается от (3.1.20) тем, что ограничивает снизу вероятность ошибки на символ, а не вероятность ошибки в блоке.
Можно заметить, что граница, задаваемая (4.3.22), довольно слабая при большом объеме М алфавита источника. Для того чтобы показать, что эта слабость границы неизбежна, построим источник, для которого Нх (U) произвольно велика, а <Ре> > 0 произвольно мала даже при С = 0. Пусть источник без памяти и его алфавит составляют буквы alt ..., ам- Пусть е — сколь угодно малое положительное число и пусть Р (dj) — 1 — ей Р (ат) = е/(М — 1) при т = 2, М. Тогда, если декодер декодирует каждый символ в букву аь то ошибки появляются только тогда, когда источник вырабатывает буквы, отличные от av Таким образом, вероятность ошибки <Р е> равна е. Вместе с тем
Я» (f/) ^ (1 — е) log --(-(ЛГ— 1) -i-log^i . (4.3.23)
1 —8 М— 1 8
При любом е > 0 можно сделать Нх (U) сколь угодно большим, выбирая достаточно большое М. Можно заметить, что эта «система связи» удовлетворяет условию (4.3.22) с равенством, если С = 0.
уС ВЫПУКЛЫЕ ФУНКЦИИ
В этом параграфе мы возвратимся к задаче вычисления пропускной способности дискретного канала без памяти. Как можно видеть из
(4.2.3), она включает в себя максимизацию нелинейной функции многих переменных с двумя условиями: одним в виде равенства и другим в виде неравенства. Эта максимизация заметно упрощается, если 4* 99
йоспользоваться свойством выпуклости взаимной информации*'. Мы прервем здесь наше рассмотрение для того, чтобы кратко описать свойство выпуклости, которое будет полезно как для этой задачи, так и для ряда последующих подобных задач в этой книге.
Пусть а — (ах, ак) является /С-мерным вектором с действительными компонентами, определенным в области #-векторного пространства. Назовем область R выпуклой, если для любого вектора а из R и любого вектора р из R вектор 0а + (1 — 0) Р принадлежит R при
О < 0 < 1. Геометрически, когда 0 изменяется от 0 до 1, 0а + (1— 0) Р проходит отрезок прямой линии от р до а. Таким образом, область является выпуклой, если для каждой пары точек из области отрезок прямой линии между этими точками принадлежит области (рис. 4.4.1).
