ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 55

2019

Вып. 3

УДК 621.391.15

Л. Ли, Ш. Чжу, Л. Лю, С. Кай

НЕКОТОРЫЕ q-ИЧНЫЕ ЦИКЛИЧЕСКИЕ КОДЫ

ПО ЯВНЫМ МОНОМАМ НАД_qm¹

Циклические коды как подкласс линейных кодов имеют практически значи-

мые применения в системах связи, бытовой электронике и системах хранения

информации благодаря наличию эффективных алгоритмов их кодирования и

декодирования. Целью настоящей статьи является построение некоторых цик-

лических кодов с помощью подхода, основанного на последовательностях. Точ-

нее говоря, найдены размерность и порождающие многочлены для трех клас-

сов q-ичных циклических кодов, задаваемых некоторыми последовательностя-

ми с явными многочленами над Fqm. Также обсуждается минимальное расстоя-

ние таких циклических кодов. Некоторые из этих классов оптимальны согласно

таблицам кодов. Кроме того, третий класс циклических кодов дает некоторые

ответы на открытую проблему 3, поставленную Дином и Чжоу в [1].

Ключевые слова: циклические коды, последовательности, размерность кода, по-

рождающий многочлен.

DOI: 10.1134/S0555292319030057

§ 1. Введение

Пусть F_q - конечное поле с q = p^m элементами, где p - простое, а m ≥ 1. Линей-

ный [n, k, d]-код над конечным полем F_q называется циклическим, если для любого

кодового слова (c₀, c₁, . . . , cn-1) ∈ C также (cn-1, c₀, . . . , cn-2) ∈ C. Хорошо извест-

но, что каждый циклический код длины n над F_q можно рассматривать как идеал

кольца главных идеалов F_q[x]/(xⁿ - 1). Пусть C = (g(x)) - циклический код над F_q

длины n, где g(x) - нормированный многочлен наименьшей степени в C. Тогда g(x)

xⁿ - 1

называется порождающим многочленом кода C, а h(x) =

∈ F_q[x] - провероч-

g(x)

ным многочленом кода C. Далее, двойственный к C код определяется как

C^⊥ = {x ∈ F^nq : x · y = 0, ∀y ∈ C},

где через x · y обозначено евклидово скалярное произведение векторов x и y. Тогда

C^⊥ = (h(x)^∗), где h(x)^∗ = h(0)-1xdeg(h(x))h(x-1) - взаимный к h(x) многочлен.

Линейный [n, k, d]-код над F_q называется оптимальным, если его параметры ле-

жат на какой-либо границе для линейных кодов. Линейный [n, k, d]-код над F_q назы-

вается почти оптимальным, если оптимален некоторый линейный код с параметрами

[n, k, d + 1]. В настоящей статье мы будем говорить, что линейный код с парамет-

рами [n, k, d] оптимален или почти оптимален, если этот код или соответствующий

код с параметрами [n, k, d + 1] является наилучшим известным линейным кодом

¹ Работа выполнена при частичной финансовой поддержке Национального фонда естественных

наук Китая (номера проектов 61772168, 61572168 и 11871187).

в соответствии с таблицами [2] (или лежит на какой-либо границе для линейных

кодов).

В общем случае корректирующая способность циклических кодов может быть

не столь хороша, как для других линейных кодов. Однако циклические коды имеют

важные применения в системах связи, бытовой электронике и системах хранения

информации благодаря наличию эффективных алгоритмов их кодирования и де-

кодирования [3-5]. Поэтому многие исследователи посвящали десятилетия своего

труда изучению структуры циклических кодов [6-17]. Имеется несколько подходов

к построению всех циклических кодов над конечными полями, а именно порож-

дающие матрицы, порождающие многочлены и порождающие идемпотенты. В по-

следнее десятилетие изучался новый метод построения циклических кодов над F_q

длины n, основанный на порождающем многочлене

xⁿ - 1

(1)

НОД(Sⁿ(x), xⁿ - 1)

где

∑

Sⁿ(x) =

s_ixⁱ ∈ F_q[x],

i=0

а s^∞ = (s_i)∞i=0 - последовательность периода n над F_q. Обозначим через C_s цик-

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

циклический код C_s кодом, определенным последовательностью s^∞, а последова-

тельность s^∞ - определяющей последовательностью для циклического кода C_s.

Очевидно, что порождающий многочлен кода C_s, определенного последователь-

ностью s^∞, является минимальным многочленом периодической последовательно-

сти s^∞, т.е. минимальный многочлен последовательности s^∞ можно использовать

как порождающий многочлен циклического кода C_s. В последнее время активно

изучалась конструкция циклических кодов, основанная на последовательностях над

конечными полями [1,18-21]. В [1,18] с помощью этого подхода были построены неко-

торые циклические коды, а также сформулированы некоторые открытые проблемы.

В дальнейшем многие первоначальные результаты о циклических кодах, получае-

мых конструкцией, основанной на последовательностях, были улучшены, и были

решены некоторые из открытых проблем [20, 21]. В [19] был дан обзор продвиже-

ний в этом направлении за последнее десятилетие, а также были поставлены новые

открытые проблемы. В настоящей статье мы продолжаем это направление иссле-

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

следовательностями с явными многочленами над F_qm . Мы также рассматриваем

некоторые из этих открытых проблем.

Статья имеет следующую структуру. В § 2 приводятся некоторые основные обо-

значения и результаты, относящиеся к q-циклотомическим смежным классам и по-

следовательностям, которые в последующем будут часто использоваться для до-

казательства основных результатов. Размерности и порождающие многочлены для

трех классов циклических кодов, определяемых некоторыми последовательностями

с явными многочленами, описываются в § 3. Минимальное расстояние таких цик-

лических кодов также обсуждается в § 3. В частности, построены некоторые опти-

мальные или почти оптимальные циклические коды. Заключение дано в § 4.

§2. Предварительные сведения

Приведем некоторые основные обозначения и результаты, относящиеся к q-цик-

лотомическим смежным классам по модулю n и последовательностям, которые в

дальнейщем будут часто использоваться для доказательства наших основных ре-

зультатов.

Пусть n = q^m - 1 и Z_n = {0, 1, 2, . . . , n - 1}. Для любого целого числа s, 0 ≤ s ≤

≤ n-1, определим q-циклотомический смежный класс по модулю n, содержащий s,

как

C_s = {s, qs, . . ., qns-¹s} ⊂ Z_n,

где n_s - наименьшее положительное целое, такое что qnss ≡ s (mod n), называемое

размером смежного класса C_s. Наименьшее целое число, содержащееся в C_s, назы-

вается лидером смежного класса C_s. Обозначим множество всех лидеров смежных⋃

классов через Γ, тогда Z_n =

C_i. Пусть α - примитивный корень степени n из

i∈Γ

∏

единицы в некотором расширении поля F_q. Тогда m_αs(x) =

(x - α^j ) - неприво-

j∈Cs

димый многочлен степени n_s над F_q, являющийся делителем многочлена xⁿ -1. При∏

этом xⁿ - 1 = m_αi(x) является разложением xⁿ - 1 на неприводимые множите-

i∈Γ

ли над F_q. Следующие леммы весьма важны для определения размеров некоторых

q-циклотомических смежных классов.

Лемма 1. Для любого целого s, 1 ≤ s ≤ qm -2, такого что НОД(s,qm -1) = 2

или 3, размер q-циклотомического смежного класса C_s равен m.

Доказательство. Для случая НОД(s,q^m-1) = 2 доказательство дано в [22].

Для второго случая НОД(s, q^m - 1) = 3 доказательство полностью аналогично и

поэтому опускается. ▴

Лемма 2 [23]. q-циклотомический смежный класс по модулю qm -1 размера ℓ

существует тогда и только тогда, когда ℓ делит m.

Пусть s^∞ = (s_i)∞i=0 - последовательность периода L над F_q, тогда найдется по-

ложительное целое число ℓ, такое что

-c₀s_i = c₁si-1 + c₂si-2 + . . . + c_ℓs_i-ℓ, i ≥ ℓ,

где c₀ = 1, c₁, . . . , c_ℓ ∈ F_q. Многочлен c(x) = 1 + c₁x + . . . + c_ℓx^ℓ называется характе-

ристическим многочленом последовательности s^∞. При этом многочлен M_s(x) на-

зывается минимальным многочленом последовательности s^∞, если M_s(x) - харак-

теристический многочлен наименьшей степени. Степень минимального многочле-

на M_s(x) называется линейной сложностью последовательности s^∞ и обозначается

через L_s. Более того, известно, что любой характеристический многочлен должен

делиться на минимальный многочлен. Для любой периодической последовательно-

сти s^∞ над F_q ее линейную сложность и минимальный многочлен описывает следу-

ющая

Лемма 3 [24]. Пусть s^∞ - последовательность периода L над F_q. Положим

∑

S_L(x) =

s_ixⁱ ∈ F_q[x].

i=0

Тогда минимальный многочлен M_s(x) последовательности s^∞ имеет вид

x^L - 1

(2)

НОД(S^L(x), x^L - 1)

а ее линейная сложность L_s равна L - deg(НОД(x^L - 1, S^L(x))).

Следующая лемма дает другой способ нахождения линейной сложности и ми-

нимального многочлена последовательности s^∞ с периодом q^m - 1, который очень

важен для доказательства наших основных результатов.

Лемма 4 [24]. Пусть s^∞ - последовательность с периодом q^m-1 над F_q, име-

ющая единственное разложение вида

∑

s_t =

c_iα^it для всех t ≥ 0,

i=0

где c_i ∈ F_qm , а α - образующая группы F^∗qm . Пусть I = {i : ci = 0}; тогда мини-

мальный многочлен последовательности s^∞ равен

∏

M_s(x) =

(1 - αⁱx),

i∈I

а ее линейная сложность равна L_s = |I|.

§3. Циклические коды по некоторым последовательностям над_qm

В этом параграфе будем рассматривать только специальный тип последователь-

ностей вида

s_t = Tr(f(1 + α^t)),

(3)

где f(x) - некоторый явный многочлен над F_qm , Tr(x) - функция следа из F_qm в F_q,

а α - примитивный элемент поля F_qm. Код C_s, определяемый одной из последова-

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

Разумеется, из различных многочленов можно получить огромное количество

различных циклических кодов. Цель настоящего параграфа - построить несколько

классов циклических кодов по некоторым последовательностям с явными многочле-

нами над F_q.

3.1. Циклические коды по моному f(x) = xqℓ+2. В этом пункте рассматривается

код C_s, определяемый мономом f(x) = xqℓ+2 над F_qm , где m = 2ℓ. Для этого сперва

потребуется доказать несколько лемм.

Лемма 5. Пусть m четно, m = 2ℓ. Пусть s^∞ - последовательность вида (3),

где f(x) = xqℓ +2. Пусть q = 2; тогда линейная сложность L_s последовательно-

сти s^∞ равна 2m + N_p(3)m + N_p(4)ℓ + N_p(m), а ее минимальный многочлен M_s(x)

имеет вид

⎧

⎨

m_α-1(x)m_α-2(x)mα-(qℓ₊₂₎ (x),

p = 2,

M_s(x) =

(x - 1)Np(m)m_α-2 (x)mα-(qℓ₊₁₎ (x)mα-(qℓ₊₂₎ (x),

p = 3,

⎩

(x - 1)Np(m)m_α-1 (x)m_α-2 (x)mα-(qℓ₊₁₎ (x)mα-(qℓ₊₂₎ (x),

p > 3,

где N_p(∗) = 0, если ∗ ≡ 0 (mod p), и N_p(∗) = 1 в противном случае.

Доказательство. Если q = 2, то из (3) получаем

(

)

(

s_t = Tr(f(1 + α^t)) = Tr

(1 + α^t)qℓ +2

= Tr

(α^t)qℓ +2 + 2(α^t)qℓ +1 + (α^t)qℓ +

)

∑

+ (α^t)² + 2(α^t) + 1

= (α^t)(qℓ+2)qj + 2

(α^t)(qℓ +1)qj +

(α^t)(qℓ)qj +

j=0

∑

(α^t)2qj + 2

(α^t)qj + Tr(1) =

(α^t)(qℓ +2)qj + 2

(α^t)(qℓ +1)qj +

j=0

∑

+ (α^t)2qj + 3 (α^t)qj + Tr(1).

j=0

Заметим, что (q^ℓ + 1) | (q^m - 1), поскольку m = 2ℓ. Из леммы 2 легко получить, что

размер q-циклотомического смежного класса C_qℓ₊₁ равен ℓ. Имеем

НОД(q^ℓ + 2, q^m - 1) = НОД(q^ℓ + 2, (q^ℓ + 1)(q^ℓ - 1)) = НОД(q^ℓ + 2, (q^ℓ - 1)) =

= НОД(q^ℓ - 1 + 3, (q^ℓ - 1)) ≤ 3,

так как m = 2ℓ и НОД(q^ℓ + 2, (q^ℓ + 1)) = 1. Тогда из леммы 1 получаем |C_qℓ₊₂| = m.

Очевидно, что C₁, C₂, C_qℓ₊₁ и C_qℓ₊₂ попарно различны. Поэтому s_t можно упростить

следующим образом:

∑

s_t =

(α^t)(qℓ +2)qj + 4

(α^t)(qℓ +1)qj +

(α^t)2qj + 3

(α^t)qj + Tr(1).

j=0

Более того, нетрудно проверить, что N_p(m) = N_p(4) = 0, если p = 2, N_p(3) = 0

и N_p(4) = 1, если p = 3, и N_p(3) = N_p(4) = 1, если p > 3. Требуемые результа-

ты о линейной сложности L_s и минимальном многочлене M_s(x) теперь следуют из

леммы 4. ▴

Лемма 6. Если q = 2, то линейная сложность L_s последовательности s^∞ из

леммы 5 равна m, а ее минимальный многочлен M_s(x) имеет вид

M_s(x) = mα-(2ℓ-1+1) (x).

Доказательство. Если q = 2, то из (3) получаем

(

)

(

)

s_t = Tr

(1 + α^t)2ℓ+2

= Tr

(α^t)2ℓ +2 + 2(α^t)2ℓ+1 + (α^t)2ℓ + (α^t)² + 2(α^t) + 1

(

)

(

)

= Tr

(α^t)2ℓ+2

= Tr

(α^t)2ℓ-1+1

Заметим, что

⎧

⎨

2ℓ

1, если

нечетно,

НОД(ℓ - 1, 2ℓ)

НОД(2ℓ-1 + 1, 22ℓ - 1) =

2ℓ

^⎩3, если

четно.

НОД(ℓ - 1, 2ℓ)

Таким образом,

^{1, если ℓ нечетно,

НОД(2ℓ-1 + 1, 22ℓ - 1) =

3, если ℓ четно.

По лемме 1 получаем, что размер смежного класса C₂ℓ-1₊₁ равен m. Требуемые

результаты о линейной сложности L_s и минимальном многочлене M_s(x) теперь сле-

дуют из леммы 4. ▴

Итак, параметры и порождающий многочлен циклического кода C_s, определяе-

мого последовательностью s^∞, описывает следующая

Теорема 1. Пусть C_s - циклический код, определяемый последовательностью

s^∞ из леммы 5. Тогда справедливы следующие утверждения:

(1) При q = 2 код C_s имеет параметры [n, n - 2m - N_p(3)m - N_p(4)ℓ - N_p(m), d] и

порождающий многочлен M_s(x), описанный в лемме 5, где

^{3 ≤ d ≤ 6, p = 2 или 3,

4 ≤ d ≤ 8, p > 3.

(2) При q = 2 код C_s имеет параметры [n, n - m, d] и порождающий многочлен

M_s(x), описанный в лемме 6, где

^{2, если ℓ четно,

3, если ℓ нечетно.

Доказательство. (1) Очевидно, требуется лишь доказать границы на мини-

мальное расстояние Хэмминга кода C_s. Заметим, что коды, порождаемые много-

членом M_s(x) и взаимным к нему многочленом, имеют одинаковое распределение

весов. Легко видеть, что многочлен, взаимный к M_s(x), имеет корни α и α², когда

q = 2 и p = 2. В этом случае d ≥ 3 согласно границе БЧХ. Аналогично получаем

d ≥ 3, когда p = 3, и d ≥ 4, когда p = 2. Теперь оценим минимальное расстояние

сверху, используя границу Хэмминга и размерность этих кодов.

(2) При q = 2 пусть C^∗s - циклический код, порождаемый многочленом, взаим-

ным к M_s(x). Ясно, что минимальное расстояние d кода C^∗s не может быть равно 1.

Из границы Хэмминга и размерности кода получаем, что d ≤ 4. Из леммы 5 рабо-

ты [25] известно, что минимальное расстояние d кода C^∗s не может быть равно 4.

Таким образом, 2 ≤ d ≤ 3. Если ℓ четно, то НОД(2ℓ-1 + 1, 22ℓ - 1) = 3. Положим

ℓ2ℓ - 1

D =

. Далее, легко видеть, что mα2ℓ-1+1 (x) | (x^D - 1), поскольку все корни

многочлена mα2ℓ-1+1(x) являются корнями многочлена x^D -1. Таким образом, d = 2.

В противном случае легко видеть, что кодовых слов веса Хэмминга 2 не существует,

если НОД(2ℓ-1 + 1, 22ℓ - 1) = 1. Таким образом, d = 3, если ℓ нечетно. ▴

Замечание 1. Следует отметить, что подкласс двоичных циклических кодов C_s,

построенных по моному f(x) = x2ℓ+2 над F₂m, оптимален, когда ℓ нечетно, и почти

оптимален, когда ℓ четно, где m = 2ℓ. Как правило, двойственный код циклическо-

го кода C_s также оптимален, когда ℓ нечетно, что показано в следующей таблице

(q = 2):

ℓ

Код C_s

Двойственный код Оптимальность / почти оптимальность

[3, 1, 3]

[3, 2, 2]

Оба оптимальны (МДР)

[15, 11, 2]

[15, 4, 6]

C_s почти оптимален

[63, 57, 3]

[63, 6, 32]

Оба оптимальны

[255, 247, 2]

[255, 8, 120]

C_s почти оптимален

[1023, 1013, 3]

[1023, 10, 512]

Оба оптимальны

[4095, 4083, 2]

[4095, 12, 2016]

C_s почти оптимален

Пример 1. Пусть (ℓ,m,q) = (1,2,4), ω - примитивный элемент поля F₄, и пусть

F₄2 = F₄[α], где α² + α + ω = 0. Тогда порождающий многочлен кода C_s имеет вид

M_s(x) = x⁶ + ω²x⁵ + ω²x⁴ + x³ + x² + ωx + 1,

а C_s является четверичным [15,9,5]-кодом. Его двойственный код - четверичный

циклический [15, 6, 8]-код. Оба кода почти оптимальны.

Пример 2. Пусть (ℓ,m,q) = (1,2,8), ω - примитивный элемент поля F₈, и пусть

F₈2 = F₈[α], где α² + ωα + ω = 0. Тогда порождающий многочлен кода C_s имеет вид

M_s(x) = x⁶ + w⁶x⁵ + w⁶x⁴ + w⁴x³ + w⁴x² + w²x + w,

а C_s является циклическим [63,57,3]-кодом над F₈. Его двойственный код - цикли-

ческий [63, 6, 48]-код над F₈. Оба кода почти оптимальны.

Пример 3. Пусть (ℓ,m,q) = (1,2,7), а α - примитивный элемент поля F₇2,

такой что α² + 6α + 3 = 0. Тогда порождающий многочлен кода C_s имеет вид

M_s(x) = x⁸ + 5x⁷ + 4x⁶ + 3x⁵ + 6x⁴ + 5x³ + 6x + 5,

а C_s является циклическим [48,40,5]-кодом над F₇. Этот циклический код почти оп-

тимален. Но его двойственный код - оптимальный циклический [48, 8, 33]-код над F₇.

3.2. Циклические коды по моному f(x) = xqh-¹. В этом пункте рассмотрим

циклический код, определяемый над F_qm мономом вида f(x) = xqh-¹, где h - поло-

жительное целое число. Для любого положительного целого h ≥ m пусть h = mk+ℓ,

где k, ℓ - некоторые явные положительные целые числа и ℓ ≤ m - 1. Ясно, что

f (x) = xqh -¹ = xqℓ -¹. В этом пункте рассматривается случай h ≤ m - 1.

Прежде чем сформулировать и доказать основной результат, введем некоторые

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

лотомического смежного класса C_s, содержащего элемент s ∈ Γ. Тогда существует

единственное целое h_s, такое что ℓ_sh_s = m. Определим q-адическое разложение чис-

ла s как s = i₀ +i₁q+. . .+im-1qm-1, где 0 ≤ i₀, i₁, . . . , im-1 ≤ q-1, и будем представ-

лять его последовательностью вида s = (i₀, i₁, i₂, . . . , im-1). Очевидно, что для любо-

го элемента i ∈ C_s его q-адическое разложение является некоторым сдвигом после-

довательности s = (i₀, i₁, i₂, . . . , im-1). В последовательности s = (i₀, i₁, i₂, . . . , im-1)

любые ℓ подряд идущих нулей будем называть 0-серией длины ℓ. Обозначим все

0-серии в s = (i₀, i₁, i₂, . . . , im-1) через As1, As2, . . . , A^sd

. Кроме того, пусть m^si - дли-

на 0-серии A^si для любого 1 ≤ i ≤ d_s. Пусть m_s,k,u = |{t : i_t = k и 0 ≤ t ≤ u}| для

любых положительных целых k, u, таких что 0 ≤ k ≤ q - 1 и 0 ≤ u ≤ m - 1. Теперь

зададим разложение функции

∑

(q-1)

f (α^t + 1) = (α^t + 1)qh-¹ = (α^t + 1)

i=0

qⁱ =

= (αtq0 + 1)q-1(αtq1 + 1)q-1 . . . (αtqh-1 + 1)q-1 =

)

∑

⁽q - 1

⁽q - 1)(αt)i0+i1q+i2 q²+...+ih-1qh-1 .

i₀

ih-1

0≤i0,i1,...,ih-1≤q-1

Положим Γ^′ = {s ∈ Γ : ms,0,m-1 + ms,1,h-1 + . . . + ms,q-1,h-1 = m}, а также C^′s =

= {i ∈ C_s : i < q^h} для любого s ∈ Γ^′. Очевидно, 0 ∈ Γ^′. Кроме того, для любых

s ∈ Γ^′ и i ∈ C^′s положим

)

⁽q - 1⁾⁽q - 1⁾⁽q - 1

B_s,i =

i₀

i₁

ih-1

Заметим, что B_s,i = B_s,s (обозначим эту величину просто через B_s) для любого

i∈C^′s.

Таким образом, получаем

∑

⁽q - 1⁾⁽q - 1⁾⁽q - 1⁾

∑∑

f (α^t + 1) =

(α^t)ⁱ =

B_s,i(α^t)ⁱ =

i₁

ih-1

s∈Γ^′ i∈C^′s

s∈Γ^′ i∈C^′

∑

B_s(α^t)ⁱ =

B_s

(α^t)ⁱ.

s∈Γ^′ i∈C^′

s∈Γ^′

i∈C^′

Для любого s ∈ Γ^′ \ {0} определим N^′s следующим образом:

∑

N^′s =

(m^si - m + h + 1).

1≤i≤ds

m^si≥m-h

Нетрудно доказать следующие леммы.

Лемма 7. Пусть B_s определено, как и выше; тогда НОД(B_s,p) = 1.

Доказательство. Пусть q = p^a, тогда p-адическим разложением q - 1 явля-

ется

∑

q - 1 = (p - 1) p^j.

j=0

∑

Для любого 0 ≤ i ≤ q - 1 пусть i =

i_jp^j, где 0 ≤ i₀, i₁, . . . , ia-1 ≤ p - 1. Согласно

j=0

теореме Люка [26]

⁽q - 1⁾

⁽p - 1⁾⁽p - 1⁾⁽p - 1)modp.

i₀

i₁

ia-1

((

)

p-1

Заметим, что НОД

= 1, поскольку p - простое. Таким образом,

((

)

q-1

НОД

= 1.

▴

Лемма 8. Пусть s^∞ - последовательность вида (3) с мономом f(x) = xqh-¹

над F_qm, где h ≤ m - 1. Тогда линейная сложность L_s и минимальный многочлен

M_s(x) последовательности s^∞ имеют вид

∑

L_s =

N_p(N^′s)ℓ_s + N_p(m)

s∈Γ^′\{0}

∏

M_s(x) = (x - 1)Np(m)

m_α-s(x)Np(Ns),

s∈Γ^′\{0}

где N_p(∗) = 0, если ∗ ≡ 0 (mod p), и N_p(∗) = 1 в противном случае.

Доказательство. Объединяя предыдущие рассуждения с формулой (3), по-

лучаем

)

(∑

∑

s_t = Tr(f(α^t

+ 1)) = Tr

B_s

(α^t)ⁱ

B_s

Tr((α^t)ⁱ) =

s∈Γ^′

i∈C^′

s∈Γ^′

i∈C^′

∑

B_s

= Tr(1) +

(m^si - m + h + 1) Tr((α^t)^s) =

h_s

s∈Γ^′\{0}

1≤i≤ds

m^si≥m-h

∑

B_s

= Tr(1) +

(m^si - m + h + 1) (α^t)squ =

h_s

s∈Γ^′\{0}

1≤i≤ds

u=0

m^si≥m-h

∑

B_s

= Tr(1) +

(m^s

- m + h + 1)h_s (α^t)ⁱ =

h_s

s∈Γ^′\{0}

1≤i≤ds

i∈Cs

m^si≥m-h

∑

= Tr(1) +

B_s

(m^si - m + h + 1) (α^t)ⁱ =

s∈Γ^′\{0}

1≤i≤ds

i∈Cs

m^si≥m-h

∑

= Tr(1) +

B_sN^′

(α^t)ⁱ.

s∈Γ^′\{0}

i∈Cs

Так как НОД(B_s, p) = 1, то N_p(B_sN^′s) = N_p(N^′s). Поэтому требуемые результаты

о линейной сложности L_s и минимальном многочлене M_s(x) теперь вытекают из

леммы 4. ▴

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

многочлен циклического кода C_s, определяемого последовательностью s^∞.

Теорема 2. Пусть C_s - циклический код, определяемый последовательно-

стью s^∞ из леммы 8. Тогда C_s имеет параметры [n, n - L_s, d] и порождающий

многочлен M_s(x), где L_s и M_s(x) указаны в лемме 7.

Следствие 1. Если h = m -1 и m ≤ p, то циклический код C_s из теоремы 2

имеет параметры [n, n - L_s, d] и порождающий многочлен

⎧

∏

⎨

m_α-s(x),

m < p,

M_s(x) =

∏

⎩

m_α-s(x), m = p,

s∈Γ^′\{0}

где

^{q^m - (q - 1)^m,

m < p,

L_s =

q^m - (q - 1)^m - 1, m = p,

⎧

⎨qm -¹

+ 1 ≤ d ≤ q^m - (q - 1)^m + 1, m < p,

q-1

⎩q^m-1

≤ d ≤ q^m - (q - 1)^m,

m = p.

q-1

Доказательство. Для любого положительного целого i < p имеем N_p(i) = 1,

поскольку НОД(i, p) = 1. Заметим, что

∑

N^′s =

(m^si - m + h + 1) ≤ m - 1 < p для любого s ∈ Γ^′ \ {0}.

1≤i≤ds

m^si≥m-h

Поэтому N_p(N^′s) = 1. Более того, N_p(m) = 1, если m < p, и N_p(m) = 0, если m = p.

По лемме 8 получаем параметры [n, n - L_s, d] и порождающий многочлен M_s(x)

∑

кода C_s, где L_s =

ℓ_s+N_p(m). Кроме того,

ℓ_s = q^m-(q-1)^m-1, так как

s∈Γ^′\{0}

h = m-1. Следовательно, L_s = q^m-(q-1)^m, если m < p, и L_s = q^m-(q-1)^m-1, если

m = p. Очевидно, что α⁰,α¹,...,αqm-1,...,αqm-1+qm-2+...+q2+^q - корни многочлена,

q^m - 1

взаимного к M_s(x), когда m < p. Таким образом,

+ 1 ≤ d согласно границе

q-1

БЧХ. Оценку сверху для d можно получить из границы Синглтона. Аналогично

получаются оценки для d при m = p. ▴

Рассмотрим случай q = 2. Из теоремы 2 немедленно получаем

Следствие 2. Пусть q = 2. Тогда циклический код C_s из теоремы 2 имеет

параметры [2^m - 1, 2^m - 1 - L_s, d] и порождающий многочлен M_s(x), где

∑

L_s =

N₂(N^′s)ℓ_s + N₂(m),

s∈Γ^′\{0}

∏

M_s(x) = (x - 1)N2(m)

m_α-s(x)

s∈Γ^′\{0}

N2(N^s)=1

⎧

^⌈m^⌉

⎨d ≥ 2h-2 + 2, m нечетно и 2 < h ≤

^⌈m^⌉

^⎩d ≥ 2h-2 + 1, m четно и 2 < h ≤

Замечание 2. Пусть при этом q = 2 и 1 ≤ h ≤ ⌈m/2⌉. Для этого подслучая в [1]

исследован двоичный циклический код C_s, определяемый последовательностью s^∞

вида (3). Покажем, что наши результаты равносильны результатам из [1, теоре-

ма 12]. Согласно [1]

∏

M_s(x) = (x - 1)N2(m)

m_α-(2j+1) (x).

1≤2j+1≤2^h-1

κ(h)2j+1=1

Так как q = 2 и h ≤ ⌈m/2⌉, то нетрудно видеть, что

i = i₀ + i₁2 + ... + ih-12h-1 ∈ Γ^′ \ {0}

тогда и только тогда, когда i₀ = 1. Таким образом, любое целое i, 1 ≤ i ≤ 2^h - 1,

вида i = 2j + 1 принадлежит Γ^′ \ {0}, и любой элемент i ∈ Γ^′ \ {0} имеет вид 2j + 1,

т.е.

Γ^′ \ {0} = {2j + 1 : 1 ≤ 2j + 1 ≤ 2^h - 1}.

Кроме того, согласно определениям величин κ(h)2j+1 (см. [1]) и N₂(N^′s) нетрудно про-

верить, что κ(h)2j+1 = N₂(N^′s), когда s = 2j + 1. Таким образом,

∏

M_s(x) = (x - 1)N2(m)

m_α-(2j+1)

(x) = (x - 1)N2(m)

m_α-s(x).

1≤2j+1≤2^h-1

s∈Γ^′\{0}

κ(h)2j+1=1

N2(N^s)=1

Пример 4. Пусть (q,m,h) = (3,4,1), а α - примитивный элемент поля F₃4,

такой что α⁴ + 2α³ + 2 = 0. Тогда Γ^′ = {0, 1, 2}. Легко убедиться, что N₃(N^′s) = 1,

когда s ∈ Γ^′ \ {0}. При этом порождающий многочлен кода C_s имеет вид

M_s(x) = x⁹ + 2x⁸ + x⁷ + 2x⁶ + x⁴ + x² + 1,

и C_s является троичным циклическим [80,71,5]-кодом. Его двойственный код - тро-

ичный циклический [80, 9, 47]-код. Оба кода оптимальны.

Пример 5. Пусть (q,m,h) = (3,4,2), а α - примитивный элемент поля F₃4,

такой что α⁴ + 2α³ + 2 = 0. Тогда Γ^′ = {0, 1, 2, 4, 5, 7, 8}. Нетрудно убедиться, что

N₃(N^′s) = 1, когда s ∈ Γ^′ \ {0}. При этом порождающий многочлен кода C_s имеет

вид

M_s(x) = x²⁵ + x²⁴ + 2x²³ + 2x²² + x²¹ + 2x¹⁸ + x¹⁵ + 2x¹¹ + 2x¹⁰ + x⁹ + x⁷ +

+ 2x⁵ + 2x⁴ + x³ + x² + x + 1,

и C_s является оптимальным троичным циклическим [80,55,11]-кодом. Его двой-

ственный код - циклический [55, 25, 24]-код.

Пример 6. Пусть (q,m,h) = (5,3,1), а α - примитивный элемент поля F₅3, та-

кой что α³ +3α+3 = 0. Тогда Γ^′ = {0, 1, 2, 3, 4}. Нетрудно проверить, что N₅(N^′s) = 1,

когда s ∈ Γ^′ \ {0}. При этом порождающий многочлен кода C_s имеет вид

M_s(x) = x¹³ + 2x¹² + 4x¹¹ + 2x¹⁰ + 4x⁹ + x⁸ + 4x⁷ + 2x⁵ + x³ + 2x² + x + 1,

и C_s является циклическим [124,111,7]-кодом над F₅. Его двойственный код - цик-

лический [124, 13, 82]-код. Оба кода оптимальны.

3.3. Циклические коды по моному f(x) = xq(3m-1)/4+(q(m-1)/2-1)/(q-1). В этом

пункте будем изучать циклический код C_s, определяемый по моному

f (x) = xq(3m-1)/4 +(q(m-1)/2-1)/(q-1)

над F_qm , где m - положительное целое число, такое что m ≡ 3 (mod 4). Тем са-

мым, существует целое k, такое что m = 4k + 3. С этой целью сперва рассмотрим

разложение функции

f (α^t + 1) = (α^t + 1)q(3m-1)/4 +(q(m-1)/2-1)/(q-1) = (α^t + 1)q3k+2+(q2k+1-1)/(q-1) =

ⁱ+q3k+2

= (α^t + 1)i=0

= (αtq0 + 1)(αtq1 + 1) . . . (αtq2k + 1)(αtq3k+2 + 1) =

∑

(α^t)i0+i1q+i2q²+...+i2k q2k +i3k+2q3k+2 =

0≤i0,...,i2k,i3k+2≤1

∑

(α^t)i0 +i1q+i2 q²+...+i2k q2k +

(α^t)i0+i1q+i2q²+...+i2k q2k +q3k+2 .

0≤i0,...,i2k≤1

0≤i0,...,i2k ≤1

Всюду далее будем использовать обозначения

A = {i : i = i₀ + i₁q + i₂q² + ... + i2kq2k, 0 ≤ i₀,...,i2k ≤ 1},

B = q3k+2 + A = {j : j = i + q3k+2 и i ∈ A}.

Тогда любые элементы i ∈ A и j ∈ B можно представить в виде последовательностей

i = (⋆,...,⋆,0,...,0) и j = (⋆,...,⋆,0,...,0,1,0,...,0) соответственно, где ⋆ ∈ {0,1}.

2k+1

2k+2

2k+1

k+1

На протяжении этого пункта всегда будем считать, что ⋆ ∈ {0, 1}, если не указано

обратное. Что более важно, лидеры смежных классов всех элементов множества A

образуют множество

A = {i ∈ A : i = (1,⋆,...,⋆,0,...,0)}.

2k+2

Лемма 9. Для любого i ∈ A смежный класс C_i имеет размер ℓ_i = |C_i| = m =

= 4k + 3.

Доказательство. Заметим, что i < q2k+1; тогда iq^t ≤ q^m - 1 для любого t,

0 ≤ t ≤ 2k + 2. Это означает, что |C_i| > 2k + 2 >

. По лемме 2 получаем ℓ_i =

= |C_i| = m. ▴

Лемма 10. Пусть j ∈ B. Тогда |C_j| = m = 4k + 3, если НОД(3,k) = 1, а ес-

ли k = 3k^′, то |C_j| =^m

тогда и только тогда, когда j = qk′ + q5k′+1 + q9k′+2,

а в противном случае |C_j| = m.

Доказательство. Замети, что j < q3k+2, поэтому jq^t ≤ q^m - 1 для любого

m+1

0 ≤ t ≤ k+1. Тогда |C_j| > k+1 =

. Если НОД(m, 2) = 1 и НОД(m, 3) = 1,

то C_j должен иметь размер m согласно лемме 2. Если k = 3k^′, то размер C_j должен

быть либо m, либо

. Предположим, что |C_j| =

, тогда представление j в виде

последовательности можно разбить на три части равной длины, причем все три

части должны быть одинаковы. Замечая, что

=k+

+ 1, отсюда легко вывести,

что каждая часть имеет вид (0, . . . , 0,1, 0, . . ., 0). Таким образом,

j = (0,...,0,1, 0, . . ., 0, 0, . . ., 0,1, 0, . . ., 0, 0, . . ., 0,1, 0, . . ., 0),

т.е. j = qk′ + q5k′+1 + q9k′+2. Пусть теперь j = qk′ + q5k′+1 + q9k′+2, тогда ясно, что

|C_j | =

. На этом доказательство завершается. ▴

Поскольку случаи k = 0 и 1 очевидны, в дальнейшем будем предполагать, что

k ≥ 2. Положим

B₁ = {j ∈ B : j = (⋆, . . ., ⋆, 0, . . ., 0, 0, . . ., 0, 1, 0, . . ., 0)},

k+1

B₂ = {j ∈ B : j = (0, . . ., 0, ⋆, . . ., ⋆, 0, . . ., 0, 1, 0, . . ., 0)}.

k+2

k-1

k+1

Разумеется, для любого элемента j множества B₁ или B₂ должен существовать

некоторый лидер смежного класса i ∈ A, такой что j ∈ C_i. Более того, множество

лидеров смежных классов всех элементов множества B₁ (или B₂) имеет вид

B₁ = {1, 0, . . ., 0, ⋆, . . ., ⋆, 0, . . ., 0)}

2k+2

(или B₂ = {1, ⋆, . . . , ⋆, 0, . . . , 0, 1, 0, . . . , 0, 0, . . . , 0, 0 ≤ t ≤ k - 2)} ∪ {1}).

k-t-2

k+1

2k+2

Таким образом, можно сформулировать следующие леммы.

Лемма 11. Для любого j ∈ B существует некоторый элемент i ∈ A, такой

что C_i ∩ C_j = ∅ тогда и только тогда, когда j ∈ B₁ или B₂.

Лемма 12. Для любых j₁ ∈ B₁ и j₂ ∈ B₂ справедливы следующие два утвер-

ждения:

(1) j₁ = j₂ тогда и только тогда, когда j₁ = j₂ = (0, . . . , 0, 1, 0, . . . , 0);

3k+2

(2) Cj1 = Cj2 (j₁ = j₂) тогда и только тогда, когда

j₁ = (0, . . ., 0, 1, 0, . . ., 0, 0, . . ., 0, 1, 0, . . ., 0)

k-t

k+t+1

j₂ = (0, . . ., 0, 1, 0, . . ., 0, 0, . . ., 0, 1, 0, . . ., 0),

k+t+1

k-t

где 1 ≤ t ≤ k - 1.

Доказательство. Первое утверждение тривиально. Докажем второе. Если

Cj1 = Cj2 (j₁ = j₂), то j₂ ∈ Cj1 , т.е. представление j₂ в виде последовательности

является некоторым сдвигом

j₁ = (⋆, . . . , ⋆, 0, . . ., 0, 0, . . ., 0, 1, 0, . . ., 0).

k+1

Очевидно, что r-кратный сдвиг j₁ не принадлежит B₂, когда 0 ≤ r ≤ 2k + 2 или

3k + 2 ≤ r ≤ m. Таким образом, считаем, что (t + 2k + 2)-кратный сдвиг j₁ равен j₂,

где 1 ≤ t ≤ k - 1. Тогда

j₂ = (0, . . . , 0, 0, . . ., 0, 1, 0, . . ., 0, ⋆, . . ., ⋆, 0, . . ., 0).

k+1

k+1-t

Поскольку j₂ ∈ B₂, получаем, что

j₂ = (0, . . . , 0, 0, . . ., 0, 1, 0, . . ., 0, 0, . . ., 0, 1, 0, . . ., 0).

k+1

k-t

Следовательно,

j₁ = (0, . . . , 0, 1, 0, . . ., 0, 0, . . ., 0, 0, . . ., 0, 1, 0, . . ., 0).

k-t

k+1

В обратную сторону утверждение очевидно. ▴

Для любого j ∈ B положим C^′j = {j^′ : j^′ ∈ C_j и j^′ ∈ B}, а через ℓ^′j обозначим

мощность C^′j . Более точно, будем считать, что C^′j = {j, j₁, . . . , j_t} и j → j₁ → . . . →

→ j_t → j. Поскольку представление в виде последовательности для каждого эле-

мента C^′j имеет вид (⋆, . . . , ⋆, 0, . . . , 0, 0, 1, 0, . . . , 0), то для каждого элемента C^′j тре-

2k+1

буется не менее k + 2 сдвигов для получения следующего элемента. Тогда общее

число сдвигов не меньше (t + 1)(k + 2). Если ℓ_j = m, то (t + 1)(k + 2) ≤ m = 4k + 3.

4k + 3

Следовательно, t ≤ 2, т.е. ℓ^′j ≤ 3. Если ℓ_j =^m, то (t+1)(k+2) ≤ ℓj =

. Значит,

t ≤ 1, т.е. ℓ^′j = 1.

Пусть

B′1 = {j ∈ B₁ : j = (0, . . ., 0, 1, 0, . . ., 0, 0, . . ., 0, 1, 0, . . ., 0)},

k-t

k+t+1

B′2 = {j ∈ B₂ : j = (0, . . ., 0, 1, 0, . . ., 0, 0, . . ., 0, 1, 0, . . ., 0)},

k+t+1

k-t

где 1 ≤ t ≤ k - 1. Лидеры смежных классов всех элементов из B′1 (или B′2) образуют

множество

B′1 = {j : j = (1, 0, . . ., 0, 1, 0, . . ., 0), 1 ≤ t ≤ k - 1}.

2k-t

2k+t+1

Согласно доказательству леммы 12 имеем

⋃

B′1 ∪ B′2 =

C^′j =

C^′j.

j∈B^′

Положим

D = {j ∈ B : j = (⋆,...,⋆,0,...,0,1,0,...,0,0,...,0,0,1,0,...,0)},

k-t-1

k+1

где 0 ≤ t ≤ k - 1, и

O = {j ∈ B : j = (0,...,0,1,0,...,0,⋆,...,⋆,0,...,0,1,0,...,0)},

2k-t

t-k

k+1

где k ≤ t ≤ 2k - 1. Кроме того, при k ≥ 3 положим

D^′ = {j^′ ∈ D : j^′ = (0, ⋆, . . ., ⋆, 0, . . ., 0, 1, 0, . . ., 0, 0, . . ., 0, 1, 0, . . ., 0)},

k-t-2

k+1

где 0 ≤ t ≤ k - 3, и

O^′ = {j^′ ∈ O : j^′ = (0, . . . , 0, 1, 0, . . ., 0, ⋆, . . ., ⋆, 0, . . ., 0, 1, 0, . . ., 0)},

2k-t

k+1

t-k-1

k+1

где k + 2 ≤ t ≤ 2k - 1. В последовательностях из множеств D^′ и O^′ имеется один и

только один элемент ⋆, принимающий значение 1. При k ≥ 3 также положим

Q = {j ∈ B : j = (0,...,0,0,1,0,...,0,0,...,0,0,1,0,...,0,0,...,0,0,1,0,...,0)},

где 0 ≤ t₁, t₂, t₃ ≤ k - 3 и t₁ + t₂ + t₃ = k - 3. Для k = 2 полагаем D^′ = O^′ = Q = ∅.

Лемма 13. Для любого j ∈ B имеет место один из следующих случаев:

(1) ℓ^′j = 3 тогда и только тогда, когда j ∈ Q, если НОД(3, k) = 1 (ℓ^′j = 3 тогда и

только тогда, когда j ∈ Q и (t₁, t₂, t₃) = (k^′ + 1, k^′ + 1, k^′ + 1), если k = 3k^′);

(2) ℓ^′j = 2 тогда и только тогда, когда j ∈ D ∪ O и j ∈ Q;

(3) В остальных случаях ℓ^′j = 1.

Доказательство. Для k = 2 результат (1) очевиден, поскольку в этом слу-

чае Q = ∅. Итак, считаем, что k ≥ 3. Если НОД(3, k) = 1, то ℓ_j = m по лем-

ме 10. Тогда ℓ′j ≤ 3. Во-первых, если ℓ′j = 3, то пусть C′j = {j, j1, j2}, где j →

→ j₁ → j₂ → j. При этом пусть для переходов j → j₁, j₁ → j₂ и j₃ → j требуются

сдвиги кратностей по крайней мере t₁ + k + 2, t₂ + k + 2 и t₃ + k + 2 соответственно.

Тогда t₁ + k + 2 + t₂ + k + 2 + t₃ + k + 2 = m = 4k + 3. Отсюда t₁ + t₂ + t₃ = k - 3.

При (t₁ + k + 2)-кратном сдвиге последовательности

j = (⋆,...,⋆,0,...,0,0,1,0,...,0)

2k+1

получаем

j₁ = (0, . . . , 0, 0, 1, 0, . . ., 0, ⋆, . . ., ⋆, 0, . . ., 0).

2k+1

k-t1

Так как j₁ ∈ B, то

j₁ = (0, . . . , 0, 0, 1, 0, . . ., 0, ⋆, . . ., ⋆, 0, . . ., 0, 1, 0, . . ., 0, 0, . . ., 0).

k-t1-1

k+1

k-t1

При (t₂ + k + 2)-кратном сдвиге j₁ получаем

j₂ = (0, . . . , 0, 0, 1, 0, . . ., 0, 0, . . ., 0, 0, . . ., 0, 0, 1, 0, . . ., 0, ⋆, . . ., ⋆, 0, . . ., 0).

k-t1

k-t1-1

k-t2

Так как j₂ ∈ B, то

j₂ = (0, . . . , 0, 0, 1, 0, . . ., 0, 0, . . ., 0, 0, . . ., 0, 0, 1, 0, . . ., 0, 0, . . ., 0

,1, 0, . . ., 0, 0, . . ., 0).

k-t1

k-t1-t2-2

k-t2

Таким образом,

j = (0,...,0 ,1,0,...,0,0,...,0,1,0,...,0,0,...,0,1,0,...,0),

k-t1-t2-2

k+1

и поэтому

j = (0,...,0,0,1,0,...,0,0,...,0,0,1,0,...,0,0,...,0,0,1,0,...,0) ∈ Q.

В обратную сторону, если j ∈ Q, результат (1) очевиден. Во-вторых, с помощью

аналогичных рассуждений получаем, что при ℓ^′j ≥ 2 последовательность j должна

принадлежать D или O. Для любого j ∈ D ∪O легко проверить, что ℓ^′j ≥ 2. Тогда из

утверждения (1) с учетом ℓ^′j ≤ 3 получаем (2). Наконец, утверждение (3) очевидно.

Для k = 3k^′ нетрудно убедиться, что ℓ^′j = 1, если (t₁, t₂, t₃) = (k^′ + 1, k^′ + 1, k^′ + 1). Из

леммы 10 известно, что ℓ_j =

тогда и только тогда, когда j = qk′ + q5k′+1 + q9k′+2,

т.е. j ∈ Q и (t₁, t₂, t₃) = (k^′ + 1, k^′ + 1, k^′ + 1). Итак, для k = 3k^′ результат также

справедлив. ▴

Лемма 14. В тех же обозначениях справедливы следующие утверждения:

(1) D^′ = O^′ = Q;

(2) D ∩ O = Q;

⋃

(3) D \ Q ∪ O \ Q =

C^′i =

C^′i.

i∈D\Q

i∈O\Q

Доказательство. (1) Для любого элемента j ∈ D′ должно существовать

некоторое целое число 0 ≤ t₁ ≤ k - 3, такое что

j = (0,⋆,...,⋆,0,...,0,1,0,...,0,0,...,0,1,0,...,0),

k-t1-2

k+1

где подпоследовательность ⋆, . . . , ⋆ содержит один и только один элемент ⋆, прини-

k-t1-2

мающий значение 1. Без ограничения общности будем считать, что

⋆, . . ., ⋆ = 0, . . . , 0, 1, 0, . . ., 0 .

k-t1-2

Тогда

j = (0,0,...,0,1,0,0,...,0,0,...,0,1,0,...,0,0,...,0,1,0,...,0),

k+1

т.е. имеем

j = (0,0,...,0,1,0,0,...,0,0,...,0,1,0,...,0,0,...,0,1,0,...,0).

k+1

Очевидно, что j принадлежит O^′, причем t = 2k - a - 1 и

⋆, . . ., ⋆ = 0, . . . , 0, 1, 0, . . ., 0 .

t-k-1

Отсюда следует D^′ ⊂ O^′. Аналогичными рассуждениями доказывается O^′ ⊂ D^′.

Таким образом, D^′ = O^′. Утверждение Q = D^′ очевидно.

(2) Из (1) получаем Q ⊂ D ∩ O. Для любого j ∈ D ∩ O имеем

j = (⋆,...,⋆,0,...,0,1,0,...,0,0,...,0,0,1,0,...,0)

k-t1-1

k+1

для некоторого t, где 0 ≤ t₁ ≤ k - 1, поскольку j ∈ D. Так как

j ∈ O = {j ∈ B : j = (0,...,0,1,0,...,0,⋆,...,⋆,0,...,0,1,0,...,0)},

2k-t

t-k

k+1

то

j = (0,...,0,1,0,...,0, 0,...,0 ,1,0,...,0,0,...,0,1,0,...,0) ∈ Q.

2k-t

t-k-t1-1

k+1

Таким образом, D ∩ O = Q.

(3) Для любого j ∈ D \ Q пусть C^′j = {j, j₁}. Ясно, что должно существовать

некоторое 0 ≤ t₁ ≤ k - 1, такое что

j = (⋆,...,⋆,0,...,0,1,0,...,0,0,...,0,0,1,0,...,0)

k-t1-1

k+1

j₁ = (0, . . . , 0, 0, 1, 0, . . ., 0, ⋆, . . ., ⋆, 0, . . ., 0, 1, 0, . . ., 0).

k-t1-1

k+1

Это показывает, что j ∈ O, причем t = 2k - t₁ - 1. Так как ℓ^′j = ℓ^′

= 2, то j ∈ O \Q.

Для любого i ∈ O \ Q пусть C^′i = {i, i₁}. Аналогичными рассуждениями можно ⋃⋃

показать, что i₁ ∈ D \ Q. Поэтому D \ Q ∪ O \ Q =

C^′i =

C^′i.

▴

i∈D\Q

i∈O\Q

При k ≥ 3, если (t₁, t₂, t₃) = (a, b, c) - некоторое решение уравнения t₁ + t₂ + t₃ =

= k - 3, то циклические сдвиги (c,a,b) и (b,c,a) также являются решениями этого

уравнения. Обозначим эти три решения через Q(a,b,c). Тогда все решения уравнения

⋃

⋂

t₁ + t₂ + t₃ = k - 3 можно представить в виде

Q(a

i,bi,ci),

где

Q(a

i,bi,ci)

= ∅.

i=0

Далее, положим R = {(a_i, b_i, c_i), 0 ≤ i ≤ e} и

{

Q = j ∈ Q : j = (0,...,0,0,1,0,...,0,0,...,0,0,1,0,...,0,0,...,0,0,1,0,...,0),

}

(a_i, b_i, c_i) ∈ R

Следует отметить, что Q(a,b,c) = Q(a,c,b), если числа a, b, c попарно различны, и

Q(a,b,c) = Q(a,c,b), если среди них есть два одинаковых.

Лемма 15. Для любых трех различных элементов j,j₁,j₂ ∈ B неравенство

C_j ∩ Cj1 ∩ Cj2 = ∅ выполнено тогда и только тогда, когда существует некоторое

J ∈ Q, такое что C^′J = {j,j₁,j₂}.

Доказательство. Если Cj ∩Cj1 ∩Cj2 = ∅, то C_j = Cj1 = Cj2. Таким образом,

j₁, j₂ ∈ C^′j. Из утверждения (1) леммы 13 получаем j, j₁, j₂ ∈ Q. Без ограничения

общности будем считать, что j → j₁ → j₂ в C^′j. Кроме того, пусть

j = (0,...,0,0,1,0,...,0,0,...,0,0,1,0,...,0,0,...,0,0,1,0,...,0) ∈ Q.

Тогда

j₁ = (0, . . . , 0, 0, 1, 0, . . ., 0, 0, . . ., 0, 0, 1, 0, . . ., 0, 0, . . ., 0, 0, 1, 0, . . ., 0) ∈ Q

j₂ = (0, . . . , 0, 0, 1, 0, . . ., 0, 0, . . ., 0, 0, 1, 0, . . ., 0, 0, . . ., 0, 0, 1, 0, . . ., 0) ∈ Q.

Отсюда следует, что один из элементов j, j₁ и j₂ принадлежит Q, обозначим его

через J. В обратную сторону утверждение тривиально. ▴

Для удобства обозначим

A = {i : i ∈ A и i ∈ B₁ ∪ B₂},

B = {j : j ∈ B и j ∈ D ∪ O ∪ B₁ ∪ B₂},

B₁ = {j : j ∈ B₁ ∪ B₂ и j ∈ B′1}

соответственно.

Лемма 16. В тех же обозначениях справедливы следующие утверждения:

(1) |A| = 22k + 2^k - 2k-1 + k - 2;

(2) |B| = 22k+1 - 2k+1 - 2^k - 2k-1 + k + 1;

(3) |B₁| = 2^k + 2k-1 - 2k + 2;

(4) |D \ Q| = 2^k -(k-1)(k-2)

- 1;

⎧

⎨

(k - 1)(k - 2)

НОД(3, k) = 1,

(5) |Q| =

⎩(k - 1)(k - 2) - 2

+ 1, k = 3k^′.

Доказательство. Результат следует из определений соответствующих мно-

жеств. ▴

Теорема 3. Пусть s^∞ - последовательность типа (3) с мономом

f (x) = xq(3m-1)/4 +(q(m-1)/2-1)/(q-1)

над полем F_qm. Тогда справедливы следующие утверждения.

(1) Если k = 0 или 1, то линейная сложность L_s и минимальный многочлен M_s(x)

для s^∞ имеют вид

^{3(N_p(2) + 1) + N_P (3),

k = 0,

L_s =

7(3N_p(2) + N_p(4) + 5) + N_p(7), k = 1,

⎧

⎨(x - 1)Np(3)m_α-1(x)Np(2)mα-(q2+1) (x),

k = 0,

∏

M_s(x) =

⎩(x-1)Np(7)mα-1 (x)Np(4)

m_α-i(x)

m_α-i(x)Np(2), k = 1,

i∈D1

i∈D2

где

D₁ = {1 + q + q², 1 + q + q⁵, 1 + q² + q⁵, q + q² + q⁵, 1 + q + q² + q⁵},

D₂ = {1 + q, 1 + q², q + q⁵}.

(2) Если k ≥ 2 и НОД(3, k) = 1, то линейная сложность L_s и минимальный мно-

гочлен M_s(x) для s^∞ имеют вид

{

∑

L_s =

N_p(m^s - 2k - 1) +

N_p(m^s - 2k) +

N_p(m^s - 2k + 1) +

s∈A\{0}

s}B1

s∈B^′

∑

N_p(2) +

N_p(3) m + N_p(m)

s∈B

s∈D\Q

s∈Q

∏

M_s(x) = (x - 1)Np(m)

m_α-s

(x)Np (ms-2k-1)

m_α-s(x)Np(ms-2k) ×

s∈A\{0}

s∈B1

∏

m_α-s

(x)Np(ms-2k+1)

m_α-s(x)

m_α-s

(x)Np (2)

m_α-s(x)Np(3).

s∈B′1

s∈B

s∈D\Q

s∈Q

(3) Если k = 3k^′, то линейная сложность L_s и минимальный многочлен M_s(x)

для s^∞ имеют вид

{

∑

L_s =

N_p(m^s - 2k - 1) +

N_p(m^s - 2k) +

N_p(m^s - 2k + 1) +

s∈A\{0}

s∈}

s∈B^′

∑

N_p(2) +

N_p(3) m +

+ N_p(m)

s∈B^∗

s∈D\Q

s∈Q^∗

∏

M_s(x) = m_α-s₀(x)Np (3)(x - 1)Np(m)

m_α-s(x)Np(ms-2k-1) ×

s∈A\{0}

∏

× m_α-s

(x)Np(ms-2k)

m_α-s

(x)Np(ms-2k+1)

m_α-s(x) ×

s∈B1

s∈B^′

s∈B^∗

∏

m_α-s

(x)Np(2)

m_α-s(x)Np(3),

s∈D\Q

s∈Q^∗

где B^∗ = B \ {s₀ = qk′ + q5k′ +1 + q9k′ +2}.

Доказательство. (1) При k = 0 имеем

)

(

)

s_t = Tr(f(α^t + 1)

= Tr

(α^t + 1)q2+1) = Tr

1 + α^t + (α^t)q2 + (α^t)1+q2

(

)

= Tr(1) + 2 Tr(α^t) + Tr

(α^t)1+q2

Аналогично, при k = 1 имеем

(

)

s_t = Tr(f(α^t + 1)) = Tr

(α^t + 1)q5+q2+q+1

= Tr(1) + 4 Tr(α^t) +

∑

(

)

∑

(

)

+ Tr

(α^t)^s

s∈D1

s∈D2

где D₁ = {1 + q + q², 1 + q + q⁵, 1 + q² + q⁵, q + q² + q⁵, 1 + q + q² + q⁵} и D₂ =

= {1 + q, 1 + q², q + q⁵}. Поэтому требуемые результаты о линейной сложности L_s и

минимальном многочлене M_s(x) теперь вытекают из леммы 4.

(2) Если k ≥ 2 и НОД(3, k) = 1, то из предыдущих рассуждений с учетом фор-

мулы (3) получаем

)

(∑

∑

(∑

∑

s_t

= Tr(f(α^t + 1)) = Tr

(α^t)ⁱ +

(α^t)ⁱ

= Tr

(α^t)ⁱ +

i∈A

i∈B

s∈A i∈C^′s

∑

(α^t)ⁱ +

′

i∈C^′

i∈B

s∈B1 i∈C^s

s∈B₁

s∈D\Q i∈C^′

)

∑

(

)

(α^t)ⁱ

= Tr(1) +

(m^s - 2k - 1) Tr

(α^t)^s

s∈Q

i∈C^′

s∈A\{0}

∑

(

)

∑

(

)

∑

(

)

+ (m^s - 2k) Tr

(α^t)^s

(m^s - 2k + 1) Tr

(α^t)^s

+ Tr

(α^t)^s

s∈B1

s∈B^′

s∈B

∑

(

)

∑

(

)

(α^t)^s

s∈D\Q

s∈Q

Поэтому требуемые результаты о линейной сложности L_s и минимальном много-

члене M_s(x) теперь вытекают из леммы 4.

(3) Результат следует из леммы 10 с учетом доказательства утверждения (2). ▴

Теорема 4. Пусть C_s - циклический код, определяемый последовательно-

стью s^∞ из теоремы 3. Тогда C_s имеет параметры [n, n - L_s, d] и порождающий

многочлен M_s(x), где L_s и M_s(x) указаны в теореме 3.

Для любого N_p(∗) из теоремы 3 положим N_P (∗) = 1. Тогда имеет место

Следствие 3. При k ≥ 2 положим R = A ∪ B₁ ∪ B′1 ∪ B ∪ (D \ Q) ∪ Q и

N_P (∗) = 1 для любого N_p(∗) из теоремы 3. Тогда код C_s, определяемый последова-

тельностью s^∞, имеет параметры [n, n-L_s, d] и порождающий многочлен M_s(x),

где

⎧

(

)

⎨

m 3·22k -2k-1 -(k-1)(k-2)

+k-2

+ 1,

НОД(3, k) = 1,

L_s =

(

)

^⎩m 3 · 22k - 2k-1 -(k-1)(k-2)+1

+k-2

+ 1, k = 3k^′,

∏

M_s(x) =

m_α-s(x).

s∈R

Доказательство. Результат следует из теоремы 3 и леммы 16. ▴

Для q = 2 хорошо известно [27, 28], что моном f(x) = x2(m-1)/2+2(3m-1)/4 -¹ явля-

ется почти совершенно нелинейной функцией над F₂m , где m ≡ 3 (mod 4). Теперь

рассмотрим двоичные циклические коды, определяемые мономами такого типа. Из

теоремы 3 получаем

Следствие 4. Пусть q = 2. Тогда s^∞ - двоичная последовательность с

f (x) = x2(m-1)/2+2(3m-1)/4 -¹

над F₂m. Кроме того, справедливы следующие три утверждения:

(1) Если k = 0 или 1, то линейная сложность L_s и минимальный многочлен M_s(x)

для s^∞ имеют вид

^{4, k = 0,

L_s =

36, k = 1,

⎧

⎨(x - 1)mα-(22+1)(x), k = 0,

∏

M_s(x) =

⎩(x - 1)

m_α-i(x), k = 1,

i∈D1

где D₁ = {7, 35, 37, 38, 39}.

(2) Если k ≥ 2 и НОД(3, k) = 1, то линейная сложность L_s и минимальный мно-

гочлен M_s(x) для s^∞ имеют вид

{

∑

L_s =

N₂(m^s - 2k - 1) +

N₂(m^s - 2k) +

N₂(m^s - 2k + 1) +

s∈A\{0}

s∈B1

s∈B^′

}

∑

m+1

s∈B∪Q

∏

M_s(x) = (x - 1)

m_α-s

(x)N2(ms-2k-1)

m_α-s(x)N2(ms-2k) ×

s∈A\{0}

s∈B1

∏

m_α-s

(x)N2(ms-2k+1)

m_α-s(x).

s∈B^′

s∈B∪Q

(3) Если k = 3k^′, то линейная сложность L_s и минимальный многочлен M_s(x)

для s^∞ имеют вид

{

∑

L_s =

N₂(m^s - 2k - 1) +

N₂(m^s - 2k) +

N₂(m^s - 2k + 1) +

s∈A\{0}

s∈B1

s∈B^′

}

∑

s∈B^∗∪Q^∗

∏

M_s(x) = (x - 1)m_α-s₀(x)

m_α-s

(x)N2(ms-2k-1)

m_α-s(x)N2(ms-2k) ×

s∈A\{0}

s∈B1

∏

m_α-s

(x)N2(ms-2k+1)

m_α-s(x),

∗

s∈B^′

s∈B^∗∪Q

где B^∗ = B \ {s₀ = 2k′ + 25k′+1 + 29k′+2}.

Таким образом, для двоичного циклического кода C_s, определяемого мономом

f (x) = x2(m-1)/2 +2(3m-1)/4 -¹, справедлива

Теорема 5. Двоичный циклический код C_s, определяемый последовательно-

стью s^∞ из следствия 4, имеет параметры [n, n - L_s, d] и порождающий много-

член M_s(x), указанные в следствии 4. Кроме того, для минимального расстояния d

имеет место следующая граница:

d ≥ 2k+1 + 2.

Доказательство. Утверждение о порождающем многочлене и размерности

кода C_s вытекают из определения кода и следствия 4. Остается доказать справед-

ливость нижней границы на минимальное расстояние d. Нетрудно вычислить, что

d ≥ 4 при k = 0 и d ≥ 6 при k = 1. Далее, согласно определению множества B

нетрудно увидеть, что {j + 2k+1 + 22k + 23k+2 : j = 0, 1, 2, . . . , 2k+1 - 1} ⊆ B^∗. От-

сюда следует, что αⁱ является корнем многочлена, взаимного к M_s(x), для любого

i ∈ {j+2k+1+22k+23k+2 : j = 0,1,2,...,2k+1-1}. Заметим, что коды, порожденные

многочленом M_s(x) и его взаимным многочленам, имеют одинаковое распределение

весов. Согласно границе БЧХ d ≥ 2k+1 + 1. Очевидно, что циклический код C_s

является кодом с четным весами. Следовательно, d ≥ 2k+1 + 2. При k = 0 и 1 ми-

нимальное расстояние d удовлетворяет неравенству d ≥ 2k+1 + 2, что и завершает

доказательство. ▴

Замечание 3. Результаты этого пункта для q = 2 дают некоторые ответы на от-

крытую проблему 3, поставленную в работе [1]. Размерность и порождающий мно-

гочлен этого подкласса двоичных циклических кодов имеют широкий диапазон зна-

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

циклических кодов.

Пример 7. Пусть (q,k,m) = (2,1,7), и пусть α - примитивный элемент по-

ля F₂7 , такой что α⁷ + α + 1 = 0. Тогда порождающий многочлен кода C_s имеет

вид

M_s(x) = x³⁶ + x³⁵ + x³² + x³⁰ + x²⁹ + x²⁸ + x²⁷ + x²² + x²¹ + x¹⁹ + x¹⁷ +

+ x¹⁶ + x¹⁵ + x¹⁴ + x¹² + x¹¹ + x⁶ + x² + x + 1,

а C_s является двоичным циклическим [127,91,10]-кодом. Его двойственный код -

двоичный циклический [127, 36, 32]-код.

§ 4. Заключение

Построены три класса циклических кодов на основе некоторых последователь-

ностей с мономами специальных типов. Размерности и порождающие многочлены

этих классов q-ичных циклических кодов имеют широкий диапазон значений. Кро-

ме того, рассмотрено минимальное расстояние таких циклических кодов. Следует

отметить, что многие из представленных кодов оптимальны или почти оптимальны

согласно таблицам [2].

СПИСОК ЛИТЕРАТУРЫ

Ding C., Zhou Z. Binary Cyclic Codes from Explicit Polynomials over GF(2^m) // Discrete

Math. 2014. V. 321. P. 76-89.

Grassl M. Bounds on the Minimum Distance of Linear Codes and Quantum Codes (elec-

tronic tables). Available at http://www.codetables.de.

Chien R.T. Cyclic Decoding Procedures for Bose-Chaudhuri-Hocquenghem Codes // IEEE

Trans. Inform. Theory. 1964. V. 10. № 4. P. 357-363.

Forney G.D., Jr. On Decoding BCH Codes // IEEE Trans. Inform. Theory. 1965. V. 11.

№ 4. P. 549-557.

Prange E. Some Cyclic Error-Correcting Codes with Simple Decoding Algorithms. Tech.

Rep. TN-58-156. Air Force Cambridge Research Center. Bedford, MA, USA. April, 1958.

Berlekamp E.R., Justesen J. Some Long Cyclic Linear Binary Codes Are Not So Bad //

IEEE Trans. Inform. Theory. 1974. V. 20. № 3. P. 351-356.

Calderbank A.R., Li W.-C.W., Poonen B. A 2-adic Approach to the Analysis of Cyclic

Codes // IEEE Trans. Inform. Theory. 1997. V. 43. № 3. P. 977-986.

Kai X., Zhu S. On Cyclic Self-Dual Codes // Appl. Algebra Engrg. Comm. Comput. 2008.

V. 19. № 6. P. 509-525.

Li C., Li N., Helleseth T., Ding C. The Weight Distributions of Several Classes of Cyclic

Codes from APN Monomials // IEEE Trans. Inform. Theory. 2014. V. 60. № 8. P. 4710-4721.

10.

Liu L., Xie X., Li L., Zhu S. The Weight Distributions of Two Classes of Nonbinary Cyclic

Codes with Few Weights // IEEE Commun. Lett. 2017. V. 21. № 11. P. 2336-2339.

11.

Luo J., Feng K. Cyclic Codes and Sequences from Generalized Coulter-Matthews Func-

tion // IEEE Trans. Inform. Theory. 2008. V. 54. № 12. P. 5345-5353.

12.

Martinez-Pérez C., Willems W. Is the Class of Cyclic Codes Asymptotically Good? // IEEE

Trans. Inform. Theory. 2006. V. 52. № 2. P. 696-700.

13.

Moreno O., Kumar P.V. Minimum Distance Bounds for Cyclic Codes and Deligne’s Theo-

rem // IEEE Trans. Inform. Theory. 1993. V. 39. № 5. P. 1524-1534.

14.

Rao A., Pinnawala N. A Family of Two-Weight Irreducible Cyclic Codes // IEEE Trans.

Inform. Theory. 2010. V. 56. № 6. P. 2568-2570.

15.

Roth R.M., Seroussi G. On Cyclic MDS Codes of Length q over GF(q) // IEEE Trans.

Inform. Theory. 1986. V. 32. № 2. P. 284-285.

16.

van Lint J.H., Wilson R.M. On the Minimum Distance of Cyclic Codes // IEEE Trans.

Inform. Theory. 1986. V. 32. № 1. P. 23-40.

17.

Zeng X., Hu L., Jiang W., Yue Q., Cao X. The Weight Distribution of a Class of p-ary

Cyclic Codes // Finite Fields Appl. 2010. V. 16. № 1. P. 56-73.

18.

Ding C. Cyclic Codes from Some Monomials and Trinomials // SIAM J. Discrete Math.

2013. V. 27. № 4. P. 1977-1994.

19.

Ding C. A Sequence Construction of Cyclic Codes over Finite Fields // Cryptogr. Commun.

2018. V. 10. № 2. P. 319-341.

20.

Rajabi Z., Khashyarmanesh K. Some Cyclic Codes from Some Monomials // Appl. Algebra

Engrg. Comm. Comput. 2017. V. 28. № 6. P. 469-495.

21.

Tang C., Qi Y., Xu M. A Note on Cyclic Codes from APN Functions // Appl. Algebra

Engrg. Comm. Comput. 2014. V. 25. № 1-2. P. 21-37.

22.

Ding C., Helleseth T. Optimal Ternary Cyclic Codes from Monomials // IEEE Trans.

Inform. Theory. 2013. V. 59. № 9. P. 5898-5904.

23. Huffman W.C., Pless V. Fundamentals of Error-Correcting Codes. Cambridge: Cambridge

Univ. Press, 2003.

24. Ding C., Xiao G., Shan W. The Stability Theory of Stream Ciphers. Lect. Notes Comp.

Sci. V. 561. Heidelberg: Springer, 1991.

25. El Rouayheb S.Y., Georghiades C.N., Soljanin E., Sprintson A. Bounds on Codes Based on

Graph Theory // Proc. 2007 IEEE Int. Sympos. on Information Theory (ISIT’2007). Nice,

France. June 24-29, 2007. P. 1876-1879.

26. Lucas E. Théorie des fonctions numériques simplement périodiques // Amer. J. Math. 1878.

V. 1. № 4. P. 289-321.

27. Dobbertin H. Almost Perfect Nonlinear Power Functions on GF(2ⁿ): The Niho Case //

Inform. and Comput. 1999. V. 151. № 1-2. P. 57-72.

28. Hollmann H.D.L., Xiang Q. A Proof of the Welch and Niho Conjectures on Cross-Correla-

tions of Binary m-Sequences // Finite Fields Appl. 2001. V. 7. № 2. P. 253-286.

Ли Ланьцян

Поступила в редакцию

Чжу Шисинь

30.09.2018

Лю Ли

После доработки

Кай Сяошань

29.04.2019

Школа математики, Технологический университет Хэфэй,

Принята к публикации

провинция Аньхой, КНР

10.06.2019

lilanqiang716@126.com

zhushixinmath@hfut.edu.cn

liuli-1128@163.com

kxs6@sina.com