Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
где {gi n} — произвольное, но фиксированное множество двоичных
чисел \ I ^ L, 1 ^ п ^ N. Из сравнения (6.1.1) и (6.1.3) видно,
что систематический код с проверкой на четность представляет собой частный случай общего кода с проверкой на четность, в котором
gl,n=X’ 1 = п-
gi, 0; l^n^L, 1фп. (6.1.4)
В тех случаях, когда при использовании некоторого кода с проверкой на четность нужно будет специально обратить внимание на длину
213
блока N и на длину последовательности сообщения L, код будем называть (N, 1)-кодом с проверкой на четность (или систематическим (jV, Z,)-кодом с проверкой на четность).
Одну из причин рассмотрения кодов с проверкой на четность как систематических, так и несистематических, можно понять, если рассмотреть реализации кодера. Для кодера с проверкой на четность необходимы регистр для запоминания последовательности сообщения и, регистр для запоминания кодового слова х и сумматоры по модулю 2, число которых пропорционально NL. Поэтому использование кодеров с проверкой на четность позволяет избежать экспоненциального роста объема памяти с ростом L, неизбежного при использовании произвольного блокового кода с 2L кодовыми словами, структура которого не выбиралась специальным образом.
Порождающие матрицы
Соотношение (6.1.3) можно выразить в более компактной форме, если ввести понятие порождающей матрицы G для(М, 1)-кода с проверкой на четность. Эта матрица, как показано на рис. 6.1.2, представляет собой двоичную матрицу с размерами L на N и компонен-
G--
$ и' $2,1 $2,2 '
-N-
дг,н
•9l,»
G-
100..
OfO..
bob..
N-L
•° 4i,u+i........
.0 fy,c+t.....fys
•* ......9t,N
а) в)
Рис. 6.1.2. Порождающая матрица: а — произвольный код с проверкой на четность; б — систематический код с проверкой на
четность.
тами п, определяемыми соотношениями (6.1.3). Из (6.1.4) следует, что в случае систематического кода с проверкой на четность подматрица, соответствующая первым L столбцам, является единичной матрицей.
Рассматривая и и х как вектор-строки, получаем
х = uG, (6.1.5)
где цG представляет собой матричное произведение, использующее сложение по модулю 2 [это означает, что uG определяется таким образом, чтобы (6.1.5) было эквивалентно (6.1.3)].
Пусть теперь и' и и” — две информационные последовательности; определим сумму по модулю 2 двоичных векторов соотношением
214
t=u'0u’ = u{[ @ u\, ..., u'L 0 u'i). Тогда, если x' = u'G и x" =
-e U"G, TO
x' Ф x" = u'G 0 u"G = (u' Ф u") G = (6.1.6)
= uG. (6.1.7)
Последнее равенство в (6.1.6) вытекает из ассоциативного, коммутативного и дистрибутивного законов сложения по модулю 2 и может быть доказано с помощью соотношения (6.1.3). Из (6.1.7) следует, что сумма по модулю 2 двух кодовых слов равна другому кодовому слову, соответствующему информационной последовательности и = и'0и".
Заметим далее, что если в информационной последовательности имеется лишь один символ 1, скажем на /-й позиции, то результирующее кодовое слово равно /-й строке матрицы G, которую обозначим
через g*. Отсюда, учитывая соотношение (6.1.6), получаем, что произвольное кодовое слово можно представить в виде
х = (6-1.8)
Другими словами, множество кодовых слов является пространством строк матрицы G, т. е. совокупностью линейных по модулю 2 комбинаций строк G, как это определяется соотношением (6.1.8).
Проверочные матрицы систематических кодов с проверкой на четность
Временно ограничимся рассмотрением систематических (N,L)-кодов с проверкой на четность и введем в рассмотрение новую матрицу
Н, называемую проверочной матрицей. Она представляет собой матрицу с размерами N на N—L и определяется, как показано на рис. 6.1.3, через коэффициенты git п, введенные в (6.1.2).
Чтобы понять значение матрицы Я, перепишем (6.1.2), используя соотношение (6.1.1), в виде
L
хп = х, glt п; L<n^M. (6.1.9)
Прибавляя хп к обеим частям (или вычитая хп, что эквивалентно в арифметике по модулю 2), получим для каждого кодового слова х:
