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

Том 55

2019

Вып. 1

УДК 621.391.15

Ж. Боржес¹, Ж. Рифа¹, В.А. Зиновьев²

О ПОЛНОСТЬЮ РЕГУЛЯРНЫХ КОДАХ

Представлен обзор результатов по полностью регулярным кодам. Рассмотре-

ны известные свойства, взаимосвязи с другими комбинаторными структурами,

а также методы построения таких кодов. Обсуждена также проблема суще-

ствования и известные результаты для некоторых частных случаев. Кроме то-

го, представлены несколько новых результатов о полностью регулярных кодах

с радиусом покрытия ρ = 2 и о расширении полностью регулярных кодов.

DOI: 10.1134/S0134347519010017

§ 1. Введение

В 1959 г. Шапиро и Злотник [1] доказали, что двоичные совершенные коды полно-

стью регулярны (этот термин тогда не использовался). Позднее, в 1971 г., Семаков,

Зиновьев и Зайцев [2] доказали, что коды Препараты, расширенные коды Препараты

и расширенные совершенные коды полностью регулярны (этот термин также не ис-

пользовался). В 1973 г. Дельсарт [3] ввел термин полностью регулярный код в метри-

ке Хэмминга. Такие коды обладают достаточно плотной упаковкой в пространстве;

к ним относятся совершенные и расширенные совершенные коды [2], равномерно

упакованные коды [2,4,5], коды, полученные их расширением [2], а также полностью

транзитивные коды [6-9]. Известные полностью регулярные коды - это, например,

коды Хэмминга, Голея, БЧХ (длины 22m+1 - 1 с расстоянием d = 5) и два кода

Адамара (длины 11 и 12). Комбинаторные свойства полностью регулярных кодов

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

рациями, такими как дистанционно регулярные графы, схемы отношений и t-схемы.

Всеобъемлющим текстом об этих взаимосвязях является монография Брауэра, Ко-

эна и Ньюмайера [10, гл. 11], дополненная обзором ван Дама, Кулена и Танаки [11].

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

массивов пересечений, построенную Куленом, Кротовым и Мартином, можно найти

в [12]. В недавней работе [13] Кулен, Ли, Мартин и Танака рассмотрели и класси-

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

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

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

радиусом покрытия в работе Соле [6]). Однако не известно ни одного нетривиаль-

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

известно полностью регулярного кода с минимальным расстоянием d > 8 и более

чем двумя кодовыми словами. В 1973 г. несуществование неизвестных совершенных

¹ Работа выполнена при частичной финансовой поддержке гранта Испании TIN2016-77918-P

(AEI/FEDER, UE).

² Работа выполнена в ИППИ РАН при финансовой поддержке Российского фонда фундамен-

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

кодов над конечными полями было независимо доказано Титвайненом в [14] и Зи-

новьевым и Леонтьевым в [15]. Аналогичный результат для квазисовершенных рав-

номерно упакованных кодов был получен в 1975 г. Геталсом и ван Тилборгом [4, 5]

(бесконечные семейства таких кодов были исключены ранее в [2]). Для частного

случая двоичных линейных полностью транзитивных кодов в 2001 г. Боржес, Ри-

фа и Зиновьев [16,17] доказали несуществование таких кодов для d > 8, имеющих

более двух кодовых слов. В 1992 г. Ньюмайером [18] была высказана естественная

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

двух кодовых слов, с минимальным расстоянием d ≥ 8 является двоичный расши-

ренный код Голея. Однако Боржес, Рифа и Зиновьев [19] нашли контрпример к

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

кода Голея, составленная из слов четного веса, также является полностью регу-

лярным кодом с минимальным расстоянием d = 8. Тем не менее существование

нетривиальных неизвестных полностью регулярных кодов с d ≥ 9 является глав-

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

полностью регулярные коды только для конечных длин и с конечным числом кодо-

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

работу [20] и библиографию в ней). Также рассмотрены полностью регулярные ко-

ды в схемах Джонсона J(n, w). Обсуждена проблема существования совершенных

кодов в таких схемах, поставленная еще Дельсартом [3] в 1973 г., и приведены из-

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

полностью регулярным схемам в схеме Джонсона J(n, w).

План обзора выглядит следующим образом. В § 2 введены основные понятия и

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

Хэмминга. В конце рассмотрены некоторые необходимые условия существования

полностью регулярных кодов, а также расширения таких кодов. Затем § 3 посвящен

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

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

кодам в схемах Джонсона. Наконец, в § 5 собраны различные методы построения

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

§ 2. Предварительные результаты о полностью регулярных кодах

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

только коды над конечными полями F_q = GF(q), где q - степень простого числа,

с метрикой Хэмминга. Множество всех векторов пространства F^nq с отношениями

эквивалентности R_i, i = 0, 1, . . . , n, задаваемыми условием (x, y) ∈ R_i, если и только

если d(x, y) = i (где d(x, y) - число позиций, в которых x и y различны), называется

схемой отношений Хэмминга или просто схемой Хэмминга и обозначается H(q, n).

Для кодов над кольцами часто используется метрика Ли. Во многих случаях такие

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

го отображения Грея. Следовательно, их можно рассматривать как двоичные коды

с расстоянием Хэмминга. Как обычно, для кода C ⊂ F^nq используются обозначения

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

ректирующей способности) и радиуса покрытия соответственно. Если C - линейный

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

лов). Используются стандартные обозначения (n, M, d)_q для q-ичного кода длины n

и мощности (или числа его кодовых слов) M с минимальным расстоянием d. Если

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

ется через [n, k, d]_q. Код с радиусом упаковки e часто называется e-кодом. Если

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

(n, M, d; ρ)_q для нелинейного кода и [n, k, d; ρ]_q для линейного. Для двоичного случая

(q = 2) индекс q опускается. Если не оговорено противное, всегда предполагается,

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

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

[n, n - k, d^⊥]_q-код C^⊥ определяется следующим образом:

C^⊥ = {x ∈ F^nq : 〈x · y〉 = 0 для каждого y ∈ C},

где через 〈x · y〉 обозначено внутреннее произведение векторов x и y в F^nq.

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

щих получить новые коды из уже известных. Для двоичного кода C длины n с мини-

мальным расстоянием d = 2e+1 обозначим через C^∗ код, полученный из C добавле-

нием еще одной проверочной позиции (общей проверки на четность). Код C^∗ (рас-

ширение кода C) имеет уже длину n^∗ = n + 1, минимальное расстояние d^∗ = 2e + 2

и ту же мощность M^∗ = M. Для q-ичного кода C расширение означает код, по-

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

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

нялась нулю. Для кода C длины n назовем i-выколотым кодом код, полученный

из C удалением i-й позиции из всех слов кода C. Если же координата i не указа-

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

позиции i. Назовем a-укороченным кодом код, полученный из C выбором всех кодо-

вых слов, имеющих элемент a в фиксированной координате, и затем удалением этой

координаты. Аналогичным образом скажем, что код получен укорочением кода C,

если его параметры не зависят от выбора a. В более общем случае для векторов

x₁, . . ., x_r длины j < n скажем, что код получен {x₁, . . . , x_r}-укорочением кода C,

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

слов C, совпадающих на этих позициях с одним из векторов x₁, . . . , x_r, и затем от-

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

длину n - j и расстояние

d^′ ≥ d - max

d(x_i, x_i′ ).

i,i^′∈{1,...,r}

i=i^′

Для двоичного кода C обозначим через Aut(C) его группу автоморфизмов, т.е.

множество перестановок координат, которые не меняют данный код (как множество

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

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

Скажем, что код C тривиален, если он имеет мощность M = |C| ≤ 2 или совпадает

со всем пространством C = F^nq.

Пусть задан код C ⊂ F^nq. Для заданного вектора x ∈ F^nq обозначим через B_x,i

число кодовых слов на расстоянии i от x, где 0 ≤ i ≤ n. Назовем матрицей внешних

спектров кода C матрицу B размера qⁿ × (n + 1) с элементами

B_x,i = |{v ∈ C | d(x, v) = i}|.

Как следует из определения, строка B_x представляет собой весовой спектр сдвига

кода C на вектор x, т.е. спектр кода C + x. Обозначим через b + 1 число различных

строк матрицы B.

Обозначим через d(x, C) = min{d(x, v)} расстояние между вектором x и кодом C,

v∈C

т.е. расстояние между x и ближайшим к нему кодовым словом. В этой терминологии

радиус покрытия кода ρ_C равен максимальному значению d(x, C), когда x пробегает

все пространство. Определим множества

C(i) = {x ∈ F^nq | d(x, C) = i}.

Множества C, C(1), . . . , C(ρ) названы в [18] подкомпонентами, а некоторые другие

авторы называют их слоями. Заметим, что C(0) = C и что C(t) = ∅, если и только

если t ≤ ρ.

Скажем, что двоичный код C длины n антиподален, если для любого кодового

слова c ∈ C имеется кодовое слово c, находящееся на расстоянии n от c, т.е. c =

= c+(1,1,...,1). Очевидно, что если C представляет собой двоичный дистанционно

инвариантный код и содержит кодовое слово веса n, то C антиподален. Если же

(1, . . . , 1) ∈ C, то C неантиподален.

Определение 1 [4]. Код C с радиусом покрытия ρ называется t-регулярным,

0 ≤ t ≤ ρ, если для всех i = 0,...,t величина B_x,i зависит только от i и от расстояния

d(x, C) от вектора x до C для всех x, таких что d(x, C) ≤ t.

Другими словами, код C является t-регулярным, если B_x зависит только от

d(x, C) для всех расстояний d(x, C) ≤ t. По определению, если C t-регулярен, то он

и j-регулярен для всех j = 0, . . ., t. Интуитивно, код C t-регулярен, если мы “видим”

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

ра x, находящегося на расстоянии не более t от кода C. Например, 0-регулярный

код в точности представляет собой дистанционно инвариантный код.

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

(ПР-кода).

Определение 2 [3]. Код C полностью регулярен, если он ρ-регулярен.

Очевидно, что следующие определения эквивалентны:

(i) Код C является ПР-кодом, если для всех x ∈ F^nq величина B_x,i зависит только

от i и расстояния d(x, C).

(ii) Код C является ПР-кодом, если для всех x ∈ F^nq весовой спектр B_x зависит

только от расстояния d(x, C).

(iii) Если для кода C имеет место равенство b = ρ, то он является ПР-кодом.

Однако увидеть эквивалентность приведенных выше определений и следующего

определения не столь просто. Два вектора x и y из F^nq назовем соседями, если они

находятся друг от друга на расстоянии d(x, y) = 1.

Определение 3 [18]. Код C полностью регулярен, если для всех ℓ ≥ 0 каж-

дый вектор x ∈ C(ℓ) имеет одно и то же число c_ℓ соседей в C(ℓ - 1) и одно и то же

число b_ℓ соседей в C(ℓ + 1), где полагаем c₀ = b_ρ = 0.

Очевидно, что множества C, C(1), . . . , C(ρ) индуцируют разбиение всего про-

странства F^nq на подкомпоненты кода C. Такое разбиение называется дистанци-

онным разбиением. Если условия определения 3 удовлетворяются, то такое разби-

ение называется равнодистанционным. Следовательно, C является ПР-кодом, если

и только если его дистанционное разбиение равнодистанционно.

Об эквивалентности определений 2 и 3 см. [18, теорема 4.1] или [22]. Для ℓ ≥ 0

положим a_ℓ = n(q - 1) - b_ℓ - c_ℓ. Таким образом, a_ℓ - это число соседей в C(ℓ) для

любого вектора из C(ℓ). Параметры a_ℓ, b_ℓ и c_ℓ называются числами пересечений,

а последовательность IA = {b₀, . . . , bρ-1; c₁, . . . , c_ρ} - массивом пересечений кода C.

Приведем примеры ПР-кодов. Напомним, что код C является совершенным, если

ρ = e, и квазисовершенным, если ρ = e + 1. Следующие коды являются тривиаль-

ными совершенными кодами:

1. Одно кодовое слово C = {x}, x ∈ F^nq;

2. Все пространство C = F^nq;

3. Двоичные коды нечетной длины с повторением, состоящие из двух слов длины n

с расстоянием между ними d = n.

Нетривиальные совершенные коды существуют только для e ≤ 3 [14,15]. В F^nq из-

вестны следующие совершенные коды:

1. Двоичный код Голея с параметрами n = 23, k = 12, d = 7;

2. Троичный код Голея с параметрами n = 11, k = 6, d = 5;

3. Совершенные коды с параметрами n = (q^m - 1)/(q - 1), M = q^n-m, d = 3.

В последнем случае для каждой степени q простого числа и каждой длины n =

= (q^m-1)/(q-1) имеется единственный линейный код, называемый кодом Хэмминга.

Интересным классом кодов, тесно связанных с ПР-кодами, являются равномер-

но упакованные коды (РУ-коды). Имеются три основных класса РУ-кодов, удовле-

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

введены в 1971 г. в [2].

Определение 4 [2]. Двоичный квазисовершенный код C с минимальным рас-

стоянием d = 2e + 1 называется равномерно упакованным в узком смысле, если су-

ществует натуральное число μ, такое что B_x,e + Bx,e+1 = μ для любого вектора

x ∈ C(e) ∪ C(e + 1).

Подчеркнем, что все двоичные совершенные коды попадают в этот класс кодов

с параметром μ = (n + 1)/(e + 1), названным в [2] плотностью упаковки; для всех

других кодов μ меньше (n + 1)/(e + 1). РУ-коды в узком смысле включают в се-

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

В этот класс входят коды Препараты, двоичные примитивные коды БЧХ с рассто-

янием 5 длины 22m+1 - 1, код Адамара длины 11. В [2] было доказано в терминах

определения 2 (iii), что все РУ-коды в узком смысле, а также коды, полученные

их расширением (равномерно упакованные уже не в узком смысле, a в широком,

см. определение 6 ниже), являются ПР-кодами.

РУ-коды в узком смысле являются подклассом РУ-кодов, введенных в 1975 г.

Гёталсом и ван Тилборгом [4].

Определение 5 [4]. Квазисовершенныйq-ичный код C, исправляющий e оши-

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

и μ, такие что для любого вектора x величина Bx,e+1 принимает два значения:

^{λ, если d(x, C) = e,

Bx,e+1 =

μ, если d(x, C) = e + 1.

Для случая μ = λ + 1 любой такой двоичный код является РУ-кодом в узком

смысле. Заметим, что двоичные расширенные совершенные коды входят в этот класс

кодов для значений λ = 0 и μ = (n + 1)/(e + 1) [2]. Эти коды включают в себя

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

его укорочением (на одну позицию). Ван Тилборг [5] (см. также [2,23]) показал, что

для e > 3 никаких других кодов, кроме указанных, не существует.

Следующий результат обобщает результат работы [2] на РУ-коды.

Предложение 1 [4]. Равномерно упакованный код полностью регулярен.

Заметим, что расширение любого РУ-кода, не являющегося совершенным, вооб-

ще говоря, может уже не быть РУ-кодом. Это было одним из мотивирующих фактов

для введения следующего класса РУ-кодов.

Определение 6 [24]. Код C с радиусом покрытия ρ называется равномер-

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

β₀, . . . , β_ρ, такие что для любого вектора x ∈ F^nq имеет место следующее равенство:

∑

β_iB_x,i = 1.

i=0

Числа β₀, . . . , β_ρ называются параметрами упаковки (например, для совершен-

ных кодов все эти числа равны: β_i = 1 для всех i = 0, 1, . . . , ρ = e). Введенный

выше класс кодов намного шире, чем коды, введенные в определениях 4 и 5. Други-

ми словами, код C представляет собой РУ-код в широком смысле, если столбец из

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

спектров B. Далее будет видно, что любой ПР-код всегда равномерно упакован в

широком смысле.

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

работу Гёталса и ван Тилборга [4], которые ввели также равномерно упакованные

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

РУ-кодами и РУ-кодами в широком смысле. Примеры ПР-кодов:

1. Как уже отмечалось, любой совершенный код полностью регулярен [1];

2. Множество всех векторов четного веса представляет собой линейный ПР-код с

ρ = 1 [2];

3. Двоичный расширенный совершенный код является квазисовершенным РУ-ко-

дом, и поэтому полностью регулярен [2];

4. Для любого ПР-кода C его подкомпонента C(ρ) также полностью регулярна, а ее

массив пересечений получен инверсией массива кода C [18].

2.2. t-схемы и дистанционно регулярные графы. Две комбинаторные структуры,

тесно связанные с ПР-кодами и представляющие особый интерес, это t-схемы и

дистанционно регулярные графы.

Определение 7. Схема T = T(v,k,t,λ) (называемая также t-(v,k,λ)-схемой)

представляет собой инцидентную структуру (X, B), где X - множество из v элемен-

тов (называемых также точками), а B - семейство k-подмножеств множества X

(называемых блоками), такие что каждое t-подмножество множества X содержится

ровно в λ блоках, где 0 ≤ t ≤ k ≤ v.

В терминах (двоичной) матрицы инцидентности схема T(v, k, t, λ) представляет

собой двоичный код C длины n = v с кодовыми словами веса w = k, такими что

любой двоичный вектор длины n и веса t покрыт в точности λ кодовыми словами.

Схема T (v, k, t, λ) называется простой, если она не содержит повторяющихся блоков

(в этом случае соответствующий код C имеет расстояние 2 или более) и нетривиаль-

ной, если она не содержит все k-подмножества X. Схема T (v, k, t, λ) с λ = 1 называ-

ется системой Штейнера и обозначается также через S(v, k, t). Следующие свойства

t-схем хорошо известны и могут быть найдены, например, в монографиях [25-27].

Предложение 2. Для заданной схемы T(v,k,t,λ) каждое i-подмножество

элементов, 0 ≤ i ≤ t, содержится ровно в λ_i блоках, где

)

⁽v-i

λ_i

⁽k-i).

t-i

Следствие 1. Пусть задана T(v,k,t,λ)-схема T. Тогда

(i) T является схемой T (v, k, i, λ_i) для любого i ≤ t;

(ii) λ = λ_t;

(iii) число блоков схемы T равно b = λ₀;

(iv) каждый элемент из X содержится в одном и том же числе блоков, а именно

в r = λ₁ = bk/v блоках (величина r называется числом повторений).

Схемы с t ≤ 5 известны давно - с 1938 г. (начиная со знаменитых схем Витта [28],

т.е. c систем Штейнера S(24, 8, 5) и S(12, 6, 5)). Первые нетривиальные схемы с t = 6

были построены в 1983 г. Магливерасом и Ливиттом [29]. В 1987 г. Терлинк [30] дока-

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

Существует естественное обобщение t-схем на q-ичный случай (см. [1,3,4,15,31,32]).

Пусть E = {0, 1, . . . , q - 1}. Семейство B векторов x длины v и веса k над E называ-

ется схемой T(v, k, t, λ)_q, если для каждого вектора y над E длины v и веса t имеется

ровно λ векторов xi1 , . . . , x_i

из B, таких что d(y, xij ) = k - t для всех j = 1, . . . , λ.

Если λ = 1, то получаем q-ичную систему Штейнера, обозначаемую через S(v, k, t)_q.

Для заданного кода C обозначим через C_w множество всех его кодовых слов

веса w. Для вектора x = (x₁, . . ., x_n) из Eⁿ обозначим через supp(x) его носитель,

т.е. множество номеров его ненулевых позиций:

supp(x) = {i : x_i = 0}.

Из регулярности кода C следует, что множества C_w являются t-схемами. Для

РУ-кодов в узком смысле этот факт был указан в 1971 г. в [2].

Теорема 1 [4]. Пусть C является e-регулярным кодом с минимальным рас-

стоянием d ≥ 2e, тогда носители его кодовых слов из любого непустого мно-

жества C_w представляют собой матрицу инцидентности e-схемы (индуцируют

e-схему).

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

Теорема 2. Пусть C - q-ичный ПР-код длины n с расстоянием d.

(i) Если d

= 2e + 1, то любое непустое множество C_w является схемой

T (n, w, e, λ_w)_q.

(ii) Если d = 2e + 2, то любое непустое множество C_w является схемой T (n, w,

e + 1,λ_w)_q.

(iii) Если C - q-ичный совершенный код, то любое непустое множество C_w яв-

ляется схемой T(n, w, e + 1, λ_w)_q, а множество C_d - системой Штейнера

S(n, 2e + 1, e + 1)_q.

(iv) Если C - расширенный двоичный совершенный код с расстоянием d = 2e + 2,

то любое непустое множество C_w является схемой T(n, w, e+2, λ_w)_q, а мно-

жество C_d - системой Штейнера S(n, 2e + 2, e + 2)_q.

Пусть Γ - конечный связанный простой граф (т.е. неориентированный граф без

петель и кратных ребер). Пусть d(γ, δ) - расстояние между двумя вершинами γ

и δ, т.е. число ребер в минимальном пути между γ и δ). Диаметром D графа Γ

называется наибольшее расстояние между двумя вершинами графа. Две вершины

γ и δ из Γ называются соседями, если d(γ,δ) = 1 (т.е. если они связаны ребром).

Обозначим

Γ_i(γ) = {δ ∈ Γ : d(γ, δ) = i}.

Автоморфизмом графа Γ называется перестановка π множества вершин Γ, та-

кая что для всех γ, δ ∈ Γ условие d(γ, δ) = 1 имеет место, если и только если

d(π(γ), π(δ)) = 1.

Определение 8 [10]. Простой связанный граф Γ называется дистанционно

регулярным, если он регулярен с валентностью k и для любых двух вершин γ, δ ∈ Γ,

находящихся на расстоянии i друг от друга, имеется ровно c_i соседей вершины δ

в множестве Γi-1(γ) и b_i соседей δ в множестве Γi+1(γ). Более того, этот граф

называется дистанционно транзитивным, если для любой пары вершин γ, δ на

расстоянии d(γ, δ) имеется автоморфизм π из его группы автоморфизмов Aut(Γ),

переводящий эту пару (γ, δ) в любую другую пару вершин γ^′, δ^′, находящихся на

том же расстоянии d(γ, δ) = d(γ^′, δ^′) друг от друга.

Последовательность {b₀, b₁, . . . , bD-1; c₁, c₂, . . ., c_D}, где D - диаметр графа Γ, на-

зывается (так же как и для ПР-кодов) массивом пересечений графа Γ. Положим

ai = k - bi - ci. Числа ai, bi и ci называются числами пересечений этого графа.

Очевидно, что b₀ = k, b_D = c₀ = 0 и c₁ = 1.

Пусть C - линейный ПР-код с радиусом покрытия ρ и массивом пересечений

IA = {b₀, . . . , bρ-1; c₁, . . . , c_ρ}. Пусть {A} обозначает множество всех смежных клас-

сов кода C. Определим граф Γ_C, называемый графом смежных классов кода C,

выбирая в качестве множества вершин графа все различные смежные классы A =

= C + x, где ребро соединяет пару вершин, если два соответствующих смежных

класса содержат пару соседних векторов. Иначе говоря, две вершины γ = γ(A) и

γ^′ = γ(A^′) соединены ребром (т.е. являются соседями), если и только если смежные

классы A и A^′ содержат векторы v ∈ A и u ∈ A^′, такие что d(v, u) = 1.

2.3. Параметры и свойства ПР-кодов. Для кода C обозначим через s + 1 чис-

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

спектра расстояний кода C, полученному преобразованием Мак-Вильямс [21]. Па-

раметр s был назван Дельсартом [3] внешним расстоянием, и он равен числу нену-

левых весов в коде C^⊥, если C - линейный код. Этот параметр является ключевым

для ПР-кодов, в чем можно убедиться по их свойствам. Напомним, что матрица B

представляет собой матрицу внешних спектров кода C, а величина b+1 равна числу

различных строк в матрице B.

Теорема 3. Имеют место следующие утверждения:

(i) rank(B) = s + 1 [3];

(ii) b ≥ s [6];

(iii) ρ ≤ s [3].

Следовательно, выполняются неравенства e ≤ ρ ≤ s ≤ b. В этих терминах имеют

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

Теорема 4. Имеют место следующие утверждения:

(i) Код C совершенен, если и только если e = s [3];

(ii) Код C равномерно упакован, если и только если s = e + 1 [2, 4];

(iii) Если код C полностью регулярен, то ρ = s [6];

(iv) Код C равномерно упакован в широком смысле, если и только если ρ = s [33].

Утверждение, обратное к (iii), вообще говоря, неверно. Дельсарт [3] привел при-

мер расширенного квадратично-вычетного [48, 24, 12]-кода с параметрами ρ = s = 8

и b = 14. Однако то же самое условие является необходимым и достаточным для

РУ-кодов в широком смысле. Следовательно, имеет место

Следствие 2. Если код C полностью регулярен, то он равномерно упакован

в широком смысле.

В работах [34, 35] было построено много бесконечных семейств РУ-кодов в ши-

роком смысле, которые не полностью регулярны. Следующие свойства ПР-кодов

получены Дельсартом [3].

Теорема 5 [3]. Имеют место следующие утверждения:

(i) Если t ≥ d - s ≥ 0, то C - t-регулярный код;

(ii) Если C - t-регулярный код, причем t ≥ s - 1 и d ≥ 2s - 1, то C полностью

регулярен.

Условия этой теоремы можно усилить, если все слова кода C имеют четный вес

(такой код называется четным).

Следствие 3. Пусть C - четный код. Тогда

(i) Если t ≥ d - s + 1 ≥ 0, то C t-регулярен [33];

(ii) Если d ≥ 2s - 2, то C полностью регулярен [10].

Теорема 6. Пусть C - неантиподальный ПР-код с радиусом покрытия ρ.

(i) Множество C(ρ) представляет собой сдвиг кода C на вектор (1, . . . , 1) [19];

(ii) Множество C ∪ C(ρ) является ПР-кодом [36].

2.4. Необходимые условия существования ПР-кодов. Для заданного ПР-кода C

с радиусом покрытия ρ и числами пересечений a_i, b_i, c_i определим следующую трех-

диагональную матрицу A, называемую матрицей пересечений:

⎡

⎤

a₀

b₀

⎢c1

a₁

b₁

⎥

⎢

⎥

⎢

c₂

a₂

⎥

⎢

⎥.

⎢

⎥

⎦

^⎣0

... aρ-1 bρ-1

c_ρ

a_ρ

Следующее утверждение называется теоремой Ллойда для ПР-кодов. Напомним,

что собственными значениями схемы Хэмминга H(q, n) являются собственные зна-

чения матрицы пересечений этой схемы H(q, n), которые равны (q - 1)n - qj, j =

= 0, 1, . . ., n.

Теорема 7 [10,18]. Пусть C - ПР-код длины n с матрицей пересечений A.

Тогда A имеет ρ целых собственных значений, которые являются собственными

значениями схемы H(q, n).

Так как любой ПР-код является РУ-кодом в широком смысле, то существует дру-

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

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

Ллойда для совершенных кодов (см. [21]). Обозначим через K_i мощность множе-

ства C(i). Определим κ_i, полагая K_i = κ_i|C|. Легко видеть, что

)

⁽n

κ_i = β_i(q - 1)ⁱ

где β₀, β₁, . . . , β_ρ - параметры упаковки РУ-кода (см. определение 7).

Теорема 8 [24]. Пусть код C длины n равномерно упакован в широком смысле

с параметрами упаковки β₀, β₁, . . ., β_ρ. Тогда обобщенный многочлен Ллойда сте-

пени ρ от ξ

∑

L_ρ(n, ξ) =

β_rP_r(n, ξ),

(1)

r=0

где P_r(n, ξ) - многочлен Кравчука

)

∑

⁽n - ξ⁾⁽ ξ

P_r(n, ξ) =

(-1)^r-j (q - 1)^j

r-j

j=o

и для любого вещественного числа a

⁽a⁾

a(a - 1) . . . (a - i + 1),

имеет ρ различных целочисленных корней в диапазоне от 0 до n.

Следующая теорема обобщает классическое условие сферической упаковки для

совершенных кодов на РУ-коды в широком смысле, и следовательно, на любой пол-

ностью регулярный код.

Теорема 9 [24]. Пусть код C длины n равномерно упакован в широком смысле

с параметрами упаковки β₀, β₁, . . . , β_ρ. Тогда мощность кода имеет вид

|C| =

(2)

∑

⁽n).

β_i(q - 1)ⁱ

i=0

Некоторые другие интересные свойства ПР-кодов (являющиеся также необходи-

мыми условиями существования таких кодов) можно найти в [10, 18].

Рассмотрим два иллюстрирующих примера [24]. Коды Препараты P с параметра-

ми (n = 22m -1, M = 2n+1-4m, d = 5) для m = 2, 3, . . . имеют следующие параметры

упаковки β_i и корни ξ_i обобщенного многочлена Ллойда P_ρ(n, ξ):

β₀ = β₁ = 1, β₂ = β₃ =

√

(n + 1)

√

ξ₁ =

(n + 1 -

n + 1), ξ₂ =

ξ₃ =

(n + 1 +

n + 1).

Интересный факт, отмеченный в [2], состоит в том, что коды Препараты не только

полностью регулярны в схеме Хэмминга H(2, n), но также полностью регулярны в

коде Хэмминга.

Двоичные примитивные коды БЧХ с параметрами [n = 22m+1 -1, k = n-4m-2,

d = 5] для m = 2,3,... имеют следующие параметры упаковки β_i и корни ξ_i много-

члена Ллойда:

β₀ = β₁ = 1, β₂ = β₃ =

(n - 1)

√

n+1

ξ₁ =

ξ₂ =

ξ₃ =

2.5. Расширение полностью регулярных кодов. Напомним, что для двоичного

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

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

вопросов для ПР-кодов связан с расширением этих кодов и формулируется следую-

щим образом: при каких условиях расширение полностью регулярного (n, N, d)-ко-

да C с нечетным расстоянием d = 2e + 1 приводит к расширенному полностью

регулярному (n + 1, N, d + 1)-коду C^∗? Здесь мы ограничимся только двоичными

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

обобщены и на недвоичный случай.

В [22] доказано, что удаление любой одной позиции в четном ПР-коде приводит

к коду, также являющемуся ПР-кодом, что отвечает на ранее поставленный в [24]

вопрос. Следовательно, если C^∗ представляет собой ПР-код, то выколотый код C

также полностью регулярен. Однако обратное, вообще говоря, не верно. В рабо-

те [33] приводится пример ПР-кода C, такого что его расширение C^∗ уже не является

ПР-кодом: это [21, 12, 5]-код C, полученный выкалыванием двух позиций из двоично-

го совершенного кода Голея. Но его расширение, т.е. [22, 12, 6]-код C^∗, уже не полно-

стью регулярно. Более того, для этого случая расширенный [22, 12, 6]-код C^∗ даже

не равномерно упакован в широком смысле. Следовательно, расширение РУ-кода

в широком смысле, вообще говоря, может не быть РУ-кодом в широком смысле.

Для таких равномерно упакованных кодов этот вопрос был полностью решен в [33].

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

расширении дает следующая

Теорема 10 [33]. Двоичный РУ-код C в широком смысле длины n с парамет-

рами упаковки β₀, . . . , β_ρ остается при расширении РУ-кодом в широком смысле,

если и только если имеет место следующая система равенств:

βρ-2i = βρ-2i-1 для всех i, 0 ≤ i ≤ [(ρ - 1)/2].

Более того, параметры упаковки γ₀, . . . , γ_ρ, γρ+1 расширенного кода C^∗ однозначно

определяются следующими формулами:

γρ-2i = βρ-2i,

∀i = 0,1,...,⌊ρ/2⌋,

⌋

(

)

^⌊ρ+1

γρ-2i+1 =

(ρ + 1 - 2i)βρ-2i + (n - ρ + 2i)βρ-2i+2

∀i = 0,...,

n+1

Условия предыдущей теоремы очевидным образом являются необходимыми для

того, чтобы ПР-код при расширении оставался ПР-кодом. Вопрос о том, является

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

Приведем еще одно также полезное необходимое условие для ПР-кодов. Как из-

вестно (теорема 2), множество C_d для двоичного РУ-кода C длины n с расстоянием

d = 2e + 1 индуцирует схему T(n,d,e,λ).

Предложение 3 [33]. Пусть C^∗ получен расширением двоичного РУ-кода C

в широком смысле. Пусть C имеет длину n и минимальное расстояние d = 2e+1.

Если C^∗ равномерно упакован, то множество C∗d+1 индуцирует схему T (n + 1,

d + 1,e + 1,λ).

В случае, когда коды C и C^∗ равномерно упакованы и C имеет радиус покрытия

ρ = e + 1, оба кода также полностью регулярны.

Предложение 4 [2,37]. Пусть C - квазисовершенный РУ-код (следователь-

но, ПР-код). Если C^∗ равномерно упакован, то он также полностью регулярен.

Другое необходимое условие существования выглядит так.

Предложение 5. Пусть C - ПР-код четной длины, являющийся антипо-

дальным. Тогда C^∗ не равномерно упакован в широком смысле, и следовательно,

не полностью регулярен.

Доказательство. Предположим, что код C^∗ равномерно упакован в широ-

ком смысле. Тогда внешнее расстояние равно s^∗ = s + 1, откуда вытекает, что для

каждого веса w в дуальном спектре число n+1-w также является весом в дуальном

спектре. Но w должно быть четным, так как C содержит вектор из всех единиц, и

следовательно, число n + 1 - w нечетно, что приводит к противоречию. ▴

Следующее свойство представляет собой усиление результата работы [38].

Предложение 6 [39]. Пусть C - двоичный линейный ПР-код длины n = 2^m-1

с минимальным расстоянием d = 3, радиусом покрытия ρ = 3 и массивом пересе-

чений {n, b₁, 1; 1, c₂, n}. Пусть дуальный код C^⊥ имеет ненулевые веса w₁, w₂ и w₃.

Тогда расширенный код C^∗ полностью регулярен с радиусом покрытия ρ^∗ = 4, если

и только если w₁ + w₃ = 2w₂ = n + 1. В этом случае массив пересечений кода C^∗

равен {n + 1, n, b₁, 1; 1, c₂, n, n + 1}.

Следовательно, веса дуального кода (когда C - линейный код) играют важную

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

при удалении разных координат из расширенного кода C^∗: результирующий i-выко-

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

позиции i.

Предложение 7 [6]. Пусть C - двоичный ПР-код. Предположим, что i-выко-

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

ции i. Пусть s^∗ - внешнее расстояние кода C^∗. Если s^∗ ≤ s + 1, то C^∗ полностью

регулярен.

Следствие 4 [6]. Пусть C - двоичный линейный ПР-код, дуальный код C^⊥

которого имеет четные веса, симметричные относительно (n + 1)/2. Если группа

Aut(C^∗) транзитивна, то C^∗ полностью регулярен.

Рассмотрим двоичный примитивный код БЧХ C, имеющий параметры [2^m - 1,

2^m - 1 - 2m, 5], где m ≥ 3 нечетно. Веса дуального кода удовлетворяют условиям

следствия 4, и C^∗ инвариантен относительно действия аффинной группы слева. Сле-

довательно, C^∗ - ПР-код с радиусом покрытия ρ^∗ = s^∗ = 4 и (радиусом упаковки)

e^∗ = 2. Этот результат можно получить из [24], где было показано, что рассматри-

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

β₀ = β₁ = 1, β₂ = β₃ =

(n - 1)

Согласно теореме 10 расширенные коды БЧХ равномерно упакованы, а в силу пред-

ложения 4 эти коды полностью регулярны.

Рассмотрим теперь коды, которые исследовались Кальдербэнком и Гёталсом в

[40,41], а именно трехвесовые циклические подкоды выколотых кодов Рида - Малле-

ра второго порядка. Обозначим через C код, дуальный к одному из таких кодов.

Код C полностью регулярен, а C^∗ инвариантен относительно действия аффинной

группы слева. Опять убеждаемся, что три ненулевых веса кода C^⊥ удовлетворяют

условиям следствия 4. Следовательно, C^∗ - ПР-код с ρ^∗ = s^∗ = 4 и e^∗ = 1.

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

Следствие 5 [6]. Пусть двоичный код C имеет четные дуальные расстоя-

ния, симметричные относительно (n + 1)/2. Если C полностью регулярен и его

группа автоморфизмов Aut(C^∗) транзитивна, то C^∗ полностью регулярен.

Из метода построения кодов Препараты, представленного в [42], вытекает, что

группа автоморфизмов расширенного кода Препараты транзитивна. Его выколотый

код, т.е. код Препараты длины n = 22m -1, m = 2, 3, . . . , является ПР-кодом [2], а его

дуальные расстояния - это расстояния кода Кердока [43], удовлетворяющие усло-

виям следствия 5. Отсюда заключаем, что расширенный код Препараты является

полностью регулярным [2] с ρ^∗ = s^∗ = 4 и e^∗ = 2.

Рассмотрим (12, 24, 6)-код Адамара C^∗. Известно, что C равномерно упакован с

дуальными расстояниями 4, 6, 8 [4, 44]. Группа автоморфизмов Aut(C^∗) изоморфна

группе Матье M₁₂. Следовательно, C^∗ полностью регулярен с ρ^∗ = s^∗ = 4 и e^∗ = 2.

В [37] было доказано следующее

Предложение 8 [37]. Пусть C - двоичный полностью регулярный код с па-

раметрами (n, d).

(i) Если (n, d) = (12, 6), то C эквивалентен коду Адамара;

(ii) Если (n, d) = (11, 5), то C эквивалентен выколотому коду Адамара.

Результаты Соле [6] были несколько усилены Брауэром в [45].

Предложение 9 [45]. Пусть C - двоичный ПР-код. Если матрицы внешних

спектров всех выколотых кодов, полученных из C^∗, имеют одно и то же множе-

ство строк, и в частности, если C^∗ инвариантен относительно группы, транзи-

тивной на множестве координатных позиций, то C^∗ полностью регулярен.

Следствие 6 [45]. Код C^∗ полностью регулярен, если и только если все его

выколотые коды являются ПР-кодами с одинаковым внешним спектром расстоя-

ний.

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

которых C^∗ был бы ПР-кодом. Из последнего следствия можно вывести некоторые

необходимые условия на выколотые коды, полученные из C^∗, в частности, на код C.

Для любого двоичного вектора v = (v₁, . . . , v_n) и для каждого i = 1, . . . , n опре-

делим вектор

τ_i(v) = (v₁, . . . , vi-1, p(v), vi+1, . . . , v_n),

где p(v) обозначает четность исходного вектора v, т.е.

∑

p(v) ≡

v_i (mod 2).

i=1

Для каждой позиции i = 1, . . . , n определим код C[i] = {τ_i(x) | x ∈ C}.

Лемма 1. Код C^∗ полностью регулярен, если и только если C и C[i] - ПР-коды

для всех i = 1, . . . , n.

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

ный i-выкалыванием кода D. Через σ_i,j обозначим транспозицию координат i и j.

Предположим, что при расширении добавляется (n + 1)-я координата. Получаем,

очевидно, что

C[i] = (σi,n+1(C^∗))(i) и C = (C^∗)(n+1).

Результат теперь вытекает из следствия 6. ▴

Предложение 10. Если C^∗ является ПР-кодом, то для всех i = 1,...,n

(i) Весовые спектры кодов C и C[i] совпадают;

(ii) Минимальные расстояния кодов C и C[i] совпадают и нечетны;

(iii) Внешние расстояния кодов C и C[i] совпадают;

(iv) Радиусы покрытия кодов C и C[i] совпадают.

Доказательство. Утверждение (i) следует из того, что для каждого кодового

слова x строка B_x должна быть одной и той же для всех кодов C и C[i]. Утверждения

(ii) и (iii) прямо вытекают из (i).

Если радиус покрытия кода C равен ρ, то радиус покрытия кода C^∗ равен ρ^∗ =

= ρ + 1. Отсюда, следовательно, получаем (iv). ▴

Теперь у нас есть следующее необходимое условие на код C (или C[i]).

Следствие 7. Если C^∗ - ПР-код длины n + 1 с минимальным расстоянием

d^∗ = 2e + 2 ≥ 4, то для всех нечетных w имеет место равенство

(n - w)A_w = (w + 1)Aw+1,

(3)

где A_w - число кодовых слов веса w ≥ 2e + 1 в коде C (или C[i]).

Доказательство. Обозначим через A∗w+1 число кодовых слов веса w+1 в ко-

де C^∗, где w + 1 нечетно. Множество C∗w+1 всех слов веса w + 1 образует согласно

теореме 1 схему T(n+1, w+1, 2, λ∗2). Число кодовых слов C∗w+1 с ненулевым элемен-

том в позиции n + 1, т.е. число повторений схемы, равно r^∗. Очевидно, что r^∗ = A_w.

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

A∗w+1(w + 1) = (n + 1)r^∗.

(4)

Объединяя (4) с очевидным равенством A∗w+1 = Aw+1 + A_w, получаем результат. ▴

В частности, любой совершенный код должен удовлетворять соотношению (3).

Для случая двоичных совершенных кодов с d = 3 это рекуррентное выражение

хорошо известно (см., например, [21]):

)

⁽n

(n - i + 1)Ai-1 + A_i + (i + 1)Ai+1 =

(5)

Объединяя теперь (3) и (5), получаем

Следствие 8. Для любого совершенного кода с d = 3, содержащего нулевое

кодовое слово, число кодовых слов веса i равно

⎧

⁽n⁾

⎨

- Ai-1, если i нечетно,

i n-i+1

A_i =

⎩n-i+1

Ai-1,

если i четно.

Из [19] мы знаем, что четная половина (двоичного) [23, 12, 7]-кода Голея, скажем,

код C^∗, является ПР-кодом. Выкалывая этот код по любой координате, получаем

код C со следующим весовым спектром:

A₀

A₇

A₈

A₁₁

A₁₂

A₁₅

A₁₆

176

330

672

616

176

Код C, конечно, полностью регулярен [19], и следовательно, подтверждает равен-

ство (3), в чем нетрудно убедиться.

§ 3. Полностью транзитивные коды

Полностью транзитивные коды (ПТ-коды) были впервые введены Соле в 1990 г.

[6] как подкласс двоичных линейных ПР-кодов. Пусть C - двоичный линейный код.

Рассмотрим действие его группы автоморфизмов Aut(C) на фактор-пространстве

Fn2/C: для любого смежного класса C + x и любого автоморфизма σ ∈ Aut(C)

положим

σ(C + x) = σ(C) + σ(x) = C + σ(x).

Определение 9 [6]. Двоичный линейный код C с радиусом покрытия ρ на-

зывается полностью транзитивным (ПТ-кодом), если группа Aut(C) индуцирует

ρ + 1 орбиту при действии на (множестве смежных классов) Fn2/C.

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

тры, то имеет место следующий факт.

Предложение 11 [6]. Если C - двоичный линейный ПТ-код, то C полностью

регулярен.

Следующий факт представляет собой усиление теоремы 6.

Предложение 12 [36]. Если C - неантиподальный двоичный линейный ПТ-

код, то C ∪ C(ρ) также является ПТ-кодом.

ПТ-коды и дистанционно регулярные графы тесно связаны. В частности, имеет

место следующее

Предложение 13. Пусть C - двоичный линейный ПР-код с радиусом покры-

тия ρ и массивом пересечений IA = {b₀, . . ., bρ-1; c₁, . . . , c_ρ}, и пусть Γ_C - граф,

построенный на смежных классах кода C. Тогда

(i) Граф Γ_C дистанционно регулярен с диаметром D = ρ и тем же самым мас-

сивом пересечений IA [10];

(ii) Если C полностью транзитивен, то Γ_C дистанционно транзитивен [46].

Следовательно, согласно предложению 13 любой ПР- или ПТ-код индуцирует

дистанционно регулярный или дистанционно транзитивный граф соответственно.

В настоящей работе мы не касаемся соответствующих дистанционно регулярных и

дистанционно транзитивных графов, существование которых вытекает из связанных

с ними ПР- и ПТ-кодов соответственно. Об этих графах с такими же массивами

пересечений, что и коды, см. в работах [10-12], где они подробно рассматриваются.

Для заданной группы перестановок G степени n (действующей на множестве из n

элементов) скажем, что G является t-транзитивной (соответственно, t-однородной),

если она переставляет любой (упорядоченный) t-набор (соответственно, t-множест-

во) в любой другой t-набор (соответственно, t-множество). Группа G транзитивна,

если она 1-транзитивна. Теорема Ливингстона и Вагнера [47] утверждает, что если G

является i-однородной с i ≤ n/2, то G также j-однородна для j ≤ i. Из этого факта

вытекает следующее

Предложение 14 [6]. Пусть C - двоичный линейный код длины n с радиусом

покрытия ρ ≤ n/2. Если Aut(C) является ρ-однородной, то код C полностью

транзитивен.

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

(i) Все совершенные двоичные линейные коды (код с повторением, коды Хэмминга

и двоичный код Голея);

(ii) Все расширенные двоичные линейные совершенные коды.

Предложение 14 дает достаточное (но не необходимое) условие для того, что-

бы код был ПТ-кодом. Это можно увидеть из двоичного [9, 5, 3]-кода C, дуального

коду, полученному кронекеровым произведением двух [3, 2, 2]-кодов с проверкой на

четность. Код C равномерно упакован в узком смысле [2, 6] с ρ = s = 2 и e = 1.

Более того, код C полностью транзитивен, однако группа Aut(C) транзитивна, но

не 2-однородна.

Необходимое условие выглядит следующим образом.

Предложение 15 [6]. Группа автоморфизмов Aut(C) полностью регулярно-

го двоичного линейного кода C, исправляющего e ошибок, e-однородна.

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

транзитивным, рассмотрим двоичный примитивный [2^m - 1, 2^m - 2m - 1, 5; 3]-код

БЧХ, т.е. циклический код C с m > 4 и нечетным m. Этот код полностью регуля-

рен [2,24,33] с массивом пересечений {n, n-1, (n+3)/2; 1, 2, (n-1)/2}, где n = 2^m -1

(эти же коды с ℓ = 3 принадлежат семейству из п. 5.13; см. также п. 2.4). Как следует

из работы [48], группа автоморфизмов Aut(C) - это полулинейная группа ΓL(1, 2^m)

поля F₂m над F₂m (напомним, что полулинейная группа, обозначаемая через ΓL(t, q),

состоит из всех обратимых полулинейных преобразований (F_q)^t над F_q). Если q = p^r,

то хорошо известно, что |ΓL(t, q)| = r|GL(t, q)|, где через GL(t, q) обозначена общая

линейная группа (см., например, в [25, с. 163]; в нашем случае t = 1). Следовательно,

порядок группы Aut(C) равен |ΓL(1, 2^m)| = m|GL(1, 2^m)| = m(2^m - 1). Так как C

имеет радиус упаковки e = 2, то известно, что C имеет ровно (2^m - 1)(2m-1 - 1)

смежных классов веса 2. Так как число смежных классов больше, чем порядок груп-

пы |Aut(C)|, то они не могут принадлежать одной и той же орбите, индуцируемой

действием Aut(C). Значит, C не полностью транзитивен.

Аналогично совершенным и квазисовершенным РУ-кодам, несуществование ПТ-

кодов также установлено для значений e > 3. В 2000 г. Боржес и Рифа [16] устано-

вили, что имеет место следующая

Теорема 11 [16]. Если C - нетривиальный двоичный линейный ПТ-код, ис-

правляющий e ошибок, то e ≤ 4.

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

и на некоторых оценках мощности кода. Используя затем границу Грайсмера и несу-

ществование некоторых схем, этот результат был улучшен. В 2001 г. Боржес, Рифа

и Зиновьев [17] доказали следующий результат.

Теорема 12 [17]. Если C - нетривиальный двоичный линейный ПТ-код, ис-

правляющий e ошибок, то e ≤ 3.

Ясно, что определение 9 может быть расширено на недвоичные линейные коды.

Джудичи и Прейгер [7,8] исследовали этот более общий случай. Эти коды, вклю-

чающие двоичные ПТ-коды, введенные Соле [6], они назвали полностью транзи-

тивными на смежных классах. В предшествующем препринте Годсил и Прейгер

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

та [49] представляет собой обновленную версию этого препринта.

Определение 10 [49]. Код C ⊂ F^nq является G-полностью транзитивным,

или просто полностью транзитивным, если существует подгруппа G группы авто-

морфизмов Aut(F^nq), такая что каждая подкомпонента (слой) C(i) дистанционного

разбиения кода C является G-орбитой.

Предложение 16 [8]. Если код C ⊂ F^nq полностью транзитивен в смысле

определения 10, то он полностью регулярен.

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

не является Aut(C)-полностью транзитивным в смысле определения 10. Это связано

с тем, что группа Aut(C) часто даже не транзитивна на C, например, когда C имеет

кодовые слова разного веса.

Для линейного кода C ⊂ F^nq определим N_C как множество всех сдвигов про-

странства F^nq векторами из кода C, т.е. N_C = {τ_x | x ∈ C}, где τ_x(v) = v + x для

каждого вектора v ∈ F^nq. Ясно, что N_C - подгруппа, так как C - линейный код.

Пусть G получена полупрямым произведением N_C и Aut(C), т.е. G = N_C ⋊ Aut(C).

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

иное, как смежные классы кода C. В частности, C является G-орбитой [8]. Из такого

рода соображений вытекает следующая

Теорема 13 [8]. Пусть C ⊂ F^nq - линейный код. Тогда C полностью транзи-

тивен на смежных классах, если и только если C является (N_C ⋊ Aut(C))-пол-

ностью транзитивным.

Однако для q ≤ 3 эти два понятия эквивалентны.

Теорема 14 [8]. Пусть C ⊂ F^nq - линейный код, причем q ≤ 3. Тогда C полно-

стью транзитивен на смежных классах, если и только если C полностью тран-

зитивен.

Пусть q ≥ 7 - степень простого числа, q = 8, и пусть C - код с повторением

в F3q, т.е. [3, 1, 3]_q-код. Определим группу G = Sq ⋊S₃. Прямая проверка показывает,

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

на смежных классах [8].

Следует отметить, что полная транзитивность представляет собой довольно спе-

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

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

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

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

чая, когда они пересекаются с кодами Кердока, т.е. за исключением кода Нордстро-

ма - Робинсона.

Теорема 15 [9]. Код Препараты длины n и его расширение полностью тран-

зитивны, если и только если n = 15.

§4. Полностью регулярные коды в схемах Джонсона

Схема Джонсона J(n, w) - это множество всех двоичных векторов длины n и

веса w (т.е. векторов с w ненулевыми позициями). Произвольное подмножество C

схемы J(n, w) - это равновесный код, имеющий четыре параметра, а именно: дли-

ну n, постоянный вес слов w, минимальное расстояние (Хэмминга) d = 2δ и мощ-

ность (число кодовых слов) N = |C|. Если определить расстояние между двумя

векторами x и y веса w как половину расстояния Хэмминга (в самом деле, рассто-

яние Хэмминга между двумя словами одного веса всегда четно), то получим новое

расстояние (также являющееся метрикой), которое называется расстоянием Джон-

сона и обозначается здесь через d_J . Два вектора x и y на расстоянии d_J = 1 друг от

друга называются соседями.

Со схемой Джонсона естественным образом связывается граф Джонсона, часто

обозначаемый таким же образом, как и схема (т.е. J(n, w)). Вершинами этого графа

являются все двоичные векторы длины n и веса w, и две вершины связаны ребром,

если соответствующие векторы являются соседями. Две вершины x и y находятся

друг от друга на расстоянии Джонсона d_J (x, y), если оно равно числу ребер в крат-

чайшем пути между x и y. Ясно, что два графа Джонсона J(n, w) и J(n, n - w)

изоморфны друг другу, и поэтому мы рассматриваем только случай w ≤ n/2.

Определение 11. Совершенной m-раскраской схемы Джонсона J(n,w) назы-

вается раскраска векторов J(n, w) в m цветов {1, . . ., m}, такая что фиксированный

вектор x цвета i имеет a_i,j соседей y цвета j, причем a_i,j не зависит от выбора x.

Очевидно, что такие m-раскраски графа Джонсона представляют собой не что

иное, как дистанционно регулярные графы. Матрица A = [a_i,j ] называется матри-

цей параметров совершенной раскраски, или кратко матрицей параметров. Совер-

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

регулярного кода.

Определение 12. Равновесный код C длины n с весом слов w и минималь-

ным расстоянием d_J = 2e + 1 является совершенным e-кодом в J(n, w), если для

любого вектора x ∈ J(n, w) найдется в точности одно кодовое слово c ∈ C, такое

что d_J (x, c) ≤ e. Другими словами, все шары радиуса (Джонсона) e, проведенные

вокруг каждого кодового слова кода C, не пересекаются друг с другом и заполняют

все множество векторов схемы J(n, w).

Обозначим через Φ_e(n, w) мощность шара в J(n, w) радиуса e. Очевидно, что

∑

⁽w⁾⁽n - w⁾

Φ_e(n, w) =

i=0

Тогда для совершенного e-кода C в J(n, w) по условию сферической упаковки по-

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

⁽n⁾

|C| =

Φ_e(n, w)

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

Известны следующие тривиальные примеры совершенных e-кодов в J(n, w):

1. Схема Джонсона J(n, w) с e = 0;

2. Любой вектор x из J(n, w) с e = w;

3. Для случая n = 4e + 2 и w = 2e + 1 любая пара векторов x и y из J(n, w) на

расстоянии d_J (x, y) = w образует совершенный e-код.

Заметим, что в специальном случае n = 2w схема Джонсона J(2w, w) полностью

транзитивна, и следовательно, полностью регулярна в схеме Хэмминга H(2, 2w)

(см. п. 5.8).

Проблема существования нетривиальных совершенных кодов в схеме Джонсо-

на была поставлена в 1973 г. Дельсартом [3] (который высказал гипотезу, что та-

ких кодов не существует), и эта проблема до сих пор открыта. Баннаи [50] доказал

несуществование совершенных e-кодов в схемах Джонсона J(2w + 1, w) при e ≥ 2.

Хаммонд [51] улучшил этот результат, показав несуществование в J(n, w) нетриви-

альных совершенных кодов для значений n ∈ {2w - 2, 2w - 1, 2w + 1, 2w + 2}. От-

метим, что обобщение теоремы Ллойда (которая была основным инструментом для

доказательства несуществования совершенных кодов в схемах Хэмминга; см. рабо-

ты [14,15] и библиографию в них) на схемы Джонсона [3,50] не привело к каким-либо

значительным результатам. Многие результаты о несуществовании были получены

в работах Этциона и Шварца [52-54]. Используя условия делимости, вытекающие из

существования совершенных кодов, а также из систем Штейнера, которые должны

сосуществовать с совершенными кодами в J(n, w), Этцион [52] получил следующие

результаты:

Теорема 16 [52]. Совершенных e-кодов не существует

1) в схемах J(2w + e + 1, w);

2) в схемах J(2w + p, w), p - простое;

3) в схемах J(2w + 2p, w), p - простое, p = 3;

4) в схемах J(2w + 3p, w), p - простое, p = 2, 3, 5.

Cимабукуро [55] добавил к этому списку схемы J(2w + p², w) (в которых совер-

шенных e-кодов нет). Этцион и Шварц [53] использовали другой подход для ре-

зультатов несуществования. Они использовали k-регулярность совершенных кодов

в схемах J(n, w). К этому понятию мы вернемся при рассмотрении совершенных

2-раскрашиваний. Для случая небольших e ≤ 2 Этцион и Шварц [53] получили

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

Теорема 17 [53]. В схеме J(n,w) не существует совершенных 1-кодов для

n ≤ 50000 и совершенных 2-кодов для n ≤ 40000.

Гордон [56] получил необходимые условия существования совершенных 1-кодов,

рассматривая возможные простые делители числа Φ_e(w, a). При этом использова-

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

ляет собой следующую лемму Куммера.

Лемма 2 [57]. Пусть p - простое число. Множитель p встречается в выра-

⁽a⁾

жении

столько раз, сколько переносов в следующий разряд появляется при

сложении чисел b и a - b по модулю p.

Второй результат - это следующая лемма Локстона [58] (в доказательстве кото-

рой Бернштейн [59] устранил одну неточность).

Лемма 3 [58,59]. Количество совершенных степеней (т.е. чисел вида a^m, где

a, m > 1) в интервале [w, w +

√w ] не превосходит

√

exp(40

log log w log log log w).

Используя эти две леммы, Гордон [56] установил, что справедлива следующая

Теорема 18 [56]. В схеме J(n,w) не существует совершенных 1-кодов для

длин n ≤ 2²⁵⁰.

К настоящему времени получен целый ряд необходимых условий для существова-

ния совершенных кодов в схемах Джонсона, часть которых мы рассмотрим. Руз [60]

(см. также [53] с более простым доказательством) ограничил длину n совершенного

e-кода в J(n, w) сверху, а Мовсисян [61] снизу. Это приводит к следующему интер-

валу длин n для существования совершенных кодов.

Теорема 19 [60,61]. Если C - совершенный e-код в схеме Джонсона J(n,w),

то его длина n ограничена следующими пределами:

2e + 1

(w + 1) ≤ n ≤

(w - 1).

(6)

e+1

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

Следствие 9 [61]. Для любого фиксированного w число совершенных e-кодов

в схеме J(n, w) конечно.

Пусть C ∈ J(n, w) - совершенный e-код. Для любого вектора y из J(n, w + 1)

обозначим через R(y) число кодовых слов x ∈ C, таких что d_J (x, y) = 2e + 1.

Следствие 10 [61]. Если C - совершенный e-код в J(n,w), то для каждого

вектора y ∈ J(n, w + 1) множество R(y) имеет мощность (w + 1)/(e + 1), откуда

следует, что e + 1 делит w + 1.

Из теоремы 19 непосредственно следует, что вес w векторов совершенного e-кода

ограничен снизу: w ≥ 2e + 1. Мовсисян [61] показал, что вес w должен расти с ро-

стом e как квадратичная функция.

Предложение 17 [61]. Для нетривиального совершенного e-кода в J(n,w) ве-

личина w ограничена снизу следующим образом:

w ≥ e² + 3e + 1.

Ясно, что два замечательных комбинаторных объекта в схемах Джонсона - си-

стемы Штейнера S(n, w, t) и совершенные e-коды - должны быть тесно связаны.

Несколько результатов относительно такой взаимосвязи получено в [52,62].

Предложение 18 [62]. Совершенный e-код в схеме J(n,w) сосуществует

с системой Штейнера S(n, w, t), если и только если выполняются следующие ра-

венства:

n = 3w - 3, t = w - 2 и e = 1.

(7)

Предложение 19 [52]. Существование совершенного e-кода в схеме J(n,w)

влечет существование систем Штейнера S(w, 2e+1, e+1) и S(n-w, 2e+1, e+1).

Предложение 20 [52]. Единственными системами Штейнера, являющими-

ся совершенными кодами в схеме Джонсона J(n, w), являются тривиальные си-

стемы S(2w, w, 1) и S(n, w, w).

Существование совершенных равновесных кодов тесно связано с задачей D-пред-

ставления кодов [63,64], которую мы сейчас обсудим. Пусть A - любое подмножество

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

стве натуральных чисел. Для вектора x из A определим область Дирихле D_x(ϕ)

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

D_x(ϕ) = {y ∈ Fn2 : ϕ(d_J (x, y)) ≤ ϕ(d_J (z, y)), ∀z ∈ A},

и будем обозначать ее просто D_x, когда ϕ - тождественная функция.

Определение 13. Множество A векторов из Fn2 называется D(ϕ)-представи-

мым кодом (D-представимым, соответственно), если и только если области Дирихле

D_x(ϕ) (соответственно, D_x) всех векторов A попарно различны в Fn2 (т.е. не пересе-

каются).

Предложение 21 [63,64]. Множество C - совершенный e-код в J(n,w), если

и только если этот код D(ϕ)-представим для любой строго монотонной функ-

ции ϕ.

Рассмотрим теперь некоторые совершенные раскраски в схемах Джонсона. Нач-

нем с простого наблюдения о том, что совершенный 1-код в J(n, w) индуцирует

совершенную 2-раскраску P схемы J(n, w) со следующей матрицей A:

[

]

w(n - w)

w(n - w) - 1

Для этого надо покрасить все кодовые слова в один цвет (обычно белый), а все

другие векторы из J(n, w) - в другой (обычно черный) [65]. Начнем с понятия k-ре-

гулярности, введенного в [65] для совершенных 2-раскрасок и обобщающего соот-

ветствующее понятие для совершенных e-кодов [53]. Для двух двоичных векторов

x и y длины n будем писать x ≼ y, если x покрыт y, т.е. если x_i ≤ y_i для всех

i ∈ {1,...,n}. Для совершенной 2-раскраски P схемы J(n,w) обозначим через W

и B множества векторов этой схемы белого и черного цвета соответственно. Для

двух векторов x и y, таких что y ≼ x (т.е. x покрывает y), обозначим через Γ^yx грань,

индуцированную x и y, т.е. следующее множество двоичных векторов из Fn2:

Γ^yx = {z + y + x : z ∈ Fn2, x ≼ z}

(т.е. Γ^yx состоит из всех 2n-wt(x) векторов пространства Fn2, покрывающих y и сов-

падающих с y на носителе x).

Определение 14 [65]. Совершенная 2-раскраска P схемы Джонсона J(n,w)

называется k-регулярной, если существуют k² чисел γ_ij , таких что для каждых

двоичных векторов x и y длины n, таких что y ≼ x, с весами wt(x) = i и wt(y) = j,

где i ≤ k ≤ w, имеет место следующее равенство:

|Γ^yx ∩ W | = γ_ij .

Достаточное условие k-регулярности совершенной 2-раскраски дает

Предложение 22 [65]. Пусть P - совершенная 2-раскраска схемы Джонсона

J (n, w) с матрицей A = [a_ij ], i, j ∈ {1, 2}. Тогда число k₁, где

(

√

)

k₁ =

n+1-

(n - 2w + 1)² + 4(w + a₁₁ - a₂₁)

является натуральным, а раскраска P является (k₁ - 1)-регулярной.

Следствие 11 [65]. Пусть P

- совершенная 2-раскраска схемы Джонсона

J (n, w) с матрицей A = [a_ij ], i, j = 1, 2. Тогда выражение

(

)

a₂₁

n-i

a₁₂ + a₂₁ w - i + j

представляет собой целое число для любых i и j, таких что 0 ≤ j ≤ i ≤ k₁ - 1,

где k₁ определено в предложении 22.

Используя эти результаты, в [66] было доказано несуществование некоторых со-

вершенных 2-раскрасок для длин n ≤ 13. В частности, это было сделано для следу-

ющих значений (n, w):

(n, w) ∈ {(9, 3), (10, 5), (11, 3), (12, 4), (12, 5), (12, 6), (13, 4)}

с соответствующими матрицами параметров для каждой пары (n, w) из этого мно-

жества.

Согласно [67] наименьший открытый случай для существования совершенной

2-раскраски в схеме Джонсона J(n, w) - это совершенная 2-раскраска в схеме J(9, 3)

со следующей матрицей параметров:

[

]

Очевидно, что система Штейнера S(n, w, t), будучи совершенным комбинатор-

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

раскрасок. Действительно, это так для случаев w = t + 1, w = t + 2 [68, 69] и неко-

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

Мартином [68, 69]. Любая простая схема T = T (n, w, t, λ) (т.е. множество различ-

ных векторов схемы Джонсона J(n, w)) определяет естественным образом (как и

любой код в схеме Хэмминга) разбиение всех векторов схемы J(n, w) согласно их

расстоянию от T . Для натурального числа i положим

{

}

T (i) := x ∈ J(n, w) : mindJ (x, b) = i

b∈T

Наибольшее число i, для которого множество T(i) не пусто, обозначим через ρ и

назовем это число радиусом покрытия схемы T . Разбиение

P = {T = T(0),T(1),...,T(ρ)},

состоящее из непустых множеств T(i), называется дистанционным разбиением.

Определение 15 [68,70]. Простая схема T = T(n,w,t,λ) называется полно-

стью регулярной (ПР-схемой) в J(n, w), если для каждого числа i ∈ {0, 1, . . . , ρ}

каждый вектор из T (i) имеет γ_i соседей в T (i - 1), α_i соседей в T (i) и β_i соседей

в T(i + 1).

Согласно Мееровичу [70], если T полностью регулярна в J(n, w) и имеет силу ноль

(t = 0), т.е. представляет собой схему T (n, w, 0, λ), то существует подмножество V

схемы J(n, w), такое что либо

T = {B : |B| = w, B ⊆ V }, либо T = {B : |B| = w, V ⊆ B}.

Мартин [68] классифицировал ПР-схемы, имеющие силу 1, т.е. схемы T(n, w, 1, λ).

Чтобы сформулировать этот результат, определим так называемые полные схемы

группового типа. Рассмотрим схему Джонсона J(n, w) с n = hℓ и w = uℓ, где ℓ ≥ 2

и h ≥ 2u. Пусть {X₁,X₂,...,X_h} - разбиение координатного множества {1,2,...,n}

⁽h⁾

на h групп размера ℓ каждая. Блоками B схемы T будут все

подмножеств вида

⋃

B= X_i,

i∈I

где I - любое u-подмножество множества {1, 2, . . . , h}. Так как ℓ ≥ 2 и h > u, такая

схема имеет силу один (т.е. t = 1). Ясно также, что эта схема (по построению) имеет

минимальное расстояние (Джонсона) ℓ. Такая схема была названа Мартином [68]

полной схемой группового типа.

Предложение 23 [68]. Пусть T - полная схема группового типа в J(n,w).

Тогда T полностью регулярна, если и только если выполняется одно из следующих

условий:

1) ℓ = w и n = 2w, а схема T - антиподальная пара (т.е. два непересекающихся

вектора);

2) ℓ = 2;

3) ℓ = 3 и u = 1.

Имеются и другие ПР-схемы силы один (см. работу [68] и библиографию в ней).

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

Теорема 20 [68]. Пусть T - простая ПР-схема силы один в J(n,w). Тогда T -

полная схема группового типа.

Пусть T - схема T (n, w, t, λ). Определим степень схемы T как число s = s(T )

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

стояний между двумя различными блоками схемы T ):

s(T ) := |{d_J (b, b^′) : b, b^′ ∈ T, b = b^′}.

Аналогично схеме Хэмминга для схемы T в схеме Джонсона J(n, w) можно опреде-

лить дуальную степень (см. [3]), обозначаемую s^∗ = s^∗(T ). Пусть d_J (T ) обозначает

минимальное расстояние (Джонсона) между различными векторами схемы T .

Предложение 24 [3]. Любая схема с дуальной степенью s^∗ и минимальным

расстоянием d_J (T ), такими что d_J (T ) ≥ 2s^∗ - 1, полностью регулярна.

Большая схема Витта, т.е. система Штейнера S(24, 8, 5), полностью регулярна

в J(24,8). Она имеет дуальную степень s^∗ = 2 и минимальное расстояние (Джон-

сона) 4. Следовательно, согласно предложению 24 эта система Штейнера S(24, 8, 5)

полностью регулярна (что было отмечено еще Дельсартом [3]). Так как вычисление

величины s^∗ довольно затруднительно, обычно используется несколько более слабое

достаточное условие [69]:

Предложение 25 [3,68]. Любая простая схема T силы t с минимальным рас-

стоянием d_J(T) ≥ 2(w - t) - 1 полностью регулярна.

Откуда немедленно вытекает

Теорема 21 [69]. Имеют место следующие утверждения:

1. Любая схема T(n, w, t, λ) с w = t + 1 полностью регулярна;

2. Система Штейнера S(n, w, t) с w = t + 2 полностью регулярна.

Мы немедленно заключаем, что маленькие схемы Витта, т.е. системы Штейнера

S(12, 6, 5) и S(11, 5, 4), полностью регулярны [69].

Чтобы проверить полную регулярность второй большой схемы Витта (системы

Штейнера S(23, 7, 4)), необходимо для всех i ∈ {0, . . . , ρ} вычислить числовые кон-

станты (α_i, β_i, γ_i) [69]. Так как первая большая схема Витта S(24, 8, 5) имеет радиус

покрытия 2, то вторая большая схема Витта S(23, 7, 4) (получаемая 1-укорочением

из S(24, 8, 5)) имеет радиус покрытия ρ = 3. Поэтому надо вычислить константы

(α_i, β_i, γ_i) для i ∈ {0, 1, 2, 3}. Для этой схемы имеем [69]

α₀ = 0,

β₀ = 112, γ₀ = 0,

α₁ = 21,

β₁ = 90, γ₁ = 1,

α₂ = 108,

β₂ = 2,

γ₂ = 12,

α₃ = 7,

β₃ = 0,

γ₃ = 105.

Отсюда мы заключаем, что система Штейнера S(23, 7, 4) полностью регулярна. Тре-

тья большая схема Витта, т.е. система Штейнера S(22, 6, 3), уже не полностью ре-

гулярна [69]. Тот же отрицательный результат имеет место для следующей системы

Штейнера S(21, 5, 2), т.е. для проективной плоскости P G(2, 4) порядка 4 [69].

Следующая простая идея позволяет получить новые ПР-схемы из систем Штей-

нера. Это специальный случай более общей известной конструкции новых схем из

уже существующих (см., например, [2]). Определим k-тень схемы T (n, w, t, λ) как

семейство всех k-множеств, содержащихся в некотором блоке схемы T. Полученная

новая схема уже находится в J(n, k). Годсил [71] заметил следующий факт.

Предложение 26 [69]. Для любой системы Штейнера S(n,w,t) ее (t + 2)-

тень полностью регулярна с радиусом покрытия ρ = 2.

Необходимое условие для существования ПР-схемы дает следующее

Предложение 27 [69]. Если T является ПР-схемой в J(n,w) с минималь-

ным расстоянием d_J (T ) < w, то

d_J (T) ≤

(2w + 1).

Отсюда получаем

Следствие 12 [69]. Если система Штейнера S(n,w,t) полностью регулярна,

то w ≤ 3t - 2.

Следующий замечательный результат [69] классифицирует все возможные сим-

метричные ПР-схемы T (n, w, 2, λ) (т.е. схемы T , для которых n = |T |).

Теорема 22 [69]. Если T - симметричная ПР-схема T(n,w,2,λ), то T - про-

ективная плоскость (т.е. λ = 1) порядка 2 или 3 (т.е. одна из двух систем Штей-

нера S(7, 3, 2) или S(13, 4, 2)).

Напомним, что схема T(n, w, t, λ) с t ≥ 2 называется квазисимметричной, если

ее степень равна s = 2 (т.е. любые два различных блока схемы находятся друг от

друга на одном из двух расстояний). Для несимметричных схем Мартин [69] получил

следующие необходимые условия.

Следствие 13 [69]. Имеют место следующие утверждения:

1. Если ПР-схема T(n, w, 2, λ) имеет минимальное расстояние d_J (T) ≥ 4, то

λ≥n-w.

2. В квазисимметричной ПР-схеме T в J(n, w) расстояние d_J(T) ≤ 7.

Для заданной системы Штейнера S(n, w, w - 1) (полностью регулярной согласно

теореме 21) Мартин [69] заметил, что раскраска J(n, w) в соответствии с расстоянием

от S является совершенной с матрицей параметров

[

]

w(n - w)

w w(n - w - 1)

Этот результат был усилен в [72] с использованием так называемой индуцированной

совершенной раскраски, идея которой была заложена в более ранних работах [73] (ди-

станционно бирегулярные графы) и [74] (индуцированные собственные функции).

Предложение 28 [72]. Система Штейнера S(n,w,w -1) индуцирует совер-

шенную 2-раскраску схемы J(n, w + 1) с матрицей параметров

[

]

(w + 1)(n - 2w - 1)

(w + 1)w

w(n - 2w)

w² - 2w - 1 + n

Так как имеются бесконечные семейства троек и четверок Штейнера - S(n, 3, 2)

и S(n + 1,4,3) (которые существуют для любого n ≡ 1,3 (mod 6)), то получаем

Предложение 29 [72]. Имеют место следующие утверждения:

1. Для каждого n ≡ 1, 3 (mod 6) существует совершенная 2-раскраска J(n, 4) с

матрицей параметров

[

]

4(n - 7)

3(n - 8) n + 2

2. Для каждого n ≡ 2, 4 (mod 6) существует совершенная 2-раскраска J(n, 5) с

матрицей параметров

[

]

5(n - 5)

4(n - 8) n + 7

Наконец, сформулируем еще один результат из [72] о раскраске, индуцированной

совершенным 1-кодом.

Предложение 30 [72]. Пусть C - совершенный 1-код в J(n,w). Тогда суще-

ствует совершенная 2-раскраска схемы J(n, w + 1) с матрицей параметров

[

]

(w + 1)(n - w - 2) w + 1

w(n - w - 1)

n-w-1

Аналогично ПР-кодам в схеме Хэмминга, содержащим большой подкласс ПТ-

кодов, подобное понятие существует и в схеме Джонсона. Схема T (n, w, t, λ), чье

дистанционное разбиение представляет собой разбиение орбит (т.е. для любого i =

= 0, 1, . . ., ρ множество T(i) является орбитой) под действием некоторой группы

автоморфизмов схемы J(n, w), называется полностью транзитивной схемой (см.

[49] для этого интересного подкласса ПР-схем).

О других результатах по совершенным e-кодам, ПР-схемам и совершенным рас-

краскам J(n, w), а также о примерах таких схем небольшой длины см. работы

[53, 54, 65-69, 72, 75].

§ 5. Существование и методы построения ПР-кодов

В этом параграфе приводятся бесконечные семейства (занумерованные в ви-

де (F.i)) и отдельные спорадические примеры (занумерованные в виде (S.i)) из-

вестных нам ПР-кодов. Для всех кодов даются их массивы пересечений IA (см.

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

в п. 2.1, и q - степень простого числа.

5.1. ПР- и ПТ-коды из совершенных кодов. В работах [1-3] описаны следующие

хорошо известные семейства ПР-кодов. Мы указываем также случаи, когда они яв-

ляются ПТ-кодами.

(F.1) Любой q-ичный совершенный (n, qⁿ/(1 + n(q - 1)), 3; 1)_q-код является ПР- и

ПТ-кодом с

IA = {(q - 1)n; 1}, где q ≥ 2, n ≥ 3.

(F.2) Любой q-ичный расширенный совершенный (n + 1, qⁿ/(1 + n(q - 1)), 4; 2)_q-код

является ПР-кодом (и ПТ-кодом в двоичном случае) с

IA = {(q - 1)(n + 1), (q - 1)n; 1, 4}, где q ≥ 2, n ≥ 4.

Код также полностью транзитивен для случая, когда q = 4 и m = 2.

(F.3) Любой q-ичный выколотый (n - 1, qⁿ/(1 + n(q - 1)), 2; 1)-код любого совершен-

ного (n, qⁿ/(1 + n(q - 1)), 3; 1)-кода является ПР- и ПТ-кодом с

IA = {(q - 1)(n - 1); q)}, где q, n ≥ 3.

Пусть B - любой q-ичный совершенный (n, N, 3)_q-код (n нечетно), и пусть C - лю-

бой его (n, N/q, 4)-подкод со следующим свойством: при любом выборе нулевого ко-

дового слова в B множество слов C₄ представляет собой q-ичную схему T (n, 4, 2, λ)_q,

где λ = (n - 3)/2. Тогда из [32, 39] получаем следующее:

(F.4) Для q ≥ 2 и n ≥ 4 код C - ПР-код с

IA = {n(q - 1), (n - 1)(q - 1), 1; 1, (n - 1), n(q - 1)}.

(F.5) В частности, для любой степени простого числа q = 2^u, где u ∈ {2, 3, . . .},

существует [q +1, q -2, 4; 3]_q-ПР-код, являющийся подкодом совершенного [q +1,

q - 1,3]_q-кода, с

IA = {q² - 1, q(q - 1), 1; 1, q, q² - 1}.

(F.6) Любой q-ичный (n, N, 3; 2)_q-код, полученный укорочением совершенного (n+1,

qN, 3; 1)_q-кода C, представляет собой ПР- и ПТ-код с

IA = {(q - 1)n, q - 1; 1, (q - 1)n}.

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

винами двоичного совершенного кода, дающих ПР-коды с разными массивами пе-

ресечений. Пусть C - двоичный совершенный (n, N, 3)-код. Из [19] известно, что

четная или нечетная половина кода C представляет собой ПР-код (входящий в се-

мейство (F.4)). Из [19] также следует, что выколотый код четной половины (совер-

шенного) кода C - это ПР-код (включенный в семейство (F.6)).

Другие половины двоичных кодов Хэмминга можно получить с помощью сле-

дующей конструкции. Пусть H_m обозначает проверочную матрицу двоичного кода

Хэмминга длины n = 2^m -1. Для заданного четного m ≥ 4 и целых i₁, i₂ ∈ {0, 1, 2, 3},

таких что i₁ = i₂, обозначим через vi1,i2 двоичный вектор длины n, в котором i-я по-

зиция v_i является следующей функцией значения веса i-го столбца h_i матрицы H_m:

^{1, если wt(h_i) ≡ i₁ или i₂ (mod 4),

v_i =

в противном случае.

Пусть Ci1,i2 - двоичный линейный [n = 2^m - 1, k = n - m - 1, 3]-код, где m четно,

заданный проверочной матрицей H_m(vi1,i2 ), полученной из проверочной матрицы

H_m (совершенного кода C той же длины) добавлением еще одной проверочной стро-

ки vi1,i2 . Тогда для результирующего кода Ci1,i2 имеем [38] следующее:

(F.7) Если {i₁, i₂} = {1, 2} или {i₁, i₂} = {2, 3}, то Ci1 ,i2 - антиподальная половина

кода Хэмминга, являющаяся [n, n - m - 1, 3; 3]-ПР- и ПТ-кодом с

IA = {n, (n + 1)/2, 1; 1, (n + 1)/2, n}.

(F.8) Если {i₁, i₂} = {0, 1} или {i₁, i₂} = {0, 3}, то Ci1,i2 - неантиподальная половина

кода Хэмминга, являющаяся [n, n - m - 1, 3; 3]-ПР- и ПТ-кодом с

IA = {n, (n - 3)/2, 1; 1, (n - 3)/2, n}.

Как можно увидеть из [38], если {i₁, i₂} = {0, 2}, то Ci1,i2 - четная половина кода

Хэмминга, которая, следовательно, входит в семейство (F.4). Если же {i₁, i₂} =

= {1, 3}, то Ci1,i2 - [n, n - m, 3]-код Хэмминга.

Расширения кодов (F.7) также полностью регулярны [38]:

(F.9) Расширение кода (F.7) является антиподальным [n + 1, n - m, 4; 4]-ПР- и ПТ-

кодом с

IA = {n + 1, n, (n + 1)/2, 1; 1, (n + 1)/2, n, n + 1}.

Из [32,76] имеем несколько семейств, полученных укорочением двоичных совер-

шенных кодов или расширенных совершенных кодов. Пусть C^∗ - произвольный дво-

ичный расширенный совершенный (n^∗, N^∗, 4)-код длины n^∗ = 2^m ≥ 8.

(F.10) Пусть C - (n = n^∗ - 2, N = N^∗/2, 2; 3)-код, полученный {(00), (11)}-укороче-

нием кода C^∗. Тогда C - ПР- и ПТ-код с

IA = {n, n - 2, 2; 2, n - 2, n}, где n = 2^m - 2 ≥ 6.

(F.11) Пусть C - двоичный (n = n^∗ - 3, N^∗/4, 1; 2)-код, полученный {(000), (111)}-

укорочением кода C^∗. Тогда C - ПР- и ПТ-код с

IA = {n - 1, 3; 1, n - 1}, где n = 2^m - 3 ≥ 5.

(F.12) Пусть B - произвольный двоичный совершенный (n, N, 3)-код длины n =

= 2^m - 1 ≥ 7. Пусть C представляет собой (n - 2,N/2,1;2)-код, полученный

{(00), (11)}-укорочением кода B. Тогда C - ПР- и ПТ-код с

IA = {n - 3, 2; 2, n - 3}.

Из работ [32, 76] получаем также семейство кодов, полученных укорочением

q-ичных расширенных совершенных кодов:

(F.13) Пусть C^∗ - произвольный q-ичный расширенный совершенный [n^∗, k^∗, 4; 2]_q-

код, такой что q = 2^m ≥ 4, n^∗ = q+2 и k^∗ = q-1. Пусть C - [n = q, k = q-2, 2; 2]_q-

код, полученный S-укорочением кода C^∗, с множеством S = {(α, α) : α ∈ F_q}.

Тогда C - ПР-код с

IA = {q(q - 1), (q - 1)(q - 2); 2, q}, где q = 2^m ≥ 4.

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

ных кодов Голея [19,76]. Полная регулярность и полная транзитивность кодов (S.5)

и (S.6) были указаны в [19].

(S.1) Двоичный код Голея. Это совершенный [23, 12, 7; 3]-ПР- и ПТ-код с

IA = {23, 22, 21; 1, 2, 3}.

(S.2) Двоичный выколотый код Голея. Это [22, 12, 6; 3]-ПР- и ПТ-код с

IA = {22, 21, 20; 1, 2, 6}.

(S.3) Двоичный расширенный код Голея. Это [24, 12, 8; 4]-ПР- и ПТ-код с

IA = {24, 23, 22, 21; 1, 2, 3, 24}.

(S.4) Двоичный дважды выколотый код Голея. Это [21, 12, 5; 3]-ПР- и ПТ-код с

IA = {21, 20, 16; 1, 2, 12}.

(S.5) Половина двоичного кода Голея. Это [23, 11, 8; 7]-ПР- и ПТ-код с

IA = {23, 22, 21, 20, 3, 2, 1; 1, 2, 3, 20, 21, 22, 23}.

(S.6) Выколотая половина двоичного кода Голея. Это [22, 11, 7; 6]-ПР- и ПТ-код с

IA = {22, 21, 20, 3, 2, 1; 1, 2, 3, 20, 21, 22}.

(S.7) {(00, 11)}-укороченный двоичный расширенный код Голея. Это [22, 11, 6; 7]-ПР-

и ПТ-код с

IA = {22, 21, 20, 16, 6, 2, 1; 1, 2, 6, 16, 20, 21, 22}.

(S.8) {(000, 111)}-укороченный двоичный расширенный код Голея. Это [21, 10, 5; 6]-

ПР- и ПТ-код с

IA = {21, 20, 16, 9, 2, 1; 1, 2, 3, 16, 20, 21}.

(S.9) {(00, 11)}-укороченный двоичный код Голея. Это [21, 11, 5; 6]-ПР- и ПТ-код с

IA = {21, 20, 16, 6, 2, 1; 1, 2, 6, 16, 20, 21}.

Обозначим через G троичный совершенный [11, 6, 5]₃-код Голея, а через G⁽⁰⁾ -

подкод кода G, состоящий из всех слов кода G с общей проверкой на четность 0.

Легко видеть, что G⁽⁰⁾ - это [11, 5, 6]₃-код, состоящий из всех кодовых слов веса 0,

6 и 9. Назовем этот код одной третьей частью троичного кода Голея.

(S.10) Троичный код Голея. Это совершенный [11, 6, 5; 2]₃-ПР- и ПТ-код с

IA = {22, 20; 1, 2}.

(S.11) Троичный выколотый код Голея. Это [10, 6, 4; 2]₃-ПР- и ПТ-код с

IA = (20, 18; 1, 6).

(S.12) Троичный расширенный код Голея. Это [12, 6, 6; 3]₃-ПР- и ПТ-код с

IA = {24, 22, 20; 1, 2, 12}.

(S.13) Третья часть троичного Кода Голея. Это троичный [11, 5, 6; 5]₃-ПР- и ПТ-

код G⁽⁰⁾ с

IA = {22, 20, 18, 2, 1; 1, 2, 9, 20, 22}.

(S.14) Выколотая третья часть троичного кода Голея. Это троичный [10, 5, 5; 4]₃-

ПР- и ПТ-код с

IA = {20, 18, 4, 1; 1, 2, 18, 20}.

Отметим, что многие из приводимых ниже кодов также тем или иным образом

основаны на совершенных кодах (см. пп. 5.2, 5.4, 5.9, 5.10 и 5.12).

5.2. Вложенные семейства ПР-кодов. Обозначим через H_m двоичный код Хэм-

минга длины n = 2^m -1. Пусть m = 2u, q = 2^u, r = 2^u +1 и r = 2^u -1. Проверочную

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

элементов поля [α⁰, α¹, . . ., αn-1], где α ∈ F₂m - примитивный элемент этого поля.

Представим теперь элементы поля F₂m как элементы квадратичного расширения

подполя F₂u. Пусть β = α^r - примитивный элемент F₂u , и пусть F₂m = F₂u [α]. Обо-

значим через E_m двоичное представление матрицы со столбцами [α⁰, α^r, . . . , α(n-1)r].

Определим матрицу P_m как вертикальное объединение матриц H_m и E_m:

[

]

H_m

P_m =

E_m

Хорошо известно [40], что код C(u) с проверочной матрицей P_m представляет

собой двоичный циклический ПР-код с радиусом покрытия ρ = 3, минимальным

расстоянием d = 3 и размерностью n - (m + u).

Как можно увидеть из [39], число смежных классов C(u) + v веса 3 равно r. Дей-

ствительно, их синдромы S(v) представляют собой ненулевые элементы поля F₂u.

Для каждого i ∈ {0, . . . , u} выберем u - i смежных классов C(u) + v⁽¹⁾, . . . , C(u) +

+v(u-i), синдромы которых S(v⁽¹⁾), . . . , S(v(u-i)) линейно независимы (т.е. их соот-

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

в пространстве Fu2). Используя выбранные синдромы, построим линейный двоичный

код C(i) как следующее линейное замыкание:

C(i) = 〈C(u), v⁽¹⁾, . . ., v(u-i)〉.

Обозначим через A_u-i линейное подпространство Fu2, порожденное синдромами

S(v⁽¹⁾), . . . , S(v(u-i)).

Размерность кода C(i) равна dim(C(i)) = u - i + dim(C(u)), где dim(C(u)) =

= n - m - u. Заметим, что максимальное число независимых синдромов, которое

можно выбрать, равно u, т.е. наибольший код, который можно построить, имеет раз-

мерность u + dim(C(u)) = n - m, что представляет собой код Хэмминга C⁽⁰⁾ = H_m.

Все построенные коды содержат код C(u), и в то же самое время все они содержатся

в коде Хэмминга C⁽⁰⁾.

Число различных кодов C(u-i) равно числу подпространств размерности i, кото-

рые можно выбрать в Fu2, т.е. равно гауссовскому биномиальному коэффициенту

]

^[u

(2^u - 1)(2^u - 2) . . . (2^u - 2i-1)

|{C(u-i)}| =

(2ⁱ - 1)(2ⁱ - 2) . . . (2ⁱ - 2i-1)

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

построить между кодами C(u) и C⁽⁰⁾ = H_m, равно

∏

(2^u-i - 1).

i=0

Следующий факт был доказан в [40] для кодов C(u), но его можно распростра-

нить на все коды C(i), i ∈ {1, . . . , u}.

Предложение 31. Для любого i ∈ {1,...,u} смежные классы веса 3 кода C(i)

находятся на расстоянии 3 друг от друга, и множество C(i) ∪ C(i)(3) является

кодом Хэмминга.

Напомним, что C(i)∗ получен из C(i) расширением и что из свойства ПТ вытекает

свойство ПР.

Теорема 23 [39]. Имеют место следующие утверждения:

(i) C⁽¹⁾ - ПТ-код с радиусом покрытия 3;

(ii) C(u) - ПТ-код с радиусом покрытия 3;

(iii) Если C(i) полностью транзитивен, то C(i)∗ также полностью транзитивен

для любого i ∈ {0, . . . , u};

(iv) Для любого i ∈ {1, . . . , u} код C(i) является подкодом C(i-1), а код C(i)∗ -

подкодом C(i-1)∗.

(F.14) Для любого i ∈ {0, . . . , u} код C(i) полностью регулярен с

IA = {2^m - 1, 2^m - 2^m-i, 1; 1, 2^m-i, 2^m - 1};

(F.15) Для любого i ∈ {0, . . . , u} расширенный код C(i)∗ полностью регулярен с

IA = {2^m, 2^m - 1, 2^m - 2^m-i, 1; 1, 2^m-i, 2^m - 1, 2^m}.

Заметим, что для значений i ∈ {0, 1, u} коды C(i) и C(i)∗ являются полностью

транзитивными. Кроме того, для случая m = 6 вычисления показали, что все коды

C(i) и C(i)∗ полностью транзитивны. В работе [77] было доказано, что дистанционно

регулярные графы смежных классов, которые строятся на основе рассматриваемых

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

делимости: 2^m должно быть степенью 2ⁱ, либо 2^m = 2ⁱ, либо 2ⁱ - 1 делит 2m. Мы

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

то расширенный код C(i)∗ также является ПТ-кодом. Более того, для таких случаев

мы предполагаем, что C(i) также является ПТ-кодом. Однако вопрос о полной тран-

зитивности кодов C(i) и C(i)∗ для случаев i ∈ {0, 1, u} открыт и требует большего

внимания.

5.3. Коды типа Препараты и коды БЧХ. Из работ [2, 24] получаем следующие

ПР-коды.

(F.16) Любой (двоичный) код типа Препараты, т.е. любой код с параметрами (n =

= 22m-1,M = 2n+1-4m,5), где m ≥ 2, полностью регулярен с радиусом покрытия

ρ = 3 [2] и

IA = {n, n - 1, 1; 1, 2, 3}.

(F.17) Расширенный код типа Препараты, т.е. любой код с параметрами (n + 1 =

= 22m, M = 2n+1-4m, 6) полностью регулярен с радиусом покрытия ρ = 4 [2] и

IA = {n + 1, n, n - 1, 1; 1, 2, 3, n + 1}.

(F.18) Двоичный примитивный код БЧХ с параметрами (n = 22m+1 - 1, N = 2n-4m,

5; 3), где m ≥ 2, полностью регулярен с

IA = {n, n - 1, (n + 3)/2; 1, 2, (n - 1)/2}.

(F.19) Расширенный двоичный примитивный код БЧХ с параметрами (n + 1 =

= 22m+1, N = 2n-4m, 6; 4) полностью регулярен с

IA = {n + 1, n, n - 1, (n + 3)/2; 1, 2, (n - 1)/2, n + 1}.

5.4. Поднятие алфавитов кодов Хэмминга. ПР-коды можно получить поднятием

алфавитов кодов Хэмминга. Обозначим через H^qm проверочную матрицу кода Хэм-

минга C = C(H^qm) длины n = (q^m - 1)/(q - 1) над F_q. Определим новый линейный

код, который мы обозначим через C_r(H^qm), той же длины n, но над полем F_qr , где

r ≥ 2, с той же проверочной матрицей H^qm.

Теорема 24 [35]. Имеет место следующее утверждение:

(F.20) Код C_r(H^qm) имеет параметры [n, n - m, 3; ρ]_qr и полностью регулярен с

ρ = min{r,m} и числами пересечений

(q^r - qⁱ)(q^m - qⁱ)

qⁱ - 1

b_i =

i = 0,...,ρ - 1; c_i = qi-1

i = 1,...,ρ.

(q - 1)

q-1

Если r = m, то коды C_r(H^qm) и C_m(H^qr) не эквивалентны, но имеют одинаковые

массивы пересечений.

Заметим, что коды Хэмминга - это единственные коды, поднятие алфавитов ко-

торых приводит к ПР-кодам.

Теорема 25 [35]. Пусть C(H^q) - нетривиальный код длины n над полем F_q с

минимальным расстоянием d ≥ 3 и радиусом покрытия ρ ≥ 1, и пусть C_r(H^q) -

поднятие кода C(H^q) над полем F_qr . Тогда новый код C_r(H^q) полностью регулярен,

если и только если исходный код C(H^q) является кодом Хэмминга.

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

кодов, никогда не являются ПР-кодами. Однако все эти коды равномерно упакованы

в широком смысле [35].

Следующее утверждение обобщает результаты работ [24,33] на недвоичный слу-

чай.

Предложение 32 [35]. Пусть C - q-ичный [n,n - m,3]-код Хэмминга длины

n = (q^m-1)/(q-1), и пусть C^∗ - расширение этого кода. Тогда код C^∗ равномерно

упакован, если и только если он имеет минимальное расстояние 4. Другими сло-

вами, C^∗ равномерно упакован, если и только если q = 2 и m ≥ 2 или q = 2^u ≥ 4

и m = 2.

Теорема 26 [35]. Пусть C - q-ичный [n,n - m,3]-код Хэмминга длины n =

= (q^m - 1)/(q - 1), и пусть C^∗ - расширение этого кода. Поднятый код C^∗r равно-

мерно упакован, если и только если код C^∗ равномерно упакован. Следовательно,

поднятый код C^∗r равномерно упакован, если и только если q = 2 и m ≥ 2 или

q = 2^u ≥ 4 и m = 2.

5.5. ПР-коды по кронекеровым произведениям. Построение ПР-кодов с помощью

кронекерова произведения матриц над одним и тем же алфавитом было рассмотрено

в [34]. Позднее эта конструкция была обобщена в [78] на случай разных алфавитов

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

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

щий интересный факт. Новая конструкция дает растущее число ПР-кодов с различ-

ными параметрами (и над различными алфавитами), но с одним и тем же массивом

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

классов изоморфны, но строятся из разных ПР-кодов с разными параметрами).

Напомним, что кронекерово произведение двух матриц A = [a_r,s] над F_qu и B

над F_q (где F_q - подполе F_qu ) - это новая матрица H = A ⊗ B, полученная заменой

каждого элемента a_r,s в A матрицей a_r,sB.

) имеют пара-

Теорема 27 [34,78]. Пусть коды Хэмминга C(Hquma)иC(Hm

метры [n_a, n_a-m_a, 3]_qu и [n_b, n_b-m_b, 3]_q соответственно, где q - степень простого

числа, n_a = (quma - 1)/(q^u - 1), n_b = (qmb - 1)/(q - 1), m_a, m_b ≥ 2 и u ≥ 1.

представляющей

(F.21) Код C = C(H) с проверочной матрицей H = Hquma^⊗Hmb,

, полностью транзитивен

собой кронекерово произведение матриц HqumaиHm

и поэтому полностью регулярен с параметрами [n, k, d; ρ]_qu, где

n = na n_b, k = n - ma m_b, d = 3, ρ = min{um_a, m_b},

(8)

и с числами пересечений

(quma - q^ℓ)(qmb - q^ℓ)

b_ℓ =

ℓ = 0,1,...,ρ - 1,

(q - 1)

q^ℓ - 1

c_ℓ = qℓ-1

ℓ = 1,2,...,ρ.

q-1

Поднятый код Cmb(H^q

) полностью регулярен с тем же самым массивом

uma

пересечений, что и код C.

), что

Заметим, что в теореме 27 нельзя выбрать код Cmb(Hquma)вместоCmb(Hu

кажется вполне естественным. Подчеркнем здесь, что коды Cmb(H^qum

) и Cmb(Hqu )_m

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

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

му код Cmb(H^q

) подходит к кодам из семейства (F.21) в том смысле, что он имеет

uma

тот же самый массив пересечений. Например, код C₂(H223) индуцирует дистанционно

регулярный граф с массивом пересечений {315, 240; 1, 20}, а код C₂(H²⁶) - дистанци-

онно регулярный граф с массивом {189, 124; 1, 6}. Отметим, что для получения всех

этих результатов в обоих случаях используется одна и та же теорема 24.

Заметим, что предыдущая теорема 27 не может быть обобщена на более общий

случай, когда алфавиты F_qa и F_qb компонентных кодов C_A и C_B, соответственно,

являются полями произвольных порядков одной и той же характеристики. Проил-

люстрируем этот факт минимальным нетривиальным примером. Возьмем два кода

Хэмминга - [5, 3, 3]-код C_A над F₂2 с проверочной матрицей H222 и [9, 7, 3]-код CB

над F₂3 с проверочной матрицей H232 . Тогда результирующий [45, 41, 3]-код C =

= C(H222 ⊗ H23) над F26 даже не является равномерно упакованным кодом в широ-

ком смысле, так как он имеет радиус покрытия ρ = 3, а внешнее расстояние s = 7,

что легко проверяется по проверочной матрице кода C.

Теорема 28 [78]. Пусть q - любая степень простого числа, и пусть a,b,u -

любые натуральные числа. Тогда существуют следующие ПР-коды с различными

параметрами [n, k, d; ρ]_q′ , где q^′ - степень q, расстояние d = 3, а радиус покрытия

ρ = min{ua,b}:

(F.22) C_ua(H^qb) над F_qua длины n =qb -¹, k = n - b;

q-1

(F.23) C_b(H^qua) над F_qb длины n =qua -¹, k = n - ua;

q-1

(F.24) C(H^qb ⊗ H^qua) над F_q длины n =qb -1qua -¹, k = n - bua;

q-1

, k = n - bu;

(F.26) C(H^qb ⊗ Hqua ) над Fq^u длины n =qb -1qua -1q-1qu-1 , k = n - ba;

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

(q^b - q^ℓ)(q^ua - q^ℓ)

q^ℓ - 1

b_ℓ =

ℓ = 0,...,ρ - 1; c_ℓ = qℓ-1

ℓ = 1,...,ρ.

(q - 1)

q-1

Все вышеприведенные коды, построенные по кронекеровым произведениям (т.е. се-

мейства (F.24)-(F.26)), являются полностью транзитивными.

Обозначим через τ(n) число различных делителей натурального числа n.

Следствие 14 [78]. Для заданной степени простого числа q выберем два про-

извольных натуральных числа a, b > 1. Тогда можно построить τ(a)+τ(b) следую-

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

ρ = min{a,b}:

∗

(i) ПТ-коды C(Hqrr

⊗ H^qb) над F_qr∗ для любого собственного делителя r числа a,

такого что rr^∗ = a;

∗

(ii) ПТ-коды C(H^qa ⊗ Hqrr ) над Fqr∗ для любого собственного делителя r числа b,

такого что rr^∗ = b;

(iii) ПР-коды C_a(H^qb) над F_qa и ПР-коды C_b(H^qa) над F_qb .

Эта конструкция дает также РУ-коды в широком смысле, не являющиеся полно-

стью регулярными. Пусть R_t = [It-1 | 1], где It-1 - двоичная диагональная матрица

порядка t - 1, а 1 - столбец из всех единиц.

Теорема 29 [78]. Пусть заданы q^u-ичный [n,k,3]_qu-код Хэмминга C(Hqum ) дли-

ны n_a = (q^um -1)/(q^u -1) и q-ичный [n_b, 1, n_b]_q-код с повторением C(R_n

) длины n_b,

где 4 ≤ n_b ≤ (q^u - 1)n_a + 1, q - степень простого числа, u ≥ 1 и m ≥ 2.

(i) Код C = C(Hqum ⊗ Rnb) - это q^u-ичный РУ-код в широком смысле с радиусом

покрытия ρ = n_b - 1 и параметрами

n = n_an_b, k = n - m(n_b - 1), d = 3.

(9)

(ii) Код C не полностью регулярен.

5.6.(и )миальные ПР-коды. Обозначим через H(m,ℓ) двоичную матрицу разме-

ра m×

, столбцами которой являются все различные векторы длины m и веса ℓ.

ℓ

Определим двоичный линейный код C(m,ℓ) с проверочной матрицей H(m,ℓ), который

будем называть биномиальным.

Теорема 30 [79]. Пусть m и ℓ - два натуральных числа, такие что 2 ≤ ℓ ≤

≤ m - 2. Код C(m,ℓ) полностью транзитивен (и следовательно, полностью регу-

лярен) в точности в следующих четырех случаях:

(F.27) Для любого m ≥ 4 код C(m,2) представляет собой [n, k, d; ρ]-код с парамет-

рами

)

⁽m

k = n - m + 1, d = 3, ρ = ⌊m/2⌋

и числами пересечений для i = 0, . . ., ρ

)

⁽m - 2i

⁽2i⁾

a_i = 2i(m - 2i), b_i =

c_i =

;

(S.15) Код C(5,3) является [10, 5, 4; 3]-кодом с

IA = {10, 9, 4; 1, 6, 10};

(S.16) Код C(6,4) является [15, 10, 3; 3]-кодом с

IA = {15, 8, 1; 1, 8, 15};

(S.17) Код C(7,4) является [35, 29, 3; 2]-кодом с

IA = {35, 16; 1, 20}.

Из кодов с ℓ = 2 можно построить новые полностью регулярные коды. Сначала

разделим все эти коды на два семейства [79]. Обозначим C(m) = C(m,2).

Теорема 31 [36,79]. Пусть m - натуральное число, m ≥ 3. Код C(m) анти-

подален, если m нечетно, и неантиподален, если m четно.

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

C(m)(ρ) представляет собой сдвиг кода C(m) (теорема 6) на вектор (1, 1, . . ., 1). Рас-

смотрим новый (линейный) код C[m] = C(m) ∪ C(m)(ρ). Его порождающая матри-

ца G[m] имеет следующую симметричную структуру:

[

]

Ik-1

Htm-1

G[m] =

0...0

1...1

где Htm-1 - это транспонированная матрица H(m-1,2). Используя тот факт, что

C(m)(ρ) = C(m) + (1, 1, . . ., 1) (теорема 6), заключаем, что справедлива следующая

Теорема 32 [36]. Пусть m четно, m ≥ 6.

(F.28) Код C[m] полностью транзитивен (и поэтому полностью регулярен) с па-

раметрами

n = m(m - 1)/2, k = n - m + 2, d = 3, ρ = ⌊m/4⌋

и следующими числами пересечений: для m ≡ 0 (mod 4) и ρ = m/4

)

⁽m - 2i

⁽2i⁾

⁽2ρ⁾

b_i =

c_i =

i = 0,1,...,ρ - 1, c_ρ = 2

а для m ≡ 2 (mod 4) и ρ = (m - 2)/4

)

⁽m - 2i

⁽2i⁾

b_i =

c_i =

i = 0,1,...,ρ.

5.7. ПР-коды, построенные с помощью прямой суммы. Пусть C₁ и C₂ - два кода,

не обязательно линейные, одной и той же длины n. Прямая сумма кодов C₁ и C₂ -

это код, полученный следующим образом:

C₁ ⊕ C₂ = {(c₁, c₂) | c₁ ∈ C₁, c₂ ∈ C₂}.

Теорема 33 [6,24]. Пусть r - произвольное натуральное число, и пусть C_i,

i = 1,2,...,r, - q-ичные (n,N,d;1)_q-ПР-коды, имеющие одинаковый массив пересе-

чений (b₀; c₁).

(F.29) Тогда для любого r ≥ 1 прямая сумма

C =C₁ ⊕...⊕C_r

представляет собой (nr, N^r, d; r)_q -ПР-код с числами пересечений

a(r)_i = n(q - 1) - (r - i)b₀ - ic₁, b(r)_i = (r - i)b₀, c(r)_i = ic₁,

где i = 0, 1, . . . , r. Более того, если все C_i - ПТ-коды, (перестановочно) эквива-

лентные друг другу, то код C также полностью транзитивен.

Заметим, что конструкция, описанная в теореме 33, была рассмотрена в [6] для

частного случая, когда все C_i - двоичные совершенные коды.

5.8. ПР-коды из комбинаторных конфигураций. Имеются следующие конструк-

ции.

(F.30) Коды на основе одного латинского квадрата. Для любого алфавита F раз-

мера q ≥ 2 существует q-ичный (3, q², 2; 1)_q-МДР-код над F , являющийся ПР-ко-

дом с

IA = {3(q - 1); 3}.

В этом случае множество C(ρ) представляет собой все остальные векторы из F³,

т.е. C(ρ) = F³ \ C.

(F.31) Коды на основе двух латинских квадратов. Для любого алфавита F размера

q ≥ 3, где q = 6, существует q-ичный (4,q²,3;2)_q-МДР-код над F, являющийся

ПР-кодом с

IA = {4(q - 1), 3(q - 3); 1, 12}.

(S.18) Код на основе трех латинских квадратов. Три взаимно ортогональных ла-

тинских квадрата порядка 4 образуют эквидистантный (т.е. любые два кодовых

слова находятся на расстоянии d) [5, 2, 4; 3]₄-код C. Этот код полностью регулярен

IA = {15, 12, 3; 1, 4, 15}.

Выколотый [4, 2, 3]₄-код C(i), полученный из этого кода, также полностью регу-

лярен и принадлежит семейству (F.31).

(S.19) Код на основе четырех латинских квадратов. Четыре взаимно ортогональ-

ных латинских квадрата порядка 5 образуют эквидистантный [6, 2, 5; 3]₅-код C.

Это ПР-код с

IA = {24, 20, 13; 1, 2, 6}.

Выколотый [5, 2, 4]₅-код C(i), полученный из кода C, уже не полностью регуля-

рен, так как множество (C(p))₄ не является 2-схемой. Но дважды выколотый

[4, 2, 3; 2]₅-код полностью регулярен и принадлежит семейству (F.31).

(S.20) Код Адамара. Единственная (с точностью до эквивалентности) матрица Ада-

мара порядка 12 индуцирует двоичный (11, 24, 5; 3)-код H. В [4] было показано,

что H полностью регулярен с

IA = {11, 10, 3; 1, 2, 9},

а в [37] установлено, что H полностью транзитивен, а также доказана единствен-

ность такого кода в классе ПР-кодов с (n, d) = (11, 5) (см. предложение 8).

(S.21) Расширенный код Адамара. Расширенный код H, рассмотренный выше, пред-

ставляет собой (12, 24, 6; 4)-код H^∗. Согласно [33] код H^∗ равномерно упакован и

поэтому является ПР-кодом с

IA = {12, 11, 10, 3; 1, 2, 9, 12}.

В [37] было установлено, что H^∗ полностью транзитивен, а также доказана един-

ственность этого кода в классе ПР-кодов с (n, d) = (12, 6) (см. предложение 8).

(F.32) Схема Джонсона в схеме Хэмминга. Для любого натурального w ≥ 1 триви-

альный равновесный (n, N, d; ρ)-код (или схема Джонсона J(n, w)) с параметрами

)

⁽2w

n = 2w, N =

d = 2, ρ = w

полностью регулярен с

IA = {2w, 2w - 1, 2w - 2, . . . , 1; w + 1, w + 2, . . . , 2w}.

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

физмов является полная симметрическая группа. В § 4 рассматриваются ПР-ко-

ды в схемах Джонсона. Таким образом, схема Джонсона J(2w, w) является пол-

ностью регулярной и полностью транзитивной в схеме Хэмминга H(2, 2w).

5.9. ПР-коды, полученные каскадными конструкциями. В этом пункте обсудим

некоторые результаты из работы [80], в которой рассматривались ПР-коды, постро-

енные каскадированием кодов Хэмминга.

Пусть H - циклическая проверочная матрица q-ичного кода Хэмминга длины n =

= (q^m -1)/(q-1), т.е. мы предполагаем, что НОД(n, q-1) = 1. Поэтому симплексный

код, порожденный матрицей H, также циклический. Для любого c ∈ {1, 2, . . . , n}

рассмотрим код C с проверочной матрицей

[

]

H H ... H

(10)

H₁

H₂

... H_c

где H_i - матрица, полученная из H циклическим сдвигом всех ее столбцов на i

позиций вправо.

(F.33) Код C с проверочной матрицей (10) полностью регулярен с параметрами

[nc, nc - 2m, 3; 2]_q и массивом пересечений

IA = {(q - 1)nc, ((q - 1)n - c + 2)(c - 1); 1, c(c - 1)}.

Почти все коды семейства (F.33) не полностью транзитивны. Однако в двоичном

случае и для любого числа m, т.е. для любой длины n = 2^m - 1, код C полностью

транзитивен для значений c ∈ {2, 3, n - 1, n}. В q-ичном случае код C полностью

транзитивен для случая c = 2.

Расширение кодов из семейства (F.33) не приводит к ПР-кодам, за исключением

двоичного случая, когда c = 2m-1 +1. В этом случае результирующий расширенный

код с параметрами [n(2m-1 + 1) + 1, n(2m-1 + 1) - 2m, 4; 3] совпадает с кодами из

семейства (F.35), описанного ниже.

Определим теперь код A(c) длины n(c + 3) с проверочной матрицей

[

]

H H ... H

H_a(c) =

(11)

H H H₁ ... H_c

где 0 обозначает нулевую матрицу того же размера, что и H. В [80] было доказано,

что все коды A(c) полностью регулярны.

(F.34) Для c ≤ n - 1 код A(c) с проверочной матрицей (11) представляет собой

ПР-код с параметрами [(c + 3)n, (c + 3)n - 2m, 3; 2]_q и массивом пересечений

IA = {(c + 3)(q - 1)n, (c + 2)((q - 1)n - 1 - c); 1, (c + 2)(c + 3)}.

В двоичном случае, когда c = n - 1, код A(n-1) совпадает с [22m - 1, 22m - 1 - 2m,

3; 1]-кодом Хэмминга.

Из всех кодов семейства (F.34) полностью транзитивными являются двоичные

коды A(c) с m > 2 для значений c ∈ {2^m - 5, 2^m - 4, 2^m - 3}.

Расширение кодов A(c) из семейства (F.34) приводит к новым ПР-кодам только

в двоичном случае для двух значений c ∈ {2m-1 - 2, 2^m - 2}.

(F.35) Пусть A(c) - код с проверочной матрицей H_a(c), и пусть A(c)∗ получен его

расширением. Для c = 2m-1 -2 код A(c)∗ с параметрами [(c+3)n+1, (c+3)n-2m,

4; 3] полностью регулярен с

IA = {(c + 3)n + 1, (c + 3)n, 22m-2; 1, (c + 2)(c + 3), (c + 3)n + 1}.

Для c = 2^m - 2 код A(c)∗ с параметрами [(c + 3)n + 1, (c + 3)n - 2m, 4; 2] совпадает

с расширенным кодом Хэмминга длины 22m. Для c ∈ {2m-1 - 2, 2^m - 2} код A(c)∗

не полностью регулярен.

Пусть m и c - натуральные числа, такие что 1 ≤ c ≤ n - 1 = 2^m - 2. Пусть

C = A(n-2), и пусть H_c - его проверочная матрица. Код C - это код Хэмминга

длины 22m -1. Пусть B(n-1-c) - код, заданный матрицей (10) после удаления из этой

матрицы столбцов, имеющихся в матрице H_a(c). Пусть H_b(n - 1 - c) - проверочная

матрица кода B(n-1-c). Три введенных кода A(c), B(n-1-c) и C имеют длины n_a =

= (c + 3)(2^m - 1), n_b = (n - 1 - c)(2^m - 1) и n_c = n_a + n_b = 22m - 1 соответственно.

Следовательно, матрица H_c представляется в виде

H_c = [H_a(c) | H_b(n - 1 - c)] .

Код B(n-1-c) эквивалентен коду, заданному условием (10), при выборе значе-

ния c, равного n - 1 - c, в этой формуле. Следовательно, A(n-1-c) и B(c) полностью

регулярны. Кроме того, коды A(n-1-c) и B(c) являются или не являются полностью

транзитивными одновременно.

Пусть Aut(B) - группа автоморфизмов кода B(c), а Aut(A) - группа автоморфиз-

мов кода A(n-1-c) для 1 ≤ c ≤ n-1. Тогда группы Aut(A) и Aut(B) изоморфны [81].

Обозначим через C_t циклическую группу порядка t, и пусть GL(m, 2) - двоичная

общая линейная группа. Напомним, что S₃ - симметрическая группа. В [81] авторы

установили, что

• Aut(B) = GL(m, 2) × GL(m, 2) × C₂ для c = 2;

• Aut(B) = GL(m, 2) × S₃ для c = 3;

• Коды A(c) и B(n-1-c) полностью транзитивны, если и только если n - 1 - c ∈

∈ {1, 2, 3}.

Заметим, что в случае c = n - 2 = 2^m - 3 код B(c) является кодом Хэмминга длины

2^m - 1.

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

тодами.

[

]

(S.22) Пусть H =

- проверочная матрица двоичного кода Хэмминга дли-

ны 3, и пусть H₁ (соответственно, H₂) - матрицы, полученные одним цикличе-

ским сдвигом столбцов H = H₀ (соответственно, двумя циклическими сдвигами).

Двоичный [15, 9, 3; 3]-код C с проверочной матрицей

]

^[H

H H

H H₁

H H H₂

полностью регулярен с

IA = {15, 12, 1; 1, 4, 15}.

(S.23) Двоичный [16, 9, 4; 4] код, полученный расширением [15, 9, 3; 3]-кода, описан-

ного выше, также полностью регулярен с

IA = {16, 15, 12, 1; 1, 4, 15, 16}.

Обозначим через D(u, q) разностную матрицу (см. [25]), т.е. квадратную матрицу

порядка qu над аддитивной группой порядка q, такую что покомпонентная разность

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

мем разностную матрицу D = D(2, 3), имеющую вид

⎡

⎤

⎢0

1⎥

⎢

⎥

⎢0

2⎥

⎢

⎥.

⎢0

2⎥

⎦

^⎣0

(S.24) Пусть H - матрица размера 12×18, полученная из D заменой каждого элемен-

та i на матрицу H_i (определенную в (S.22)). Тогда [18, 12, 3; 2]-код с проверочной

матрицей H полностью регулярен с IA = {18, 15; 1, 6}.

(S.25) Используем ту же конструкцию, что и в (S.24), для матрицы D^∗, полученной

из разностной матрицы D(2, 3) удалением тривиального столбца. Полученный та-

ким образом [15, 9, 3; 3]-код представляет собой ПР-код с IA = {15, 12, 1; 1, 4, 15}.

Этот код совпадает с кодом, построенным в (S.22).

5.10. Линейные q-ичые ПР-коды с ρ = 1. Линейные q-ичные ПР-коды с ρ = 1

полностью классифицированы в [82] с помощью следующих двух простых конструк-

ций.

Конструкция I(u). Пусть C - [n, k, d]_q-код с проверочной матрицей H. Опреде-

лим новый код C+u с параметрами [n + u, k + u, 1]_q как код с проверочной матри-

цей H+u, полученной из H добавлением к ней u > 0 нулевых столбцов.

Теорема 34 [82]. Коды C и C+u имеют одинаковые радиусы покрытия. Более

того, код C+u полностью регулярен, если и только если C полностью регулярен.

В этом случае оба кода имеют одни и те же числа пересечений b_i = b^′i и c_i = c^′i,

так что

a^′i = a_i + (q - 1)u, b^′i = b_i, c^′i = c_i, i = 0, 1, . . ., ρ

(здесь a_i, b_i, c_i - числа пересечений кода C).

Конструкция II (ℓ). Пусть C - [n, k, d]_q-код с проверочной матрицей H. Пусть

C^×ℓ - код с параметрами [nℓ, k+(ℓ-1)n, 2]_q, чья проверочная матрица H^×ℓ получена

ℓ-кратным повторением матрицы H (или матриц, эквивалентных матрице H), т.е.

[

]

H^×ℓ =

H⁽¹⁾ | H⁽²⁾ | . . . | H(ℓ)

где для всех i = 1, . . . , ℓ матрица H(i) - это проверочная матрица кода, эквивалент-

ного коду C.

Теорема 35 [82]. Новый [n,k,d]_q-код C^×ℓ является ПР-кодом с радиусом по-

крытия ρ = 1, если и только если C - ПР-код с радиусом покрытия ρ^′ = 1.

Итак, для линейных ПР-кодов с ρ = 1 имеет место следующая

Теорема 36 [82]. Пусть C = C(H) - нетривиальный [n,k,d]_q-код с радиусом

покрытия ρ = 1 и проверочной матрицей H.

(F.36) Тогда код C полностью транзитивен (следовательно, полностью регуля-

рен) с параметрами [n, n - m, d; 1]_q, где n = n_m ℓ + u и n_m = (q^m - 1)/(q - 1),

если и только если матрица H имеет (с точностью до эквивалентности) сле-

дующий вид:

(

)+u

H =

(H^qm)^×ℓ

где H^qm - проверочная матрица кода Хэмминга длины n_m = (q^m - 1)/(q - 1)

над F_q.

Более того,

d = 3, если и только если u = 0, ℓ = 1, n = n_m, а C - код Хэмминга; в этом случае

эти коды включены в семейство (F.1);

(F.37) d = 2, если и только если u = 0, ℓ ≥ 2, n = n_mℓ;

(F.38) d = 1, если и только если u > 0, ℓ ≥ 1.

Во всех случаях код C имеет

IA = {(q - 1)ℓ n_n-k; ℓ}

Отметим, что аналогичный результат был получен в [13] в терминах арифмети-

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

5.11. Нелинейные q-ичные ПР-коды с ρ = 1. Смежный класс линейного ПР-ко-

да с ρ = 1, очевидным образом, является нелинейным ПР-кодом с тем же самым

ρ = 1. Кроме этих тривиальных кодов, мало что известно для этого случая. Имеют-

ся интересные результаты Фон-Дер-Флааса [83-85], к которым мы сейчас перейдем.

Эквивалентный термин для построения ПР-кодов с заданным ρ - так называемая

совершенная (ρ + 1)-раскраска гиперкуба. Особенно просто совершенная раскраска

определяется для случая ρ = 1, т.е. для 2-раскраски. Пусть H(2, n) - двоичный ги-

перкуб размерности n (или двоичная схема Хэмминга). Вершинами его являются

все двоичные векторы длины n, и две вершины соединены ребром (или являются

соседями), если соответствующие векторы находятся друг от друга на расстоянии 1.

Раскраска вершин гиперкуба (обычно) белым и черным цветами называется совер-

шенной 2-раскраской с матрицей пересечений

[

]

a b

c d

если каждая черная вершина имеет в качестве соседей a черных и b белых вершин,

а каждая белая вершина - c черных и d белых вершин. Так как в двоичном случае

любая вершина имеет n соседей, то получаем, очевидно, что a + b = c + d = n.

В терминах чисел пересечения

a₀ = a, b₀ = b, c₁ = c, a₁ = d,

и следовательно, совершенная 2-раскраска - это нелинейный ПР-код с массивом пе-

ресечений IA = {b; c}. Нижнюю оценку на величину a = n - b (представляющую со-

бой наилучшую известную оценку на корреляционную иммунность (см. работу [83]

и библиографию в ней) дает

Теорема 37 [83]. Пусть C - двоичный ПР-код длины n с радиусом покрытия

ρ = 1 и массивом пересечений IA = {b;c}. Если b = c, то

c-a≤

(12)

Другое необходимое условие обеспечивает [84] следующая

Теорема 38 [84]. Пусть C - двоичный ПР-код длины n с ρ = 1 и массивом

пересечений (b; c). Тогда b = 0 = c, и

b+c

- степень числа 2,

(13)

НОД(b, c)

где НОД(b, c) - наибольший общий делитель.

Обе конструкции для линейных кодов с ρ = 1, рассмотренные в предыдущем

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

ние обобщает соответствующие результаты [82] на нелинейные коды и результа-

ты [84] на недвоичный случай.

Предложение 33. Имеют место следующие утверждения:

(i) Для каждого n = (q^m - 1)/(q - 1), m ≥ 2, и любого k, 1 ≤ k ≤ (q - 1)n, суще-

ствует q-ичный ПР-код C с ρ = 1 и IA = {(q - 1)n - k+ 1; k}, образованный k

произвольными сдвигами q-ичного совершенного кода длины n c минимальным

расстоянием d = 3;

(ii) Существование q-ичного ПР-кода C длины n с IA = {b; c} влечет для любого

k ≥ 1 существование ПР-кода C+k с IA = {b+k(q-1);c+k(q-1)}, образован-

ного заменой каждого кодового слова c ∈ C множеством из q^k кодовых слов

вида (c | x), где x пробегает F^nq;

(iii) Существование ПР-кода C длины n с IA = {b; c} влечет для любого k ≥ 1

существование ПР-кода C^×k с IA = {kb; kc}. Каждое кодовое слово v =

= (v₁, . . . , v_n) кода C заменяется на все векторы вида

(v1,1, v1,2, . . . , v1,k, . . . , v1,1, v1,2, . . . , v1,k) ∈ F^knq,

для которых

∑

v_i,j = v_i.

j=1

Наиболее интересны, конечно, коды, достигающие оценки (12). Такие коды дли-

ны n = 3u должны иметь массив пересечений IA = {3u - a; a + u}, где a ≥ 0.

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

сечений (см. работы [83,85] и библиографию в них): {3k; k} и {5k; 3k}. Эти семейства

получены из начальных кодов с массивами пересечений {3; 1} и {5; 3} применением

предложения 33. Первый начальный код - это тривиальный двоичный совершенный

код длины 3, а второй - код длины 6, построенный Таранниковым в [86]. Второй код

можно построить из первого, используя следующие две леммы Фон-Дер-Флааса [84].

Лемма 4 [84]. Пусть задан ПР-код C с ρ = 1 и матрицей пересечений

[

]

a b

c d

Предположим, что C можно представить в виде объединения непересекающихся

k-граней, где 0 ≤ k ≤ a. Тогда существует ПР-код с ρ = 2 и матрицей пересечений

]

^[a - k a + k 2b

a+k a-k

Лемма 5 [84]. Существование ПР-кода с ρ = 2 и матрицей пересечений

]

^[a - k a + k 2b

a+k a-k

где c ≥ a + k, влечет существование ПР-кода с ρ = 1 и матрицей пересечений

[

]

a-k

2b + c

2d + 2c - a - k

В связи с условием делимости (13) возникает естественный вопрос [84]: найти

для всех пар b, c значение a^∗(b, c), удовлетворяющее условию (13). Под величиной

a^∗(b, c) понимается минимальное число a, для которого существует ПР-код с мас-

сивом пересечений IA = {b; c}, если и только если a ≥ a^∗(b, c). На эту величину

a^∗(b, c) имеются нижние и верхние оценки (см. работу [84] и библиографию в ней).

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

Теорема 39 [84]. Имеют место следующие утверждения:

(i) Если c < b < 2c, то

√

a^∗(b, c) ≥

+ c(b - c) +

- (b - c);

(ii) Если 2c < b < 2c +

^√3c - 2, то a^∗(b, c) ≥ 1.

Для заданных натуральных чисел x, y, таких что x+y = 2^k -1, одно из этих чисел

нечетно и содержит в своем двоичном разложении ℓ единиц подряд, где 1 ≤ ℓ < k.

Определим функцию z(x, y) = k - 1.

Теорема 40 [84]. Имеют место следующие утверждения:

(i) a^∗(2b + c, c) ≤ max(0, a^∗(b, c) - 1);

(ii) Пусть b и c удовлетворяют условию (13). Тогда

a^∗(c, b) = a^∗(b, c) + b - c;

(iii) Пусть b и c удовлетворяют условию (13) и b ≥ c. Пусть m = (b, c), b =

= m(2b^′ + 1) и c = m(2c^′ + 1). Если c^′ = 0, то a^∗(b, c) = 0. В противном случае

a^∗(b, c) ≤ max(0, c - m(z(b^′, c^′) + 1)).

Оптимальный двоичный ПР-код длины n = 12 с массивом пересечений IA =

= {9; 7}, удовлетворяющий границе (12), был построен в [85]. Там же было доказано,

что предполагаемый ПР-код длины n = 12 с массивом пересечений IA = {11; 5} не

существует.

5.12. Линейные q-ичные ПР-коды с ρ = 2. Код, дуальный любому линейному ко-

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

ПР-кодом с ρ = 2 согласно результату Дельсарта [3] о том, что ρ ≤ s (см. теоре-

му 3). Имеется большое число различных бесконечных семейств таких кодов, и их

классификация далека от завершения (подробный обзор по этим кодам см. в [87]).

Классификация линейных ПР-кодов с радиусом покрытия ρ = 1 дает возмож-

ность описать структуру линейных ПР-кодов с ρ = 2, дуальные коды которых ан-

типодальны.

Теорема 41 [82]. Пусть C = C(H) - нетривиальный [n,k,d]_q-код. Тогда C

полностью регулярен с радиусом покрытия ρ = 2 и дуальным антиподальным ко-

дом C^⊥, если и только если его проверочная матрица H имеет следующий вид

с точностью до эквивалентности:

[

]

H =

где матрица M порождает эквидистантный код E с минимальным расстояни-

ем d^′, обладающий следующим дополнительным свойством: для любого ненулевого

кодового слова v ∈ E каждый символ α ∈ F_q, встречающийся в его координатной

позиции, встречается в этом слове ровно n - d^′ раз. Более того, с точностью до

эквивалентности код C получен расширением ПР-кода C^′ с радиусом покрытия

ρ^′ = 1.

Перечислим теперь известные нам ПР-коды с радиусом покрытия ρ = 2, ду-

альные коды которых антиподальны [82]. Пусть C₁ и C₂ - линейные q-ичные коды

одинаковой мощности с порождающими матрицами G₁ и G₂, где q - произвольная

степень простого числа. Будем говорить, что C₁ и C₂ - дополнительные коды, если

матрица G = [G₁ | G₂] (с точностью до перестановки строк матрицы G₂) порождает

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

n = (q^m - 1)/(q - 1), k = m, d = qm-1

(дуальный коду Хэмминга H_m).

Следствие 15 [82]. Следующие коды, дуальные коды которых антиподальны,

полностью регулярны с радиусом покрытия ρ = 2:

(F.39) Двоичный расширенный совершенный [n, k, 4; 2]₂-код H^∗m длины n = 2^m, где

k = n - m - 1 и m ≥ 2, с

IA = {n, n - 1; 1, n};

(F.40) Расширенный q-ичный совершенный [n, k, 4; 2]_q-код H^∗m длины n = q + 2 с

k = q - 1, где q = 2^r ≥ 4, и m = 2 [88,89] (семейство TF1 в обзоре [87]) с

IA = {(q + 2)(q - 1), q² - 1; 1, q + 2};

(F.41) [n, k, 3; 2]_q-код, дуальный коду, порожденному разностной матрицей D_m =

= D(n/q, q) (см. определение после кода (S.23)), с

IA = {n(q - 1), n - 1; 1, n(q - 1)}.

Этот код имеет длину n = q^m, размерность k = n - (m + 1) и проверочную

матрицу D_m, где m ≥ 1, а q ≥ 3 - любая степень простого числа (все ко-

ды такого типа, порожденные матрицей D_m, были построены в работе [90]).

Дополнительным к приведенному коду является код Хэмминга H_m;

(F.42) [n, n-2, 3; 2]_q-код, дуальный МДР-коду с k = 2 длины n, где 3 ≤ n ≤ q, q ≥ 3 -

любая степень простого числа, с массивом пересечений [89]

IA = {n(q - 1), (q - n + 1)(n - 1); 1, n(n - 1)};

(F.43) [n = q(q - 1)/2, k = n - 3, 4; 2]_q-код над алфавитом размера q = 2^r ≥ 4 [89] с

IA = {(q - 1)n, (q - 2)(q + 1)(q + 2)/4; 1, q(q - 1)(q - 2)/4}.

Код, дополнительный к этому коду, принадлежит семейству TF1^d, т.е. это

проективный дуальный код из семейства TF1 в [87];

(F.44) [n = 1 + (q + 1)(h - 1), k = n - 3, 4]_q-код, где 1 < h < q и h делит q для

q = 2^r ≥ 4 (семейство TF2 в [87]), с

IA = {(q - 1)n, (q + 1)(h - 1)(q - h + 1); 1, (h - 1)n};

(F.45) [n = q(q-h+1)/h, k = n-3, 4]_q-код, где 1 < h < q и h делит q для q = 2^r ≥ 4, с

IA = {(q - 1)n, (q + 1)(q - h)(q(h - 1) + h)/h²; 1, q(q - h)(q - h + 1)/h²}.

Дополнительный код принадлежит семейству TF2^d в [87].

Некоторые из этих кодов самодуальны [82].

Теорема 42 [82]. Пусть код C^′ ⊂ F^nqr получен поднятием алфавита совер-

шенного [n, n - m, 3]_q-кода Хэмминга. Тогда

(F.46) Для любого r код C^′ полностью регулярен. Более того, C^′ самодуален, если

и только если H_m - троичный [4, 2, 3]₃-код Хэмминга.

Теорема 43 [82]. Пусть {0,1,ξ₂,...,ξq-1} - элементы поля F_q, где q ≥ 4 -

любая степень простого числа. Пусть

[

]

D₁ =

ξ_i ξ_j

представляет собой проверочную матрицу для кода C и порождающую матрицу

для дуального кода C^⊥, где ξ_i, ξj ∈ F∗q - два разных элемента поля, таких что

ξ_i + ξ_j + 1 = 0. Тогда

(F.47) Код C, так же как и код C^⊥, представляет собой линейный антиподальный

полностью регулярный [4, 2, 3; 2]_q-код с

IA = {4 (q - 1), 3 (q - 3); 1, 12};

(F.48) В случае q = 2^r ≥ 4 эти два эквивалентных кода совпадают: C = C^⊥, т.е. C

самодуален.

Приведем еще одно семейство кодов, дуальные к которым - хорошо известные

коды, имеющиеся в [87]. Пусть H_m - проверочная матрица q-ичного кода Хэммин-

га H_m длины n = (q^m - 1)/(q - 1). Для заданной степени простого q и натуральных

чисел m и u < m определим код C_u,m, проверочная матрица которого получена из

матрицы H_m выкидыванием всех (q^u -1)/(q-1) столбцов проверочной матрицы H_u.

Код C_u,m имеет параметры

[n = (q^m - q^u)/(q - 1), k = (q^m - q^u)/(q - 1) - m, d; 2]_q,

где

^{4, если u = m - 1, q = 2,

в противном случае.

Теорема 44. Имеет место следующее утверждение:

(F.49) Для любой степени простого q и любых натуральных m > 3 и u < m

код C_u,m полностью транзитивен и полностью регулярен с радиусом покры-

тия ρ = 2 и

IA = {q^m - q^u, q^u - 1; 1, q^m - q^u}.

5.13. Двоичные линейные ПР-коды с ρ = 3 и ρ = 4 из булевых бент- и почти

бент-функций. Пусть F - любая функция из Fm2 в Fm2. Для любых элементов

(a, b) ∈ (Fm2)² определим преобразование Фурье функции F :

∑

μ_F (a, b)

(-1)〈b·F(x)〉+〈a·x〉 ,

(14)

x∈F^m

где 〈·〉 обозначает обычное внутреннее произведение на Fm2.

Для четных m функция F на Fm2 называется бент-функцией, если для всех

a, b ∈ Fm2 (где b = 0) ее преобразование Фурье равно μ_F (a, b) = ±2m/2. Для нечет-

ных m функция F на Fm2 называется почти бент-функцией (AB-функцией), если

для всех a, b ∈ Fm2 (где b = 0) ее преобразование Фурье равно μ_F (a, b) = ±2(m-1)/2.

Пусть F - любая функция из F_q в F_q, где q = 2^m, такая что F (0) = 0. Определим

множество

^{{2m-1, 2m-1 ± 2m/2},

если m четно,

Ω_m =

{2m-1, 2m-1 ± 2(m-1)/2}, если m нечетно.

Для двоичного линейного кода C определим числовое множество W_C , состоящее из

всех значений весов ненулевых кодовых слов:

W_C = {wt(c) : c ∈ C, c = 0}.

Для произвольной функции F определим матрицу

[

]

n-1

α²

H_F =

(15)

F (1) F (α) F (α²) . . . F (αn-1)

Следующие утверждения можно найти в работе [91].

Теорема 45 [91]. Для заданной функции F пусть C = C_F представляет собой

[n = 2^m - 1, k, d]-код, заданный проверочной матрицей H_F вида (15).

(i) Если m нечетно, то F является AB-функцией, если и только если W_C⊥ = Ω_m;

(ii) Если m четно, то F является бент-функцией, если и только если W_C⊥ = Ω_m;

(iii) Код C_F равномерно упакован в широком смысле, если и только если |W_C⊥ | = 3;

(F.50) Для четного m код C_F полностью регулярен, если F - бент-функция;

(F.51) Для нечетного m код C_F полностью регулярен, если F - AB-функция.

Используя соответствующие результаты работ [38,39], получаем следующее

Предложение 34. Пусть код C = C_F длины n = 2^m-1, где m нечетно, задан

проверочной матрицей (15), и пусть C^⊥ - дуальный к нему код с множеством

значений весов W_C⊥ . Тогда

(i) Код C^∗ равномерно упакован, если и только если C равномерно упакован и

W_C⊥ = Ω_m.

(ii) Код C^∗ полностью регулярен, если и только если C полностью регулярен с

минимальным расстоянием d ∈ {3, 5} и код C^∗ равномерно упакован.

Доказательство. Первое утверждение непосредственно следует из [33]. Для

второго утверждения случай d = 3 известен [39]. Рассмотрим случай d = 5. Так как

C - ПР-код, его радиус покрытия ρ = 3. Следовательно, C - квазисовершенный код.

Теперь результат следует из предложения 4. ▴

(F.52) Выбирая теперь степенные функции F в (15) для нечетного m, получаем дво-

ичные циклические примитивные [n = 2^m -1, n-2m, d; ρ]-коды с порождающими

многочленами вида g(x) = m₁(x)m_ℓ. Для случая d = 5 все такие коды полностью

регулярны [90] с ρ = 3 и с массивом пересечений

IA = {n, n - 1, (n + 3)/2; 1, 2, (n - 1)/2}.

В литературных источниках мы нашли следующие случаи:

(i) Коды БЧХ с d = 5 длины n = 22m+1 - 1 [24] (см. п. 5.3), ℓ = 3;

(ii) Коды Голда [92], ℓ = 2^t + 1, НОД(t, m) = 1;

(iii) Коды Касами [93], ℓ = 22t - 2^t + 1, НОД(t, m) = 1;

(iv) Коды Велча [94] (см. также [95, 96]), ℓ = 2m21 + 3;

(v) Коды Нихо [97]:

^{2^t + 2t/2 - 1,

если t четно,

ℓ=

2^t + 2(3t+1)/2 - 1, если t нечетно;

(vi) Инверсные коды [98], ℓ = 22t - 1, m = 2t + 1;

(vii) Коды Доббертина [99], ℓ = 24t + 23t + 22t + 2^t - 1, m = 5t.

Существование всех указанных выше кодов вытекает из существования извест-

ных AB-функций. Некоторые новые AB-функции (которые также приводят к новым

ПР-кодам), не являющиеся степенными функциями, могут быть найдены, напри-

мер, в работах [100-102]. Вопрос о полной транзитивности указанных кодов требует

дополнительного внимания.

(F.53) Коды, полученные расширением всех выше указанных двоичных кодов, так-

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

сивом пересечений

IA = {n + 1, n, n - 1, (n + 3)/2; 1, 2, (n - 1)/2, n + 1}.

5.14. Новые РУ-код длины 11 и ПР-код длины 33. В [24] в результате компьютер-

ного поиска РУ-кодов были найдены следующие параметры возможного семейства

4-ичных РУ-кодов:

22m+1 + 1

22m - 1

q = 4, n =

k = n - 2m - 1, d = 5, μ = λ + 1 =

m = 2,3,...

Линейные коды над F₄ с такими параметрами (которые оказались не равномер-

но упакованными) были построены в [103]. Позднее был построен нелинейный ад-

дитивный 4-ичный код над F₄ с параметрами (12, 4⁶, 6)₄, называемый додекакодом

(см. ссылку в [104]). Удаление любой позиции этого кода дает (11, 4⁶, 5)₄-код, кото-

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

в [24]. Следуя [104], опишем конструкцию этого кода:

(S.26) Удалим одну позицию додекакода. Пусть G - порождающая матрица резуль-

тирующего кода длины 11, и пусть α - примитивный элемент F₄. Из матрицы G

построим теперь двоичную матрицу H, заменяя каждый элемент поля F₄ одним

из двух двоичных векторов длины 3 следующим образом:

→ 000

или

111,

→ 100

или

011,

α →

001

или

110,

α²

→ 010

или

101.

Это означает, что из каждой строки матрицы G мы получаем 2¹¹ слов в матри-

це H. Таким образом, H порождает двоичный линейный [33, 23, 3; 3]-код, являю-

щийся полностью регулярным (но не полностью транзитивным) с

IA := {33, 30, 15; 1, 2, 15}.

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

Shapiro H.S., Slotnick D.L. On the Mathematical Theory of Error Correcting Codes //

IBM J. Res. Dev. 1959. V. 3. № 1. P. 25-34.

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

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

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

Philips Res. Rep. Suppl. 1973. № 10.

Goethals J.-M., van Tilborg H.C.A. Uniformly Packed Codes // Philips Res. Rep. 1975.

V. 30. P. 9-36.

van Tilborg H. C. A. Uniformly Packed Codes. PhD Thesis. Technische Hogeschool Eind-

hoven, Nederland, 1976.

Solé P. Completely Regular Codes and Completely Transitive Codes // Discrete Math.

1990. V. 81. № 2. P. 193-201.

Giudici M. Completely Transitive Codes in Hamming Graphs. PhD Thesis. Univ. of West-

ern Australia, Perth, Australia, 1998.

Giudici M., Praeger C.E. Completely Transitive Codes in Hamming Graphs // European

J. Combin. 1999. V. 20. № 7. P. 647-662.

Gillespie N.I., Praeger C.E. New Characterisations of the Nordstrom-Robinson Codes //

Bull. London Math. Soc. 2017. V. 49. № 2. P. 320-330.

10.

Brouwer A.E., Cohen A.M., Neumaier A. Distance-Regular Graphs. Berlin: Springer-

Verlag, 1989.

11.

van Dam E.R., Koolen J.H., Tanaka H. Distance-Regular Graphs // Electron. J. Combin.

2016. DS22, Dynamic Survey, 156 pp.

12.

Koolen J., Krotov D., Martin B. Completely Regular Codes. 2016. Available at https:

//sites.google.com/site/completelyregularcodes.

13.

Koolen J.H., Lee W.S., Martin W.J., Tanaka H. Arithmetic Completely Regular Codes //

Discrete Math. Theor. Comput. Sci. 2016. V. 17. № 3. P. 59-76.

14.

Tietäväinen A. On the Nonexistence of Perfect Codes over Finite Fields // SIAM J. Appl.

Math. 1973. V. 24. № 1. P. 88-96.

15.

Зиновьев В.А., Леонтьев В.К. Несуществование совершенных кодов над полями Га-

луа // Проблемы управления и теории информации. 1973. Вып. 2. С. 123-132.

16.

Borges J., Rifà J. On the Nonexistence of Completely Transitive Codes // IEEE Trans.

Inform. Theory. 2000. V. 46. № 1. P. 279-280.

17.

Borges J., Rifà J., Zinoviev V. Nonexistence of Completely Transitive Codes with Error-

Correcting Capability e > 3 // IEEE Trans. Inform. Theory. 2001. V. 47. № 4. P. 1619-1621.

18.

Neumaier A. Completely Regular Codes // Discrete Math. 1992. V. 106/107. P. 353-360.

19.

Borges J., Rifà J., Zinoviev V.A. On Non-antipodal Binary Completely Regular Codes //

Discrete Math. 2008. V. 308. № 16. P. 3508-3525.

20.

Avgustinovich S.V., Krotov D.S., Vasil’eva A.Yu. Completely Regular Codes in the Infinite

Hexagonal Grid // Сиб. электрон. матем. изв. 2016. Т. 13. С. 987-1016.

21.

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

Связь, 1979.

22.

Brouwer A.E. A Note on Completely Regular Codes // Discrete Math. 1990. V. 83. № 1.

P. 115-117.

23.

Lindström K. All Nearly Perfect Codes Are Known // Inform. Control. 1977. V. 35. № 1.

P. 40-47.

24.

Бассалыго Л.А., Зайцев Г.В., Зиновьев В.А. О равномерно упакованных кодах //

Пробл. передачи информ. 1974. Т. 10. № 1. С. 9-14.

25.

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

26.

Blake I.F., Mullin R.C. The Mathematical Theory of Coding. New York: Academic Press,

1975.

27.

Hughes D.R., Piper F.C. Design Theory. Cabmridge: Cambridge Univ. Press, 1985.

28.

Handbook of Combinatorial Designs. Boca Raton: Chapman & Hall, 2007.

29.

Magliveras S.S., Leavitt D.W. Simple Six Designs Exist // Congr. Numer. 1983. V. 40.

P. 195-205.

30.

Teirlinck L. Non-trivial t-Designs without Repeated Blocks Exist for All t // Discrete

Math. 1987. V. 65. № 3. P. 301-311.

31.

Assmus E.F., Jr., Goethals J.-M., Mattson H.F., Jr. Generalized t-Designs and Majority

Decoding of Linear Codes // Inform. Control. 1976. V. 32. № 1. P. 43-60.

32.

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

передачи информ. 2007. Т. 43. № 2. С. 34-51.

33.

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

передачи информ. 1977. Т. 13. № 3. С. 22-25.

34.

Rifà J., Zinoviev V.A. New Completely Regular q-ary Codes Based on Kronecker Prod-

ucts // IEEE Trans. Inform. Theory. 2011. V. 56. № 1. P. 266-272.

35.

Rifà J., Zinoviev V.A. On Lifting Perfect Codes // IEEE Trans. Inform. Theory. 2011.

V. 57. № 9. P. 5918-5925.

36.

Rifà J., Zinoviev V.A. On a Family of Binary Completely Transitive Codes with Growing

Covering Radius // Discrete Math. 2014. V. 318. P. 48-52.

37.

Gillespie N.I., Praeger C.E. Uniqueness of Certain Completely Regular Hadamard

Codes // J. Combin. Theory Ser. A. 2013. V. 120. № 7. P. 1394-1400.

38.

Borges J., Rifà J., Zinoviev V.A. New Families of Completely Regular Codes and Their

Corresponding Distance Regular Coset Graphs // Des. Codes Cryptogr. 2014. V. 70. № 1-2.

P. 139-148.

39.

Borges J., Rifà J., Zinoviev V.A. Families of Nested Completely Regular Codes and

Distance-Regular Graphs // Adv. Math. Commun. 2015. V. 9. № 2. P. 233-246.

40.

Calderbank A.R., Goethals J.-M. Three-Weight Codes and Association Schemes // Philips

J. Res. 1984. V. 39. № 4-5. P. 143-152.

41.

Calderbank A.R., Goethals J.-M. On a Pair of Dual Subschemes of the Hamming Scheme

Hn(q) // European J. Combin. 1985. V. 6. № 2. P. 133-147.

42.

Baker R.D., van Lint J.H., Wilson R.M. On the Preparata and Goethals Codes // IEEE

Trans. Inform. Theory. 1983. V. 29. № 3. P. 342-345.

43.

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

параты и Кердока // Тр. V конф. по теории кодирования и передачи информации.

Ч. 2. Тез. докл. Москва - Горький, 1972. С. 55-58.

44.

Camion P., Courteau B., Delsarte P. On r-Partition Designs in Hamming Spaces // Appl.

Algebra Engrg. Commun. Comput. 1992. V. 2. № 3. P. 147-162.

45.

Brouwer A.E. On Complete Regularity of Extended Codes // Discrete Math. 1993. V. 117.

№ 1-3. P. 271-273.

46.

Rifà J., Pujol J. Completely Transitive Codes and Distance Transitive Graphs // Ap-

plied Algebra, Algebraic Algorithms and Error-Correcting Codes (Proc. 9th Int. Sympos.

AAECC-9. New Orleans, LA, USA. October 7-11, 1991). Lect. Notes Comp. Sci. V. 539.

Berlin: Springer, 1991. P. 360-367.

47.

Livingstone D., Wagner A. Transitivity of Finite Permutation Groups on Unordered Sets //

Math. Z. 1965. V. 90. № 5. P. 393-403.

48.

Berger T.P. The Automorphism Group of Double-Error-Correcting BCH Codes // IEEE

Trans. Inform. Theory. 1994. V. 40. № 2. P. 538-542.

49.

Godsil C.D., Praeger C.E. Completely Transitive Designs // arXiv:1405.2176 [math.CO],

2014.

50.

Bannai E. Codes in Bipartite Distance-Regular Graphs // J. London Math. Soc. (2). 1977.

V. 16. № 2. P. 197-202.

51.

Hammond P. On the Non-existence of Perfect and Nearly Perfect Codes // Discrete Math.

1982. V. 39. № 1. P. 105-109.

52.

Etzion T. On the Nonexistence of Perfect Codes in the Johnson Scheme // SIAM J. Discrete

Math. 1996. V. 9. № 2. P. 201-209.

53.

Etzion T., Schwarz M. Perfect Constant-Weight Codes // IEEE Trans. Inform. Theory.

2004. V. 50. № 9. P. 2156-2165.

54.

Etzion T. Configuration Distribution and Designs of Codes in the Johnson Scheme //

J. Combin. Des. 2007. V. 15. № 1. P. 15-34.

55.

Shimabukuro O. On the Nonexistence of Perfect Codes in J(2w + p², w) // Ars Combin.

2005. V. 75. P. 129-134.

56.

Gordon D.M. Perfect Single Error-Correcting Codes in the Johnson Scheme // IEEE Trans.

Inform. Theory. 2006. V. 52. № 10. P. 4670-4672.

57.

Kummer E.E.

Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen //

J. Reine Angew. Math. 1852. V. 44. P. 93-146.

58.

Loxton J.H. Some Problems Involving Powers of Integers // Acta Arith. 1986. V. 46. № 2.

P. 113-123.

59.

Bernstein D.J. Detecting Perfect Powers in Essentially Linear Time // Math. Comp. 1998.

V. 67. № 223. P. 1253-1283.

60.

Roos C. A Note on the Existence of Perfect Constant Weight Codes // Discrete Math.

1983. V. 47. № 1. P. 121-123.

61.

Мовсисян Г.Л. Совершенные коды в схемах Джонсона // Вестн. Моск. ун-та. Сер. 15.

Вычисл. Матем. Киберн. 1982. № 1. С. 64-69.

62.

Мовсисян Г.Л. Совершенные равновесные коды и системы Штейнера // Пробл. пере-

дачи информ. 1983. Т. 19. № 2. С. 109-112.

63.

Movsisian G.L., Margarian Zh.G. D-Representing Code Problem Solution // Fundamen-

tals of Computation Theory (Proc. Int. Conf. FCT’87. Kazan, USSR. June 22-26, 1987).

Lect. Notes Comp. Sci. V. 278. Berlin: Springer, 1987. P. 328-331.

64.

Leont’ev V.K., Movsisyan G.L., Margaryan Zh.G. Constant Weight Perfect and D-Repre-

sentable Codes // Уч. записки ЕГУ. Сер. Физика и Математика. 2012. № 1. С. 16-19.

65.

Могильных И.Ю. О регулярности совершенных раскрасок графов Джонсона в два

цвета // Пробл. передачи информ. 2007. Т. 43. № 4. С. 37-44.

66.

Могильных И.Ю. О несуществовании некоторых совершенных 2-раскрасок графов

Джонсона // Дискретн. анализ и исслед. опер. 2009. Т. 16. № 5. С. 52-68.

67.

Августинович С.В., Могильных И.Ю. Совершенные раскраски графов Джонсона

J(8, 3) и J(8, 4) в два цвета // Дискретн. анализ и исслед. опер. 2010. Т. 17. № 2.

С. 3-19.

68.

Martin W.J. Completely Regular Designs of Strength One // J. Algebraic Combin. 1994.

V. 3. № 2. P. 177-185.

69.

Martin W.J. Completely Regular Designs // J. Combin. Des. 1998. V. 6. № 4. P. 261-273.

70.

Meyerowitz A. D. Cycle-Balance Conditions for Distance-Regular Graphs // Discrete

Math. 2003. V. 264. № 1-3. P. 149-165.

71.

Godsil C. Частное сообщение У.Дж. Мартину [69].

72.

Avgustinovich S.V., Mogilnykh I.Yu. Induced Perfect Colorings // Сиб. электрон. матем.

изв. 2011. Т. 8. С. 310-316.

73.

Delorme C. Régularité métrique forte // Rapport de Recherche № 156, Univ. Paris Sud.

Orsay, France, 1983.

74.

Godsil C. Association Schemes. Univ. of Waterloo, Canada, 2005. Available at https:

//www.math.uwaterloo.ca/~cgodsil/pdfs/assoc2.pdf.

75.

Godsil C.D. Equitable Partitions // Combinatorics, Paul Erdős is Eighty. V. 1. Budapest:

János Bolyai Math. Soc., 1993. P. 173-192.

76.

Rifà J., Zinoviev V.A. On Completely Regular Codes from Perfect Codes // Proc. 10th

Int. Workshop on Algebraic and Combinatorial Coding Theory (ACCT-10). Zvenigorod,

Russia. September 3-9, 2006. P. 225-229.

77.

Ivanov A.A., Liebler R.A., Penttila T., Praeger C.E. Antipodal Distance-Transitive Covers

of Complete Bipartite Graphs // European J. Combin. 1997. V. 18. № 1. P. 11-33.

78.

Rifà J., Zinoviev V.A. Completely Regular Codes with Different Parameters Giving the

Same Distance-Regular Coset Graphs // Discrete Math. 2017. V. 340. № 7. P. 1649-1656.

79.

Rifà J., Zinoviev V.A. On a Class of Binary Linear Completely Transitive Codes with

Arbitrary Covering Radius // Discrete Math. 2009. V. 309. № 16. P. 5011-5016.

80.

Borges J., Rifà J., Zinoviev V. Completely Regular Codes by Concatenating Hamming

Codes // Adv. Math. Commun. 2018. V. 12. № 2. P. 337-349.

81.

Borges J., Rifà J., Zinoviev V. On New Infinite Families of Completely Regular and Com-

pletely Transitive Binary Codes // Proc. 16th Int. Workshop on Algebraic and Combina-

torial Coding Theory (ACCT-16). Svetlogorsk, Russia. September 2-9, 2018. P. 7-8.

82.

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.

83.

Fon-Der-Flaass D.G. A Bound on Correlation Immunity // Сиб. электрон. матем. изв.

2007. Т. 4. С. 133-135.

84.

Фон-Дер-Флаас Д.Г. Совершенные 2-раскраски гиперкуба // Сиб. матем. журн. 2007.

Т. 48. № 4. С. 923-930.

85.

Фон-Дер-Флаас Д.Г. Совершенные 2-раскраски 12-мерного гиперкуба, достигающие

границы корреляционной иммунности // Сиб. электрон. матем. изв. 2007. Т. 4.

С. 292-295.

86.

Tarannikov Y.V. On Resilient Boolean Functions with Maximal Possible Nonlinearity //

Progress in Cryptology - INDOCRYPT 2000 (Proc. 1st Int. Conf. in Cryptology in India.

Calcutta, India. December 10-13, 2000). Lect. Notes Comp. Sci. V. 1977. Berlin: Springer-

Verlag, 2000. P. 19-30.

87.

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

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

88.

Bush K.A. Orthogonal Arrays of Index Unity // Ann. Math. Statist. 1952. V. 23. № 3.

P. 426-434.

89.

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

Lab. Report R160. Brussels, Belgium, 1971.

90.

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

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

91.

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

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

92.

Gold R. Maximal Recursive Sequences with 3-Valued Recursive Cross-Correlation Func-

tions // IEEE Trans. Inform. Theory. 1968. V. 14. № 1. P. 154-156.

93.

Kasami T. The Weight Enumerators for Several Classes of Subcodes of the 2nd Order

Binary Reed-Muller Codes // Inform. Control. 1971. V. 18. № 4. P. 369-394.

94.

Welch L.R. Trace Mappings in Finite Fields and Shift Register Cross-Correlation Prop-

erties // Dept. Electrical Engineering Report. Univ. of Southern California, Los Angeles,

1969.

95.

Canteaut A., Charpin P., Dobbertin H. Binary m-Sequences with Three-Valued Crosscor-

relation: A Proof of Welch’s Conjecture // IEEE Trans. Inform. Theory. 2000. V. 46. № 1.

P. 4-8.

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

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

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

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

98. Beth T., Ding C. On Almost Perfect Nonlinear Permutations // Advances in Cryptol-

ogy - EUROCRYPT’93 (Proc. Workshop on the Theory and Application of Cryptographic

Techniques. Lofthus, Norway. May 23-27, 1993). Lect. Notes Comp. Sci. V. 765. Berlin:

Springer-Verlag, 1994. P. 65-76.

99. Dobbertin H. Almost Perfect Nonlinear Power Functions on GF(2ⁿ): A New Case for n

Divisible by 5 // Finite Fields and Applications. Berlin: Springer, 2001. P. 113-121.

100. Budaghyan L., Carlet C., Pott A. New Classes of Almost Bent and Almost Perfect Non-

linear Polynomials // IEEE Trans. Inform. Theory. 2006. V. 52. № 3. P. 1141-1152.

101. Berger T.P., Canteaut A., Charpin P., Laigle-Chapuy Y. On Almost Perfect Nonlinear

Functions over Fn2 // IEEE Trans. Inform. Theory. 2006. V. 52. № 9. P. 4160-4170.

102. Carlet C. Boolean Functions for Cryptography and Error-Correcting Codes // Boolean

Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge:

Cambridge Univ. Press, 2010. Ch. 8. P. 257-397.

103. Думер И.И., Зиновьев В.А. Некоторые новые максимальные коды над полем Галуа

GF (4) // Пробл. передачи информ. 1978. Т. 14. № 3. С. 24-34.

104. Shi M., Krotov D.S., Solé P. A New Distance-Regular Graph of Diameter 3 on 1024

Vertices // arXiv:1806.07069v3 [math.CO], 2018.

Боржес Жуаким

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

Рифа Жузеп

22.12.2018

Школа инженерии, отделение информационной

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

и телекоммуникационной инженерии,

06.02.2019

Независимый университет Барселоны, Испания

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

joaquim.borges@uab.cat

11.02.2019

josep.rifa@uab.cat

Зиновьев Виктор Александрович

Институт проблем передачи информации

им. А.А. Харкевича РАН

zinov@iitp.ru