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

Том 58

2022

Вып. 4

УДК 621.391 : 519.725

О КОДАХ С РАССТОЯНИЯМИ d И n

Перечислены все q-ичные аддитивные (и в частности, линейные) блоковые

коды длины n и мощности N ≥ q², имеющие ровно два расстояния: d и n.

Для произвольных кодов длины n с расстояниями d и n получены верхние

оценки на мощность с помощью линейного программирования и через связь

с множествами точек на евклидовой сфере с двумя расстояниями.

Ключевые слова: код с двумя расстояниями, двухвесовой код, линейный двух-

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

тогональная таблица, оценка на коды, граница линейного программирования,

сферический код.

DOI: 10.31857/S0555292322040064, EDN: NAWXWG

§ 1. Введение

В статье рассматриваются q-ичные блоковые коды длины n, имеющие ровно два

расстояния - d и n. Коды с двумя расстояниями - это классический объект иссле-

дования в алгебраической теории кодирования в течение более 55 лет. Исчерпы-

вающий обзор таких кодов можно найти в работе [1]. Построение новых семейств

таких кодов, так же как и описание некоторых существующих классов таких кодов,

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

(см., например, работу [2] и библиографию в ней). Несмотря на многие известные

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

дов весьма далека от завершения. Даже в случае кодов с расстояниями d и n до этой

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

В двух предыдущих работах [3,4] мы описали такие коды для специального слу-

чая, когда два расстояния - это d и d+1, и показали, что все такие коды получаются

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

позиции (так чтобы сохранить линейность кода) ко всем словам, либо выбрасыва-

нием одной произвольной позиции из всех кодовых слов. Затем в работах [5,6] мы

рассмотрели произвольные линейные и нелинейные коды с двумя весами d и d + δ

и усилили известные результаты Дельсарта [7, 8], касающиеся необходимых усло-

вий существования таких проективных кодов. Следует также упомянуть работу [9],

где с помощью описания всех дуг в проективной геометрии P G(r, q) с кратностями

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

(проект KP-06-Russia/33-2020).

² Работа выполнена при частичной поддержке Национального научного фонда Болгарии (NSF)

(проект KP-06-N32/2-2019).

³ Исследования были выполнены в ИППИ им. А.А. Харкевича РАН в рамках проводимых фун-

даментальных исследований по теме “Математические теории корректирующих кодов”, а также

поддержаны грантом Национального научного фонда Болгарии (номер проекта 20-51-18002).

пересекающих их гиперплоскостей w, w + 1 и w + 2 были классифицированы все

q-ичные линейные коды с расстояниями d, d + 1 и d + 2.

Главная цель данной статьи - это перечисление аддитивных и неаддитивных

(включая дистанционно инвариантные) блоковых кодов длины n, имеющих ровно

два расстояния для очень специального случая, когда эти расстояния равны d и n.

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

ные с порождающими матрицами эквидистантных линейных кодов (они получаются

из последних добавлением нулевого столбца и строки из всех единиц). Этот эффект

был замечен в [10] в терминах полностью регулярных кодов с радиусом покрытия

ρ = 2. Мы приводим необходимые и достаточные условия для существования таких

кодов и даем их простое описание. Мы также приводим некоторые новые верхние

оценки на мощность таких произвольных кодов ровно с двумя расстояниями d и n.

Одна из таких оценок это граница линейного программирования, а другая оценка

связана со сферическими кодами, имеющими между кодовыми точками ровно два

расстояния в евклидовой метрике.

§ 2. Предварительные результаты

Пусть q ≥ 2 - целое положительное число, и пусть всюду далее Q = {0, 1, . . . , q-1}

- абелева группа, представленная в аддитивной форме, с нейтральным элементом 0.

Любое подмножество C ⊆ Qⁿ представляет собой код длины n, мощности N = |C|

с минимальным расстоянием d (т.е. d = min{d(x, y) : x, y ∈ C, x = y}), где

d(x, y) = |{i} : x_i = y_i, i = 1, . . . , n}| для x = (x₁, . . . , x_n) и y = (y₁, . . . , y_n),

который обозначается через (n, N, d)_q. Если q - степень простого числа, то Q - это

множество элементов поля Галуа F_q, которые мы также будем обозначать через

0, 1, . . ., q - 1, но операции над этими элементами будут осуществляться в поле F_q.

Если (n, N, d)_q-код C представляет собой k-мерное подпространство линейного про-

странства Qⁿ, то мы используем для такого кода стандартное обозначение [n, k, d]_q,

где N = q^k. Для двоичного случая, т.е. когда q = 2, символ q опускается и ис-

пользуются обозначения (n, N, d) и [n, k, d] соответственно. В настоящей статье под

понятием аддитивный мы имеем ввиду абелеву подгруппу в абелевой группе Qⁿ

с аддитивной покоординатной операцией в Q (так что, конечно, эти коды включают

в себя и линейные коды).

Пусть (n, N, {d, n})_q обозначает (n, N, d)_q-код C ⊂ Qⁿ, обладающий следующим

свойством: для любых двух различных кодовых слов x и y кода C расстояние Хэм-

минга d(x, y) между этими словами равно либо d, либо n. Если не оговорено про-

тивное, то мы всегда полагаем, что в таком коде оба расстояния d и n реализуются.

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

ких (n, N, {d, n})_q-кодов, а также верхние оценки максимально возможной мощности

произвольных кодов такого вида.

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

ние двух (или более) (n₁, N, {d₁, n₁})_q- и (n₂, N, {d₂, n₂})_q-кодов с одинаковыми или

разными параметрами, эквидистантные коды, коды с тривиальными (т.е. постоян-

ными) координатными позициями и так далее.

Определение 1. Пусть G - абелева группа порядка q, представленная в ад-

дитивном виде. Квадратная матрица D порядка qμ с элементами из G называется

разностной матрицей и обозначается через D = D(q, μ), если покоординатная раз-

ность любых двух ее различных строк содержит каждый элемент G ровно μ раз.

Ясно, что матрица D инвариантна относительно сложения любой ее строки или

столбца с постоянным вектором (a, a, . . . , a), где a ∈ G. Осуществляя такие операции,

мы всегда можем привести разностную матрицу D к нормализованной разностной

матрице, которая имеет нулевую первую строку и нулевой первый столбец. В даль-

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

полагать, что разностная матрица представлена в нормализованной форме.

Из [11] (см. также [12]) известен следующий результат.

Лемма 1. Для любого простого числа p и любых натуральных чисел ℓ и h

существует разностная матрица D(p^ℓ, p^h).

Опишем кратко построение всех таких разностных матриц D(p^ℓ, p^h) из рабо-

ты [12]. Для любого целого m ≥ 1 зафиксируем взаимно-однозначное соответствие

между элементами поля F_pm и элементами векторного пространства F^mp. Для лю-

бых натуральных чисел ℓ и h положим u = ℓ + h. Для поля Галуа F_pu с элементами

{f₀ = 0, f₁ = 1, f₂, . . ., f_pu-1} обозначим через F = [f_i,j] матрицу размера p^u × p^u,

строки и столбцы которой индексированы элементами поля F_pu, где f_i,j = f_if_j,

т.е. F - таблица умножения элементов F_pu. Определим оператор Φ = Φ_u→ℓ, отобра-

жающий элементы x = (x₁, . . . , x_u) поля F^up в элементы x(ℓ) = (x₁, . . . , x_ℓ) поля F^ℓp

путем удаления правых u - ℓ координатных позиций векторов из F^up:

Φ_u→ℓ(x₁, . . ., x_ℓ, . . . , x_u) = (x₁, . . ., x_ℓ).

Обозначим через F[ℓ] матрицу, полученную из матрицы F действием оператора Φ

на все элементы матрицы F :

[

]

[ℓ]

F[ℓ] = f[ℓ]

i,j

f_i

= Φ_u→ℓ(f_i,j).

Получаем теперь (см. [11], а также [12]), что имеет место следующая

Лемма 2. Для любого простого числа p и любых натуральных чисел ℓ и h мат-

рица F[ℓ] представляет собой аддитивную разностную матрицу D = D(p^ℓ, p^h).

Если ℓ делит h, т.е. N = ph+ℓ = pℓ(h/ℓ+1), то F[ℓ] является векторным простран-

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

Опишем построение (n, N, {d, n})_q-кода на основе разностной матрицы D(q, μ)

над G. В рассматриваемом случае G = F_q. Предположим, что первая строка D

состоит из нулей. Обозначим через D(g) матрицу, полученную из D прибавлением

элемента g ∈ G ко всем элементам D, т.е. если D = [d_i,j ], то D(g) = [d_i,j + g] для

всех i и j (напомним, что сложение осуществляется в G). По определению D матри-

ца D(g) является разностной матрицей D(q, μ). Из определения следует также, что

для любых двух строк r из D и r(g) из D(g) выполняется следующее свойство [12]:

^{qμ,

если r(g) = r + (g, g, . . . , g),

d(r, r(g)) =

(1)

(q - 1)μ, если r(g) = r + (g, g, . . . , g).

Ясно, что матрица D(q, μ) индуцирует эквидистантный (qμ - 1, qμ, μ(q - 1))_q-код,

оптимальный относительно верхней границы Плоткина

N ≤

(2)

qd - (q - 1)n

если знаменатель положителен. Чтобы убедится в этом, следует вначале предста-

вить D в нормализованной форме, при которой первый столбец состоит из нулей,

а затем выкинуть этот тривиальный столбец. Из (1) вытекает следующий результат.

[

]_t

Лемма 3 [12]. Строки (N × n)-матрицы

D⁽⁰⁾ | . . . | D(q-1)

образуют двух-

весовой (n, N, {d, n})_q-код с параметрами

n = qμ, N = q²μ, d = μ(q - 1).

(3)

Назовем код C, основанный на разностной матрице D (как описано выше), раз-

ностным матричным кодом, или кратко РМ-кодом. Любой (n, N, {d, n})_q-код, па-

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

ным кодом, или кратко ПРМ-кодом. Ниже мы убедимся, что аддитивные ПРМ-коды

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

лога верхней границы Грея - Рэнкина [13], которого они достигают с точным равен-

ством. Любой q-ичный (n, N, {d, n})_q-код, который можно разбить на тривиальные

(n, q, n)_q-подкоды (называемые симплексами), удовлетворяет этой границе [13]

q(qd - (q - 2)n)(n - d)

≤

(4)

n - ((q - 1)n - qd)²

при условии, что n - ((q - 1)n - qd)² > 0.

Напомним также границу линейного программирования на мощность N кода C,

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

величиной D (см. работы [14] для первого случая границы D = n и [15] для общего

случая). Для D = n эта оценка выглядит следующим образом:

q²d

N ≤

(5)

dq - (q - 1)(n - 1)

если знаменатель положителен. Заметим, что (n, N, {d, n})_q-ПРМ-код достигает этой

границы с точным равенством.

Как мы уже упоминали, мы рассматриваем не только аддитивные коды, но также

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

онно инвариантные коды, т.е. такие, весовой спектр которых не зависит от выбора

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

Напомним, что q-ичная (N ×n)-матрица M называется ортогональной таблицей

силы t индекса λ = N/q^t с n ограничениями и обозначается через OA(N, n, q, t), если

каждая (N × t)-подматрица содержит в качестве строк каждый q-ичный вектор

длины t ровно λ раз [16].

Будем говорить, что (n+1, N, d^∗)_q-код C^∗, где d^∗ ∈ {d, d+1}, получен расширени-

ем (n, N, d)_q-кода C, если ко всем кодовым словам кода C добавлена координатная

позиция общей проверки на четность, т.е.

∑

C^∗ = {(c₁, . . . , c_n, cn+1) : (c₁, . . . , c_n) ∈ C}, где cn+1 =

c_i.

i=1

Следующий результат хорошо известен; его можно найти, например, в [17]. Для

заданного q и натурального m введем величину n_m = (q^m - 1)/(q - 1).

Лемма 4. Пусть H_m - [n_m,k,3]_q-код Хэмминга. Тогда расширенный код H^∗m

имеет минимальное расстояние 4, если и только если

(i) q = 2 и m ≥ 2, или

(ii) q = 2^r ≥ 4 и m = 2, т.е. n_m + 1 = q + 2 и k = q - 1.

Для произвольного (n, N, d)_q -кода C определим его радиус покрытия ρ = ρ_C как

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

кодовых слов C (с центрами в этих словах), покрывают все пространство Qⁿ.

§3. Необходимые условия

Естественный вопрос о существовании q-ичного двухвесового (n, N, {d, d + δ})_q-

кода - это при каких условиях существует такой код? Здесь мы отвечаем на этот

вопрос для случая, когда d + δ = n и код удовлетворяет некоторым условиям регу-

лярности. Нам потребуются некоторые известные факты о проективных двухвесо-

вых кодах (см. работы [1, 7, 8] и библиографию в них). Пусть PG(n, q) обозначает

n-мерное проективное пространство над полем F_q. Тогда m-дуга точек в PG(n, q),

где m ≥ n + 1 и n ≥ 2, - это множество M, содержащее m точек, такое что никакие

n + 1 точек множества M не лежат в гиперплоскости пространства PG(n,q). Ду-

га, содержащая (q + 1) точек PG(2, q), называется овалом, а дуга из (q + 2) точек

пространства PG(2, q) для четного q называется полным овалом, или гиперовалом

(см., например, [18-20]).

Линейный код C называется проективным, если дуальный к нему код C^⊥ имеет

минимальное расстояние d^⊥ ≥ 3 (т.е. любая порождающая матрица C не содер-

жит двух столбцов, являющихся скалярными кратными друг друга). Для проек-

тивных [n, k, d]_q-кодов C можно ввести понятие дополнительного к нему кода C_c

(см., например, [1,7]). Пусть [C] обозначает матрицу, образованную всеми кодовыми

словами кода C (т.е. строками [C] являются[кодовые]слова C). Код Cc называет-

ся дополнительным к коду C, если матрица

[C] | [C_c]

является линейным эквиди-

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

свойство. Для данного [n, k, d]_q-кода C с проверочной матрицей H дополнительный

к нему [n_n-k - n, k, d_c]-код C_c имеет проверочную матрицу H_c, полученную из мат-

рицы H_n-k удалением всех столбцов матрицы H и столбцов, кратных столбцам H.

Напомним важное свойство дополнительного кода: любому кодовому слову веса w

в [n, k, d]_q-коде C соответствует кодовое слово веса w_c = qk-1 - w в дополнитель-

ном к нему коде C_c. Следствием этого простого факта является

Лемма 5 [7]. Линейный [n,k,d]_q-код C с радиусом покрытия ρ = 2, не дуаль-

ный РМ-коду, существует одновременно с дуальным к нему проективным кодом C_c

с тем же самым радиусом покрытия ρ_c = 2.

Обобщение этих хорошо известных фактов на произвольные линейные двухвесо-

вые [n, k, {d, d + δ}]_q-коды было получено в [5, 6]. Здесь мы приводим вариант этого

результата на случай [n, k, {d, n}]_q-кодов. Для любого кода C с проверочной матри-

цей H обозначим через s максимальное число появлений любого столбца H с учетом

кратных к нему столбцов, т.е. полученных из него умножением на ненулевой элемент

поля F_q.

Лемма

[5, 6]. Пусть C - q-ичный линейный нетривиальный двухвесовой

[n, k, {d, n}]_q-код, не дуальный s раз повторенному РМ-коду, и пусть μ₁ и μ₂ обо-

значают число кодовых слов веса d и n соответственно. Тогда существует до-

полнительный к нему линейный двухвесовой [n_c, k, {d_c, d_c + δ}]_q-код C_c, такой что

q^k - 1

n+n_c =s

d + d_c + δ = sqk-1, n = d + δ, s = 1,2,...,

q-1

причем C_c содержит μ₁ кодовых слов веса d_c + δ и μ₂ кодовых сл[в веса d], и Cc

имеет минимально возможную длину n_c, такую что матрица

[C] | [C_c]

пред-

ставляет собой эквидистантный [s(q^k - 1)/(q - 1), k, sqk-1]_q-код.

Заметим, что целое число s в лемме 6 является максимальным числом столб-

цов в порождающей матрице C, которые являются скалярными кратными одного

столбца. Для проективных двухвесовых [n, k, {d, n}]_q-кодов (т.е. для случая s = 1)

известны следующие результаты.

Лемма 7 [8]. Пусть C - проективный двухвесовой [n,k,{w,n}]_q-код над F_q,

где q = p^m и p простое. Тогда существуют два целых числа u ≥ 0 и h ≥ 1, такие

что

w = hp^u, n = (h + 1)p^u.

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

текает из тождеств Мак-Вильямс, если принять во внимание, что дуальный код C^⊥

имеет минимальное расстояние d^⊥ ≥ 3) (см. [8]).

Лемма 8. Пусть C - двухвесовой проективный [n,k,{w,n}]_q-код над F_q, где

q = p^m и p - простое число. Обозначим через μ₁ и μ₂ число кодовых слов кода C

веса w и n соответственно. Тогда

^{wμ₁ + nμ₂ = n(q - 1)qk-1,

(6)

w²μ₁ + n²μ₂ = n(q - 1)(n(q - 1) + 1)qk-2.

В [5, 6] (см. также [4] для специального случая n - d = 1) нами были получе-

ны условия целочисленности, аналогичные условиям, полученным Дельсартом в [8]

(см. также [1]), для проективных двухвесовых кодов на основе простых комбина-

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

графов. Для случая произвольных двухвесовых (n, N, {d, n})_q-кодов с расстояниями

d и n эти условия сводятся к следующему. Как и в работах [8] и [1], мы рассмат-

риваем здесь только двухвесовые (n, N, {d, n})_q-коды мощности N ≥ q². Имеются

тривиальные и нетривиальные примеры таких кодов с N ≤ q², которые мы упомя-

нем ниже. Мы считаем такие коды неинтересными, так как их мощность не всегда

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

кодами мы понимаем также такие двухвесовые коды, которые можно представить

в виде прямой суммы (или повторения) двух или более (n_i, N, {d_i, n_i})_q-кодов.

Теорема 1. Пусть Q - алфавит любого размера q, и пусть C - произвольный

нетривиальный q-ичный двухвесовой (n, N, {d, n})_q-код, где N ≥ q². Тогда

(i) Мощность N кода C лежит в следующих пределах :

q²d

(q - 1)n + 1 ≤ N ≤

(7)

qd - (q - 1)(n - 1)

при условии, что qd - (q - 1)(n - 1) > 0;

(ii) Правое неравенство в (7) становится равенством, если и только если матри-

ца [C], образованная всеми кодовыми словами кода C, является ортогональной

таблицей силы t ≥ 2;

(iii) Если правое неравенство в (7) является равенством, то длина n и расстоя-

ние d кода C имеют следующий вид:

N (q(d + 1) - 1) - q²d

(8)

N (q - 1)

(q - 1)N

d = (n - 1)

;

(9)

q(N - q)

(iv) Левое неравенство в (7) становится равенством, если и только если C -

эквидистантный (n, N, d)_q-код;

(v) Если правое неравенство в (7) является равенством, то число N делит q²d,

а число q - 1 делит (N - 1)d.

Доказательство. (i) Для случая, когда C - произвольный q-ичный двухве-

совой (n, N, {d, n})_q-код, это утверждение следует непосредственно из границы ли-

нейного программирования для этих кодов, которую мы приводим в п. 5.1. Для

случая, когда C - ортогональная таблица силы t ≥ 2, этот результат получается из

аргументов, аналогичных тем, которые мы использовали в [6]. Здесь мы приведем

простое доказательство для общего случая, когда C - произвольный дистанционно

инвариантный (n, N, {d, n})_q-код мощности N ≥ q²; приводимые здесь аргументы

понадобятся нам в дальнейшем.

Предположим, что C содержит нулевое кодовое слово и μ кодовых слов веса d.

Пусть код C^∗ состоит только из кодовых слов веса d, и пусть [C^∗] - матрица размера

μ × n, строками которой являются слова кода C^∗.

Сначала подсчитаем полное число нулей (которое мы обозначим Σ₀) в матри-

це [C^∗] двумя разными (очевидными) способами. Действительно, по определению

Σ₀ = μ(n - d) = (N/q - 1)n.

Далее, так как C дистанционно инвариантен, и следовательно, каждый столбец со-

держит одно и то же число нулей, а именно N/q = μ(n - d)/n + 1, то получаем,

что

n(N - q)

μ=

(10)

q(n - d)

Затем найдем полное число Σ(0,0) пар координатных позиций, содержащих нулевые

элементы (0, 0), которые встречаются во всех n(n - 1)/2 позициях всех строк мат-

рицы [C^∗]. Обозначим через s(i, j) число таких нулевых пар (0, 0), встречающихся

в столбцах с номерами i и j матрицы [C^∗]. Получаем очевидным образом

(

)

∑

-1

n(n - 1) ≤ Σ(0,0) =

s(i, j) = μ(n - d)(n - d - 1).

(11)

q²

1≤i<j=n

Подставляя выражение для μ из (10) в формулу (11), получаем следующее неравен-

ство:

N (qd - (q - 1)(n - 1)) ≤ q²d.

(12)

Отсюда получаем правое неравенство в (7), так как выполняется условие

qd - (q - 1)(n - 1) > 0.

Рассмотрим теперь левое неравенство в (7). Правое неравенство в (7) (которое

имеет место для произвольного двухвесового (n, N, {d, n})_q-кода) влечет следующую

верхнюю оценку на величину d:

N (q - 1)

d ≤ (n - 1)

q(N - q)

Но величина d для (n, N, {d, n})_q-кода не может быть больше величины (обозначим

ее через d(p)), гарантируемой верхней границей Плоткина (2), которая точна для

эквидистантного кода (действительно, средняя оценка по всем расстояниям всегда

больше минимального расстояния кода с несколькими расстояниями). Поэтому из

неравенства

N (q - 1)

(q - 1)N

d ≤ (n - 1)

≤d(p) =n

q(N - q)

q(N - 1)

получаем, что

(n - 1)(N - 1) ≤ n(N - q),

откуда вытекает левое неравенство для N в формуле (7).

(ii) Правое неравенство в (7) становится равенством, если и только если вы-

ражение (11) является равенством. Это имеет место, когда код C удовлетворяет

следующему условию: величина s₀(i, j) = s(i, j) постоянна для любых выбранных

позиций кода с номерами i и j. Мы утверждаем, что это возможно только тогда,

когда матрица [C] является ортогональной таблицей силы t ≥ 2. Предположим про-

тивное - пусть для некоторого элемента a ∈ Q величина s_a(i, j) не одна и та же

для всех i и j. Тогда определим новый код C(a), полученный из C перестановкой

элементов алфавита 0 и a во всех кодовых словах C. Производя для него такие же

вычисления, мы придем к противоречию. Так как величина s_a(i, j) не постоянна в

выражении (7), мы получим строгое неравенство, противоречащее условию утвер-

ждения. Итак, заключаем, что матрица [C] должна быть ортогональной таблицей.

Но если [C] - ортогональная таблица, то тогда s₀(i, j) = s(i, j) является постоянной

величиной для всех i j, выражение (11) представляет собой равенство, и следова-

тельно, правое неравенство в (7) является равенством.

(iii) Если правая часть (7) является равенством, то это означает, что неравен-

ство (11) также является равенством, что можно переписать в следующем виде:

(N - q²)n(n - 1) = qn(N - q)(n - d - 1).

(13)

Поэтому можно выписать выражение для n как функции от q, d и N, получая таким

образом (8), и выражение для d как функции от q, n и N, получая (9).

(iv) Условие N = (q-1)n+1 относится к случаю эквидистантных кодов, подробно

рассмотренному в [21] (в этом случае матрица [C] также является ортогональной

таблицей силы t = 2).

(v) Так как n - натуральное число, мы заключаем из (13), что число d должно

быть кратным N/q². Из этого же равенства, учитывая, что

N (q(d + 1) - 1) - q²d = (q - 1) (N(d + 1) - d(q + 1)) + d(N - 1),

мы заключаем, что d(N - 1) кратно q - 1. ▴

Следующий результат показывает, что существование аддитивного двухвесового

(n, N, {d, n})_q-кода C над алфавитом Q, представляющим собой абелеву группу, на-

кладывает очень сильное условие на эту группу. Порядок группы q, а также струк-

тура группы Q совсем не произвольны. Напомним, что для заданной аддитивно

абелевой группы Q порядком элемента x, обозначаемым через ord(x), называется

=^=0.

t раз

Имеет место следующая

Теорема 2. Пусть Q - абелева группа порядка q, и пусть C - аддитивный

нетривиальный q-ичный двухвесовой (n, N, {d, n})_q-код C над алфавитом Q, содер-

жащий нулевое кодовое слово. Тогда

(i) Все элементы Q имеют один и тот же порядок, т.е. ord(x) = ord(y), для

любой пары ненулевых элементов x, y ∈ Q^∗;

(ii) Группа Q является прямой суммой m циклических групп Z_p, так что

Q=Z_p ⊕Z_p ⊕...⊕Z_p;

(iii) Число q имеет вид q = p^m, где p - простое число, а m - натуральное;

(iv) Код C содержит не менее чем q - 1 слов веса n.

Доказательство. Очевидно, что любая перестановка π элементов Q, такая

что π(0) = 0, примененная к любой позиции кода C, сохраняет свойство кода оста-

ваться двухвесовым (n, N, {d, n})_q-кодом с нулевым кодовым словом. Обозначим че-

рез π перестановку, которая не меняет свойство кода C быть аддитивным, так что

x - y = π(x) - π(y) = π(x - y).

(i) Для заданной пары элементов алфавита x, y ∈ Q^∗ = Q \ {0} и кодового слова

c = (x₁,x₂,...,x_n) ∈ C веса n выберем некоторые перестановки π₁,...,π_n элемен-

тов Q с условием π_i(0) = 0 и такие, что при их применении ко всем координатным

позициям кодового слова c мы получим слово c^′ = (x, y, . . . , y) аддитивного кода

(действительно, применение таких перестановок π_i ко всем координатам не меня-

ет свойство кода быть аддитивным). Предположим, что t = ord(x) = ord(y). Тогда

t-кратная сумма c^′ с самим собой c^′+. . .+c^′ будет равна кодовому слову (0, ty, . . . , ty),

вес которого равен n - 1, так как по предположению ty = 0. Тем самым, приходим

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

порядок.

(ii) Этот факт прямо следует из (i). Действительно, хорошо известно, что любая

абелева группа представляет собой прямую сумму (прямое произведение) цикличе-

ских групп. С другой стороны, любая циклическая группа Zp1p2 имеет элементы

порядка p₁, p₂ и p₁p₂, что противоречит (i) и доказывает утверждение.

(iii) Из (ii) следует, что все p_i равны, откуда получаем утверждение.

(iv) Так как код аддитивен, мы заключаем, что N ≥ qn. Зафиксируем коорди-

натную позицию, скажем, первую. Разобьем все кодовые слова на смежные классы

согласно элементам, стоящим на первой позиции. Каждый смежный класс является

эквидистантным кодом, мощность которого не менее n [21] (откуда следует выше-

приведенное неравенство). Так как код является группой, то ясно, что мы можем

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

Отсюда следует также, что каждый элемент алфавита встречается в столбце одно

и то же число раз.

Пусть μ₁ обозначает число слов кода C веса d, а μ₂ - число слов веса n. Рассмот-

рим сначала случай N = qn. Положим μ = n - d. Тогда можно подсчитать общее

число ненулевых позиций в коде C. Имеем следующие два выражения:

^{μ₁ + μ₂ = N - 1,₍

)

(14)

dμ₁ + nμ₂ = nN 1 -

Выражение для μ₁ из первого уравнения подставим во второе, и учитывая, что

N = nq, приведем его к виду

(

)

d(N - 1 - μ₂) + nμ₂ = nN

= n²(q - 1).

Учитывая, что μ = n - d, получаем

d(qn - 1 - μ₂) + nμ₂ = d(qn - 1) + (n - d)μ₂ = (n - μ)(qn - 1) + μμ₂ = n²(q - 1).

Таким образом, приходим к уравнению

μμ₂ = n(qμ - n) + n - μ.

(15)

Так как обе его части - положительные целые числа, заключаем, что qμ - n ≥ 0.

Поэтому можно положить

qμ = n + λ,

где λ ≥ 0 - целое число. Уравнение (15) можно переписать в следующем виде (где μ

перенесено в левую сторону):

^{qμ = n + λ,

(16)

μ(μ₂ + 1) = (λ + 1)n.

Так как (λ + 1)n ≥ n + λ, то отсюда вытекает, что

μ(μ₂ + 1) ≥ qμ,

или, эквивалентным образом, μ₂+1 ≥ q. Следовательно, мы получаем, что μ₂ ≥ q-1.

Для случая N > qn доказательство не изменяется. ▴

В следующем утверждении мы сформулируем вариант теоремы 2 из [6] для слу-

чая нетривиальных [n, k, {d, n}]_q-кодов, и поэтому это утверждение не нуждается

в доказательстве. Здесь мы предположим, что q = p^m, где m ≥ 1 и p - простое. Для

заданного q = p^m и произвольного натурального числа a обозначим через γ_a ≥ 0

максимальное целое число, такое что pγa делит a, т.е. a = pγa h, где h и p взаимно

просты. Пусть числа γ_d, γ_δ и γ_c определены аналогичным образом для d, δ и d_c со-

ответственно. Напомним, что через (a, b) обозначается наибольший общий делитель

целых чисел a и b.

Теорема 3. Пусть q = p^m, где m ≥ 1 и p - простое число. Пусть C - q-ич-

ный линейный (двухвесовой) [n, k, {d, n}]_q-код размерности k ≥ 2, и пусть C_c -

дополнительный к нему двухвесовой [n_c, k, {d_c, d_c + δ}]_q-код C_c, где

d + δ = n и d + d_c + δ = sqk-1, s ≥ 1.

(i) Если s = 1 и k ≥ 4, т.е. C и, следовательно, C_c - проективные коды, то

справедливы следующие два равенства:

(q, d) = (q, δ) и (q, d_c) = (q, δ);

(17)

(ii) Если s = 1 и k = 3, то оба равенства в (17) имеют место, если справедливо

одно из следующих двух условий:

(d, q)² ≤ q(n(n - 1), q) или (d + δ, q)² > q(n_c(n_c - 1), q);

(iii) Если s = 1 и k ≥ 2, то выполняется по крайней мере одно из следующих двух

равенств:

γ_d = γ_δ или γ_c = γ_δ;

(18)

(iv) Если s ≥ 1 и k ≥ 3, то выполняется по крайней мере одно из двух равенств

в (18) (соответственно, в (17)).

§4. Известные (n, N, {d, n})_q-коды

Здесь мы перечислим все известные нетривиальные аддитивные (n, N, {d, n})_q-

коды. Большинство этих двухвесовых кодов можно найти в подробном обзоре таких

кодов в [1].

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

соответствующего результата из [10], где были приведены все известные полностью

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

антиподальны (т.е. содержат слова веса n). В работе [10] эта теорема была приве-

дена и доказана для случая линейных кодов. Здесь мы сформулируем аналогичный

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

Теорема 4. Пусть C - нетривиальный аддитивный (n,N,{d,n})_q-код мощ-

ности N ≥ q² над Q. Код C можно привести эквивалентными преобразованиями

к коду C^∗ так, чтобы имели место следующие условия:

(i) Для каждого ненулевого кодового слова v ∈ C^∗ веса d каждый элемент a ∈ Q,

который встречается в координатной позиции этого слова v, встречается

в этом слове ровно n - d раз;

(ii) Каждое ненулевое кодовое слово v ∈ C^∗ веса n либо удовлетворяет свой-

ству (i), либо имеет вид v = (a, a, . . . , a), где a ∈ Q;

(iii) Длина n кода C^∗ (а значит, и кода C) кратна n - d.

Напомним, что в § 2, следуя [13], мы назвали тривиальный (n, q, n)_q-код сим-

плексом. Напомним также, что q-ичный дистанционно инвариантный код длины n

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

(n, q, n)_q-код. Ясно, что аддитивный (n, N, {d, n})_q-код, содержащий симплекс, пред-

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

тат можно найти в [13].

Предложение 1. Пусть q-ичный код C длины n c минимальным расстояни-

(q - 1)n

ем d =

имеет мощность N = qn. Тогда этот код C можно представить

в виде объединения непересекающихся симплексов.

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

ный в предложении 1, является ПРМ- или РМ-кодом? Следующее утверждение

дает частичный ответ на этот вопрос.

Теорема 5. Пусть C - дистанционно инвариантный симплексный код с па-

раметрами (n, N, {d, n})_q. Тогда

(i) Код C можно разбить на непересекающиеся подкоды следующим образом:

⋃

C = C_i,

i=1

где C_i для каждого i является симплексом, а мощность N кратна q;

(ii) Для любого кодового слова c ∈ C, отличного от слов вида (a, a, . . . , a), a ∈ Q,

каждый символ α ∈ Q, который встречается на координатной позиции сло-

ва c, встречается на этой позиции ровно μ раз, где μ = n - d, а n кратно

числу μ;

(iii) Расстояние d кода C удовлетворяет неравенству

q-1

d≤n

;

(19)

(iv) Если (19) обращается в равенство и N = qn, то код C представляет собой

ПРМ-код с параметрами

n = μq, N = μq², d = μ(q - 1), μ = n - d;

(v) Если в (iv) код C аддитивен, то он является РМ-кодом.

Доказательство. (i) Так как C содержит в качестве подкода симплекс, со-

держащий нулевое кодовое слово 0, то можно выбрать q - 1 кодовых слов веса n

вида a = (a, a, . . . , a), где a ∈ {1, . . . , q - 1}, которые имеются в C. В противном слу-

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

элементов алфавита. Так как C дистанционно инвариантен, это справедливо для

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

качестве подкода некоторый симплекс, содержащий q-1 кодовых слов веса n. Таким

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

ляет собой симплекс. Ясно, что каждое кодовое слово кода C будет принадлежать

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

могут иметь одно и то же кодовое слово. В самом деле, один из таких симплексов

мы можем сдвинуть в симплекс, содержащий кодовые слова вида a = (a, a, . . . , a).

Ни одно из его слов не может принадлежать другому симплексу, так как все ко-

довые слова из других симплексов находятся на расстоянии d от этого симплекса.

Мы заключаем, что C можно разбить на непересекающиеся подкоды мощности q,

и следовательно, мощность N должна быть кратна q.

(ii) Обозначим через C₀ симплекс, который содержит нулевое кодовое слово и

остальные q - 1 кодовых слов вида a = (a, a, . . ., a). Рассмотрим любое кодовое сло-

во c, не принадлежащее симплексу C₀. Ясно, что каждый элемент a, встречающийся

на координатной позиции слова c, должен встречаться (для того чтобы расстояние

было в точности d от q слов симплекса C₀) ровно n - d раз. Отсюда следует, во-

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

чаться ровно μ = n - d раз, а во-вторых, что число n должно быть кратным n - d.

(iii) Так как на позициях любого кодового слова c, не принадлежащего C₀, име-

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

венство: n ≤ q(n - d). Отсюда вытекает неравенство (19).

(iv) Равенство в (19) означает, что n можно представить в виде n = qμ, где

μ = n - d, и следовательно, d = μ(q - 1). Для этих значений n и d мы заключаем

из оценки (4), что N ≤ q2μ. Если N = qn, то N = q2μ, и согласно [13] код C

представляет собой ПРМ-код, что дает (iv).

(v) Из (iv) мы получили, что C является ПРМ-кодом. Покажем теперь, что ад-

дитивный ПРМ-код является РМ-кодом. Так как C аддитивен, то сумма любых

двух строк, скажем, r₁ и r₂, принадлежит C и содержит на координатных пози-

циях каждый элемент алфавита μ раз (теорема 4). Из кода C строим матрицу D

размера qμ × qμ, содержащую все кодовые слова с нулем на первой позиции, где

μ = n - d. Ясно, что это справедливо, так как C - аддитивный код.

Итак каждая строка D содержит любой элемент Q ровно μ раз (теорема 4), и для

любых двух строк c₁ и c₂ кода D покомпонентная разность этих строк c₁ -c₂ также

принадлежит (по определению слова D имеют 0 в первой позиции) коду D. Любое

кодовое слово c ∈ C с первой ненулевой позицией a ∈ Q получено из D сложе-

нием с вектором (a, a, . . . , a), который принадлежит C, так как C - симплексный

код по условию. Мы заключаем, что D - разностная матрица D(q, n - d), а C -

(n, qn, {d, n})_q-РМ-код. ▴

Замечание 1. Условия n = q(n-d) и N = qn в (iv) и (v) опустить нельзя, как по-

казывает следующий пример. Рассмотрим матрицу [C] = [D⁽⁰⁾ | . . . | D(q-1)]^t, обра-

зованную сдвигами D(i) разностной матрицы D = D(q, μ), где C - (n, N, {d, n})_q-РМ-

код. Если мы удалим одну или несколько таких матриц D(i) из матрицы [C], то по-

лучим дистанционно инвариантный симплексный код некоторой мощности N^∗ < qn,

т.е. нелинейный двухвесовой (n, N^∗, {d, n})_q-код, удовлетворяющий условию теоре-

мы. Аналогично нельзя опустить условие N = qn в (iv) и (v). Например, линейный

код Боуза - Буша имеет длину (см. ниже) n < q(n - d). Аналогично, аддитивный

(n, N, {d, n})_q-код не обязательно должен иметь мощность q^k. Так, например, раз-

ностная матрица D(4, 2) индуцирует оптимальный аддитивный (8, 32, {6, 8})₄-код

мощности N = 4^k.

Замечание 2. Случай кодов мощности N = q² также очень специален. Хоро-

шо известный результат гарантирует, что r - 2 взаимно ортогональных латинских

квадратов порядка q индуцирует (r, q², {r - 1, r})_q-код. Для случая, когда q - сте-

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

индуцирующих линейный эквидистантный [q + 1, 2, q]_q-код (обратное утверждение

также имеет место для любой длины r ≥ 2 и также хорошо известно). Используя

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

мой суммы (используя разбиения на симплексы) (n, q², {d, n})_q-код для любых на-

туральных d = n - s и n = r₁ + . . . + r_s, рассматривая прямую сумму s исходных

(r_i, q², {r_i-1, r_i})_q-кодов латинских квадратов. Поэтому мы исключили (как и в [1,8])

все эти тривиальные коды, за исключением (r, q², {r - 1, r})_q-кодов длины r ≤ q,

которые индуцируются r - 2 взаимно ортогональными латинскими квадратами по-

рядка q. Кроме того, имеются еще, конечно, [q +2, 2, {q +1, q +2}]_q-коды, полученные

из эквидистантных [q + 1, 2, q]_q-кодов добавлением одной позиции (см [4]).

Теперь мы можем привести все известные семейства нетривиальных аддитивных

(n, N, {d, n})_q-кодов, которые были приведены в обзоре [1] (а также были указа-

ны в [10] для линейного случая). Если исключить коды, образованные латинскими

квадратами, то все известные (n, N, {d, n})_q-коды делятся на два больших класса

кодов: разностно-матричные (n = qμ, N = qn, {(q - 1)μ, qμ})_q-коды, длина n кото-

рых кратна q, и [n, k, {d, n}]_q-коды Деннистона длины n, такой что n - 1 кратно

(qk-1 - 1)/(q - 1).

Разностно-матричные коды (РМ-коды). Это (qμ, q²μ, {(q - 1)μ, qμ})_q-коды [12],

индуцированные разностными матрицами. Лемма 1 описывает построение таких

кодов для значений q = p^h и μ = p^ℓ, где p - простое, а h и ℓ - произвольные

натуральные числа.

Следует заметить, что эти коды включают в себя (двоичные) (4m, 8m, {2m, 4m})-

коды Адамара. Действительно, двоичная (т.е. состоящая из элементов 0 и 1) матрица

Адамара является разностной матрицей D(2, 2m).

Коды Деннистона. Это [n = 1 + (q + 1)(h - 1), 3, {q(h - 1), n}]_q-коды, где 1 < h < q

и h делит q, для q = 2^r ≥ 4 (см. семейство TF2 в [1]). В теореме 1 этот случай

соответствует расстоянию d = n - h + 1 = (n - 1)q/(q + 1), из которого следует,

что N = q³. Для случая h = 2 мы получаем [n = q + 2, 3, {q, n}]_q-коды Боуза -

Буша (см. семейство TF1 в [1]), построенные в 1952 г. [11], которые индуцируют-

ся гиперовалами в P G(3, q). Значению h = q/2 соответствуют [n = q(q - 1)/2, 3,

{q(q - 2)/2, n}]_q-коды Дельсарта [7] (см. семейство TF1^d в [1]), построенные незави-

симо в 1971 г., которые проективно дуальны кодам Боуза - Буша [1].

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

стях [18] (см. также [19, 20]). Коротко объясним, как построить такие коды для

произвольного q = 2^m ≥ 4 и натурального h ≥ 2, делящего q, т.е. h = 2^u ≤ q/2. Для

заданного F_q пусть H обозначает подгруппу порядка h аддитивной группы поля F_q.

Пусть ϕ(x, y) = ax² + bxy + cy² - неприводимая квадратичная форма над F_q. Тогда

[n, 3, {d, n}]_q-код Деннистона порождается следующей (3 × n)-матрицей:

]

^[1

G_d = x₁ x₂ . . . x_n

(20)

y₁

y₂

... y_n

где n = (q + 1)(h - 1) + 1, d = n - h, а (x_i, y_i) - все упорядоченные пары элементов

поля F_q, которые отображаются в H, т.е. ϕ(x_i, y_i) ∈ H.

Приведем также порождающие матрицы для кодов Боуза - Буща, а также кодов

Дельсарта, так как они приводятся в явном виде. Пусть матрица G имеет вид

]

^[1

G= 0 1 0 x₀ x₁ ... x_i ... xq-2

(21)

y₀

y₁

... y_i ... yq-2

где x_i и y_i пробегают все ненулевые элементы поля F_q. Тогда, если y_i = x2i, то

матрица G порождает код Боуза - Буша. Если же x_i и y_i пробегают все упорядочен-

ные пары ненулевых элементов (x_i, y_i) (число таких различных пар равно, очевидно,

(q-1)×q/2, т.е. длине кодов Дельсарта), такие что Tr(x_iy_i) = 1, где Tr(x) - функция

следа из F_q в поле F₂, т.е.

Tr(x) = x + x² + x⁴ + . . . + xq/2,

то матрица G порождает код Дельсарта.

Теорема 6. Пусть C - аддитивный нетривиальный (n,N,{d,n})_q-код, где

q = p^m, p - произвольное простое число и m = 1,2,... Предположим, что N ≥ q²

и n > 2. Тогда параметры этого кода совпадают с параметрами кода, принадле-

жащего одному из семейств указанных выше кодов.

Доказательство. Так как C - нетривиальный аддитивный код, то он имеет

мощность N = q²μ ≥ q².

Начнем со случая N = q². Для любого натурального q существование r попарно

ортогональных латинских квадратов влечет существование (r + 2, q², {r + 1, r + 2})_q-

МДР-кода (см. также замечание 2). Эти коды включают в себя самые короткие

нетривиальные (q, q², {q - 1, q})_q-РМ-коды, которые существуют для любой степени

простого числа q и совпадают с кодами по латинским квадратам. Еще раз подчерк-

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

(n, q², {d, n})_q-кодов, указанных в замечаниях выше, которые мы не рассматриваем.

Напомним также, что так как C аддитивен, то все ПРМ-коды согласно теореме 5

являются РМ-кодами.

Теперь докажем, что для случая N = q²μ, где 2 ≤ μ < q, нетривиальный адди-

тивный (n, N, {d, n})_q-код C есть не что иное, как (qμ, q²μ, {(q - 1)μ, n})_q-код ПРМ

или РМ. Следующий аргумент использовался в [13] (см. также [21]), где были вве-

дены q новых кодов C_j , j = {0, 1, . . . , q - 1}, полученных из C выбором всех кодовых

слов кода C, имеющих элемент j на первой позиции, и затем удалением этой пер-

вой позиции. Легко видеть [13], что каждый код C_j имеет только одно расстояние,

а именно d. Следовательно, C_j - эквидистантный (n₀, N₀, d₀)_q = (n - 1, qμ, d)_q-код

мощности N₀ = qμ. Более того, параметры этого кода достигают верхней грани-

цы Плоткина (2) с точным целочисленным равенством, и следовательно, каждый

символ i алфавита {0, 1, . . . , q - 1} встречается одно и то же число раз (а имен-

но μ) в каждой позиции всех кодовых слов кода C_j (см. [21]). Теперь применим

теорему 4, которая утверждает, что каждое кодовое слово c кода C_j содержит все

элементы i = j алфавита как координатные элементы ровно μ раз, а элемент j -

ровно μ - 1 раз.

Так как C - аддитивный код, то его подкод C₀ также является аддитивным

кодом, удовлетворяющим следующему свойству: каждое ненулевое слово кода C₀

содержит каждый ненулевой элемент алфавита ровно μ раз. Мы заключаем, следо-

вательно, что по теореме 5 код C₀ станет разностной матрицей, если мы добавим

ко всем словам кода C₀ нулевые позиции. Из свойства аддитивности вытекает, что

любой подкод C_j представляет собой сдвиг кода C₀. Таким образом, C является

РМ-кодом.

Рассмотрим теперь случай N = q³. Сначала покажем, что в кодах Деннистона

число h должно делить q. Из теоремы 5 заключаем, что n кратно n-d. Следователь-

но, n можно представить в виде n = (n - d)ℓ для некоторого натурального числа ℓ.

Поэтому d = n(ℓ - 1)/ℓ, и мы получаем из (19), что

ℓ-1

q-1

d=n

≤n

ℓ

откуда следует, что ℓ ≤ q. Но случай ℓ = q дает РМ-код. Мы заключаем, следова-

тельно, что ℓ < q. Предположим теперь, что

n = 1 + (q + 1)(h - 1) и d = q(h - 1)

для некоторого натурального числа h ≥ 2. Это означает, что

n = q(h - 1) + h = d + h.

Таким образом, объединяя равенства

ℓ-1

n = 1 + (q + 1)(h - 1) и d = q(h - 1) = n

ℓ

получаем

ℓ-1

q(h - 1) = (q(h - 1) + h)

ℓ

откуда вытекает, что h(ℓ - 1) = q(h - 1). Так как h ≥ 2, и следовательно, h и h - 1

взаимно просты, мы заключаем, что h делит q, откуда следует, что получается код

с параметрами кода Деннистона.

Случай N > q³ исключается из аналогичных аргументов. Сначала рассматрива-

ется случай N = q³μ, где 2 ≤ μ < q. Напомним, что q = p^m. Мы утверждаем, что

в этом случае могут получиться только РМ-коды. Действительно, для всех значе-

ний μ = p^r, где 0 < r < m, существует (q²μ, q³μ, {q(q - 1)μ, n})_q-РМ-код. В § 2 мы

описали построение всех таких кодов (см. текст после леммы 1), которое можно най-

ти в [12]. Убедимся, почему это единственно возможные случаи. Деля обе стороны

выражения (8) на q³μ, мы получим, что d = n(q - 1)/q, поэтому это должна быть

разностная матрица. Следовательно, для случая, когда d = n(q - 1)/q, который

(для случая q³μ) эквивалентен условию d = q(q - 1)μ, мы не получим целочис-

ленное равенство в (8). Так как повторение s копий РМ-кода не меняет равенства

d = n(q - 1)/q, заключаем, что вышеуказанный нетривиальный РМ-код является

единственным нетривиальным кодом для этих значений N.

Рассмотрим теперь случай N = q⁴, который дает линейные разностно-матричные

коды [12]. В самом деле, имея такой [n, 4, {d, n}]_q-код C, можно построить (как мы

делали это раньше, например, в теореме 5) код C₀, представляющий собой линейный

эквидистантный [n - 1, 3, d]_q-код длины n - 1 = (q⁴ - 1)/(q - 1) с расстоянием d = q³,

дуальным к которому является q-ичный совершенный код Хэмминга.

Покажем теперь, что для случая N = q⁴ не существует кодов типа Деннистона.

По теореме 4 длина кода типа Деннистона должна иметь вид n = s(q³ -1)/(q-1)+1.

Так как n кратно n - d (см. снова теорему 4), то это выражение принимает вид

n = dℓ/(ℓ-1) для некоторого натурального ℓ ≤ q. Учитывая, что d = sq², получаем

q³ - 1

ℓ

n=s

+1=d

= sq²

(22)

q-1

ℓ-1

Теперь следует рассмотреть отдельно случаи (s, q - 1) = 1 и (s, q - 1) ≥ 2.

Пусть вначале (s, q - 1) = 1. Тогда мы видим, что выражение для n в левой

части (22) не делится на s и на q, а в правой части оно делится на оба эти числа.

Мы заключаем, следовательно, что коды такого типа не существуют.

Рассмотрим теперь случай (s, q - 1) ≥ 2. Для случая s = q - 1 получаем, что

n = q³, и так как N = q⁴, т.е. N = qn, то заключаем, что C является РМ-кодом.

Предположим теперь, что s = u(q-1), где u ≥ 2. Используя это s в (22), приходим

к равенству

q³ - 1

ℓ

u(q - 1)

+ 1 = u(q - 1)q²

q-1

ℓ-1

которое после упрощения и умножения обеих сторон на (ℓ-1) принимает следующий

вид:

(ℓ - 1)(u(q³ - 1) + 1) = ℓu(q³ - q²).

Упрощая, приходим к неравенству

0 ≤ uq²(q - ℓ) = -uℓ + (u + ℓ) - 1 ≤ -1,

что невозможно, так как 2 ≤ ℓ ≤ q и u ≥ 2, что завершает рассмотрение случая

N =q⁴.

Случай q⁴ < N < q⁵ рассматривается аналогично. Здесь мы имеем только адди-

тивные РМ-коды для значений n = q⁴μ, где μ пробегает все степени p и q = p^m.

Случай N = q^k для k ≥ 5 можно рассмотреть аналогичным образом, и мы его

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

Теперь следует сделать несколько замечаний для случая, когда q - степень про-

стого нечетного числа. Буш в 1952 г. доказал в [22] несуществование [q+2, 3, q]_q-кодов

для нечетного q, что влечет несуществование [q(q - 1)/2, 3, {q(q - 2)/2, q(q - 1)/2}]_q-

кодов Дельсарта, так как они проективно дуальны друг другу (см. семейства TF1

и TF1^d в [1]). Затем в 1997 г. в [23] было доказано несуществование максималь-

ных дуг (на которых основаны коды Деннистона) в дезарговых плоскостях PG(2, q)

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

стона для нечетных q. ▴

§5. Верхние границы

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

A_q(n; {d, n}) = max{N : ∃(n, N, {d, n})-код},

т.е. границы на максимально возможную мощность кода в Q^nq с двумя расстояниями

d и n.

5.1. Границы линейного программирования. Мы провели всестороннее исследо-

вание границы линейного программирования (ЛП) Дельсарта на A_q(n; {d, n}), ис-

пользуя эту границу в следующем виде. Определим многочлены Кравчука

)

n(1 - t)

⁽n

Q(n,q)i(t) =

K(n,q)i(z), z =

ri = (q - 1)ⁱ

где

∑

⁽z⁾⁽n - z⁾

K(n,q)i(z) =

(-1)^j (q - 1)^i-j

i-j

j=0

представляют собой (обычные) многочлены Кравчука. Для вещественного много-

члена f(t) степени не выше n рассмотрим его разложение

∑

f (t) =

f_iQ(n,q)i(t)

(23)

i=0

по многочленам Кравчука.

Теорема 7. Пусть n ≥ q ≥ 2, и пусть f(t) ∈ R[t] - многочлен степени не

выше n, такой что:

(A1) f(-1) ≤ 0 и f(1 - 2d/n) ≤ 0;

(A2) Коэффициенты в разложении (23) удовлетворяют условиям f₀ > 0 и f_i ≥ 0

для каждого i ≥ 1.

Тогда A_q(n; {d, n}) ≤ f(1)/f₀. Если (n, N, {d, n})_q-код C достигает этой границы

для некоторого f(t), то f(1 - 2d/n) = f(-1) = 0 и f_iM_i(C) = 0 для каждого i ≥ 1,

где

∑

M_i(C) =

Q(n,q)i(1 - 2d(x, y)/n).

(24)

x,y∈C

Граница линейного программирования из нашей работы [6] (формула (40)), ко-

торая была выведена для δ = n - d, дает для нашего случая оценку (5) (которая

в точности представляет собой верхнюю границу в (7)). Это дает нам простое дока-

зательство необходимого условия в утверждении (ii) теоремы 4.

Второе доказательство утверждения (ii) теоремы 1. Верхняя граница в (5) полу-

чена с помощью теоремы 1 с использованием многочлена f(t) = (t - 1 + 2d/n)(t + 1)

второй степени. Если эта оценка достигается (n, N, {d, n})_q-кодом C, то из условий

теоремы 7 следует, что M₁(C) = M₂(C) = 0, так как f₁ > 0 и f₂ > 0. Это означа-

ет, что код C является ортогональной таблицей силы 2. Мы заключаем очевидным

образом, что мощность N кода C, т.е. величина

N =

qd - (q - 1)(n - 1)

делится на q² и что d делится на qd - (q - 1)(n - 1). ▴

Численные результаты дают несколько общих ЛП-границ для специальных слу-

чаев семейств параметров q, n, d. Одну из них (другие оценки кажутся слабее) мы

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

но полученной в работе [24], для диапазона чуть вне диапазона границы Плоткина.

Теорема 8. Для каждого натурального числа m ≥ 2 имеет место неравен-

ство

A₂(4m + 1, {2m, 4m + 1}) ≤ 4m + 2.

(25)

Доказательство. Используем теорему 7 для длины n = 4m+1 и расстояния

d = 2m с многочленом

f (t) = 1 + 2mQ(4m+1,2)2(t) + (2m + 1)Q(4m+1,2)4m-1(t).

(26)

Условие (A2) очевидным образом выполняется. Докажем, что условие (A1) выпол-

няется с равенствами.

Из условия Q(n,2)i(-1) = (-1) получаем f(-1) = 0. Так как 1-2d/n = 1/(4m+1),

рассмотрим выражение

(

)

∑

⁽2m⁾⁽2m + 1⁾

=1+

(-1)^j

4m + 1

⁽ 4m + 1⁾

2-j

j=0

)

∑

2m + 1

⁽2m⁾⁽ 2m + 1

(-1)^j

⁽ 4m + 1⁾

4m - 1 - j

j=0

4m - 1

Первую сумму можно подсчитать непосредственно, и она равна -2m/(4m+1). Для

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

биномиальных коэффициента ненулевые, - это 2m - 2 ≤ j ≤ 2m. Отсюда приходим

к равенству f(1/(4m + 1)) = 0.

Таблица 1

Оптимальные многочлены с одним ненулевым коэффициентом, q = 3

sb3(n, d)

152

153

224

225

Вычисление соответствующих моментов M_i(C), заданных выражением (24), дает

равенство M₂(C) = M4m-1(C) = 0 (так как f₂ > 0 и f2m+1 > 0) для любого (4m + 1,

4m + 2, {2m, 4m + 1})-кода, достигающего этой оценки. ▴

5.2. Численные вычисления верхних оценок линейного программирования. Здесь

мы представим ЛП-границы для величины A_q(n, {d, n}), полученные прямым вычис-

лением ЛП-границы с помощью симплекс-метода с использованием программного

пакета Maple 19. Используемый алгоритм был применен нами для каждого q ≤ 5 и

n ≤ 50. Имеется много случаев, для которых наилучшие оценки получались с помо-

щью многочленов степени 1 и 2, приводящих к уже существующим оценкам. Поэто-

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

с помощью многочленов степени 3 или выше. Более того, мы исключили границы на

все тривиальные коды мощности 4 или менее, границу, заданную выражением (5),

а также все границы, значения которых не являются натуральными числами. На-

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

сферических кодов (см. п. 5.3 ниже), лучше, или которые соответствуют случаю,

включенному в теорему 8.

Нашу ЛП-границу мы нормализовали, положив f₀ = 1, и поэтому оценка, зада-

ваемая допустимым многочленом f, выглядит следующим образом:

A_q(n, {d, n}) ≤ 1 + f₁ + f₂ + . . . + f_n,

в точности как и в классической формулировке Дельсарта границы линейного про-

граммирования. Во всех интересных случаях только один или два коэффициента f_i

не равны нулю. Отметим, что благодаря специфике ЛП-границы мы не ожидаем

большого числа ненулевых коэффициентов, и на самом деле, мы не увидели ни од-

ного случая с тремя или более ненулевыми коэффициентами.

Обозначим через sb_q(n, d) наилучший численный результат, полученный указан-

ным выше путем, для величины A_q(n, {d, n}). Так как все случаи для q = 2 уже

покрыты указанными выше исключениями и результатами из работы [24], мы нач-

нем наш обзор результатов по интересующей нас ЛП-границе с q = 3.

Результаты для q = 3. Как и для двоичного случая, для случая q = 3 среди мно-

жеств числовых параметров, содержащих только один ненулевой коэффициент (не

считая, конечно, f₀ = 1) в разложении по многочленам Кравчука оптимального мно-

гочлена, мы наблюдали только коэффициент f₃. Это означает, что ЛП-многочлен

имеет вид f(t) = 1+f₃Q(n,3)3(t). Все эти многочлены, кроме одного, имеют d, близкое

к n/2. Все эти результаты систематизированы в табл. 1.

Остальные случаи, где мы имели два ненулевых коэффициента, кроме обязатель-

ного значения f₀ = 1, приведены в табл. 2.

Наконец, мы приводим два случая многочленов

f (t) = 1 + f₅Q(n,3)5(t)

Таблица 2

Оптимальные многочлены с двумя ненулевыми коэффициентами, q = 3

Ненулевые

sb3(n, d)

коэффициенты

f2 = 6, f3 = 20

f2 = 12, f3 = 20

f3 = 113, f4 = 210

324

f3 = 208, f4 = 400

609

f3 = 320, f4 = 624

945

f3 = 4, f5 = 16

Таблица 3

Оптимальные многочлены для q = 4

Ненулевые

sb4(n, d)

коэффициенты

f1 = 3/4, f3 = 81/4

f3 = 27

f1 = 1/2, f3 = 45/2

f2 = 12, f3 = 63

f3 = 81

f2 = 33, f3 = 126

160

f2 = 57, f3 = 198

256

f3 = 615

616

для (n, d) = (46, 23) и (48, 24), что дает

sb₃(46, 23) = 2753 и sb₃(48, 24) = 3009

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

Результаты для q = 4. Для q = 4 мы нашли оптимальные многочлены почти

полностью третьей степени, всего восемь таких случаев, как показано в табл. 3.

Единственный случай, отличный от приведенных в табл. 3, был многочлен пятой

степени

f (t) = 1 + 75Q(18,4)4(t) + 468Q(18,4)5(t),

который дает

sb₄(18, 9) = 544.

Результаты для q = 5. Найденные нами для случая q = 5 оптимальные много-

члены приведены в табл. 4.

5.3. Верхние границы с помощью сферических кодов. Взаимосвязь между кодами

с двумя расстояниями в множестве Q^nq и сферическими кодами с двумя расстояни-

ями на евклидовой сфере Sn-1 (описанной, например, в [6, раздел 4.3]) влечет, что

каждый (n, N, {d, n})_q-код C ⊂ Q^nq соответствует сферическому коду с двумя рассто-

яниями W ⊂ S(q-1)n-1. Квадраты расстояний между точками W равны 2dq/(q - 1)n

и 2q/(q - 1). Используя классический результат работы [25], а также результаты

из [6], мы заключаем, что либо

(k - 1)n

(27)

[

√

]

для некоторого натурального k ∈

2, (

2(q - 1)n + 1)/2

(и число n очевидным

образом делится на k), либо мощность N ограничена сверху неравенством N ≤

≤ 2(q - 1)n + 1.

Для произвольного q ≥ 3 выражение (27) при k > q влечет, что d > (q -1)n/q, т.е.

величина d находится в диапазоне границы Плоткина. Используя оценку Плоткина,

получаем, что ее можно записать в виде N ≤ (k-1)q/(k-q). Эти наблюдения можно

суммировать следующим образом.

Таблица 4

Оптимальные многочлены для q = 5

Ненулевые

sb5(n, d)

коэффициенты

f1 = 4/3, f3 = 128/3

f3 = 64

f1 = 1, f3 = 48

f2 = 40, f3 = 224

265

f3 = 304

305

f3 = 624,

625

f2 = 92, f3 = 432

525

f3 = 1984

1985

f2 = 152, f3 = 672

825

f3 = 32, f4 = 2272

2405

f3 = 1696, f4 = 6528

8225

Теорема 9. Если C - (n,N,{d,n})_q-код, то либо

N ≤ 2(q - 1)n + 1,

либо

d = (k - 1)n/k,

[

√

]

где k ∈

2, (

2(q - 1)n + 1)/2

- натуральное число, и более того, имеет место

неравенство

(k - 1)q

N ≤

k-q

√

для q ≥ 3 и q < k ≤ (

2(q - 1)n + 1)/2.

Дальнейший набор оценок (для применения их к различным режимам для d и n)

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

которые были рассмотрены и использованы в [26]. Отметим, что работа [26] имеет

дело только с двоичными кодами, но при этом лемму 3.3 и теорему 3.5 из этой

работы можно также применять и для q ≥ 3. Хотя мы интересуемся здесь случаем,

когда расстояния равны d и n, другие случаи также следуют из этих результатов.

В дальнейшем предположим, что q ≥ 3.

В этом месте будет удобно переключится на скалярные произведения для точек

сферического кодов. Легко видеть, что скалярные произведения α и β, -1 < α <

< β < 1, для точек из множества W равны

n(q - 1) - dq

α=-

β=

q-1

n(q - 1)

Теперь из [26, лемма 3.3] вытекает, что если d > n(q-2)/q (это эквивалентно условию

α + β < 0), то

)

⁽n(q - 1)

A_q(n, {d, n}) ≤

за исключением (возможно) случаев n(q - 1) = γ² - 2 и n(q - 1) = γ² - 3, где γ :=

:= (n - d)q/n(q - 1) - целое нечетное число. Аналогично [26, теорема 3.5] (первона-

чально полученная в [27]) дает оценку

n(q - 1) + 2

A_q(n, {d, n}) ≤

1 - (n(q - 1) - 1)(q - 1)²/dq

которая справедлива для dq > (n(q - 1) - 1)(q - 1)².

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

Calderbank R., Kantor W.M. The Geometry of Two-Weight Codes // Bull. London Math.

Soc. 1986. V. 18. № 2. P. 97-122. https://doi.org/10.1112/blms/18.2.97

Shi M., Guan Y., Solé P. Two New Families of Two-Weight Codes // IEEE Trans. Inform.

Theory. 2017. V. 63. № 10. P. 6240-6246. https://doi.org/10.1109/TIT.2017.2742499

Boyvalenkov P., Delchev K., Zinoviev D.V., Zinoviev V.A. Codes with Two Distances:

d and d + 1 // Proc. 16th Int. Workshop on Algebraic and Combinatorial Coding Theory

(ACCT-XVI). Svetlogorsk, Kaliningrad region, Russia. Sept. 2-8, 2018. P. 40-45. Available

at https://www.dropbox.com/s/h7u89lh8vyirww9.

Бойваленков П., Делчев К., Зиновьев Д.В., Зиновьев В.А. О q-ичных кодах с двумя

расстояниями d и d + 1 // Пробл. передачи информ. 2020. Т. 56. № 1. С. 38-50. https:

//doi.org/10.31857/S0555292320010040

Boyvalenkov P., Delchev K., Zinoviev D.V., Zinoviev V.A. Two-Weight (Linear and Non-

linear) Codes // Proc. 17th Int. Workshop on Algebraic and Combinatorial Coding Theory

(ACCT’2020). On-line, Bulgaria. Oct. 11-17, 2020. P. 11-17. https://doi.org/10.1109/

ACCT51235.2020.9383353

Boyvalenkov P., Delchev K., Zinoviev D.V., Zinoviev V.A. On Two-Weight Codes // Dis-

crete Math. 2021. V. 344. № 5. Paper No. 112318 (15 pp.). https://doi.org/10.1016/j.

disc.2021.112318

Delsarte P. Two-Weight Linear Codes and Strongly Regular Graphs // MBLE Research

Lab. Report R160. Brussels, Belgium, 1971.

Delsarte P. Weights of Linear Codes and Strongly Regular Normed Spaces // Discrete Math.

1972. V. 3. № 1-3. P. 47-64. https://doi.org/10.1016/0012-365X(72)90024-6

Landjev I., Rousseva A., Storme L. On Linear Codes of Almost Constant Weight and the

Related Arcs // C. R. Acad. Bulgare Sci. 2019. V. 72. № 12. P. 1626-1633. https://doi.

org/10.7546/CRABS.2019.12.04

10.

Borges J., Rifà J., Zinoviev V.A. On q-ary Linear Completely Regular Codes with ρ = 2

and Antipodal Dual // Adv. Math. Commun. 2010. V. 4. № 4. P. 567-578. https://doi.

org/10.3934/amc.2010.4.567

11.

Bose R.C., Bush K.A. Orthogonal Arrays of Strength Two and Three // Ann. Math. Statist.

1952. V. 23. № 4. P. 508-524. https://doi.org/10.1214/aoms/1177729331

12.

Семаков Н.В., Зиновьев В.А., Зайцев Г.В. Класс максимальных эквидистантных ко-

дов // Пробл. передачи информ. 1969. Т. 5. № 2. С. 84-87. http://mi.mathnet.ru/

ppi1804

13.

Бассалыго Л.А., Додунеков С.М., Зиновьев В.А., Хеллесет Т. Граница Грея - Рэнкина

для недвоичных кодов // Пробл. передачи информ. 2006. Т. 42. № 3. С. 37-44. http:

//mi.mathnet.ru/ppi51

14.

Helleseth T., Kløve T., Levenshtein V.I. A Bound for Codes with Given Minimum and

Maximum Distances // Proc. 2006 IEEE Int. Symp. on Information Theory (ISIT’2006).

Seattle, WA, USA. July 9-14, 2006. P. 292-296. https://doi.org/10.1109/ISIT.2006.

261600

15.

Boyvalenkov P.G., Dragnev P.D., Hardin D.P., Saff E.B., Stoyanova M.M. Universal

Bounds for Size and Energy of Codes of Given Minimum and Maximum Distances // IEEE

Trans. Inform. Theory. 2021. V. 67. № 6. P. 3569-3584. https://doi.org/10.1109/TIT.

2021.3056319

16.

Beth T., Jungnickel D., Lenz B. Design Theory. Cambridge, UK: Cambridge Univ. Press,

1986.

17.

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

Связь, 1979.

18.

Denniston R.H.F. Some Maximal Arcs in Finite Projective Planes // J. Combin. Theory.

1969. V. 6. № 3. P. 317-319. https://doi.org/10.1016/S0021-9800(69)80095-5

19. Thas J.A. Construction of Maximal Arcs and Partial Geometry // Geom. Dedicata. 1974.

V. 3. № 1. P. 61-64. https://doi.org/10.1007/BF00181361

20. Thas J.A. Projective Geometry over a Finite Field // Handbook of Incidence Geometry:

Buildings and Foundations. Amsterdam: Elsevier, 1995. Ch. 7. P. 295-347. https://doi.

org/10.1016/B978-044488355-1/50009-8

21. Семаков Н.В., Зиновьев В.А. Эквидистантные q-ичные коды с максимальным рассто-

янием и разрешимые уравновешенные неполные блок-схемы // Пробл. передачи ин-

форм. 1968. Т. 4. № 2. С. 3-10. http://mi.mathnet.ru/ppi1845

22. Bush K.A. Orthogonal Arrays of Index Unity // Ann. Math. Statist. 1952. V. 23. № 3.

P. 426-434. https://doi.org/10.1214/aoms/1177729387

23. Ball S., Blokhuis A., Mazzocca F. Maximal Arcs in Desarguesian Planes of Odd Order

Do Not Exist // Combinatorica. 1997. V. 17. № 1. P. 31-41. https://doi.org/10.1007/

BF01196129

24. Landjev I., Rousseva A., Vorobev K. Constructions of Binary Codes with Two Distances.

Preprint, 2022.

25. Larman D.G., Rogers C.A., Seidel J.J. On Two-Distance Sets in Euclidean Space // Bull.

London Math. Soc. 1977. V. 9. № 3. P. 261-267. https://doi.org/10.1112/blms/9.3.261

26. Barg A., Glazyrin A., Kao W.-J., Lai C.-Y., Tseng P.-C., Yu W.-H. On the Size of Maximal

Binary Codes with 2, 3, and 4 Distances, https://arXiv.org/abs/2210.07496 [math.CO],

2022.

27. Glazyrin A., Yu W.-H. Upper Bounds for s-Distance Sets and Equiangular Lines // Adv.

Math. 2018. V. 330. P. 810-833. https://doi.org/10.1016/j.aim.2018.03.024

Бойваленков Петър

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

Делчев Константин

14.11.2022

Институт математики и информатики

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

Болгарской академии наук, София, Болгария

25.11.2022

peter@math.bas.bg

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

kdelchev@math.bas.bg

28.11.2022

Зиновьев Виктор Александрович

Зиновьев Дмитрий Викторович

Институт проблем передачи информации

им. А.А. Харкевича РАН, Москва

vazinov@iitp.ru

dzinov@iitp.ru