Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
из двух случаев рассматривается. Начнем с изучения обращения теоремы кодирования, так как она почти не отличается от соответствующей теоремы для случая без ограничений.
Используя обозначения последнего параграфа, пропускную способность дискретного по времени канала без памяти с ограничением на входе f (х) <1 $, определим следующим образом:
C = supI(Xd; Yp), (7.3.1)
где верхняя грань берется по всем разбиениям выходного пространства, всем дискретным множествам входов (aj, ..., ак) и всем распределениям вероятностей Q (а^, ..., Q (ак), удовлетворяющим ограничению
S QK)/K)<S. (7.3.2)
k=l
Заметим, что при этом определении функция f (х) и присутствующее в ограничении значение $ рассматриваются как неотъемлемые части описания канала.
Теорема 7.3.1. (Обращение теоремы кодирования.) Пусть дискретный стационарный источник с алфавитом объема М имеет энтропию Нж (U) и порождает одну букву каждые секунд. Пусть дискретный по времени канал без памяти с ограничением на входе / (х) ^ & имеет пропускную способность С, определенную (7.3.1). Пусть последовательность символов источника длины L связана с адресатом каналом, по
342
которому передается последовательность N символов хи ..., xn, где N равно \_LxJxc_\. Пусть ансамбль XN, образовавшийся на входе канала, удовлетворяет ограничению
(7.3.3)
п— 1
Тогда, в пределе при L -*¦ оо, вероятность ошибки на букву источника <Ре> удовлетворяет соотношению
<Ре> log (М-1) + Ж «Ре» > Я„ (U)-^- С. (7.3.4)
(Замечания. Заметим, что условие (7.3.3) означает, что ограничение удовлетворяется при усреднении по кодовым словам. Допускается нарушение ограничения для отдельных кодовых слов, а также для отдельных букв в последовательности N посылок по каналу. Другими словами, при ограничении на энергию допускается распределение энергии, приходящейся на блок, любым желаемым образом между N посылками по каналу.)
Доказательство. Доказательство теоремы 7.2.2 применимо здесь в той части, где оно касается установления справедливости неравенств
/(VL; VL)</(XW; \N) и / (Х"; Yw) < 2 HXn;Yn).
п = 1
В конце доказательства теоремы 7.2.2 было показано, что
I (Х„; Yn) ^ С для каждого п. Этот результат не сохраняется здесь,
поскольку для каждой отдельной посылки по каналу не требуется,
чтобы удовлетворялись ограничения. Для того чтобы завершить доказательство, надо показать, что
|/(Xn; Yn)^NC. (7.3.5)
П= 1
Пусть аъ ..., а^ — множество входных букв канала, используемых для какого-либо кода, Q„ (ak) — вероятность появления входной буквы ah при п-и использовании канала. Согласно (7.3.3) имеем
S 2 (7-3.6)
п=1&=1
Введем вероятности Q(ah)
2QnK). (7.3.7)
п = 1
Подставляя (7.3.7) в (7.3.6), получаем
2 k а» 1
(7.3.8)
343
Пусть I (X; Y) — средняя взаимная информация между входом и выходом канала при использовании букв аъ ..., ак с вероятностями Q (aj, ..., Q (ак). Так как (7.3.8) эквивалентно (7.3.2), то
/(Х;У)<С. (7.3.9)
В теореме 4.4.2 было показано, что средняя взаимная информация в канале с дискретным входом является выпуклой ^ функцией входных вероятностей*). Из (4.4.5) (если положить 0„ равным 1 /N) следует
Z-^гПХп, УпХПХ; Y). (7.3.10)
N
Сочетая (7.3.9) и (7.3.10), получаем (7.3.5), что и доказывает теорему. | Перед тем как приступить к формулировке и доказательству теоремы кодирования для дискретного по времени канала без памяти с ограничением на входе, следует рассмотреть влияние ограничения на входе на дискретный канал без памяти. Так же как и в гл. 5, обозначим через Р (/|k) переходные вероятности для дискретного канала без памяти с входным алфавитом 0, ..., К— 1 и выходным алфавитом 0, ..., J— 1. Пусть / (k)— функция, определенная на входных буквах; рассмотрим класс кодов, для которых каждое кодовое слово х = (хи ..., Xn) удовлетворяет ограничению
2/(*„)</V?, (7.3.11)
п= 1
где ё — заданная постоянная.
Построим теперь ансамбль кодов, в котором каждое кодовое слово удовлетворяет (7.3.11). Пусть Q (k) — вероятности входных букв,
удовлетворяющие неравенству
2 Q (?)/(*)<?• (7.3.12)
