Ранговые q-циклические и псевдо-q-циклические коды

В теории кодов, исправляющих ошибки в метрике Хэмминга, хорошо известны три класса кодов: циклические коды, укороченные циклические коды и псевдоциклические коды.

Линейным ( n,k )-кодом над расширенным полем F _q N называется k -мерное подпространство пространства F _q ⁿ N .

Линейный ( n,k )-код называется циклическим, если для любого кодового вектора g = = g l i 9 2 ... д П его правый циклический сдвиг c ( g ) = ( g n 9 1 ... 9 n - 2) также является кодовым вектором. В полиномиальном представлении циклические коды являются идеалами кольца F q N [ x ] / ( x n - 1).

Среди кодов, построенных в метрике Хэмминга, циклические коды составляют очень важный класс. Цикличность позволяет уменьшить сложность процедур кодирования и декодирования.

Близкими к ним являются укороченные циклические коды. Они строятся путем укорочения тех подкодов циклического кода, у которых последние m символов являются нулевыми.

Другим близким классом кодов являются псев-доциклические коды. Эти коды являются идеалами кольца F q N [ x ] /f ( x ), где f ( x ) — некоторый многочлен степени n .

Важным является результат, состоящий в том, что класс линейных укороченных циклических кодов совпадает с классом линейных псевдоцикличе-ских кодов [1].

В теории кодов, исправляющих ошибки в ранговой метрике, подобные результаты неизвестны. В этой работе результат, аналогичный результату для кодов в метрике Хэмминга, получен для линейных кодов, основанных на ранговой метрике. Коды с ранговой метрикой нашли применение в пространственно-временном кодирова- нии [2], криптографии [3], сетевом кодировании [4] и т.д.

Пусть F q — конечное базовое поле из q элементов и пусть F _q N — расширение этого поля степени N .

Пусть вектор g = ( 9 i , д 2 , ..., д _п ) G F ^ n .

Ранг вектора g , — обозначаемый Rk( g ), это максимальное число компонент g j , которые линейно независимы над базовым полем F q .

Ранговое расстояние между g 1 ∈ F _q ⁿ N и g 2 ∈ ∈ F _q ⁿ _N равно по определению рангу их разности: d ( g i , g 2 ) = Rk( g i - g 2 ).

q -циклическим сдвигом вектора g = = ( 9 1 , 9 2 , ..., 9 n ) называется вектор следующего вида:

c q ⁽ g ) = ⁽ 9 ^ , 9 q , ••; 9 П - 1 ) .

Другими словами, q -циклический сдвиг — это композиция операций правого циклического сдвига координат вектора и возведения каждой координаты в степень q .

Линейный ( n,k )-код над полем F _q N называется q -циклическим, если q -циклический сдвиг любого кодового вектора g также является кодовым вектором.

q -циклические коды как подкласс кодов в ранговой метрике были введены в работе [5] для n = N . Существуют q -циклические коды с максимальным ранговым расстоянием. Свойство q -цикличности позволяет улучшить характеристики кода, так как уменьшает число вычислений при кодировании и декодировании. Поэтому применение q -циклических кодов вызывает большой интерес.

В этой статье, во-первых, обобщаются конструкции q -циклических кодов для длин n = = sN ; во-вторых, вводится класс укороченных q -циклических кодов; в-третьих, вводится класс псевдо- q -циклических кодов; в-четвертых, показывается, что последние два класса совпадают.

II.    Линеаризованные многочлены

Многочлен вида

n

g ( x ) = ^a i X q , ^a i E F q N ,         (1)

i =0

называется линеаризованным.

Обозначим R n [ x ] множество линеаризованных многочленов с коэффициентами из поля F _q N .

Сложение R n [ x ] определяется как обычное сложение многочленов.

Некоммутативное умножение двух линеаризованных многочленов h(x) E Rn [x] и g(x) E Rn [x] определяется как композиция f (x) = h(x) ® g(x) deef h(f (x)).

С операциями + ,® множество линеаризованных многочленов R n [ x ] становится некоммутативным полиномиальным кольцом без делителей нуля. Нулевой многочлен 0 является нулевым элементом этого кольца. Многочлен x является единичным элементом кольца. Это кольцо является левым и правым Евклидовым кольцом. Все левые и правые идеалы являются главными идеалами. Кольцо R n [ x ] было введено в работах [6--7].

Кольцо Rn [x] является некоммутативным. Однако существуют линеаризованные многочлены f (x), перестановочные со всеми многочленами из Rn [x], то есть f (x) ® r (x) = r (x) ® f (x), V r (x) E R N [ x ].

Множество C[R n [ x ]] всех таких многочленов называется центром. Известно, что центр C[R n [ x ]] состоит из многочленов вида

{f0x + fixqN + ... + fsxqN},s E N, где все коэффициенты fj принадлежат базовому полю Fq.

Центральный многочлен f (x) = fо x + f i xqN + ... + fsxqsN, fs = 0 порождает фактор-кольцо:

L n ( f ( x ))[ x ] d = ^f R N [ x ] /f ( x ) .

Это кольцо является конечным некоммутативным кольцом, состоящим из q ^{N 2 s} линеаризованных многочленов степени не выше q ^{sN 1} с коэффициентами из F _q N . Операции в этом кольце осуществляются по модулю f ( x ). Для h ( x ) ,g ( x ) E L _N ( f ( x ))[ x ], сумма и произведение определены в виде h ( x ) + g ( x ) mod f ( x ), и h ( x ) ® g ( x ) mod f ( x ) = h ( g ( x ))mod f ( x ) соответственно.

Приведем две новые леммы.

Лемма 1. Пусть f (x) = fоx + f 1 xqN + ... + fnxqn E C[RN[x]]

является центральным многочленом, удовлетворяющим условиям f о = 0 ,f n = 0. Тогда существует целое число s , n ^ s ^ q ^{N n} — 1, такое, что двучлен x q — x делится без остатка слева и справа на f ( x ).

Доказательство. Фактор-кольцо R n [ x ] /f ( x ) может быть представлено как конечное множество линеаризованных многочленов вида g о x + g i x q + ... + g nN _ 1 x q " ,g j E F q N . Следовательно, оно содержит q ^{N n} — 1 ненулевых элементов (то есть остаточных классов по модулю двустороннего идеала ( f ( x ))).

Рассмотрим последовательность ненулевых остаточных классов

x ^{[ iN ]} + ( f ( x )) , i = 0 , 1 , ..., q ^N 2 ⁿ — 1 .

Очевидно, что существуют целые

0 < a < b < qN2 n — 1, такие, что xq = xq mod (f (x)). Обозначим s = b — a. Тогда xqN = xq(b a)N = x mod (f (x)). Это означает, что xq — x делится слева и справа без остатка на f (x). Ясно, что n < s < qN n — 1.

Пример 1. Пусть q = 2 и f (x) = xq 4 N + xq2 N + xqN + x.

Тогда двучлен x q — x делится без остатка на f ( x ):

x q 7 N — x = h ( x ) ® f ( x ) =

= ( x q  + x q + x ) ® ( x q  + x q  + x q + x ) .

Не существует двучлена x q — x с s <  7 N , который делится без остатка на f ( x )= x q + x q + x q + x .

Лемма 2. Пусть f (x) = fоx + f1 xqN + ... + fsxqsN E C[RN[x]]

центральный многочлен. Предположим, что f (x) = f1( x) ® f2( x), где f1( x), f2( x) E R n [x ]. Тогда многочлены fi(x), f2(x) перестановочны, то есть f (x)= f 1(x) ® f2(x)= f2(x) ® f 1(x) .    (2)

Доказательство. Рассмотрим разность

A( x ) = f 1 ( x ) ®f 2 ( x ) — f 2 ( x ) ®f 1 ( x ) = f ( x ) — f 2 ( x ) ®f 1 ( x ) .

Умножим обе части справа на f ₂ ( x ) и получим

А( x ) ® f 2 ( x ) =

= f ( x ) ® f 2 ( x ) — f 2 ( x ) ® f 1 ( x ) ® f 2 ( x ) =

= f ( x ) ® f 2 ( x ) — f 2 ( x ) ® f ( x ) .

Верно равенство f ₂ ( x ) ® f ( x ) = f ( x ) ® f ₂ ( x ), так как f ( x )- центральный многочлен. Следовательно,

A( x ) ® f 2 ( x ) = f ( x ) ® f 2 ( x ) — f ( x ) ® f 2 ( x ) = 0 .

Отсюда следует, что А( x)    =    0 и f1( x) 0 f2( x) = f2( x) ® f1( x).

III.    Идеалы как коды

Рассмотрим центральный многочлен x ^{q sN} - x и соответствующее фактор-кольцо:

L _N ( x q    — x )[ x ] def R _N [ x ] / ( x q    — x ) .

Кольцо Ln (xq — x)[x] является конечным некоммутативным кольцом. Оно состоит из всех многочленов вида sN a (x) = a о x + a 1 xq + ... + asN - 1 xq

,a j ∈ F q N .

Мы свяжем с многочленом a ( x ) вектор a = ( a о ,a 1 ,...,a sN - 1 ) € F sN длины sN .

Подкольцо I[ x ] c L n ( x q —x )[ x ] называется левым идеалом, если оно замкнуто относительно левого умножения на многочлены фактор-кольца, то есть

L _N ( x q — x )[ x ] 0 I[ x ] (mod x q — x )= I[ x ] .

Левые (и правые) идеалы являются главными и могут быть описаны с помощью порождающих многочленов G ( x ), которые являются множителями в разложении многочлена x ^{q sN} -x .

Предположим, что x q —x = H ( x ) 0 G ( x ), где G ( x ) — линеаризованный полином степени, например q ^sN - k . Тогда левый идеал I[ x ], порожденный G ( x ), состоит из всех многочленов вида g ( x ) = i ( x ) 0 G ( x ) (mod x q —x ). При систематическом кодировании многочлен i ( x ) есть линеаризованный многочлен степени не выше q ^{k - 1} . Однако произведение i ( x ) 0 G ( x ) (mod x q —x ) есть кодовый многочлен, даже если степень i ( x ) больше или равна q ^k .

Обозначим M линейный ( sN,k )-код с векторами в F ^s _q ^N и обозначим M ( x ) его полиномиальное представление.

Лемма 3. Линейный (sN,k)-код M является q-циклическим, если и только если M(x) есть левый идеал фактор-кольца Ln (xq —x)[x], порожденного линеаризованным многочленом G(x), таким, что xq —x = H(x) 0 G(x) и deg( G (x)) = qsN-k.

Доказательство. Для s = 1 доказательство приведено в работе [7]. Приведем доказательство для s >  1. Пусть ( sN,k )-код M ( x ) является левым идеалом L n ( x q —x )[ x ], порожденным многочленом G ( x ). Тогда кодовый многочлен g ( x ) может быть представлен в виде

s

g ( x )= i ( x ) 0 G ( x )= g о x + g 1 x q + ... + g sN - 1 x q

- 1

также кодовый многочлен. С другой стороны, он совпадает с q-циклическим сдвигом g (x), так как xq 0g (x) (mod xq —x) =

= x q 0 ( g о x + g 1 x q + ... + g sN - 1 x q    ) (mod x q —x ) =

= g Q x q + g Q x q + ... + g s _N - 1 x q    (mod x q —x ) =

= g qN - 1 ^{x +} g q ^x q ⁺ ... ⁺ g sN - 2 ^x q N 1 •

Наоборот, пусть линейный ( sN,k )-код M ( x ) в полиномиальном представлении является q -циклическим кодом. Пусть

g ( x ) = g 0 x + g 1 x q + ... + g sN - 1 x q sN 1 € M ( x )

есть кодовый многочлен. Вычислим многочлен x q 0 g ( x ):

x q 0 g ( x ) mod x q — x = g ( x ) q (mod x q — x ) = = g q x q + g* q x ^q + ... + g sN - 1 x q    (mod x q — x ) =

= g qN - 1 ^{x +} g q ^x q ⁺ g ^{q x} q 2 ⁺ ... ⁺ g qN - 2 ^x q ^sN 1 .

Видно, что полученный многочлен есть q -циклический сдвиг g ( x ). Следовательно, как и предполагалось, x q 0 g ( x ) (mod x q — x ) € M ( x ) и x q 0 M ( x ) (mod x q^ N — x ) C M ( x ). Отсюда по индукции следует, что для любого многочлена с ( x ) € L n ( x q —x )[ x ] имеем c ( x ) 0 M ( x ) (mod x q —x ) C M ( x ), или

L _N ( x q — x )[ x ] 0M ( x ) (mod x q —x ) = M ( x ) .

Значит,   M ( x )  — левый идеал кольца

L N ( x ^{q sN} —x )[ x ].

Замечание. Из леммы 3 следует, что для данного q длины q -циклических кодов кратны расширению степени N . Однако поле может быть получено с помощью различных расширений. Например, поле F 256 может быть представлено как F ₂ 6 с q = 2 и N = 6 или как F 4 3 с q = 4 и N = 3, или как F 8 2 с q = 8 и N = 2. Следовательно, длины q -циклических кодов могут быть кратны 6 или 3, или 2. Пусть в общем случае q = p r , где p — простое число. Видим, что поле F _q N может быть представлено как поле F q n 1 с q 1 = p n , N 1 = ( rN ) /n , где n — множитель числа rN . Длины q -циклических кодов кратны N 1 для всех множителей n . Заметим также, что все q -циклические коды являются кодами над полем F _q N .

Новый q -циклический код может быть описан в терминах порождающего многочлена или альтернативно в терминах проверочного многочлена. Пусть x q s —x = H ( x ) 0 G ( x ), где

G ( x )  = G 0 x + G 1 x ^q + ... + G sN - k x q^ N k^k ,

H ( x )  = H 0 x + H 1 x ^q + ... + H _k x q¹ " .

для некоторого i ( x ). Ясно, что многочлен x q 0 g ( x ) = ( x q 0 i ( x )) 0 G ( x ) (mod x q —x ) есть

Многочлен G(x) называется порождающим многочленом, потому что любой кодовый многочлен имеет вид g (x) = g о x + g 1 xq + ... + gsN -1 xqsN 1 =

= i (x) ® G (x) mod xq — x для некоторого i(x). Пусть i(x) = ^k-) iixq , где ii E FqN, l = 0,...,k — 1, — информационные символы. Тогда соответствующий кодовый многочлен есть k-1           k-1 sN-k

g ( x ) = £ i i G q ( x ) = £ ii £ GV ^{+ 1}. l —0              l —0 j —0

Следовательно, кодовый вектор может быть представлен в виде g = (gо g 1   ... gsN-1) = (i0  i 1   ... ik-1) G, где

/ G0 G1 ... GsNkk 0    ...0

0 GO ... GN-k- 1 GsNkk ...

G =      . .            .           ..

.        . ...             .                     .          ....

_n kk 1        kk 1         kk 1

\ 0  0 ...  G o       G o ... G sNkk)

— порождающая матрица ( sN,k )-кода M в векторном представлении.

Многочлен H (x) называется проверочным многочленом, потому что для любого кодового многочлена g (x) условие H (x) ® g (x) (mod xq —x) = 0 удовлетворяется. Отсюда следует, что проверочная матрица (sN,k)-кода M в векторном представлении имеет вид h0

h ^O 1

0 ...        0

h ^O ₀ ...        0

H =

h k- 1 ...

h q k

.         ...              .

sN-k- 1

0    ... h k

. ...              .

sN -k- 1

......h 0

def q ^{k - i} где h i = H i .

Предположим, что k>N. Тогда мы можем вычеркнуть из матрицы (3) последние N строк, получив (k—N) x sN матрицу со нулевыми последними N столбцами. Удаление этих столбцов дает нам новую (k — N) x (s — 1) N порождающую матрицу. Эта матрица определяет N -укороченный q-циклический код размерности k — N и длины (s — 1)N. Подобным образом, если k > mN, то стирание последних mN строк и последних mN столбцов матрицы (3) дает mN -укороченный q-циклический код размерности k — mN и длины (s — m)N. Заметим, что укороченные коды име- ют то же самое минимальное ранговое расстояние, что и исходный код M.

Теперь рассмотрим обобщенное фактор-кольцо Ln(f (x))[x] = Rn[x]/ f (x), где f (x) — центральный многочлен степени qnN, то есть f (x) = f0x + f 1 xqN + ... + fnxq^N E C[Rn[x]], (5)

при f n = 0.

Пусть G ( x ) — правый делитель многочлена f ( x ), то есть f ( x ) = H ( x ) ® G ( x ).

Определение. Идеал M ( x ) кольца L n ( f ( x ))[ x ], порожденного всеми левыми множителями правого фактора G ( x ) центрального многочлена f ( x ), называется псевдо- q -циклическим кодом в полиномиальном представлении.

Пусть deg( G ( x )) = q ^{nN - k} . Из определения следует, что псевдо- q -циклический код M в векторном представлении есть ( nN,k )-код. В соответствии с леммой 3, если f ( x ) = x q — x , то любой псевдо- q -циклический код есть q -циклический.

IV.    Основные результаты

Основные результаты — это следующие две теоремы.

Теорема 1. Каждый псевдо- q -циклический код есть укороченный q -циклический код.

Доказательство. Пусть

L n ( f ( x ))[ x ] = R N [ x ] /f ( x )

— фактор-кольцо, где f ( x ) представлено в (5). Пусть G ( x ) — правый делитель f ( x ), порождающий псевдо- q -циклический код T . В соответствии с леммой 1 существует двучлен x q — x , где s ^ n , который делится без остатка на f ( x ) и, следовательно, на G ( x ). Это означает, что G ( x ) порождает q -циклический код длины sN . Если s = n , тогда этот код совпадает с псевдо- q -циклическим кодом T , порождаемым G ( x ). Если s > n , мы можем иметь только кодовые векторы, содержащие все нулевые последние ( s — n ) N компонент. Удаление этих компонент дает псевдо- q -циклический код T . Следовательно, код T является mN -укороченным q -циклическим кодом, у которого m = s — n .

Теорема 2. Каждый mN -укороченный q -циклический код размерности ( k — mN ) и длины ( s — m ) N есть псевдо- q -циклический код.

Доказательство. Предположим, что многочлен G ( x ) порождает q -циклический ( sN,k )-код M при k > mN . Представим центральный многочлен x ^{q sN} — x как произведение центральных многочленов:

x ^{q N} — x = f 1 ( x ) ® f 2 ( x ) ® ... ® f r ( x ) .

Множители могут быть записаны в любом порядке.

Многочлен G ( x ) есть правый делитель произведения f ( x ) = f j 1 ( x ) ®... ® f j r ( x ) нескольких многочленов f j ( x ). Выберем произведение со степенью q ^{( s - m} ) ^N , например: f ( x )= x q ⁽ ) + ... + f ₀ x . Тогда можно получить mN -укороченный код длины ( s — m ) N . Такой код порождается G ( x ) и является идеалом фактор-кольца, порождаемого с помощью f ( x ). Следовательно, укороченный код есть псевдо- q -циклический код.

Пример 2. Пусть q = 2, N = 3. Рассмотрим кольцо линеаризованных многочленов с ко- эффициентами из FqN = F8. Пусть а — примитивный элемент поля F8 , удовлетворяющий уравнению а3 + а + 1 = 0. Разложим на множители двучлен xq — x таким образом: xq — x = H 1 ® G 1, где Hi(x) = xq + аx,G 1 (x) = xq + а4xq + а6x.

В свою очередь разложим на множители двучлен x ^[12] - x следующим образом:

_x [12] _{— x} =

= ( x q 3 — x ) ® ( x q ³ — x ) ® ( x q ³ — x ) ® ( x q ³ — x ) =

= H 1 ® G 1 ® H 1 ® G 1 ® H 1 ® G 1 ® H 1 ® G 1 =

= H 1 ® G 1 ® H 1 ® G 1 ® H 1 ® H 1 ® G 1 ® G 1 =

= H ® G, где

H = H 1 ® G 1 ® H 1 ® G 1 ® H 1 ® H 1 ,

G = G ₁ ® G ₁ = x q + аx ^q + x q + а ⁵ x q + а ⁵ x.

Построим q -циклический код длины 4 N = 12, порожденный многочленом G ( x ). Порождающая матрица кода такова (см. (3)):

G =

/

V

α 5	α 5	1	α	1	0	0	0	0	0	0	0	\
0	α 3	α 3	1	α 2	1	0	0	0	0	0	0
0	0	α 6	α 6	1	α 4	1	0	0	0	0	0
0	0	0	α 5	α 5	1	α	1	0	0	0	0
0	0	0	0	α 3	α 3	1	α 2	1	0	0	0
0	0	0	0	0	α 6	α 6	1	α 4	1	0	0
0	0	0	0	0	0	α 5	α 5	1	α	1	0
0	0	0	0	0	0	0	α 3	α 3	1	α 2	1	/

Удаление последних N = 3 строк и последних N = 3 столбцов в матрице G дает порождающую матрицу G ^-укороченного q-циклического кода длины 3N = 9:

G 1 =

α ⁵

0 0

а5  1  а  1   0  0  0  0\ а3 а3  1 а2  10  00

0 а ⁶ а ⁶ 1 а ⁴ 10 0

0  0 а5 а5 1 а10

0   0   0  а3 а3 1 а2 1/

Этот код является также псевдо-q-циклическим кодом длины 3 N = 9, порождаемым тем же самым многочленом G(x) в фактор-кольце L№(f 1(x))[x] = R№[x]/f 1(x), где f1(x)  =  (xq3 —x) ® (xq3 —x) ® (xq3 —x) =

=   x ^[9] + x ^[6] + x q ³ + x.

В свою очередь удаление последних трех строк и последних трех столбцов в матрице G 1 дает порождающую матрицу G 2 для 6-укороченного q -циклического кода длины 6:

/ а ⁵   а ⁵    1    а   1   0

0    а ³   а ³    1   а ²   1

Этот код является также псевдо-q-циклическим кодом длины 2 N = 6, порождаемым тем же самым многочленом G(x) в фактор-кольце L№(f2(x))[x] = R№[x]/f2(x), где f2(x) = (xq —x) ® (xq —x) = = x[6] + x.

Легко видеть, что этот код есть q -циклический код длины 6.

В этом примере мы проанализировали sN -укороченные q -циклические коды для q = 2 , N = 3 , s = 4 , m = 1 , 2. Однако если длина укорочения не кратна N , то теорема 2 не верна. Рассмотрим в примере 28-укороченный q -циклический код длины 5 и размерности 1. Он описывается порождающей матрицей

G 3 = ( а ⁵ а ⁵ 1 а 1 ) .

Однако этот код не является ни q -циклическим кодом длины 5, ни псевдо- q -циклическим кодом.

V.    Выводы

• •    Обобщено понятие q -циклических кодов и введены два новых семейства кодов, а именно, укороченные q -циклические коды и псевдо- q -циклические коды.

• •    Доказано, что класс псевдо- q -циклических кодов совпадает с классом укороченных q -циклических кодов, если число позиций укорочения кратно степени расширения основного поля. Для других случаев проблема остается открытой.

• •    Построены три класса линейных кодов над полем F _q N :

• 1.    q -циклические ( sN,k )-коды длины sN и размерности k ;

• 2.    mN -укороченные q -циклические

• 3.    псевдо- q -циклические

(( s — m ) N,k — mN )-коды;

(( s — m ) N,k — mN )-коды.

• •    Доказано, что mN -укороченные q -циклические коды эквивалентны псевдо- q -циклическим кодам.

• •    Открытой проблемой остается описание M -укороченных q -циклических кодов, если M не является множителем при N .

Работа частично финансировалась в рамках программы РНПВШ, проект 2931.