Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Нетрудно убедиться, что имеет место следующее полезное свойство проверочной матрицы: последовательность х является кодовым словом тогда и только тогда, когда хН = 0. Было показано, как найти одну такую проверочную матрицу Н для любой порождающей матрицы с линейно независимыми строками. Легко проверить (задача
6.11), что для всякой матрицы Н', столбцы которой порождают то же пространство, что и столбцы матрицы Н, х является кодовым словом тогда и только тогда, когда хН = 0. По этой причине будем называть любую такую матрицу проверочной матрицей для данного кода.
221
6.2. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КОДОВ С ПРОВЕРКОЙ НА ЧЕТНОСТЬ
При доказательстве теоремы кодирования для кодов с проверкой на четность удобно ввести в рассмотрение несколько более широкий класс кодов, которые по причинам, объясняемым в следующем параграфе, назовем смежными кодами. Смежным (N, L)-nodoM называется код с 2L кодовыми словами, имеющими длину блока N > L, в котором сообщения являются двоичными последовательностями длины L, а отображение сообщения ц в кодовое слово х дается равенством
x = uG©v, (6.2.1)
где G — фиксированная, но произвольная двоичная матрица размера L на N, a v — фиксированная, но произвольная последовательность N двоичных символов. Кодовые слова смежного кода образуются из кодовых слов соответствующего кода с проверкой на четность х' = uG путем добавления фиксированной последовательности v к каждому кодовому слову. В случае ДСК эта фиксированная последовательность может быть исключена из принятой последовательности перед декодированием и тем самым ее влияние нейтрализуется. Точнее, если принята последовательность у = x0z, то после вычитания из нее v получим у' = y®v, что в точности равно x'0z. Так как в случае ДСК шумовая последовательность не зависит от переданной последовательности, то декодер максимального правдоподобия правильно декодирует то же самое множество шумовых последовательностей, что и при соответствующем коде с проверкой на четность, и вероятность ошибки будет та же самая.
Теорема 6.2.1. Рассмотрим ансамбль смежных (N, ?)-кодов, в котором все символы G и v выбираются случайно и независимо равными 0 или 1, причем вероятности этих значений одинаковы. Средняя по этому ансамблю кодов вероятность ошибки для каждого из сообщений при передаче их по ДСК и декодированию по максимуму правдоподобия ограничена неравенством
Ре, ехр [ — NEr(R)], (6.2.2)
где ЕТ (R) выражается через переходную вероятность канала соотношениями (5.6.41) и (5.6.45) и R = (L In 2)/N.
Доказательство. Пусть um — произвольная информационная последовательность и хт — соответствующее ей кодовое слово. Для рассматриваемого ансамбля кодов вероятность того, что um будет отображена в данную последовательность хт, равна
QN(xm) = 2~". (6.2.3)
Чтобы доказать это, заметим, что существуют 2N<L+i’> способов выбора G и v, каждый из которых имеет вероятность 2—л'(/-+1>. Для каждой фиксированной G существует один способ выбора v, 222
Г при котором xm принимает любое фиксированное значение. Поскольку существует 2WL способов выбора G, то
Qw(xJ=2^ 2-"^ + » =2-".
Пусть далее ит- — информационная последовательность, отличная от ит и пусть хт- —соответствующее ей кодовое слово. Покажем, что хт и хШ' статистически независимы в рассматриваемом ансамбле кодов. Имеем
xmexm. = (um®um.)G. (6.2.4)
Предположим, что um и um- отличаются в /-й позиции. Тогда при любом выборе gb ..., gj_j, g7 + i, ..., gl существует один способ выбора
gj, при котором xm0xm' принимает любое фиксированное значение. Поэтому существуют 2Af(L-1> способов выбора G и v, при которых пара (хт, хШ') принимает любое наперед заданное значение и Р(хт, хт') = 2~2N. Отсюда и из (6.2.3) следует, что хт и хт- независимы.
Теперь заметим, что в теореме 5.6.1 предполагалось, что кодовые слова выбирались независимо. Вместе с тем, если внимательно просмотреть доказательство, то можно установить, что в нем использовалась лишь попарная независимость. Таким образом, теорема 5.6.1 применима и к нашему ансамблю. Следовательно, также применима и теорема 5.6.2, из которой непосредственно вытекают выражения ЕТ (R) для ДСК, приведенные в (5.6.41) и (5.6.45). |
Как и в § 5.6, этот результат доказывает существование смежного (N, L)-кода со средней вероятностью ошибки, по большей мере равной ехр [—NET (R)], и в силу сделанного замечания, соответствующий код с проверкой на четность, получающийся после устранения фиксированной последовательности v, обладает той же самой вероятностью ошибки. Так как множество правильно декодируемых шумовых последовательностей не зависит от сообщения, то точно так же Ре m ^ ^ ехр [—NEr (R)] для всех сообщений, закодированных этим кодом. Наконец, как было доказано в § 6.1, матрица G может быть преобразована в систематическую порождающую матрицу с помощью элементарных операций над строками и, быть может, перестановки некоторых столбцов*). Это доказывает следующее следствие.
