Мы также определяем полином гтформса/ионного сообгцення х{р)

Ы = *-./" \х, у-+...+х,р + х,, (8.1.27)

1 к-1 •••1 Xq

определяет к информационных бит. Ясно, что произведение х{р)р) - это полином степени меньшей или равной и -1, который может представлять кодовое слово. Заметим, что имеется 2* полиномов jf,(p)J и, следовательно, имеется 2*

возможных кодовых слов, которые можно формировать при заданном gip).

Допустим, что мы обозначим эти кодовые слова так

cSp) = n{p)s{p), гп=\,2, 2" (8.1.28)

Чтобы показать, что кодовые слова в (8.1.28) удовлетворяют циклическому сдвигу, рассмотрим какое-либо кодовое слово С(р) в (8.1.28), Циклический сдвиг с{р) дает

сЫ-рС(р) + с„ ,[рл-\) (8.1.29)

и, поскольку и + 1, и cip) делятся на gp) без остатка, то и С,(/?) делится на g(p) без

остатка, т.е. С,(р) можно представить как

cip) = xXp)g{p).

Следовательно, циклический сдвиг в кодовом слове с{р), генерируемый согласно (8.1.28),

порождает другое кодовое слово.

Из вышесказанного мы видим, что кодовые слова, обладающие циклическими свойствами, можно генерировать умножением 2" сообщений на уникальный полином степени п-к g(p) - называемый порождающим полиномом циклического {п,к) кода, который является множителем при факторизации р" + \. Циклический код, генерируемый указанным образом, занимает подпространство векторного пространства S.

Размерность подпространства равна к.

Пример 8.1.3. Рассмотрим код с длиной блока « = 7. Полином р+ \ можно разложить на следующие сомножители

+1 = (р + \){р +р+ \)[р +р + \). (8.1.30)

Чтобы синтезировать циклический код (7,4), мы можем взять один из двух порождающих полиномов:

gip) = p+p + \ или \ \ (8.1.31)

g2\p) = P + P + -

Коды, генерируемые порождающими полиномами gi{p) и gnip), эквивалентны Кодовые слова кода (7,4), генерируемые полиномом gp) = р +р~ + 1 даны в табл. 8.1.2. В общем полином р" +1 можно факторизовать так:

p" + l = g{p)h{p),

где g(p) - означает порождающий полином для циклического (п,к) кода, /?(/?) означает проверочный полином степени к. Последний можно использовать для генерирования дуального кода.

Таблица 8.1.2. Циклический код (7,4). Порождающий полином gi{p) = +Р

с этой целью можно использовать полином, обратный h(p), определяемый так: Р-) = Р(Р +h, ,p-+...+h,p - + l)= 1 +V,P ++P (8.1.32)

Ясно, что p" + 1 делится без остатка и на обратный полином. Следовательно, является порождающим полиномом циклического (w, п-к) кода. Этот циклический код дуален коду (п,к), генерируемому порождающим полиномом g(p). Таким образом,

(и, дуальный код образует нуль-пространство циклического (п,к) кода.

Пример 8.1.4. Рассмотрим циклический код, дуальный коду (7,4), генерированному в примере 8.1.3. Этот дуальный циклический код (7,3) связан с проверочным полиномом

[р) = {р+i)(p+р + \) = р+р+р + \. (8.1.33)

Обратный полином равен

р\(р-) = 1 + р + р+р\

Этот полином генерирует дуальный код (7, 3), данный в таблице 8.1.3. Читатель может убедиться в том, что кодовые слова дуального кода (7, 3) ортогональны кодовым словам циклического кода (7, 4) из примера 8.1.3. Заметим, что ни код (7, 4), ни код (7, 3) не являются систематическими.

Желательно показать, как можно получить порождающую матрицу из порождающего полинома циклического кода {п,к). Как указано выше, порождающую матрицу для (п,к) кода можно сконструировать из любого набора к линейно независимых кодовых слов. По заданному порождающему полиному g(p) легко генерировать набор к линейно независимых кодовых слов-это кодовые слова, соответствующие набору к линейно независимых полиномов p~g{p), pg(p), g(p).

Таблица 8.1.3. Дуальный код (7, 3). Порождающий полином ph (/?") = 1 + р + р +

Информационные биты

Кодовые слова

Поскольку любой из полиномов степени меньшей или равной п- \, который делится на g{p), можно выразить как линейную комбинацию этих полиномов, набор образует базис размерностью к. Следовательно, кодовые слова, связанные с этими полиномами, формируют базис размерности к для циклического кода («, л).

Пример 8.1.5. Четыре строки порождающей матрицы для циклического кода (7, 4) с порождающим полиномом gi{p) = р + р + \ можно получить из полиномов

Pgip)-P"*+P"+P\ = 3,2,1,0. Легко видеть, что порождающая матрица равна

1 1 0 1 0 0 0" 0 110 10 0 0 0 110 10 0 0 0 1 1 0 1

(8.1.34)

Аналогично, порождающая матрица для циклического кода (7,4), образуемая порождающим полиномом gjip) Р р-, равна

10 110 0 0 0 10 110 0 0 0 10 110 0 0 0 1 0 1 1

(8.1.35)

С,, можно сконструировать

Проверочные матрицы, соответствующие ( аналогичным образом, используя соответствующие обратные полиномы (задача 8.8).

Заметим, что порождающие матрицы, полученные таким конструированием, не имеют систематическую форму. Мы можем сконструировать порождающую матрицу

1,:р

форму можно получить делением р" на g[p). Таким образом, имеем

циклического кода в систематической форме G-[lj:PJ от порождающего полинома , следующим образом. Для начала заметим, что /-ая строка G соответствует полиному формы р" +/?,(/?), / = 1, 2, ...,к, где R,{p) - полином степени, меньшей чем п-к. Эту