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

Том 56

2020

Вып. 1

УДК 621.391.15

П. Бойваленков¹, К. Делчев², Д.В. Зиновьев³, В.А. Зиновьев³

О q-ИЧНЫХ КОДАХ С ДВУМЯ РАССТОЯНИЯМИ d И d + 1

Рассматриваются q-ичные блоковые коды с ровно двумя расстояниями: d и

d+1. Приведено несколько конструкций таких кодов. В линейном случае пока-

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

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

кодов. Приведены таблицы нижних и верхних границ для малых значений q и n.

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

для кодов.

DOI: 10.31857/S0555292320010040

§ 1. Введение

Положим Q = {0, 1, . . ., q - 1}. Любое подмножество C ⊆ Qⁿ называется кодом

и обозначается через (n, N, d)_q - код длины n и мощности N = |C| с минимальным

расстоянием (Хэмминга) d. Для линейных кодов используется обозначение [n, k, d]_q

(т.е. N = q^k). Эквидистантным называется (n, N, d)_q-код C, у которого для любых

двух различных кодовых слов x и y имеет место равенство d(x, y) = d, где d(x, y) -

расстояние (Хэмминга) между x и y. Код C называется равновесным и обозначается

через (n, N, w, d)_q , если каждое кодовое слово c имеет вес wt(c) = w.

Мы рассматриваем коды, имеющие только два расстояния: d и d + 1. Одна из

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

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

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

зие кодов значительно увеличивается по сравнению с эквидистантными кодами. Та-

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

амплитудно-фазовой модуляции (поскольку они почти эквидистантны). Мы также

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

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

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

с двумя последовательными расстояниями.

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

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

ношение d(x, y) ∈ {d, d + 1}. Нас будут интересовать конструкции, классификация и

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

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

сти” (ICTinSES) Министерства образования и науки Болгарии. Часть исследования была выпол-

нена во время визита первого автора в отделение математических наук Университета Пердью в

Форт-Уэйне.

² Работа выполнена при финансовой поддержке Национальной программы “Молодые ученые и

постдокторанты” Министерства образования и науки Болгарии.

³ Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных

исследований (номер проекта 19-01-00364).

границы на максимально возможный размер (n, N, {d, d + 1})_q-кодов. Мы покажем,

что линейные q-ичные коды с двумя расстояниями d и d + 1 полностью известны

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

Предварительные результаты этой статьи (а именно, двоичный случай и гипоте-

за для q ≥ 3) были приведены в [1]. Одновременно с нами этот же результат для

линейных q-ичных кодов мощности N ≥ q³ был доказан в [2] другим методом.

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

Напомним следующую классическую границу Джонсона на размер N_q(n, d, w)

q-ичного равновесного (n, N, w, d)_q-кода [3]:

(q - 1)dn

N_q(n, d, w) ≤

(1)

qw² - (q - 1)(2w - d)n

если qw² > (q - 1)(2w - d)n.

Определение 1. Уравновешенной неполной блок-схемой B(v,k,λ) называется

структура инцидентности (X, B), где X = {x₁, . . . , x_v} - множество элементов, а B =

= {B₁, . . ., B_b} - набор k-элементных множеств B_i (называемых блоками), таких что

любые два различных элемента множества X содержатся ровно в λ ≥ 0 блоках из B

(здесь 1 ≤ k ≤ v - 1).

Двумя другими параметрами блок-схемы B(v, k, λ) являются b = |B| (количество

блоков) и r (число блоков, содержащих один фиксированный элемент):

v-1

v(v - 1)

r=λ

b=λ

если λ > 0

k-1

k(k - 1)

(λ = 0 соответствует случаю k = 1 и, тем самым, b = rv).

Всякая блок-схема B(v, k, λ) полностью описывается своей матрицей инцидент-

ности A = [a_i,j ], где a_i,j = 1, если a_i ∈ B_j , и a_i,j = 0 в противном случае. Таким

образом, A - двоичная (v × b)-матрица со столбцами веса k, такая что любые две

различные строки содержат ровно λ общих ненулевых позиций.

Схема B(v, k, λ) называется разрешимой (и обозначается через RB(v, k, λ)), если

ее матрица инцидентности A имеет вид

A = [A1 | ... |A_r],

(2)

где для любого i ∈ {1, . . . , r} каждая строка матрицы A_i имеет вес 1. Блок-схема

B(v, k, λ) называется m-квазиразрешимой (схемой NRB_m(v, k, λ)) [4], если ее матри-

ца инцидентности A представляется в виде

A = [A1 | ... |A_n], n =

(3)

v-m

таком что выполнены следующие свойства:

v-m

(1) Каждая подматрица A_j размера v ×

состоит из строк веса 1, за исключе-

нием m нулевых строк, номера которых принадлежат множеству V_j , |V_j | = m,

V_j ⊂ {1, 2, . . ., v};

(2) Множества V₁, . . . , V_n (как набор из n блоков размера m) индуцируют блок-схему

B(v, m, ξ) (называемую сопутствующей) для некоторого ξ.

Нам потребуются следующие результаты работ [4,5].

Теорема 1. Всякая m-квазиразрешимая блок-схема NRB_m(v,k,λ) индуциру-

ет q-ичный эквидистантный равновесный (n, N, w, d)_q-код C с параметрами q =

= (v - m + k)/k, N = v,

λv(v - 1)

λ(v - 1)

λ(v + m - k)

(k - 1)(v - m)

k-1

лежащий на границе Джонсона (1), с дополнительным свойством, что n его бло-

ков размера m = (n - w)N/n, образованных номерами нулевых позиций, задают

блок-схему B(v, m, ξ).

Напомним следующий широкий класс q-ичных эквидистантных кодов, построен-

ных в [6].

Теорема 2. Пусть p - простое, а s, ℓ и h - положительные целые числа.

Тогда существует эквидистантный (n, N, d)_q -код с параметрами

ps(h+ℓ) - 1

p^sh - 1

q=p^sh, n=

N =ps(h+ℓ), d=p^sℓ

p^s - 1

Определение 2 [7]. Пусть G - абелева группа порядка q в аддитивной запи-

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

матрицей и обозначается через D(q, μ), если покомпонентные разности любых двух

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

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

код [6].

§ 3. Конструкции

3.1. Комбинаторные конструкции. Обозначим через W_q(n) шар радиуса 1 с цен-

тром в нулевом векторе, т.е. W_q(n) = {x ∈ Qⁿ : wt(x) ≤ 1}.

Конструкция 1a. Шар W_q(n) является (n, (q - 1)n + 1, {1, 2})_q-кодом.

Конструкция 1b. Добавляя к конструкции 1a проверку на четность (по моду-

лю 2), получаем (n + 1, (q - 1)n + 1, {2, 3})_q-код, который будем обозначать через

W^∗q(n + 1). Для любого кодового слова (0 . . . 0 a 0 . . .0) из W_q(n) мы образуем кодо-

вое слово (0 . . .0 a 0 . . .0 | a) из W^∗q(n + 1).

Конструкция 2. Эквидистантный (n, N, d)_q-код C дает два (n^′, N, {d^′, d^′ +1})_q-ко-

да, а именно (n - 1, N, {d - 1, d})_q-код C₁, получаемый удалением (любой) позиции

из C, и (n + 1, N, {d, d + 1})_q-код C₂, получаемый добавлением одной позиции к C.

Объединяя конструкции 1a, 1b с конструкцией 2, получаем следующие две кон-

струкции.

Конструкция 3a. Эквидистантный (n₁, N₁, d)q1-код и Wq2(n₂) = (n₂, N₂, {1, 2})

дают (n, N, {d + 1, d + 2})_q-код с параметрами

q = max{q₁,q₂}, n = n₁ + n₂, N = min{N₁,N₂}.

Конструкция 3b. Эквидистантный (n₁, N₁, d)q1-код и W^∗q

(n₂) = (n₂, N₂, {2, 3})

дают (n, N, {d + 2, d + 3})_q-код с параметрами

q = max{q₁,q₂}, n = n₁ + n₂, N = min{N₁,N₂}.

Конструкция 4. Если существует r взаимно ортогональных латинских квадра-

тов порядка q, то существует семейство (s + 2, q², {s + 1, s + 2})_q-кодов C_s, где

s = 0,1,...,r. Для степени простого q код C_s линеен.

Объединяя конструкции 2 и 4, получаем следующее:

Конструкция 5. Для любой степени простого числа q существует семейство (ли-

нейных) [n, 2, {d, d + 1}]_q-кодов с параметрами

n = s(q + 1) + r, d = sq + r - 1, s ≥ 1, r = 1,...,q + 1.

Конструкция 6. Если существует разностная матрица D(q, μ), то существуют

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

n = qμ - 2,

N = qμ, d = (q - 1)μ - 1,

n = qμ,

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

Хорошо известный эквидистантный [4, 2, 3]₃-код C₁ и [2, 2, {1, 2}]₃-код C₂ (кон-

струкция 4) по конструкции 3 дают [6, 2, {4, 5}]₃-код C, этот код не очень хорош, но

линеен. Используя [3, 2, {2, 3}]₃-код C₃ (конструкция 4) и применяя конструкцию 3,

получаем [7, 2, {5, 6}]₃-код, хуже оптимального по мощности на 1.

Из эквидистантного (13, 27, 9)₃-кода (теорема 2) с помощью конструкции 2 полу-

чаем (14, 27, {9, 10})₃-код, что лучше, чем случайный (14, 18, {9, 10})₃-код, а также

(12, 27, {8, 9})₃-код, лежащий на верхней границе (наилучший найденный случайный

код имеет мощность 18).

Разностная матрица D(4, 3) (см. [8]) без тривиального столбца является опти-

мальным эквидистантным (11, 12, 8)₃-кодом. Разностная матрица D(3, 4) (см. [8]) без

тривиального столбца является оптимальным эквидистантным (11, 12, 9)₄-кодом.

Хорошо известный эквидистантный (5, 16, 4)₄-код C₁ и (5, 16, {1, 2})₄-код C₂ (кон-

струкция 1) по конструкции 3 дают (10, 16, {5, 6})₄-код (не являющийся хорошим -

имеется случайный (10, 20, {5, 6})₄-код). Двукратное повторение (5, 16, 4)₄-кода C₁

дает оптимальный (10, 16, 8)₄-код.

Из эквидистантного (6, 9, 5)₄-кода [4] с помощью двукратного повторения полу-

чаем (12, 9, {10, 11})₄-код (лучше, чем случайный). Из эквидистантного (21, 64, 16)₄-

кода [6] получаем (22, 64, {16, 17})₄- и (20, 64, {15, 16})₄-коды с помощью конструк-

ции 2. Из эквидистантного (9, 10, 8)₅-кода [5] с помощью конструкции 2 получаем

(8, 10, {7, 8})₅- и (10, 10, {8, 9})₅-коды. C помощью конструкции 5 получаем следую-

щее семейство (n, N, {d, d + 1})₅-кодов:

n = 9 + s, N = 10, d = 8 + s - 1, s = 0,1,...,6.

В частности, при s = 0 получаем оптимальный (9, 10, 8)₅-код, а при s ≥ 2 все полу-

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

ного (9, 10, 8)₅-кода получаем (11, 9, {9, 10})₅-код.

Из эквидистантного (6, 25, 5)₅-кода получаем семейство (6+s, 25, {5+s-1, 5+s})₅-

кодов, где s = 0, 1, . . . , 6, что для s ≥ 1 дает лучшие (или новые) коды.

Хорошо известная разрешимая блок-схема (15, 35, 7, 3, 1) эквивалентна оптималь-

ному эквидистантному (7, 15, 6)₅-коду [6]. Теперь, применяя конструкцию 5, полу-

чаем из него коды со следующими параметрами: n = 7 + s, N = 15, d = 6 + s - 1,

s = 1,...,6.

Из аффинной блок-схемы (16, 4, 1) (см. [5]) получаем эквидистантный равновес-

ный (16, 16, 15, 14)₆-код, из которого в свою очередь получаем (16, 17, {14, 15})₆-код

(добавлением нулевого кодового слова).

3.2. Случайные коды. Мы использовали компьютерную программу для генера-

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

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

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

ство поиска состоит из векторов веса d и d + 1. Оно выделяется из начальной базы

данных всех qⁿ векторов длины n, генерируемой (один раз) стандартным лекси-

кографическим образом. Программа добавляет случайно выбираемые подходящие

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

только расстояния d и d+1). Можно совершать много итераций, однако обычно наи-

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

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

конструкций текущего параграфа.

Результаты показывают, что такой подход хорош, когда d = 1, 2 и когда d близко

к n-1, но не позволяет находить хорошие коды с богатой структурой. Вероятно, он

также не хорош для средних значений d.

§4. Линейные (n, N, {d, d + 1})_q-коды

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

расстояниями d и d + 1. В частности, мы покажем, что линейные коды с двумя рас-

стояниями d и d + 1 полностью известны. Нижеследующая теорема была доказана в

двоичном случае в [1], где также была выдвинута гипотеза для q-ичного случая. Мы

дадим здесь простое доказательство этой гипотезы для случая q ≥ 2 и k ≥ 2, опира-

ющееся только на соображения из теории кодирования. Соответствующий результат

для k ≥ 3 был одновременно доказан в [2] на основе геометрических рассуждений.

Пусть C - q-ичный (линейный) эквидистантный [n, 3, q²]_q-код длины n = q² +q+1

с расстоянием q² и мощностью q³.

Лемма. Пусть C - вышеуказанный код, представленный в виде (n × q³)-мат-

рицы над F_q (обозначим ее через [C]). Тогда [C] нельзя представить в виде кон-

катенации двух матриц, т.е. [C] = [C₁ | C₂], где [C₁] - матрица размера (x × q³)

(здесь x < (n - 1)/2), задающая линейный [x, q³, {d, d + 1}]_q-код C₁.

Доказательство. Если x ∈ C, то, очевидно, αx ∈ C для всех α ∈ F^∗q. Тем

самым, q³ - 1 ненулевых кодовых слов кода C разбиваются на q² + q + 1 классов.

Таким образом, мы получили код на классах таких элементов. Он задается (n × n)-

матрицей P .

Предположим, что матрица P является конкатенацией двух матриц P₁ и P₂, т.е.

P = [P1 |P₂], где P₁ - матрица размера x × (q² + q + 1), соответствующая классам

эквивалентности линейного [x, q³, {d, d + 1}]-кода C₁. Тогда каждое слово кода C₁

имеет x - d или x - d - 1 позиций, содержащих нули. Для упрощения дальней-

ших вычислений положим ℓ = x - (d + 1) (поскольку вместо веса слова мы будем

рассматривать число его нулевых позиций).

Так как P соответствует эквидистантному коду с кодовым расстоянием q², то,

очевидно, P₂ соответствует (линейному) [n - x, 3, q² - d - 1]_q-коду C₂ с двумя рас-

стояниями q² - d - 1 и q² - d. Поэтому без ограничения общности можно считать,

что x ≤ n/2. Поскольку n = q² + q + 1, будем предполагать, что x ≤ q(q + 1)/2

и ℓ ≤ (q + 1)/2 (действительно, каждая ненулевая строка (так же как и каждый

столбец) матрицы P содержит q + 1 нулей).

Так как любой столбец P содержит q + 1 нулей, в матрице P имеется n(q + 1)

нулевых элементов. Пусть матрица P₁ содержит ровно η слов веса d + 1 (т.е. с ℓ

нулями) и остальные n - η слов веса d (т.е. с ℓ + 1 нулями). Таким образом, имеем

ℓη + (ℓ + 1)(n - η) = (q + 1)x.

Выражая отсюда η, получаем

η = (ℓ + 1)n - (q + 1)x.

(4)

Поскольку C₁ - линейный код размерности 3, для любой пары координатных по-

зиций существует ровно одна строка матрицы P₁ с нулями в этих позициях. Всего

имеется x координатных позиций и x(x - 1)/2 пар позиций. C другой стороны, име-

ется η строк с ℓ нулями (каждая строка дает ℓ(ℓ - 1)/2 пар координат) и n - η

строк с ℓ+1 нулями (каждая строка дает ℓ(ℓ+1)/2 пар координат). Итак, получаем

равенство

x(x - 1)

ℓ(ℓ - 1)

ℓ(ℓ + 1)

η+

(n - η).

(5)

Наша цель - показать, что равенство (5) не может выполняться при любом x из

интервала [2, q(q + 1)/2]. С учетом (4) выражение (5) принимает вид

x(x - 1) = ℓ(ℓ - 1)η + ℓ(ℓ + 1)n - ℓ(ℓ + 1)η = ℓ(ℓ + 1)n - 2ℓη =

= ℓ(ℓ + 1)n - 2ℓ[(ℓ + 1)n - (q + 1)x] = 2ℓ(q + 1)x - ℓ(ℓ + 1)n.

Таким образом, приходим к следующему квадратному уравнению на x:

x² - (2ℓ(q + 1) + 1)x + ℓ(ℓ + 1)n = 0.

(6)

Покажем, что его дискриминант отрицателен. Итак, следует проверить, что

(2ℓ(q + 1) + 1)² < 4ℓ(ℓ + 1)n.

С учетом того, что n = q² + q + 1, это равносильно

4ℓ²(q² + 2q + 1) + 4ℓ(q + 1) + 1 < 4ℓ(ℓ + 1)(q² + q + 1) =

= 4ℓ²(q² + q + 1) + 4ℓ(q² + q + 1).

После упрощения получаем

4ℓ²q + 1 < 4ℓq².

Так как ℓ ≤ (q + 1)/2, последнее неравенство очевидно выполнено при ℓ ≥ 1. Таким

образом, мы получили, что подматрицы P₁ не существует, и следовательно, линей-

ный [q² + q + 1, 3, q²]_q-код C не может быть представлен в виде конкатенации двух

линейных кодов C₁ и C₂ типа (n, N, {d, d + 1})_q. ▴

Теорема 3. Пусть C - q-ичный линейный [n,k,d]_q-код с двумя расстояниями

d и d + 1, где k ≥ 2. Тогда C может быть получен конструкцией 2 предыдущего

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

матрице линейного q-ичного эквидистантного кода, за исключением случая k = 2

и q ≥ 3, когда C может быть получен конструкцией 2 или конструкцией 5.

Доказательство. Вначале рассмотрим случай k = 2. В этом случае может

иметься [n, 2, d]_q-код C с двумя расстояниями d и d + 1, получаемый также кон-

струкцией 5. Пусть C₁ - эквидистантный [n₁, 2, d₁]_q-код с параметрами n₁ = s(q +1),

d₁ = sq, а C₂ - [n₂, 2, d₂]_q-код с параметрами n₂ = r, d₂ = r-1. Порождающая матри-

ца G кода C имеет вид G = [G₁ | G₂], где G₁ и G₂ - порождающие матрицы кодов C₁

и C₂, имеющие (с точностью до эквивалентности) следующий вид: G₁ = [G0 | . . . | G₀]

является s-кратным повторением матрицы

[

]

a₀

a₁

G₀ =

a₁

a₀

a₁

a₂

... aq-1

где используются обозначения F_q = {a₀ = 0, a₁ = 1, a₂, . . . , aq-1}, а матрица G₂

имеет вид

[

]

a₀

a₁

G₂ =

a₁

a₀

a₁

a₂

... ar-2

Все эти факты широко известны и не нуждаются в доказательствах. Единственное,

что требуется отметить, это тот факт, что все элементы второй строки матрицы G₂,

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

достаточно для того, чтобы G₂ была порождающей матрицей кода C₂.

Теперь мы утверждаем, что любой [n, 2, d]_q-код с двумя расстояниями должен

иметь такой вид. Это очевидно для случая n ≤ q. Для больших n предположим,

что код C₁ длины q + 1 не является эквидистантным [q + 1, 2, q]_q-кодом, т.е. име-

ет минимальное расстояние d = q - 1. Поскольку его среднее расстояние известно

(и равно q), отсюда заключаем, что этот код имеет три расстояния, а именно q - 1, q

и q+1. Обозначая через α_w число кодовых слов веса w и учитывая, что αq-1 = αq+1,

получаем

αq-1 = αq+1 = q - 1, α_q = (q - 1)².

(7)

Как мы знаем, [r, 2, r - 1]_q-код C₂ имеет веса r - 1 и r. Обозначая через β_w число

кодовых слов веса w, получаем, что

βr-1 = (q - 1)r, β_r = (q - 1)(q + 1 - r).

(8)

Таким образом, конкатенация этих двух кодов C₁ и C₂ должна была бы быть ко-

дом C с по крайней мере тремя расстояниями d, d + 1 и d + 2, где d ≤ q + r - 1,

т.е. получаем противоречие. Значит, код C₁ длины (q + 1)s должен быть эквиди-

стантным. Следовательно, любой [n, 2, d]_q-код C с двумя расстояниями d и d + 1

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

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

[n, 3, d]_q-код с двумя расстояниями d и d + 1 может быть получен только конструк-

цией 2. Предположим противное - пусть C₁ является [n₁, 3, d₁]_q-кодом с двумя рас-

стояниями d₁ и d₁ + 1 длины n₁ в интервале 2 ≤ n₁ ≤ q² + q - 1. Это означает,

что существует [n₂, 3, d₂]_q-код C₂ (дополнительный к C₁) с двумя расстояниями d₂

и d₂ + 1 длины n₂ = q² + q + 1 - n₁. Следовательно, существует q-ичный эквиди-

стантный [n, 3, q²]_q-код C длины n = q² + q + 1, который можно представить в виде

конкатенации кодов C₁ и C₂. Но согласно лемме это невозможно. Так как любой

[n, k ≥ 4, d]_q-код с двумя расстояниями d и d + 1 укорочением сводится к [n^′, 3, d]_q-

коду с двумя расстояниями d и d + 1, то это и завершает доказательство.

▴

Замечание 1. Рассматриваемые коды с весами d и d+1 являются подклассом бо-

лее широкого класса кодов с двумя весами - классического объекта алгебраической

теории кодирования. Однако такие коды с весами d и d+1 ранее не рассматривались

в литературе (см., например, дающий исчерпывающую информацию обзор [9]). Та-

ким образом, теорема 3 является результатом о классификации для линейных кодов

с весами d и d+ 1. Как хорошо известно [9,10], двойственный код любого линейного

проективного кода с двумя весами равномерно упакован (и следовательно, полно-

стью регулярен - см. [11, 12]). Коды с двумя весами, получаемые удалением одной

позиции из линейных эквидистантных кодов, также индуцируют полностью регу-

лярные коды и хорошо известны [11, 12].

Замечание 2. Доказательство леммы, приведенное выше, можно обобщить на

любой эквидистантный код C, обладающий следующим свойством: для любых двух

координатных позиций, скажем, i и j, 1 ≤ i, j ≤ n, существуют λ кодовых слов

c = (c₁,...c_n) кода C с двумя нулями в этих двух позициях, т.е. c_i = c_j = 0, где λ

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

(n, N, d) = (4m - 1, 4m, 2m)-код Адамара нельзя представить в виде конкатенации

двух кодов C₁ и C₂ (длин n_i ≥ 2) с двумя последовательными расстояниями d₁, d₁ +1

и d₂, d₂ + 1 соответственно. Но эту лемму нельзя использовать для доказательства

соответствующей теоремы, где линейность весьма существенна. Заметим также, что

это сведение к квадратному уравнению не дает никакого результата для кодов с рас-

стояниями d и d + δ, где δ ≥ 2. Даже для следующего случая δ = 2 соответствующие

коды существуют (в случае q = 2^m [9]), а решение квадратного уравнения сводится

к решению диофантова уравнения, что выходит за рамки настоящей статьи.

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

Нас интересуют верхние границы на величину

A_q(n; {d, d + 1}) = max{|C| : C является (n, |C|, {d, d + 1})-кодом},

максимальную возможную мощность кода в Qⁿ с двумя расстояниями d и d + 1.

Общая граница гармонического анализа Дельсарта [10]

)

⁽n

A_q(n; {d, d + 1}) ≤ 1 + (q - 1)n + (q - 1)²

и ее улучшение Барга - Мусина [13]

)

⁽n

A_q(n; {d, d + 1}) ≤ 1 + (q - 1)²

(при (2d + 1)q < 2n(q - 1) + 2 - q) кажутся слишком общими, в то время как наша

ситуация довольно специфическая.

5.1. Границы линейного программирования. Для фиксированных n и q (норми-

рованные) многочлены Кравчука определяются как

)

n(1 - t)

⁽n

Q(n,q)i(t) =

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

ri = (q - 1)ⁱ

где

∑

⁽d⁾⁽n - d⁾

K(n,q)i(d) =

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

i-j

j=0

- (обычные) многочлены Кравчука. Если многочлен f(t) ∈ R[t] имеет степень m ≥ 0,

то он имеет единственное разложение вида

∑

f (t) =

f_iQ(n,q)i(t).

i=0

Следующая теорема является адаптацией для оценки A_q(n; {d, d + 1}) общей грани-

цы линейного программирования Дельсарта. Доказательства таких границ обычно

считаются фольклорными (см., например, [10, 14]).

Теорема 4. Пусть n ≥ q ≥ 2, и пусть f(t) - вещественный многочлен сте-

пени m ≤ n, такой что

(A1) f(t) ≤ 0 для t ∈ {1 - 2d/n, 1 - 2(d + 1)/n};

∑

(A2) Коэффициенты в разложении по многочленам Кравчука f(t) =

f_iQ(n,q)i(t)

удовлетворяют условию f_i ≥ 0 для всех i.

i=0

Тогда A_q(n; {d, d + 1}) ≤ f(1)/f₀. Если эта граница достигается для некоторого

(n, N, {d, d + 1})_q-кода C и многочлена f(t), то f(1 - 2(d + i)/n) = 0, i = 0, 1, когда

существуют точки кода C на расстоянии d + i, i = 0, 1, и при этом f_iM_i(C) = 0,

где

∑

M_i(C) =

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

x,y∈C

- i-й момент кода C.

Большинство верхних границ, приведенных в таблицах ниже, получены согласно

теореме 4 симплексным методом (т.е. получены наилучшие возможные границы из

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

хороших границ.

Многочлен первой степени f(t) = t - 1 + 2d/n дает границу Плоткина, дости-

гающуюся для многих больших значений d. Оптимизация по многочленам второй

степени дает следующий результат.

Теорема 5. Если d ≥ (n - 1)(q - 1)/q, то

q²d(d + 1)

A_q(n; {d, d + 1}) ≤

(9)

n²(q - 1)² - n(q - 1)(2dq + q - 1) + dq²(d + 1)

Если некоторый (n, N, {d, d + 1})_q-код C достигает этой границы, то M₂(C) = 0,

и кроме того, M₁(C) = 0 при d > (n - 1)(q - 1)/q.

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

(

)(

)

2d + 2

(n,q)

f (t) = t - 1 +

t-1+

=f₀ +f₁Q

(t) + f₂Q(n,q)2(t),

где

4(n²(q - 1)² - n(q - 1)(2dq + q - 1) + dq²(d + 1))

f₀ =

n²q²

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

f₁ =

nq²

4(q - 1)²(n - 1)

f₂ =

nq²

Условие (A1), очевидно, выполнено.

Условие f₀ > 0 равносильно квадратичному по dq неравенству, которое выпол-

нено при n ≥ q. Условие f₁ ≥ 0 равносильно dq ≥ (n - 1)(q - 1), а f₂ > 0 очевидно.

Таким образом, f(t) удовлетворяет (A1) и (A2) при условии, что d ≥ (n-1)(q -1)/q.

Вычисляя теперь f(1)/f₀, получаем границу (9).

Условия достижимости границы (9) вытекают из общих условий теоремы 4.

▴

В некоторых случаях граница (9) достигается. В частности, A_q(n; {d, d + 1}) ≤ q²

для d = n - 1, что достигается при (q, n) = (3, 3), (3, 4), (4, 5) и (5, 6). Далее, в си-

лу (9) имеем A₂(7; {4, 5}) = A₂(7; {3, 4}) = 8, A₂(10; {5, 6}) = 12, A₃(12, {8, 9}) =

= A₃(13, {9, 10}) = 27. Случаи, когда граница (9) достигается, в приведенных ниже

таблицах отмечены знаком d2.

Кроме того, если граница (9) достигается для некоторого кода C и при этом

d > (n-1)(q-1)/q (т.е. f₁ > 0), то M₁(C) = M₂(C) = 0. Таким образом, C является

ортогональной таблицей силы 2. В частности, мощность C кратна q². Это сообра-

жение позволяет улучшить границу (9) на единицу, приводя к точным значениям

A₂(12, {5, 6}) = A₂(12, {6, 7}) = A₂(13, {6, 7}) = 13 и границе 13 ≤ A₃(6, {4, 5}) ≤ 14.

Эти случаи отмечены в таблицах знаком n. Еще один интересный случай - это

A₃(7, {4, 5}) = 15, где граница (9) достигается при d = (n - 1)(q - 1)/q.

Дальнейшие границы можно получить с помощью специально подобранных мно-

гочленов. Например, многочлен

f (t) = 1 + (q - 1)nQ(n,q)(n(q-1)+1)/q(t)

дает A_q(n, {1, 2}) = (q - 1)n + 1 (см. конструкцию 1a), когда q кратно n - 1. В част-

ности, получаем A₂(n, {1, 2}) = n + 1 при нечетном n. Аналогично, многочлен

n+2

f (t) = 1 +

Q(n,2)n/2(t) +

Q(n,2)1+n/2(t),

где n четно, дает A₂(n, {1, 2}) ≤ f(1)/f₀ = n + 2. Если эта граница достигается,

то условия дополняющей нежесткости линейного программирования теоремы 4 да-

ют уравнения Mn/2 = M1+n/2 = 0, которые вместе с тривиальным уравнением

A_d(x) + Ad+1(x) = |C| - 1 позволяют вычислить (используя Maple) распределе-

ния расстояний кодов (с двумя расстояниями), достигающих этой границы. Здесь

Ad+i(x) = |{y ∈ C : d(x, y) = d + i}|, i = 0, 1, x ∈ C. Поскольку это распреде-

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

образом, оба многочлена доказывают, что A₂(n, {1, 2}) = n + 1 (что достигается

конструкцией 1a). Такие случаи отмечены в таблицах знаком a.

Дальнейшее тщательное изучение условий достижения границ линейного про-

граммирования могут, возможно, привести к другим улучшениям в таблицах.

5.2. Границы через сферические коды. Коды в Qⁿ можно естественным образом

отобразить на сферу S(q-1)n-1. Вначале биективно отобразим символы алфавита

0, 1, . . ., q - 1 в вершины правильного симплекса размерности q - 1, а затем поко-

ординатно отобразим кодовые слова q-ичного кода C ⊂ Qⁿ в R(q-1)n. Нетрудно

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

сферический код на сфере S(q-1)n-1. Этот сферический код имеет мощность |C|

и максимальное скалярное произведение 1 - 2dq/(q - 1)n (т.е. минимальный квад-

рат расстояния 2dq/(q - 1)n). Очевидно, q-ичные коды с расстояниями d и d + 1

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

2dq/(q - 1)n и 2(d + 1)q/(q - 1)n. Из этого вытекает следующая верхняя граница на

A_q(n, {d, d + 1}).

√

Теорема 6. Если d > (

2(q - 1)n - 1)/2, то

A_q(n, {d, d + 1}) ≤ 2(q - 1)n + 1.

Доказательство. В [15] было доказано, что если мощность множества в Rⁿ

с двумя расстояниями a и b, a < b, больше чем 2n + 3, то отношение a²/b² равно

√

(k - 1)/k, где k - положительное целое число, такое что 2 ≤ k ≤ (

2n + 1)/2.

В работе [16] ограничение 2n + 3 было улучшено до 2n + 1.

В нашей ситуации a²/b² = d/(d + 1) = (k - 1)/k, откуда следует, что d = k - 1

√

должно принадлежать интервалу [1, (

2(q - 1)n - 1)/2]. Иными словами, не суще-

ствует q-ичных кодов с расстояниями d и d + 1 и мощностью, большей 2(q - 1)n + 1,

√

если d > (

2(q - 1)n - 1)/2, и таким образом, A_q(n, {d, d + 1}) ≤ 2(q - 1)n + 1.

▴

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

больших n и средних значений d. В первый раз это происходит при (n, d) = (13, 4)

для q = 2, (9, 3) для q = 3, (8, 3) для q = 4 и (7, 4) для q = 5.

Мы не нашли границ линейного или полуопределенного программирования для

сферических кодов, которые давали бы хорошие границы для наших кодов.

§ 6. Таблицы

Мы приводим таблицы для q = 2, 3, 4, 5. По горизонтали даются значения d, по

вертикали - значения n. Нижние границы показывают наилучший из найденных

на компьютере случайных кодов и кодов по конструкциям из § 3. Все найденные

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

Таблица 1

Границы для q = 2

13 14 15 16 17

7-10

8d2

9^a

8-12

8-10

9-14

8-16

8-10

11^a 10-16

8-16

10-16

12d2

6d2

2-3

11-18

8-19

10-20

12d2

13^a 12-20

8-25

10-21

13ⁿ

13-22

8-26

10-27

13-19

13ⁿ

8d2

15^a 14-24 8-29t6 10-29t6

14-27

14-19

16d2

2-3

15-26 8-31t6 11-31t6

14-29

14-30

16*

2* 2*

17^a 16-28 8-33t6 11-33t6 14-33t6 15-33t6 16-18 16-18

2* 2* 2*

17-30 9-35t6 12-35t6 14-35t6 15-35t6 17-22 16-18

10*

2* 2* 2* 2*

19^a 18-32 9-37t6 12-37t6 14-37t6 15-37t6 17-35 18-22

20*

4* 2-4

2* 2* 2* 2* 2*

Таблица 2

Границы для q = 3

11 12 13

9^a

11-13

9-17

11-13

13-15 11-18

11-16

13-14ⁿ

15^a

13-27

11-27

15d2

17-19 15-31

11-30

15-31

18-19

19-21 17-33 11-37t6

15-36

18-25

18-21

21^a

19-45 11-41t6 15-41t6 18-41t6

18-21

13-14

23-25 21-45 11-45t6 15-45t6

18-45

18-25

12^∗

4^∗

3^∗

25-27 23-51 12-49t6 15-49t6 18-49t6 18-49t6

18-30

27d2

9^∗

4^∗

3^∗

27^a

25-63 13-53t6 15-53t6 18-53t6 18-53t6 18-53t6 18-27

27d2

6^∗

3∗ 3∗

29-31 27-63 14-57t6 15-57t6 18-57t6 18-57t6 18-57t6 18-45

27-31

12-13 6∗ 3∗ 3∗

Таблица 3

Границы для q = 4

16^a

16-25

16^∗

19-22

16-37

18-22

9^∗

22-26

19-41

16-43

18-41

21-26

8^∗

25-28

22-50

16-49t6

18-49t6

21-32

19-28

5^∗

28^a

25-67

16-86

18-55t6

21-55t6

19-28

15-20^∗

5^∗

31-34

28-72

16-90

18-61t6

20-61t6

19-61t6

21-34

16^∗

5^∗

34-38

31-78

16-134

18-67t6

21-67t6

19-67t6

20-56

22-38

12^∗

4^∗

37-40

34-97

18-152

18-73t6

21-73t6

19-73t6

20-73t6

22-43

21-40

9^∗

4^∗

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

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

ных многочленов из п. 5.1 (помечены знаками d2, n и a соответственно), соответству-

ющих наилучших известных границ на A_q(n, d) [17] (помечены знаком ∗) и границ

теоремы 6 (помечены знаком t6).

Таблица 4

Границы для q = 5

25-30

19-25^∗

25^a

25-51

19-25

15-25^∗

29-34

25-66

25-81

19-57t6

25-34

12-15^∗

33-40

29-75

25-88

19-65t6 22-65t6

26-40

10^∗

37-43

33-83

25-130 21-73t6 22-73t6

26-65

25-43 8-10∗

10 41-45 37-114 25-177 21-81t6 22-81t6 26-81t6 25-49 25-45 7∗

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

но первоначальной версии настоящей статьи, а также Г. Кабатянского за полезные

обсуждения, касающиеся рассматриваемых кодов.

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

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, Russia. Sept. 2-8, 2018. P. 40-45. Available at https://www.

dropbox.com/s/h7u89lh8vyirww9/Proceedings\%20final.pdf?dl=0.

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.

Бассалыго Л.А. Новые верхние границы для кодов, исправляющих ошибки // Пробл.

передачи информ. 1965. Т. 1. № 4. С. 41-44.

Бассалыго Л.А., Зиновьев В.А., Лебедев В.С. Об m-квазиразрешимых блок-схемах и

q-ичных равновесных кодах // Пробл. передачи информ. 2018. Т. 54. № 3. С. 54-61.

Бассалыго Л.А., Зиновьев В.А. Замечание об уравновешенных неполных блок-схемах,

почти разрешимых блок-схемах и q-ичных равновесных кодах // Пробл. передачи ин-

форм. 2017. Т. 53. № 1. С. 55-59.

Семаков Н.В., Зиновьев В.А., Зайцев Г.В. Класс максимальных эквидистантных ко-

дов // Пробл. передачи информ. 1969. Т. 5. № 2. С. 84-87.

Beth T., Jungnickel D., Lenz H., Design Theory. Cambridge: Cambridge Univ. Press, 1986.

Богданова Г.Т., Зиновьев В.А., Тодоров Т.Й. О построении q-ичных эквидистантных

кодов // Пробл. передачи информ. 2007. Т. 43. № 4. С. 13-36.

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

Soc. 1986. V. 18. № 2. P. 97-122.

10.

Delsarte P. An Algebraic Approach to the Association Schemes of Coding Theory // Philips

Res. Rep. Suppl. 1973. № 10.

11.

Семаков Н.В., Зиновьев В.А., Зайцев Г.В. Равномерно упакованные коды // Пробл.

передачи информ. 1971. Т. 7. № 1. С. 38-50.

12.

Боржес Ж., Рифа Ж., Зиновьев В.А. О полностью регулярных кодах // Пробл. пере-

дачи информ. 2019. Т. 55. № 1. С. 3-50.

13.

Barg A., Musin O. Bounds on Sets with Few Distances // J. Combin. Theory Ser. A. 2011.

V. 118. № 4. P. 1465-1474.

14.

Levenshtein V.I. Krawtchouk Polynomials and Universal Bounds for Codes and Designs in

Hamming Spaces // IEEE Trans. Inform. Theory. 1995. V. 41. № 5. P. 1303-1321.

15.

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.

16.

Neumaier A. Distance Matrices, Dimension, and Conference Graphs // Nederl. Akad.

Wetensch. Indag. Math. 1981. V. 43. № 4. P. 385-391.

17.

Brouwer A.E. Tables of Bounds for q-ary Codes. Published electronically at www.win.tue.

nl/~aeb/.