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

Том 56

2020

Вып. 4

УДК 621.391 : 519.725

И.Ю. Могильных, Ф.И. Соловьева

О БАЗИСАХ КОДОВ БЧХ С КОНСТРУКТИВНЫМ

РАССТОЯНИЕМ 3 И ИХ РАСШИРЕНИЙ¹

Рассматриваются коды БЧХ в узком смысле длины p^m - 1 над Fp, m ≥ 3.

Доказано, что такой код с конструктивным расстоянием δ = 3 и его расшире-

ние при p ≥ 5 не порождаются множеством своих кодовых слов минимального

ненулевого веса. Установлено, что расширенные коды БЧХ с конструктивным

расстоянием δ = 3 при p ≥ 3 порождаются множеством слов веса 5, причем

базисные векторы могут быть выбраны среди аффинных орбит некоторых ко-

довых слов.

Ключевые слова: код БЧХ, циклический код, аффинно-инвариантный код, ба-

зис минимального веса, аффинный порождающий элемент.

DOI: 10.31857/S0555292320040026

§ 1. Введение

Вопрос существования базиса, состоящего из векторов минимального или неболь-

шого веса линейного кода, как компактного способа хранения информации, задаю-

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

вания [1, § 3.2], а также теории тестов [2-4].

Так как циклический МДР-код достигает границы Синглтона, его порождающий

многочлен имеет минимальный вес. Следовательно, существует базис из кодовых

слов минимального веса для такого кода. К этим кодам относятся коды Рида-Соло-

мона, а также некоторые другие связанные с ними коды [5, гл. 11, теоремы 9, 10].

Известно [5, теорема 10, гл. 13], что всякий код Рида-Маллера порождается сло-

вами минимального веса. Также базис, состоящий из векторов минимального веса,

существует для q-ичных кодов Хэмминга вследствие их единственности для задан-

ных параметров и леммы Глаголева (см. данный результат в работе [6] и анало-

гичный результат для q-ичного случая в [7]). Итеративная конструкция базисов из

кодовых слов минимального веса для двоичного кода Хэмминга была получена в ра-

боте [8]. Отметим, что этот результат может быть обобщен на случай расширенных

двоичных кодов Хэмминга и q-ичных кодов Хэмминга (со сходной схемой доказа-

тельства на основе конструкции Шонхайма). В [2] было доказано, что расширенные

двоичные коды БЧХ в узком смысле достаточно большой длины порождаются мно-

жеством слов минимального веса.

С другой стороны, в работе [9] установлено, что совокупность слов минимального

веса двоичного примитивного кода БЧХ с конструктивным расстоянием 2m-2 - 1

совпадает с множеством слов минимального веса выколотого кода Рида-Маллера

RM(2, m).

¹ Работа выполнена при поддержке Министерства науки и высшего образования РФ (соглашение

№ 075-02-2020-1479/1).

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

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

выдерживающих аффинные преобразования поля. Кодовое слово c аффинно-инва-

риантного кода называется аффинным порождающим элементом (single orbit affine

generator, см. [4]), если орбита вектора c действия аффинной группы поля F_pm содер-

жит базис кода. Очевидно, аффинным порождающим элементом аффинно-инвари-

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

дающему многочлену выколотого циклического кода. Естественной представляется

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

В [3] приводятся результаты, мотивирующие поиск аффинных порождающих

элементов небольшого веса с позиций локальных тестирований. В работе [4] доказа-

но, что двоичный расширенный код БЧХ в узком смысле с конструктивным рассто-

янием 5 имеет аффинный порождающий элемент минимального веса. В работе [10]

авторами настоящей статьи были получены аффинные порождающие элементы ми-

нимального веса аффинно-инвариантных кодов, отвечающих функции Голда.

В данной статье исследуется вопрос существования аффинного порождающе-

го элемента минимально возможного веса расширенного кода БЧХ над F_p, p = 2.

Отметим, что его структура для недвоичных кодов БЧХ с конструктивным рас-

стоянием 3 существенно отличается от такового в двоичном случае (для двоичных

расширенных кодов Хэмминга результат был получен в [4, следствие 8]).

В §2 приводятся основные понятия и утверждения. В §3 доказывается несу-

ществование базисов, состоящих из векторов минимального веса для расширенных

кодов БЧХ с конструктивным расстоянием 3 над F_p для любого простого p, p = 2, 3.

В §4 вводится понятие ранга кодового слова аффинно-инвариантного кода. Дока-

зано, что ранг аффинного порождающего элемента веса 5 расширенного кода БЧХ

с конструктивным расстоянием 3 равен 3. Ранг введен по аналогии с рангом кодового

слова циклического кода [5, гл. 9, § 11], предложенным для определения минималь-

ного расстояния некоторых циклических кодов. Полученное ограничение на ранг

неявно использовано при нахождении подходящего аффинного порождающего эле-

мента в теореме 4. Отметим, что при p = 3 аффинный порождающий элемент имеет

минимальный вес, поскольку кодовое расстояние кода равно 5, а при p > 3 имеет

предминимальный вес, равный 5.

§2. Циклические и аффинно-инвариантные коды

Основные определения и обозначения см. в [5]. Линейный код называется цик-

лическим, если циклический сдвиг любого его кодового слова является кодовым

словом. В дальнейшем будем рассматривать лишь циклические коды длины p^m - 1

над простым полем F_p. Для всякого ненулевого элемента β поля Галуа F_pm спра-

ведливо βpm-¹ = 1. Элемент поля F_pm называется примитивным, если его поря-

док равен p^m - 1. Координаты векторного пространства Fpm-1p перенумеруем чис-

лами 0, . . . , p^m - 2 и отождествим координату с номером i с элементом αⁱ, где

i ∈ {0,...,p^m-2} и α - примитивный элемент поля F_pm. Циклотомическим классом

элемента i ∈ {0, . . . , p^m - 2} по модулю p^m - 1 называется множество

{

}

cl(i) =

ip^j (mod p^m - 1) : j ∈ {0, . . ., m - 1}

Со всяким вектором c = (c₀, . . . , c_pm-2) в пространстве Fpm-1p отождествим много-

∑

член c(x) =

c_ixⁱ. Элемент поля F_pm называется нулем p-ичного циклического

i=0

кода длины p^m - 1, если он является корнем каждого его кодового многочлена.

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

митивного элемента, пробегающих объединение некоторых циклотомических клас-

сов. Если i₁, . . . , i_ℓ - представители некоторых циклотомических классов, то через

Ci1,...,i_ℓ обозначим соответствующий циклический код

{c(x) : c(α^j) = 0, j ∈ cl(i₁) ∪ . . . ∪ cl(i_ℓ)}.

Согласно теореме о границе БЧХ, если найдется δ - 1 подряд идущих степеней

примитивного элемента α, являющихся нулями циклического кода, то кодовое рас-

стояние в коде не меньше δ. Кодом с таким свойством является C1,...,δ-1, именуемый

кодом БЧХ в узком смысле с конструктивным расстоянием δ.

Для вектора c = (c₀, . . . , c_pm-2) длины p^m - 1 обозначим его расширение через c,

т.е.

(

)

∑

c = c₀,...,c_pm-2,-

c_i

i=0

Расширенный код {c : c ∈ C} обозначим через C. В дальнейшем считаем, что до-

бавляемая при расширении координата занумерована нулем поля Галуа F_pm. Таким

образом, на координатных позициях векторного пространства Fpmp действует аф-

финная группа поля F_pm, состоящая из перестановок, которые могут быть описаны

парами (γ, σ), а именно: (γ, σ)(β) = γβ + σ, где γ, σ ∈ F_pm , γ = 0, относительно

операции композиции. Код длины p^m над F_p называется аффинно-инвариантным,

если аффинная группа поля F_pm оставляет на месте множество кодовых слов этого

кода.

Пусть i ∈ {0, . . . , p^m - 1}. Через I обозначим вектор, представляющий число i

∑

в p-ичной системе счисления, т.е. i =

Isp^s. Пусть J и I - записи чисел j и i,

s=0

соответственно, в p-ичной системе счисления. Обозначим j ≺ i, если J_s ≤ I_s для

всех s ∈ {0, . . ., m - 1}. Следующая теорема характеризует аффинно-инвариантные

коды.

Теорема

[11]. Пусть C - циклический код длины p^m - 1. Если αⁱ - нуль

кода C и для всякого ненулевого j, j ≺ i, элемент α^j является нулем кода C, тогда

код C является аффинно-инвариантным. Верно и обратное.

Следствие 1. Расширенный код БЧХ C1,2,...,δ-1 для всякого δ ≥ 2, а также

код C1,2,p2₊₁ являются аффинно-инвариантными.

В дальнейшем нам понадобится следующий факт.

Предложение. Пусть конструктивное расстояние кода БЧХ в узком смысле

совпадает с кодовым расстоянием d. Тогда расширение этого кода имеет кодовое

расстояние d + 1.

Доказательство. Предположим, что c - кодовое слово веса d расширенного

кода БЧХ C1,...,d-1. Тогда c = (c₀, . . . , c_pm-2) - кодовое слово веса d кода C1,...,d-1,

а {i₁, . . ., i_d} - множество позиций ненулевых символов слова c, такое что

∑

cij = 0.

j=1

Так как c ∈ C1,...,d-1, то

∑

cij αℓij = 0

j=1

для всех ℓ ∈ {1, . . . , d - 1}. Учитывая, что матрица системы относительно неизвест-

ных ci1 , . . . , c_i

является матрицей Вандермонда, и следовательно, невырождена,

имеем ci1 = ci2 = . . . = c_i

= 0, противоречие. ▴

Кодовое расстояние кодов БЧХ и других кодов с двумя нулями было получено

в работе [12]. При p = 3 имеем C1,2 = C1,2,3, откуда в силу границы БЧХ кодовое

расстояние C1,2 равно 4. Отсюда получаем

Следствие 2. Кодовое расстояние кода БЧХ C1,2 равно 3 при всех простых p,

p = 3, и равно 4 при p = 3. Расширения этих кодов имеют кодовые расстояния 4

и 5 соответственно.

§ 3. Несуществование базисов кодов C1,2 и C1,2 из слов минимального веса

Лемма 1. Пусть c ∈ C₂ - такое кодовое слово, что для всякого i, для которого

c_i = 0, имеет место αⁱ ∈ F_p. Тогда c ∈ C2,p2₊₁.

Доказательство. Так как c ∈ C₂, то

∑

c_iα2i = 0.

i∈{0,...,p^m -2}: ci=0

По условию леммы для всякого i, для которого c_i = 0, имеет место αⁱ ∈ F_p,

откуда αip2 = αⁱ. Следовательно,

∑

c_iα(p2+1)i =

c_iα2i = 0,

i∈{0,...,p^m -2}: ci=0

другими словами, αp2+1 является корнем c(x), который, в свою очередь, принадле-

жит C2,p2₊₁. ▴

Теорема 2. Множество кодовых слов кода C1,2 веса 3 содержится в C1,2,p2₊₁.

Доказательство. Без ограничения общности имеем c(x) = 1 + axⁱ + bx^j,

c(x) ∈ C1,2, где a, b - ненулевые элементы поля Галуа F_p. По определению кода

БЧХ выполнены проверочные соотношения

1 + aαⁱ + bα^j = 0,

(1)

1 + aα2i + bα2j = 0.

(2)

Покажем, что αp2+1 является корнем многочлена c(x), т.е.

1 + aα(p2+1)i + bα(p2+1)j

(3)

равно нулю. Возможны следующие случаи.

Случай 1. Пусть b = -a. Используя это равенство и подставляя выражение

для α^j из (1) в (2), получаем a-1-2aαⁱ = 0. Таким образом, αⁱ и, следовательно, α^j

принадлежат F_p. Отсюда и из леммы 1 получаем требуемое.

Случай 2. Пусть a + b = 0. Обозначим a + b через -f-1. Преобразуем (1) и (2),

используя замену

αⁱ = by_i + f, α^j = ay_j + f.

(4)

Из (1) после преобразований имеем y_i = -y_j. Отсюда с учетом (2) и a + b = -f-1

получаем

y2iab(a + b) = f - 1.

(5)

Преобразуем выражение (3), произведя замену (4) и принимая во внимание ра-

венства y_i = -y_j, ap2 = a и bp2 = b:

1 + aα(p2+1)i + bα(p2+1)j =

= 1 + a(by_i + f)p2(by_i + f) + b(-ay_i + f)p2(-ay_i + f) =

= 1 + a(byp2i + f)(byi + f) + b(-ayi2 + f)(-ayi + f) =

= 1 + ab(a + b)yp2+1i + f²(a + b).

Из полученного выражения согласно обозначению a + b = -f-1 получаем

yp2+1iab(a + b) + 1 - f.

Однако (p² + 1)/2 = (p - 1)(p + 1)/2 + 1, и так как из (5) следует, что y2i ∈ F_p, то

(y2i)(p2+1)/2 = y2i.

Таким образом, приходим к выводу, что выражение (3) преобразуется в y2iab(a+b)+

+1 - f. Из (5) следует, что αp2+1 является корнем c(x). ▴

Следствие 3. Для любого простого p, не равного 2 или 3, код C1,2 и рас-

ширенный код C1,2 не порождаются множествами кодовых слов минимального

ненулевого веса.

Доказательство. В силу следствия 2 минимальные расстояния кодов C1,2 и

C1,2 равны 3 и 4 соответственно. Число p² + 1 не принадлежит циклотомическим

классам cl(1) = {pⁱ : i ∈ {0, . . . , m - 1}} и cl(2) = {2pⁱ : i ∈ {0, . . . , m - 1}},

следовательно, C1,2,p2₊₁ является собственным подкодом кода C1,2. Из теоремы 2

заключаем, что все слова веса 3 кода C1,2 содержатся в C1,2,p2₊₁.

Рассмотрим расширенные коды. Пусть c - кодовое слово веса 4 кода C1,2, полу-

ченное добавлением общей проверки на четность к кодовому слову c кода C1,2. По-

кажем, что вектор c принадлежит коду C1,2,p2₊₁. Пусть c имеет вес 4, т.е. в позиции

вектора c, занумерованной нулем поля F_pm, стоит символ 0. Пусть для некоторо-

го i в позиции вектора c, занумерованной элементом αⁱ, стоит ненулевой символ.

В силу того, что аффинная группа поля действует 2-транзитивно на координат-

ных позициях c, найдется аффинное преобразование, меняющее местами позиции,

занумерованные элементами 0 и αⁱ. Другими словами, представитель c^′ аффинной

∑

орбиты кодового слова c может быть выбран таким, что c^′ имеет вес 3 и

c^′i = 0.

i=0

В силу следствия 1 коды C1,2 и C1,2,p2₊₁ аффинно-инвариантны, поэтому c и c^′

или содержатся в этих кодах одновременно, или одновременно не содержатся. Из

теоремы 2 заключаем, что векторы c^′ и, следовательно, c принадлежат C1,2,p2₊₁. ▴

§ 4. Базис кода C1,2 веса 5

4.1. Ранг аффинного порождающего элемента. Рангом вектора c ∈ Fpmp назовем

размерность векторного пространства над F_p, натянутого на носитель вектора c, т.е.

{αⁱ : i ∈ {0, . . ., p^m - 2}, c_i = 0}.

Теорема 3. Пусть c - кодовое слово кода C1,2 веса 4 и c - аффинный порож-

дающий элемент кода C1,2. Тогда c имеет вес 5 и ранг 3.

Доказательство. По следствию 3 аффинный порождающий элемент кода

C1,2 имеет вес не меньше 5. Пусть слово c веса 5 является аффинным порождающим

элементом кода C1,2. Так как вес c равен 4 и c ∈ C₁, то ранг c не превосходит 3. Если

ранг c равен 1, то по лемме 1 вектор c принадлежит аффинно-инвариантному коду

C1,2,p2₊₁, являющемуся собственным подкодом кода C1,2. Следовательно, кодовое

слово c не является аффинным порождающим элементом кода C1,2.

Пусть c(x) = h + axⁱ + bx^j + fx^k и кодовое слово c имеет ранг 2. Так как ранг c

равен 2, то

α^j = s + tαⁱ, α^k = u + vαⁱ

для некоторых элементов s, t, u, v поля Галуа F_p.

Так как c ∈ C₂, то

c(α²) = h + aα2i + b(s + tαⁱ)² + f(u + vαⁱ)² =

= h + aα2i + bs² + 2bstαⁱ + bt²α2i + fu² + 2fuvαⁱ + fv²α2i =

= aα2i(a + t²b + v²f) + 2αⁱ(stb + uvf) + h + bs² + fu² = 0.

(6)

Последнее равенство имеет место в случае тождества, т.е.

a + t²b + v²f = stb + uvf = h + bs² + fu² = 0,

(7)

или если αⁱ ∈ F_p2 .

Покажем, что c(x) ∈ C1,2,p2₊₁. Учитывая, что элементы s, t, u, v принадлежат

простому полю F_p, имеем

c(αp2 +1) = h + aαi(p2+1) + b(s + tαⁱ)p2+1 + f(u + vαⁱ)p2+1 =

= aα(p2+1)i(a + t²b + v²f) + (αip2 + αⁱ)(stb + uvf) + h + bs² + fu².

Из этого выражения для c(αp2+1) заключаем, что если выполнено условие (7),

то c(αp2+1) = 0. Если αⁱ ∈ F_p2 , то αip2 = αⁱ, и выражение для c(αp2+1) совпадает

с выражением для c(α²) из (6), а следовательно, кодовое слово c из C1,2,p2₊₁ не

является аффинным порождающим элементом кода C1,2. ▴

4.2. Явный вид аффинного порождающего элемента. В следующей лемме найдем

подходящий для дальнейших рассмотрений кодовый многочлен кода C1,2.

Лемма 2. Пусть α - примитивный элемент поля Галуа F_pm, p,m ≥ 3. Тогда

циклический код C1,2 длины p^m - 1 содержит многочлен

c(x) = 2 + xⁱ + x^j - 2x^k,

где i, j, k удовлетворяют условиям

αⁱ = α + 2-1α², α^j = -α + 2-1α², α^k = 1 + 2-1α².

(8)

Доказательство. Справедливы следующие равенства:

c(α) = 2 + αⁱ + α^j - 2α^k = 2 + α + 2-1α² - α + 2-1α² - 2 - α² = 0,

c(α²) = 2 + α2i + α2j - 2α2k =

= 2 + α² + 2-2α⁴ + α³ + α² + 2-2α⁴ - α³ - 2 - 2-1α⁴ - 2α² = 0.

Так как c(α) = c(α²) = 0, то c(x) ∈ C1,2. ▴

Обозначим многочлен

2 + (x + 2-1x²)spℓ+^t + (-x + 2-1x²)spℓ+^t - 2(1 + 2-1x²)spℓ+^t

через P_ℓ,s,t(x). Если i, j, k удовлетворяют (8) для α ∈ F_pm и c(x) - многочлен, ука-

занный в лемме 2, то c(αspℓ+^t) = P_ℓ,s,t(α).

Лемма 3. Многочлен P_ℓ,s,t(x) не является тождественно нулевым при любых

s, t ∈ {1, 2} и любых ℓ ∈ {1, 2, . . ., m - 1}, а также при ℓ = s = 0, t ∈ {3, . . ., p - 1}.

Доказательство. Коэффициент при x² произвольного многочлена P_ℓ,s,t(x)

при указанных в формулировке ограничениях на ℓ, s, t является ненулевым. Дей-

ствительно, при раскрытии скобок в слагаемых многочлена P_ℓ,s,t(x) только в по-

следнем слагаемом имеем коэффициент при x², равный -(sp^ℓ + t). ▴

Теорема 4. Для любого простого p ≥ 3 и любого m ≥ 3 существует прими-

тивный элемент α поля Галуа F_pm, такой что слово c, где

c(x) = 2 + xⁱ + x^j - 2x^k

и i, j, k удовлетворяют условиям (8), является аффинным порождающим элемен-

том кода C1,2 длины n = p^m.

Доказательство. Согласно лемме 2 вектор c принадлежит коду C1,2. Дока-

жем, что существует примитивный элемент α поля F_pm, такой что аффинная орбита

слова c порождает код C1,2, а координатные позиции кода C1,2 перенумерованы сте-

пенями элемента α.

Пусть

D - расширенный циклический код, являющийся линейной оболочкой аф-

финной орбиты вектора c, и

D ⊊ C1,2. Докажем, что множества нулей кодов C1,2

и D совпадают.

Пусть α^r - нуль многочлена c(x), где r - минимальное число относительно по-

рядка ≺, такое что r ∈ cl(1) ∪ cl(2). По определению циклотомического класса без

ограничения общности r можно полагать не делящимся на p. Рассмотрим вектор R,

являющийся p-ичным представлением числа r. Согласно теореме 1 возможны два

случая: либо вектор R = (t, 0, . . . , 0) имеет вес 1, где t ∈ {3, . . . , p - 1}, либо R =

= (t, 0, . . . , 0, s, 0, . . . , 0) имеет вес 2, т.е. r = sp^ℓ + t, где s, t ∈ {1, 2}, ℓ ∈ {1, . . . , m - 1}.

Предположим, что во втором случае ℓ больше, чем ⌊m/2⌋, где αspℓ+^t - корень мно-

гочлена c(x). Тогда

α(spℓ+t)pm-ℓ = αtpm-ℓ+^s

является корнем c(x), поскольку sp^ℓ + t и tp^m-ℓ + s принадлежат одному и тому же

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

реть ℓ ∈ {1, . . . , ⌊m/2⌋}.

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

члена

P_ℓ,s,t(x) = c(xspℓ+^t)

для любых s, t, ℓ, таких что s = ℓ = 0, t ∈ {3, . . . , p - 1} или t, s ∈ {1, 2}, ℓ ∈

∈ {1, . . ., ⌊m/2⌋}.

Для этого рассмотрим многочлен

)(⌊m/2⌋

)

(p-1∏

∏

Q(x) =

P0,0,t(x)

P_ℓ,s,t(x)

(9)

t=3

ℓ=1

1≤s,t≤2

Так как по лемме 3 многочлены P_ℓ,s,t не являются тождественно нулевыми, то и

многочлен Q не тождественно нулевой. Убедимся, что степень deg(Q) многочлена Q

меньше числа всех примитивных элементов поля F_pm.

Из определения многочлена P_ℓ,s,t имеем

deg(P_ℓ,s,t) ≤ 2sp^ℓ + 2t.

Отсюда и из (9) получаем

p⌊m/2⌋+1 - p

deg(Q) ≤ (p + 2)(p - 3) + 12

+ 6m.

(10)

p-1

Покажем, что deg(Q) < ϕ(p^m -1) начиная с некоторого достаточно большого m, где

ϕ(p^m - 1) - число всех примитивных элементов поля Галуа F_pm. Учитывая хорошо

известное неравенство для функции Эйлера ϕ

ln 2

ϕ(n) >

ln n

при n = p^m - 1 получаем

p^m - 1

ln 2

ϕ(p^m - 1) >

(11)

ln(p^m - 1)

Сравнивая нижнюю оценку (11) для ϕ(p^m -1) с верхней оценкой (10) степени deg(Q)

многочлена Q(x), нетрудно видеть, что

ϕ(p^m - 1) > deg(Q)

(12)

начиная с некоторого достаточно большого m. Следовательно, найдется примитив-

ный элемент α в F_pm, такой что Q(α) = 0, и значит, D = C1,2.

В частности, (12) выполняется для всех простых p ≥ 101 и любого m ≥ 3. Для

каждого простого p < 101 и m ≥ 3, для которых (12) не выполняется, с помощью

компьютера был найден примитивный элемент α, такой что Q(α) = 0.

Следовательно, D = C1,2, и кодовое слово c является аффинным порождающим

элементом кода C1,2 длины n = p^m для любого m ≥ 3. ▴

Задача нахождения аффинного порождающего элемента наименьшего возмож-

ного веса оказалась достаточно трудной для расширенных кодов БЧХ и далека от

своего полного решения для всех значений конструктивного расстояния. Открытой

и сложной проблемой представляется поиск аффинного порождающего элемента

для двоичных расширенных циклических кодов из различных APN-мономов [13]

(напомним что в [10] получено решение этой задачи для функции Голда), а так-

же расширенного двоичного кода БЧХ C1,3,5. В работе [14] установлено, что класс

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

максимальное кодовое расстояние 4. В этой связи задача существования базиса из

кодовых слов минимального веса может быть естественным образом сформулиро-

вана, например, для троичных аффинно-инвариантных кодов C1,4 длины 3^m при

нечетных m.

Авторы выражают свою благодарность рецензенту за ряд замечаний и предло-

жений, позволивших улучшить изложение статьи.

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

1. Charpin P. Open Problems on Cyclic Codes // Handbook of Coding Theory. Amsterdam:

Elsevier, 1998. V. 1. Ch. 11. P. 965-1063.

2. Kaufman T., Litsyn S. Almost Orthogonal Linear Codes Are Locally Testable // Proc. 2005

46th Annu. IEEE Symp. on Foundations of Computer Science (FOCS’05). Pittsburgh, PA,

USA. October 23-25, 2005. P. 317-326.

3. Kaufman T., Sudan M. Algebraic Property Testing: The Role of Invariance // Proc. 40th

Annu. ACM Symp. on Theory of Computing (STOC’08). Victoria, BC, Canada. May 17-20,

2008. New York: ACM, 2008. P. 403-412.

4. Grigorescu E., Kaufman T. Explicit Low-Weight Bases for BCH Codes // IEEE Trans.

Inform. Theory. 2011. V. 58. № 2. P. 78-81.

5. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.:

Связь, 1979.

6. Курляндчик Я.М. О логарифмической асимптотике длины максимального цикла раз-

броса r > 2 // Дискретный анализ. Новосибирск: Инст. матем. СО АН СССР, 1971.

Вып. 19. С. 48-55.

7. Simonis J. On Generator Matrices of Codes // IEEE Trans. Inform. Theory. 1992. V. 38.

№ 2. P. 516-516.

8. Соловьева Ф.И. O факторизации кодообразующих д.н.ф. // Методы дискретного ана-

лиза в исследовании функциональных схем. Новосибирск: Инст. матем. СО АН СССР,

1988. Вып. 47. С. 66-88.

9. Augot D., Charpin P., Sendrier N. Studying the Locator Polynomials of Minimum Weight

Codewords of BCH Codes // IEEE Trans. Inform. Theory. 1992. V. 38. № 3. P. 960-973.

10. Mogilnykh I.Yu., Solov’eva F.I. On Explicit Minimum Weight Bases for Extended Cyclic

Codes Related to Gold Functions // Des. Codes Cryptogr. 2018. V. 86. № 11. P. 2619-2627.

11. Kasami T., Lin S., Peterson W.W. Some Results on Cyclic Codes Which Are Invariant

under the Affine Group and Their Applications // Inform. Control. 1967. V. 11. № 5-6.

P. 475-496.

12. Charpin P., Tietäväinen A., Zinoviev V. On the Minimum Distances of Non-binary Cyclic

Codes // Des. Codes Cryptogr. 1999. V. 17. № 1-3. P. 81-85.

13. Carlet C., Charpin P., Zinoviev V. Codes, Bent Functions and Permutations Suitable for

DES-like Cryptosystems // Des. Codes Cryptogr. 1998. V. 15. № 2. P. 125-156.

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

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

Могильных Иван Юрьевич

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

Региональный научно-образовательный математический центр,

10.07.2020

Томский государственный университет

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

Институт математики им. С.Л. Соболева СО РАН

26.10.2020

Новосибирский Государственный университет

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

ivmog@math.nsc.ru

27.10.2020

Соловьева Фаина Ивановна

Институт математики им. С.Л. Соболева СО РАН

Новосибирский государственный университет

sol@math.nsc.ru