Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
х (D) = a (D)g (D). (6.5.10)
Теперь покажем, что g (D) должен быть делителем многочлена DN — 1. Так как g (D) — нормированный многочлен степени т, то
239
получаем
DN-m g (?)) — DN — 1 -f л (D).
(6.5.11)
Поскольку r (D) = /?дл/_1 (D)], то многочлен r (D) получается
циклическим сдвигом кодового слова и имеет^ (D) в качестве делителя. Тогда из соотношения (6.5.11) следует, что g (D) является делителем DN — 1.
Многочлен g (D) называется порождающим многочленом циклического кода; смысл его состоит в том, что g (D) является делителем всех кодовых слов. Множество кодовых слов — это множество линейных комбинаций g (D) и его первых N — т — 1 циклических сдвигов. Порождающая матрица для циклического кода в несистематической форме представлена на рис. 6.5.2. В терминах числа информационных символов кода L получим, что N — т = L, а степень g (D) равна N — L.
Теперь рассмотрим эту задачу несколько иначе; пусть g (D) — любой нормированный многочлен в GF (q) степени N — L, являющийся делителем DN — 1. Покажем, что код, порождаемый g(D) [т. е. код, у которого все кодовые слова являются линейными комбинациями g (D) и его первых L—1 сдвигов], является циклическим кодом. Очевидно, что этот код линейный и имеет порождающую матрицу, представленную на рис. 6.5.2. Далее, если л: (D) — любое кодовое слово, то
Dx(D)^=xN- 1 (DN — l)-f Хы-\2 DN~1 + ...-f + (6.5.12)
Так как x (D) и DN — 1 делятся на g (D), то отсюда следует, что xn_2Dn_1 + ... + x0D + xN_! делится на g (D) и что любой циклический сдвиг кодового слова является другим кодовым словом. Эти результаты можно сформулировать в виде следующей теоремы.
Теорема 6.5.1. Любой циклический код над GF (q) с L информационными символами и с длиной блока N порождается нормированным многочленом g (D) над GF (q) степени N — L. Этот многочлен является делителем DN— 1. Обратно, любой нормированный многочлен над GF (q) степени N — L, который делит DN — 1, порождает циклический код с L информационными символами и длиной блока N.
Точно так же, как порождающая матрица циклического кода может быть выражена через порождающий многочлен g (D) (N — L)-u степени, проверочная матрица может быть выражена через многочлен L-й степени h (D), называемый проверочным многочленом и определяемый соотношением
g (D)h (D) = DN — I. (6.5.13)
Если умножить любое кодовое слово х (D) = а (D)g (D) на h (D), то получим
f (D) — х (D) h(D) = a (D)g (D) h (D) = D*a (D) - a(D). (6.5.14)
Так как степень a (D) не превышает L — 1, то из рассмотрения
240
(6.5.14) следует, что / (D) = 2/nD" должен иметь нулевые слагаемые при L ^ ti ^ N — 1. Произведя умножение л: (D) h (D), получим
L
И- htXn-t = fn = 0; L<n<tf-1. (6.5.15)
i = 0
Из (6.5.13) следует, что h (D) — нормированный многочлен и mohL = = 1. Поэтому можно переписать (6.5.15) в виде
L— 1
Xn~L= ~ S L:
1 = 0
:n—i.
(6.5.16)
ti-i
Не
f А
h1
* 1
к *ffQ
* % N
Ъч, :
"4
Равенство (6.5.16) дает рекуррентное соотношение для вычисления в соответствующем порядке проверочных символов x^-l-u xn—l—2, ..., х0 по информационным символам xN-lt ..., xN-L. Поэтому любой х (D), удовлетворяющий (6.5.15), является кодовым словом и любое кодовое слово удовлетворяет (6.5.15). На языке матриц это означает, что хЯ = 0 тогда и только тогда, когда х = (xN-lt ..., х0) является кодовым словом, где Я представлено на рис. 6.5.3.
Так как многочлен h (D) является делителем/?^—1, то он также порождает циклический код, который называется дуальным кодом по отношению к коду, порождаемому g (?>). Поэтому все циклические сдвиги h (D) являются линейными комбинациями N — L сдвигов, изображенных на рис. 6.5.3, и часто удобно использовать эти дополнительные сдвиги в качестве проверочных соотношений, которым должны удовлетворять кодовые слова, порождаемые g(D).
До настоящего момента рассмотрение носило в основном абстрактный характер, поэтому настало время обсудить вопрос о том, как в действительности можно реализовать кодирование циклического кода. Первый из способов кодирования основывается на (6.5.16) и иллюстрируется рис. 6.5.4.
Первоначально информационные символы хранятся в разрядах регистра сдвига, как это представлено на рис. 6.5.4. Содержимое в каждом разряде подается на выход разряда (т. е. на линию, выходящую из правой части разряда) и умножается на соответствующее /гг; эти произведения суммируются и умножаются на —1, что дает в итоге Xn—l—i, как это следует из (6.5.16). Затем регистр сдвига сдвигается на одну позицию вправо, символ xN^1 поступает в канал, а символ xN_L^x подается в левый разряд регистра. После этого сдвига на выходе умножителя на (—1)появляется символ xN_L_2. После N сдвигов в канал будет передан х0, а кодер будет подготовлен к поступлению в него следующей информационной последовательности.
