Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
X|2<3(*)f(i] й)1/(1 + Р2)1(1 + Р2) (I-0). (5Б.9)
Используем теперь неравенство Гельдера (см. задачу 4.15(6)) 2 г - rv „l/eie rv », i/d-ел i-е
(5Б.10)
Sa,.6,-<[2a]/e]e[2^/(1-e)j1
для правой части (5Б.9) и получим
2 |2<Э(й)Р(/|й)1/(1+р"^1+Ра < |2|2Q(*)P(/l^)1/<I+Pl>j1 + Pl|ex
х 12 [2 <2 (k)P(l\ й)1/<1 + р^|1 + Р2|1-9 . (5Б.11)
Взяв логарифм от обеих частей (5Б.11), будем иметь
—(Рз> Q)<^ —QE0 (Pl, Q) — (1- 0) Еа (p2, Q). (5Б.12)
Это означает, что E0(p, Q) является выпуклой гл по р. Выпуклость перестает быть строгой тогда и только тогда, когда как (5Б.9), так и (5Б.10) удовлетворяются с равенством. Согласно лемме (5Б.9) удовлетворяется с равенством тогда и только тогда, когда P(j \ k) не зависит от k для всех j, k, удовлетворяющих Q(k)P(j \ k) >
209
>0. Условие равенства в (5Б.10) (см. задачу 4.15(6)) состоит в том, что существует постоянная С, такая, что для всех /
[2Q(?)P(/'| ?)1/(1 + Pl,j1 + P1 = C|^Q(A)P(/| *)!/(>+P^)J1+P^.
Если (5Б.^"удовлетворяется с равенством, то ненулевые P(j ] k) могут быть удалены из написанного выше равенства, что даст
Г 2 <2 (А)11 + Р‘ = СГ 2 Q(A)11+P* (5Б.13)
l*:.P(/|*)>0 J [k-.P(j\k)>0 J
при всех /. Это означает, что выражение в квадратных скобках является некоторой постоянной а, не зависящей от j, и поэтому для любых /, k, для которых Q(k)P(} 1 *) > 0, будем иметь
2q(0P(/I0
(5Б.14)
P(i\k)
Доказательство теоремы 5.7.2. Имеем
Ех(р, Q) = — In {2 2 Q (A) Q (0 [2 VP и I k) Р (/ I 0J1/PJP . (5Б.15)
Можно применить лемму непосредственно к (5Б. 15), сопоставляя двойную сумму в (5Б.15) однократной сумме в (5Б.1), сопоставляя Q(k)Q(i) функции Q(k) в (5Б.1) и сопоставляя
HVP(i\k)P(i\i)
числам aft в (5Б. 1). Таким образом, Ех (р, Q) является возрастающей и выпуклойгл функцией р. Выпуклость является строгой, если не все ненулевые значения
2УР(Л*)Р(Ж)>
/
для которых Q(k)Q(i) > 0, равны друг другу. Эта сумма равна 1 при k = i и (как следует из задачи 4.15(a)) она равна 1 при k^i тогда и только тогда, когда P(j | k) = P(j \ i) для всех/. Подобно этому указанная выше сумма равна 0 тогда и только тогда, когда P(j | k)P(j | /) = 0 для всех /, что доказывает указанные в теореме условия строгой выпуклости. |
6
МЕТОДЫ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ
6.1. КОДЫ С ПРОВЕРКОЙ НА ЧЕТНОСТЬ
В предыдущей главе было рассмотрено использование блокового кодирования для надежной передачи данных по дискретным каналам. Было доказано, что для соответствующим образом выбранных кодов и при любой заданной скорости передачи, меньшей пропускной способности, вероятность ошибочного декодирования ограничена неравенством Ре ^ ехр [—NEr (/?)], где N — длина блока, a Er (R) > О определяется соотношением (5.6.16). Вместе с тем число кодовых слов и число возможных принятых последовательностей являются экспоненциально растущими функциями N; поэтому при больших N практически невозможно осуществить хранение в памяти кодера всех кодовых слов и хранение в памяти декодера способа отображения принятых последовательностей в сообщения.
В настоящей главе будут рассмотрены методы кодирования и декодирования, позволяющие избежать упомянутой проблемы памяти путем использования алгоритмов для построения кодовых слов по сообщениям и сообщений по принятым последовательностям. Почти все известные методы кодирования и декодирования основаны на идеях, лежащих в основе кодов с проверкой на четность, и поэтому мы начнем изучение с этих кодов. Полезно начать описание таких кодов применительно к двоичному симметричному каналу (ДСК), хотя позднее будет показано, что это ограничение не является обязательным.
Код с проверкой на четность является частным случаем отображения двоичной последовательности длины L в двоичную последовательность некоторой большей длины N. Прежде чем определять коды с проверкой на четность, приведем довольно простой, но широко используемый пример проверки на четность. Допустим, что последовательность двоичных символов кодируется с помощью простого добавления одного двоичного символа в конце последовательности; этот последний символ выбирается таким образом, чтобы общее число единиц в кодовой последовательности было четным. Назовем первоначальные символы информационными символами, а добавленный в конце последовательности символ — проверочным символом. Легко видеть, что если затем изменить один из символов последовательности, то общее число единиц станет нечетным, что обнаруживает факт наступления ошибки. Однако, если произойдут две ошибки, число единиц вновь станет четным и ошибки не будут обнаружены. Кодирование такого типа широко используется при записи на магнитные ленты, а также и в других случаях, когда желательна некоторая небольшая возможность обнаружения ошибок при минимальных затратах на оборудование.
