algebcodes (1)

П р и м е р 5. 1.

Положим g(x) = 1 + x + x3 над GF (2), −1 = 1. Можно проверить, что x7 − 1 = (1 + x)(1 + x + x3)(1 + x2 + x3). Таким образом, n = 7, r = 3, k = 4.

Прямым умножением находим

u(1)(x)g(x) = 1 + x3 + x5 + x6, u(2)(x)g(x) = 1 + x4 + x5,

u(3)(x)g(x) = 1 + x2 + x5,

u(4)(x)g(x) = 1 + x + x2 + x3 + x4 + x5 + x6, u(5)(x)g(x) = x + x5 + x6,

u(6)(x)g(x) = 1 + x2 + x3 + x4, u(7)(x)g(x) = 1 + x + x2 + x5, u(8)(x)g(x) = 1 + x + x4 + x6, u(9)(x)g(x) = x + x3 + x4 + x5, u(10)(x)g(x) = x + x2 + x3 + x6, u(11)(x)g(x) = x2 + x4 + x5 + x6, u(12)(x)g(x) = 1 + x + x3,

u(13)(x)g(x) = x + x2 + x4, u(14)(x)g(x) = x2 + x3 + x5, u(15)(x)g(x) = x3 + x4 + x6, u(16)(x)g(x) = 0.

В процессе кодирования получен циклический код.

Напомним, что при всех сдвигах показатели степеней приводятся по модулю n.

Нетрудно убедиться, что

Назовем орбитой все те векторы кода, которые получаются друг из друга циклическими сдвигами. В приведенном примере 16 векторов кода распадается на 4 орбиты: две орбиты — (5.2.3) и (5.2.4) — по 7 векторов и две по одному вектору. Это u(4)(x)g(x) = 1 + x + x2 + x3 + x4 + x5 + x6 и 0. Орбиты не пересекаются, но одна из другой получаются сложением каждого

вектора одной орбиты с вектором u(4)(x)g(x).

5.3. Проверочная матрица циклического кода

Многочлен g(x) порождает циклический код, т.е. линейное циклическое подпространство (идеал) A V, базисом которого является порождающая матрица (5.2.1). Существует ли много-

член, который таким же образом порождает нулевое подпространство нашего кода, и если существует, то как с его помо-

щью изображается проверочная матрица H?

Согласно теореме 5.1.7 не составляет труда найти такой многочлен h(x), что

Это значит, что

(xn−1) = g(x)h(x). Но в кольце F [x]/(xn−1) имеем xn−1 = 0, а потому

g(x)h(x) = 0.

Это равенство может рассматриваться как аналог равенства (4.3.3), тем более, что слагаемые n − k и k в сумме степеней многочленов g(x) и h(x) такие же, как и размерности ортогональных подпространств, порождаемых матрицами H и G.

В связи с этим многочлен h(x) называется проверочным многочленом кода A. Однако полной аналогии между соотношением "порождающий многочлен g(x) — порождающая матрица G" и соотношением "проверочный многочлен h(x) — проверочная матрица H" нет.

Действительно, пусть f(x)g(x)− произвольный вектор кода

A, и f(x)g(x) = ∑n−1 cixi = c(x). Найдем (в кольце F [x]/(xn−1))

произведение

i=0

Разумеется, hl = 0 для всех l ≥ k.

Кроме того, в подчеркнутой части суммы нижние индексы каждого слагаемого таковы, что эти слагаемые являются как

будто коэффициентами при xn+j. Однако в кольце F [x]/(xn−1) имеет место равенство xn = 1.

Равенство (5.3.7) означает, что aj есть скалярное произведение двух векторов:

aj = (c0, c1, . . . cn−1)(hj, hj−1, . . . , h0, hn−1, hn−2, . . . , hj+1).

В первой скобке — кодовый вектор f(x)g(x) кода A. Вторая скобка содержит коэффициенты многочлена h(x), расположенные в порядке убывания нижних индексов , а не возрастания, как в (5.2.1), и сдвинутые циклически на j + 1 шагов вправо. И это скалярное произведение равно нулю ввиду (5.3.6). Таким

суть кодовые векторы циклического кода A, порожденного многочленом g(x). При i = n − k, n − k + 1, . . . , n − 1 они линейно

независимы, так как в слагаемых xi показатели степеней различны. Поэтому их можно взять в виде базиса подпростран-

ства A, т.е. в виде строк порождающей матрицы G. Расположим правые части этих равенств в порядке возрастания ин-

декса i сверху вниз. Кроме того, как это естественным образом получилось в (5.2.1), каждый вектор располагается в поряд-

ке возрастания показателей степеней x слева направо. Тогда получим

где Ik — единичная (k×k)-матрица, а −R есть (k×(n−k))−матрица, строка которой с номером j = i − n + k + 1 образована коэффициентами остатка −ri(x), i = n −k, n −k + 1, . . . , n −1,

Таким образом, сравнивая матрицы (4.4.4) и (5.4.10), видим: последняя предполагает, что проверочные символы пред-

шествуют информационным, а не наоборот, как это имеет место в (4.4.4).

В таком случае, согласно теореме 4.4.1, каноническая, т.е.

приведённо-ступенчатая, форма проверочной матрицы циклического кода немедленно получается в виде

Здесь In−k есть единичная (n − k) × (n − k)-матрица, RT есть (n−k) ×k-матрица, столбец которой с номером j = i−n+ k + 1 образован коэффициентами остатка ri(x), i = n − k, n − k + 1, . . . , n − 1. В полном соответствии с (5.3.8) в каждой строке многочлен расположен в порядке убывания степеней x.

Формулы (5.4.10) и (5.4.11) свидетельствуют, что первые n − k символов кодового вектора, т.е. коэффициенты при сте-

пенях x0, x, . . . , xn−k−1 выбраны проверочными, а последние k символов — информационными.

П р и м е р 5. 3. Пусть снова

g(x) = 1 + x + x3, n = 7, k = 4, r = n − k = 3.

176 Глава 5. Циклические коды

Базисные векторы-многочлены циклического кода:

1 + x + x3, x + x2 + x4, 1 + x + x2 + x5, 1 + x2 + x6.

Каноническая форма порождающей матрицы:

Построим теперь проверочную матрицу H, пользуясь проверочным многочленом h(x) = (x7 + 1)/g(x) = x4 + x2 + x + 1.

Имеем

Базисные векторы-многочлены подпространства, ортогонального подпространству строк матрицы G :

x6 + x3 + x + 1, x5 + x3 + x2 + x, x4 + x2 + x + 1.

Располагая эти многочлены в порядке убывания показателей степеней x, получим проверочную матрицу

Совпадение очевидно! Читатель без труда проверит справед-

ливость равенства GHT .

Читателю полезно усвоить, что обмен местами матриц I и

R в канонических формах матриц G и H циклического кода не имеет никакого принципиального значения, но является след-

ствием исключительно соглашения. Недаром выше подчеркивается, что все многочлены в матрице G (5.2.1), как и было

условлено, располагаются по возрастающим степеням x, и как в связи с этим получилось, в матрице H (5.3.8), они располагаются по убывающим степеням x.

Однако впервые в тексте читатель познакомился с канонической формой порождающей матрицы именно в виде (4.4.4), а с канонической формой проверочной матрицы именно в виде (4.4.6). Чтобы вернуться к более привычному виду базисных матриц, именно матрицам (4.4.4) и (4.4.6) следует выбирать первые k символов кодового вектора, т.е. коэффициенты при xn−1, xn−2, . . . , xn−k информационными, а последние n−k сим-

волов, т.е. коэффициенты при xn−k−1, xn−k−2, . . . , x0 — проверочными. Читатель легко самостоятельно трансформирует на этот случай выкладки примера 5.3.

5.5.Порождающий многочлен с заданными свойствами

Задача, сформулированная в заглавии, напрашивается сама собой, так как порождающий многочлен выступает главной характеристикой циклического кода. Один из признаков многочлена представлен его корнями в некотором поле. Например, в технической диагностике существенным является требование построить многочлен, который бы не делил ни одного из многочленов из заданного множества. Пользуясь кодовой терминологией, такая задача означает построение кода, который не содержал бы многочленов из заданного множества. Простым ее решением было бы построение такого многочлена, минимальный набор корней которого не содержался бы целиком в множествах корней заданных многочленов. Этот пример приведен только для того, чтобы показать, что построение кода с заданным расстоянием является не единственной задачей теории кодирования, хотя в данном руководстве она является основной.

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

Пусть элементы

суть корни порождающего многочлена g(x) над GF (q). (Положим для простоты, что среди них нет кратных.)

Тогда эти же элементы являются корнями любого многочлена v(x) = v0 + v1x + v2x2 + . . . + vn−1xn−1, принадлежащего

циклическому коду, порождаемому многочленом g(x).

Это следует из того, что, если v(x) = q(x)g(x), то v(αi) = q(αi)g(αi) = 0, i = 1, 2, . . . , ρ.

Иначе говоря, v(αi) = v0 + v1αi + v2αi2 + . . . + vn−1αin−1 = 0,

а это означает, что равно нулю скалярное произведение

(v0, v1, v2, . . . vn−1)(1, αi, αi2, . . . αin−1).

В свою очередь это означает, что, векторы (1, αi, αi2, . . . αin−1)

есть не что иное, как строки проверочной матрицы нашего циклического кода:

Далее, многочлен g(x) по теореме 3.5.5 делится на все минимальные функции mi(x), i = 1, 2, . . . , ρ, своих корней

α1, α2, . . . , αρ GF (qm), m = 1, 2, . . .

Следовательно, g(x) делится на наименьшее общее кратное

M(m1(x), m2(x), . . . , mρ(x)).

З а м е ч а н и е. Так как минимальная функция — неприводимый многочлен, требование делимости на наименьшее об-

щее кратное, а не на произведение, обусловлено только тем, что различные элементы αi имеют одну и ту же минимальную

функцию. Последнее не исключено ввиду теоремы 3.5.12. Зато исключена отличная от единицы кратность корней ввиду оговорки, сделанной по поводу элементов (5.5.12).

Так как αi GF (qm), то deg mi(x) ≤ m.

Отсюда

Но степень порождающего многочлена есть в точности число r проверочных символов порождаемого им кода.

Это означает, что число k информационных символов этого кода удовлетворяет соотношению k ≥ n − ρm.

Остается найти длину n циклического кода с таким порождающим многочленом g(x), что g(αi) = 0, i = 1, 2 . . . , ρ. Согласно теореме 5.1.7, многочлен g(x) делит многочлен xn − 1. Это значит, что все элементы αi, будучи корнями многочлена g(x), являются также корнями многочлена xn−1, т.е. удовлетворяют

уравнению xn − 1 = 0. Таким образом, αin = 1. Отсюда сразу следует, что число n делится на порядок каждого αi, а зна-

чит, и на наименьшее общее кратное порядков корней (5.5.12). Иными словами, верна

Теорема 5.5.1. Длина n циклического кода не может быть меньше наименьшего общего кратного порядков корней порождающего многочлена g(x).

С другой стороны, заметим, что как только длина n′ кода по какой-нибудь причине превысит это значение n, двучлен xn−1 станет принадлежать коду, и его минимальное расстояние будет равным двум.

Так как корнями порождающего многочлена выбраны элементы конечного поля GF (qm), то помня, что порождающий

многочлен g(x) является делителем двучлена xn − 1, следует установить связь между этим двучленом и конечным полем

GF (qm).

Теорема 5.5.2. Такое число m, что многочлен xn − 1 делит многочлен xqm−1 − 1, найдется тогда и только тогда, когда

(q, n) = 1

Согласно теореме 3.5.10 надлежит доказать, что qm −1 делится на n тогда и только тогда, когда (q, n) = 1.

Д о к а з а т е л ь с т в о. Необходимость.

Пусть (q, n) = d > 1. Так как число qm − 1 заведомо не делится ни на один делитель числа qm, то оно не делится и на число d, а значит и подавно не делится на n.

Достаточность. Пусть (q, n) = 1. Тогда по теореме Эйлера

qφ(n) ≡ 1(modn).

Поэтому достаточно взять m = φ(n). Однако, если q не есть первообразный корень по модулю n, то в качестве m берут показатель δ, которому число q принадлежит по модулю n. Как известно (см. утверждение 1.11.4), этот показатель делит φ(n).

180 Глава 5. Циклические коды

В теории циклических кодов это число m принято называть мультипликативным порядком числа q по модулю n.

Если число m есть показатель, которому которому число q

Получается что среди n чисел ri, (i = 1, 2, . . . , n) оказывается не более, чем n − 1 различных. Значит, не менее двух из них совпадают. Пусть ry = rz = r, и y ≥ z. Тогда находим последовательно qy −qz = nty + r −ntz −r, qz(qy−z −1) = (ty −tz)n. Из

(q, n) = 1 следует, что n делит qy−z − 1, и потому m = y − z, что и требовалось.

Длинами n циклических кодов могут быть только делители чисел qm − 1 и, разумеется, само это число. Подобно тому, как в разделе 3.2 поле GF (qm) называется полем разложения

многочлена xqm −x, оно же называется полем разложения многочлена xn − 1.

Если n = qm − 1, то циклический код называется примитивным.

На случай q = 2 в Таблице П.1 представлены канонические разложения чисел 2m − 1, m = 1, 2, . . . , 34.

Из циклического кода можно построить код меньшей длины путем его укорочения. Новый код уже не будет циклическим.

Можно показать, что он будет т.н. квазициклическим кодом в кольце многочленов уже по другому модулю, а не по модулю многочлена xn − 1.

П р и м е р 5. 4.

Пусть корнями порождающего многочлена будут α, α3, α5 GF (24). Элемент α — примитивный. Элементы α3 и α5 имеют порядки 5 и 3 соответственно. Длина кода n = 15.

На основании примера 3.9 в разделе 3.5 элемент α может быть корнем одного из двух примитивных многочленов 4-й сте-

пени над GF (2) : x4 + x + 1, или x4 + x3 + 1 в зависимости от того, по модулю какого из них построено поле GF (2m).

Пусть, для определенности, это будет x4 + x+ 1. Минимальные функции элементов α3 и α5 суть x4+x3+x2+x+1 и x2+x+1.