e.i. код с точки з1>ёния расширения пол li6

Таким образом мы перешли от матричного описания линейных кодов к полиномиальному описанию одного частного подкласса линейных кодов. Мы ограничиваемся рассмотрением этого подкласса потому, что полиномиальная формулировка облегчает поиск хороших кодов и разработку кодеров и декодеров. По прИ чинам, которые выясняются в следуюш,ем параграфе, эти коды называются циклическими кодами.

Например, выберем некоторый примитивный элемент а поля GF (16) и примем длину кода равной 15. Для построения проверочной матрицы кода над GF (2) выберем = а, Тг =

а с: а а" а а« а а" a a

й" й а- «« о£ а* а" «-о а а" 0£- а«

Другой выбор элементов и 72 приводит к другой проверочной матрице, иногда хорошей, а иногда плохой. Мы надеемся, что сделанный выбор приведет к хорошей проверочной матрице, но пока что еще рано объяснять причины этого.

При желании можно эту проверочную матрицу заменить проверочной матрицей над GF (2), используя приведенное в § 4.5 представление поля GF (16). Для этого надо каждую степень элемента а заменить 4-битовым столбцом, полагая верхний элемент столбца равным коэффициенту при z" в полиномиальном представлении этого элемента поля, второй элемент столбца равным коэффициенту при z* и т. д. В результате получится матрица

10 0 0 10 0 1 10 1

0 10 0 1 10 10 1 1

0 0 10 0 1 10 10 1

0 0 0 10 0 1 10 1 о

1110

1111

10 0 0 110 0 0 110 0 0 1 0001 10001 10001 I OOlOlOOlOlOOIOl о 1 I I 1 о 1 1 1 I о 1 I I 1

Хотя этого сразу не видно, строки данной проверочной матрицы линейно независимы, и, следовательно, она определяет двоичный (15,7)-код. Минимальное расстояние этого кода равно 5 (хотя это тоже не очевидно). Этот код можно также представить в виде множества многочленов над GF (2) степени не выше 14, таких, что в расширении Gf (16) каждый многочлен удовлетворяет равенствам с (а) = О ис (а) = 0. Иначе говоря, кодовые слова являются многочленами с корнями в а и а.

Можно показать, что всегда проще иметь дело с Матрицей в расширении, и поэтому мы в большинстве случаев будем работать в большом поле. Конечно, ограничиваясь проверочными матрицами такого частного вида, мы исключаем из дальнейшего рассмо трения многие коды.

5,2, ПОЛИНОМИАЛЬНОЕ ОПИСАНИЕ ЦИКЛИЧЕСКИХ КОДОВ

Начнем изложение заново, а затем вернемся к материалу предыдущего пар*рафа. Линейный код Ф называется циклическим, если из того, что слово с = (Cq, с,, c„ i) принадлежит , следует, что слово с = (с„ 1. Со, с„ 2) также принадлежит . Кодовое слово с получается из кодового слова с циклическим сдвигом всех компонент на одну позицию вправо. Примером циклического кода является приведенный в табл. 1.1 код Хэмминга. КаждЬш линейный код над GF (q) длины п представляет собой подпространство пространства GF" (q), а циклический код является частным случаем подпространства, так как обладает дополнительным свойством цикличности.

Каждый вектор из GF" (q) можно представить многочленом от X степени не выше п-1. Компоненты вектора отождествляются с коэффициентами многочлена. Множество многочленов обладает структурой векторного пространства, идентичной структуре пространства Of" (q). Это же множество многочленов обладает структурой определенного в § 4.2 кольца GF (q) [х]/{х"- 1). Как в кольце, в этом множестве определено умножение

Pi (Х) Р2 (Х) = Rn [pi (Х) Р2 (Х)].

Заметим, что в это равенство входят произведения двух видов. Произведение в левой части является произведением в кольце GF (q) [х]/(х"-1), определенным через произведения в кольце GF (q) [х] в правой части.

Циклический сдвиг может быть записан через умножение в этом кольце:

x-p{x)=-Rni [хр{х)].

Итак, если кодовые слова некоторого кода задаются в виде многочленов, то код является подмножеством кольца GF (q) [.v]/(x"-1). Такой код является циклическим, если вместе с каждым кодовым словом с (х) он содержит кодовый многочлен х-с (х).

6.2. полиномиальное описание 117

Теорема 5.2.1. Подмножество кольца GF (д) [л;]/(х«-1) образует циклический код тогда и только тогда, когда он обладает следующими двумя свойствами ):

1) W образует подгруппу кольца GF (q) [x]/{x~\) по сложению;

2) если с (х) и а (х) GF (д) [xV{x"-l), то

Rn i [а (х) с (х)] е .

Доказательство. Предположим, что данное подмножество обладает этими двумя свойствами. Тогда оно замкнуто относительно сложения и умножения на скаляр и, следовательно, является подпространством. Оно замкнуто относительно умножения на любой элемент кольца, в частности на элемент х, и, следовательно, образует циклический код.

Теперь предположим, что рассматриваемое множество является циклическим кодом и поэтому замкнуто относительно сложения И умножения на элемент х. Но тогда оно замкнуто относительно умножения на степени элемента х и на линейные комбинации этих степеней, т. е. относительно умножения на произвольный многочлен. Следовательно, оно удовлетворяет обоим сформулированным условиям, И теорема доказана. □

Выберем теперь в ё ненулевой кодовый многочлен наименьшей степени и обозначим его степень через п-k (она должна быть меньше п). Умножим этот многочлен на элемент поля, чтобы сделать его приведенным. Поскольку код ё линеен, результирующий многочлен тоже принадлежит ё. В коде не содержится никакого другого приведенного многочлена этой степени, так как в противном случае разность этих двух приведенных многочленов давала бы кодовый многочлен степени меньше п-й,а это противоречит выбору исходного многочлена.

Единственный приведенный ненулевой многочлен наименьшей степени в коде ё называется порождающим многочленом кода ё и обозначается через g (х).

Теорема 5.2.2. Циклический код соспюит из всех произведений порождающего многочлена g ix) на многочлены степени не выше k-l.

Доказательство. Согласно теореме 5.2.1, все такие многочлены принадлежат коду, так KaKg- (х) принадлежит коду. Далее,

Это подмножество называется идеалом кольца. В общем случае подмножество / кольца R называется идеалом в R, если: 1) / является подгруппой аддитивной группы кольца R и 2) из г R и а I следует, что