Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Умножив обе части (6.5.2) на произвольный элемент а, принадлежащий GF (q), можно убедиться, что если х — кодовое слово, соответствующее и, то ах = (ахх, ах2......axN) — кодовое слово, соответствующее аи. Аналогично, если хг и х2 — кодовые слова для Uj и и2 соответственно, то Xi + х2 — кодовое слово, соответствующее Uj + u2. На
математическом языке это означает, что отображение информационных последовательностей в кодовые слова линейно и множество кодо-
237
вых слов образует линейное подпространство пространства jV-мерных последовательностей над GF (q).
Систематическим линейным кодом называется такой линейный код, у которого первые L компонент каждого кодового слова удовлетворяют соотношениям
Xi = ut; 1 L, (6.5.3)
Это достигается путем выбора git7l = 1 для I — п и g^n — 0 для п ^ L, п ф. I. Порождающая матрица для систематического линейного кода представлена на рис. 6.1.2, б.
Проверочная матрица Я, соответствующая систематическому линейному коду, должна'быть некоторой модификацией матрицы, представленной на рис. 6.1.3, поскольку при переходе от (6.1.9) к (6.1.10) получаем
0= 23 xtglt „ — хп. (6.5.4)
/= I
Поэтому матрица Я принимает такой вид, как это представлено на рис. 6.5.1, и для всех кодовых слов выполняется соотношение
хЯ = 0. (6.5.5)
Несмотря на модификацию матрицы, результаты § 6.1 и 6.2 могут быть непосредственно перенесены на рассматриваемое обобщение кодов. Например, если кодовые слова передаются по каналу, у которого символы входного и выходного алфавитов являются элементами GF (q), то можно представить принятую последовательность вектором у, а шумовую последовательность — вектором г, где у = х + г. Определяя синдром S соотношением S = yЯ, получаем, как и ранее, что S = yН — = zH, и можно построить таблицу декодирования для нахождения z по синдрому S.
Циклическим кодом над GF (q) называется такой линейный код, у которого при любом циклическом сдвиге какого-либо кодового слова получается другое кодовое слово. Таким образом, если (хъ ..., xN) — какое-либо кодовое слово, то (х2, х3, ..., xN, хг) — другое кодовое слово. При изучении циклических кодов более удобно несколько изменить обозначения, последовательно перенумеровав элементы не с начала, а с конца, от (N — 1) до 0. Таким образом, запишем х в виде (xN_lt xN^2, ..., х0). Это эквивалентно следующему представлению последовательности х в виде многочлена над GF (q):
x(D) —Xn—i Dn~' xn— 2 DN~2 + ... +x0- (6.5.6)
Если x (D) — кодовое слово циклического кода (т. е. его коэффициенты являются буквами кодового слова), то вычет Dx (D) по модулю DN — 1 также является кодовым словом. Чтобы убедиться в этом, рассмотрим
Dx(D) = xN-i Dn + ...+xqD, (6.5.7)
Dx (D) = xN_ i (DN — 1) -f xN-2 DN~1 -f ... -f x0 D -f- xN_ i,
238
Rdn— 1 U-)X (D)]—Xn~2 Dn 1 -f- ... -J- X0 D -f- Xn— 1. (6.5.8)
Допустим, что g (D) — нормированный многочлен минимальной степени, являющийся кодовым словом циклического кода, и пусть степень g (D) равна т. Из свойства линейности непосредственно следует, что если а0 — произвольный элемент GF (q), то a0g (D) — также кодовое слово. Кроме того, из свойства цикличности непосредственно следует, что axDg (D) является кодовым словом при всех аъ принадлежащих GF (q), и что aiD‘g(D) является кодовым словом для i N — 1 —
— т. Складывая эти кодовые слова, в конце концов можно доказать, что для любого многочлена а (D) над GF (q) со степенью, не большей N — 1 — т, а (D) g (D) является кодовым словом.
N-L
Н=
Уим ... 9UN
b,LH 92,N
?L,L + 1 ... N
-10 0 еэ«*»* Q
O-IO
ООО ... -1 и
ЗМ=9т*т+'
У/п-1 @0
5/77 3q
9т' 9д N-
I
Рис. 6.5.1. -Проверочная матрица систематического группового кода в GF(q).
Рис. 6.5.2. Порождающая матрица циклического кода.
Покажем теперь, что все кодовые слова циклического кода представимы в таком виде. Согласно алгоритму Евклида деления многочленов, любой многочлен х (D), степень которого не больше N — 1, можно представить в виде
x(D) = a(D)g(D) + r(D). (6.5.9)
Так как a (D)g (D) всегда является*, кодовым словом, то из свойства линейности вытекает, что если х (D) — кодовое слово, то г (D) -— также кодовое слово. Но г (D) имеет меньшую степень, чем g (D)\ поэтому, если степень r(D) отлична от нуля, то г (D) всегда можно умножить на элемент GF (q) таким образом, чтобы полученный в результате нормированный многочлен был бы кодовым словом, степень которого меньше степени g (D). По определению g (D) это невозможно и, следовательно, г (D) = 0. Таким образом, х (D) является кодовым словом в том и только в том случае, если существует такой многочлен a (D), степень которого не больше N — т — 1, что
