ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ
Том 57
2021
Вып. 4
УДК 621.391.1 : 519.725
© 2021 г.
Ф.И. Соловьева
О ПЕРЕСЕЧЕНИИ КОДОВ ТИПА РИДА - МАЛЛЕРА1
Двоичный код с параметрами и основными свойствами классического кода
Рида - Маллера RMr,m порядка r будем называть кодом типа Рида - Маллера
порядка r и обозначать через LRMr,m. Класс таких кодов содержит семей-
ство кодов, полученных конструкцией Пулатова, а также классические линей-
ные и Z4-линейные коды Рида - Маллера. Исследуется проблема пересечения
кодов типа Рида - Маллера. Доказано, что для любого четного k в интерва-
∑
2
(m-1i)
ле 0 ≤ k ≤ 2i=0
существуют коды LRMr,m порядка r длины 2m, пе-
ресечение которых равно k. Доказано также, что существуют два кода типа
Рида - Маллера порядка r длины 2m, пересечение которых равно 2k1k2, где
1 ≤ ks ≤ |RMr-1,m-1|, s ∈ {1,2}, для любой допустимой длины, начиная с 16.
Ключевые слова: код Рида - Маллера, код типа Рида - Маллера, задача о пере-
сечении кодов, коды Пулатова, компоненты кода Рида - Маллера, i-компонента,
свитчинг, свитчинговая конструкция кодов.
DOI: 10.31857/S0555292321040057
§ 1. Введение
Векторное пространство размерности n над полем Галуа GF(2), снабженное мет-
рикой Хэмминга, будем обозначать через Fn. Основные определения см. в [1].
Напомним определение и основные свойства классического двоичного линейного
кода Рида - Маллера порядка r, который будем обозначать через RMr,m, а его вы-
колотый код - через RM∗r,m. Код Рида - Маллера определяется для любых 1 ≤ m,
0 ≤ r ≤ m, как совокупность всех векторов длины 2m, отвечающих булевым функ-
циям степени не более r от m переменных. Код RMr,m имеет следующие параметры:
∑
длина кода равна n = 2m, мощность 2k, где k =
(m),кодовоерасстояние2m-r.
i=0
i
Код RMr,m антиподален, т.е. для любого кодового слова x вектор x = x + 1n также
принадлежит коду, здесь и далее 1n - вектор длины n, состоящий из единичных
координат, а знаком + обозначено сложение по модулю 2. Код RMr,m является ду-
альным к коду RMm-1-r,m, 0 ≤ r ≤ m, и кроме того, RMr-1,m ⊂ RMr,m. Коды
RMm-2,m и RM1,m являются расширенными кодами Хэмминга и Адамара соответ-
ственно. Код Рида - Маллера RMr,m порождается множеством своих кодовых слов
минимального веса (см. [1, § 13.5]).
Двоичный антиподальный код с параметрами классического кода Рида - Малле-
ра RMr,m порядка r назовем кодом типа Рида - Маллера порядка r и будем обозна-
чать через LRMr,m. Этот код не обязательно линеен. Класс данных кодов совпадает
с обширным классом расширенных совершенных кодов при r = m-2. По определе-
нию все коды RMr,m являются кодами LRMr,m. При r ∈ {0, m - 1, m} код LRMr,m
1 Работа выполнена в рамках государственного задания ИМ СО РАН (проект № 0314-2019-0016).
63
совпадает с кодом RMr,m. Несколько конструкций кодов LRMr,m любых порядков,
т.е. содержащих не только совершенные расширенные коды и коды Адамара, были
предложены в работах [2-4]. Заметим, что, как и код RMr,m длины n = 2m, код ти-
па Рида - Маллера с теми же параметрами, полученный конструкцией Пулатова [3]
из кодов Рида - Маллера длины n = 2m-1 с нелинейной функцией λ (см. опреде-
ление кода в § 2), образует ортогональный массив силы 2r - 1. Класс кодов типа
Рида - Маллера содержит важный класс Z4-линейных кодов Рида - Маллера (см. их
конструкции в работах [5,6]). Групповые коды над кольцом Z4, являющиеся прооб-
разами этих Z4-линейных кодов Рида - Маллера под действием отображения Грэя,
имеют базисы минимального веса (см. [7]).
В настоящей работе исследуется следующий вопрос: каков размер пересечения
двух кодов LRMr,m? Аналогичная проблема ранее, в 1994 г., была выдвинута в [8]
для совершенных кодов.
Исследованиям проблемы пересечения совершенных q-ичных кодов и двоичных
кодов Адамара посвящено достаточно много статей (см. обзор [9] и библиографию
в нем). Полное решение проблемы пересечения двоичных кодов Хэмминга найде-
но в работе [10]. В статье [11] решена проблема пересечения для всех q-ичных ли-
нейных кодов, q ≥ 2, включая двоичные коды Рида - Маллера. Согласно [11] для
некоторой подстановки π длины 2m код Рида - Маллера RMr,m порядка r удовле-
творяет условию |RMr,m ∩ π(RMr,m)| ≥ 2, где минимальное значение 2 достижимо
только при r ≤ [(m - 1)/2]. В [10] показано, что для каждого m ≥ 3 существуют два
нелинейных совершенных двоичных кода длины 2m - 1, пересекающихся по двум
кодовым словам. В работе [12] доказано, что для любых чисел k1 и k2, таких что
1 ≤ ks ≤ 2(n+1)/2-log(n+1), s = 1,2, найдутся совершенные двоичные коды C1 и C2
длины n = 2m - 1, m ≥ 4, удовлетворяющие |C1 ∩ C2| = 2k1k2. В [13] показано, что
для любого четного числа k в интервале 0 ≤ k ≤ 2n+1-2log(n+1) существуют совер-
шенные двоичные коды C1 и C2 длины n = 2m - 1, m ≥ 4, такие что η(C1, C2) = k.
Следует отметить, что совокупности чисел пересечений, полученных в [12] и [13],
не покрывают друг друга. В работе [14] исследовались пересечения кодов Адамара.
В [15] полностью решена проблема пересечения аддитивных (Z4- и Z2Z4-линейных),
расширенных и нерасширенных совершенных кодов. Аналогичный результат был
получен для аддитивных (Z4- и Z2Z4-линейных) кодов Адамара (дуальных кодов
к Z4- и Z2Z4-линейным совершенным кодам соответственно) в работе [16].
Очевидно, что мощность пересечения расширений кодов C1 и C2 посредством
общей проверки на четность остается такой же, как и для исходных кодов, причем
верно также и обратное.
В данной работе доказано (см. теорему 2), что для любого четного k в интервале
∑
2
(m-1i)
0 ≤ k ≤ 2i=0
существуют LRMr,m коды C и C′ с длинами 2m, пересечение
которых равно k. Доказано также (см. теорему 3), что существуют два кода LRMr,m
порядка r, имеющих длину по крайней мере 16 и пересекающихся по 2k1k2 кодовым
словам, где 1 ≤ ks ≤ |RMr-1,m-1|, s ∈ {1, 2}. Отметим, что полученные результа-
ты обобщают результаты работ [8,11-13]. Кроме того, значение 2 также достижимо
среди указанных множеств чисел пересечений кодов типа Рида - Маллера, и как и в
случае совершенных кодов, совокупности чисел пересечений, представленных в этих
теоремах, не покрывают друг друга. Для получения данных результатов потребо-
валось изучить свойства i-компонент кода Рида - Маллера и использовать свитчин-
говую конструкцию Пулатова [3] для построения кодов типа Рида - Маллера.
§ 2. Необходимые определения и понятия
В этом параграфе рассмотрим необходимые определения и понятия и напомним
конструкцию Пулатова [3] для кодов типа Рида - Маллера.
64
Число η для кодов C1 и C2 назовем числом пересечения этих кодов. Обозна-
чим выколотый код типа Рида - Маллера порядка r через LRM∗r,m. Приведем кон-
струкцию Пулатова. Пусть LRM∗r,m-1 и LRM∗r-1,m-1 - два выколотых кода типа
Рида - Маллера порядков r и r - 1 длины 2m-1 - 1, мощностей 2kr и 2kr-1, с кодо-
∑(m-1)и
выми расстояниями 2m-r-1 - 1 и 2m-r - 1 соответственно, где kr =
i
i=0
∑(m-1).Пустьλ-произвольнаяфункция,действующаян
kr-1 =
а множестве
i
i=0
кодовых слов кода LRM∗r-1,m-1 со значениями в множестве {0, 1}. Для любых r
и m ≥ 2, 0 < r < m, код, полученный итеративной конструкцией Пулатова
{(x + y, x, |x| + λ(y)) : x ∈ LRM∗r,m-1, y ∈ LRM∗r-1,m-1},
(1)
является выколотым кодом типа Рида - Маллера длины n = 2m -1 с числом кодовых
∑
слов 2k, где k =
(m), и кодовым расстоянием, равным 2m-r - 1.
i
i=0
Если LRM∗r,m-1 = RM∗r,m-1, LRM∗r-1,m-1 = RM∗r-1,m-1 и λ ≡ 0, то код, получен-
ный конструкцией Пулатова, является выколотым линейным кодом Рида - Маллера
RM∗r,m порядка r. Конструкция Пулатова (1) для выколотых кодов типа Рида - Мал-
лера является обобщением известной свитчинговой конструкции Васильева для со-
вершенных двоичных кодов [17], а для расширенного случая - известной конструк-
ции Плоткина [1].
Пусть C - произвольный код длины n с кодовым расстоянием d, d ≥ 3. Для
i ∈ {1,...,n} через Gi(C) обозначим граф с множеством кодовых слов кода C в ка-
честве множества вершин и с множеством ребер {(x, y) : d(x, y) = d, xi = yi}.
Компонента связности K графа Gi(C) называется i-компонентой кода C. При этом
говорят, что код C′ = (C\K)∪(K +ei) получен из кода C методом свитчинга i-ком-
поненты K. Здесь и далее ei обозначает вектор веса один пространства Fn, имеющий
единицу только в i-й координатной позиции. Код C′ имеет те же параметры, что и
код C: длину, мощность и кодовое расстояние. Метод свитчинга i-компонент ока-
зался весьма эффективным для построения и исследования свойств совершенных
кодов и позволил решить ряд проблем, стоящих для совершенных q-ичных кодов,
q ≥ 2 (см. обзоры в работах [9,18]).
Рассмотрим конструкцию Пулатова (1) в случае, когда LRM∗r,m-1 и LRM∗r-1,m-1
- выколотые линейные коды Рида - Маллера RM∗r,m-1 и RM∗r-1,m-1 соответственно,
а λ - произвольная функция из множества кодовых слов кода RM∗r-1,m-1 в множе-
ство {0, 1}:
LRM∗r,m = {(x + y, x, |x| + λ(y)) : x ∈ RM∗r,m-1, y ∈ RM∗r-1,m-1}.
(2)
Через 0n обозначим вектор длины n, состоящий из нулевых координат.
Согласно [3] множество
Rn = {(x, x, |x|) : x ∈ RM∗r,m-1}
является n-компонентой кодов LRM∗r,m и RM∗r,m, где n = 2m - 1. Легко видеть, что
код (2) может быть представлен в виде
(
)
\
⋃
⋃
LRM∗r,m = RM∗
Ry
∪
(Ryn + en),
(3)
r,m
n
y∈RM∗r-1,m-1, λ(y)=1
y∈RM∗r-1,m-1, λ(y)=1
где Ryn = Rn + (y, 02m-1), y ∈ RM∗r-1,m-1. Код (3) задан свитчинговой конструк-
цией, так как получен из кода RM∗r,m свитчингами n-компонент Ryn и Ryn + en для
каждого y, удовлетворяющего λ(y) = 1.
65
Теорема 1. Для любых r и m, 2 ≤ m, 0 ≤ r < m, существуют два выколо-
тых кода типа Рида - Маллера порядка r длины 2m - 1 (а также их расширения
длины 2m посредством общей проверки на четность), имеющих пересечение η, где
{
}
η∈
|RM∗r,m-1|, 2|RM∗r,m-1|, . . . , (|RM∗r-1,m-1| - 1)|RM∗r,m-1|
Доказательство. Для получения требуемых чисел пересечений выколотых
кодов типа Рида - Маллера рассмотрим следующие пары кодов длины 2m - 1: выко-
лотый код Рида - Маллера порядка r и выколотые коды типа Рида - Маллера поряд-
ка r, определенные в (3). Пусть A - произвольное подмножество кодовых слов кода
RM∗r-1,m-1 и λ(y) = 1 в случае y ∈ A. Поскольку по определению Ryn выполняется
|Ryn| = |RM∗r,m-1|, то легко видеть, что коды
(
)
⋃
⋃
RM∗r,m и RM∗r,m \ Ry
n
∪ (Ryn + en)
y∈A
y∈A
пересекаются по
(|RM∗r-1,m-1| - |A|)|RM∗r,m-1|
кодовым словам. Выбирая подмножество A в коде RM∗r-1,m-1 произвольным обра-
зом, т.е. варьируя число кодовых слов y в RM∗r-1,m-1, удовлетворяющих λ(y) = 1,
из конструкции (3) немедленно получаем, что следующие числа пересечений η яв-
ляются достижимыми для выколотых кодов типа Рида - Маллера:
{
}
η∈
|RM∗r,m-1|, 2|R∗r,m-1|, . . . , (|RM∗r-1,m-1| - 1)|RM∗r,m-1|
Заметим, что (|RM∗r-1,m-1| - 1)|RM∗r,m-1| = |RM∗r,m| - |RM∗r,m-1|.
Такое же множество чисел пересечений получаем и для расширенных кодов
LRMr,m. ▴
Отметим, что аналогичный результат был получен для совершенных кодов в
работе [8].
§3. Пересечение кодов типа Рида- Маллера
В данном параграфе будут получены два существенно более богатых класса чи-
сел пересечений для кодов типа Рида - Маллера, чем те, которые дает прямой свит-
чинговый метод, описанный в теореме 1. Для достижения этой цели построим два
кода типа Рида - Маллера специального вида, используя конструкцию Пулатова (1)
для расширенного случая.
Прежде чем привести описание кодов, рассмотрим три вспомогательных леммы,
одна из которых взята из работы [13]. Пусть π - циклическая подстановка дли-
ны n/2, здесь и всюду далее n = 2m. Пусть ϕ обозначает отображение x → x + π(x)
из Fn/2 в себя, и пусть Fn/2 = Fn/20 ∪ Fn/21, где Fn/20 и Fn/21 - множества всех векторов
четного и нечетного весов в Fn/2 соответственно. Обозначим через ker(ϕ) ядро отоб-
ражения ϕ, а через dim(ker(ϕ)) - его размерность. Для полноты изложения приведем
с доказательством лемму из [13] о свойствах отображения ϕ, которые потребуются
нам в дальнейшем.
Лемма 1. Отображение ϕ линейно и обладает следующими свойствами:
1. dim(ker(ϕ)) = 1;
2. ϕ(Fn/2) = Fn/20;
3. ϕ(Fn/2) = V ∪ (z + V ), где V
= ϕ(Fn/20), z = ϕ(u) для некоторого u ∈ Fn/21 и
z + V = ϕ(Fn/21).
66
Доказательство. 1. Очевидно, что ϕ - линейное отображение, и так как
x = π(x) только при x ∈ {0n/2,1n/2}, то размерность ядра этого отображения рав-
на 1.
2. Поскольку w(x) = w(π(x)) для любого x ∈ Fn/2, то справедливо ϕ(Fn/2) = Fn/20,
n
и размерность ϕ(Fn/2), очевидно, равнаn
- dim(ker(ϕ)) =
- 1.
2
2
Аналогично dim(ϕ(Fn/20)) = dim(ϕ(Fn/2)) - dim(ker(ϕ)) =n
- 2.
2
3. Так как V = ϕ(Fn/20) - подпространство пространства ϕ(Fn/2), то ϕ(Fn/2) =
= V ∪(z+V ), где z+V - класс смежности подпространства V с лидером z. Поскольку
z + V ⊂ ϕ(Fn/2), то найдется вектор u в Fn/21, такой что z = ϕ(u). ▴
Лемма 2. Для любого кодового слова y из кода RMr-1,m, 0 ≤ r ≤ m-1, 4 ≤ m,
n = 2m, существуют ровно два различных кодовых слова u, u ∈ RMr,m, удовлетво-
ряющих y = u + π(u) и y = u + π(u), где u = u + 1n.
Доказательство. Заметим, что в силу леммы 1 размерность ядра отображе-
ния ϕ равна единице. Отсюда, если существует одно решение для y, т.е. найдется
некоторый u, такой что y = u + π(u), то решений ровно два, так как антиподаль-
ный к u вектор u = u + 1n также удовлетворяет y = u + π(u). Поэтому достаточно
ограничиться в лемме доказательством существования одного вектора u.
Доказательство проведем индукцией по m ≥ 3. При m = 3 имеем вложение кодов
Рида - Маллера RM0,3 ⊂ RM1,3 ⊂ RM2,3. Непосредственной проверкой для любо-
го кодового слова y кода RM1,3, который является расширенным кодом Хэмминга
длины 8, легко найти два кодовых слова u и u из RM2,3, удовлетворяющих y = u +
+π(u) и y = u + π(u). Для этого достаточно решить для любого y = (y1, . . . , y8) ∈
∈ RM1,3 систему линейных уравнений ui + u(i+1) mod 8 = yi, i = 1, 2, . . ., 8. Положим
u1 = 0. Легко проверить, что в этом случае система имеет единственное решение u,
u ∈ RM2,3, что дает представление y = u + π(u). Второе решение также получа-
ем однозначно, полагая u1 = 1, т.е. имеем y = u + π(u). Для наглядности приве-
дем для каждого вектора yi, yi ∈ RM1,3, соответствующий вектор ui, ui ∈ RM2,3,
i = 1,...,16:
y1 = (0, 0, 0, 0, 0, 0, 0, 0), u1 = (0, 0, 0, 0, 0, 0, 0, 0);
y2 = (1, 1, 1, 1, 0, 0, 0, 0), u2 = (0, 1, 0, 1, 1, 1, 1, 1);
y3 = (1, 1, 0, 0, 1, 1, 0, 0), u3 = (0, 1, 1, 1, 0, 1, 1, 1);
y4 = (1, 0, 1, 0, 1, 0, 1, 0), u4 = (0, 0, 1, 1, 0, 0, 1, 1);
y5 = (1, 1, 0, 0, 0, 0, 1, 1), u5 = (0, 1, 1, 1, 1, 1, 0, 1);
y6 = (1, 0, 1, 0, 0, 1, 0, 1), u6 = (0, 0, 1, 1, 1, 0, 0, 1);
y7 = (1, 0, 0, 1, 1, 0, 0, 1), u7 = (0, 0, 0, 1, 0, 0, 0, 1);
y8 = (1, 0, 0, 1, 0, 1, 1, 0), u8 = (0, 0, 0, 1, 1, 0, 1, 1);
y9 = (1, 1, 1, 1, 1, 1, 1, 1), u9 = (0, 1, 0, 1, 0, 1, 0, 1);
y10 = (0, 0, 0, 0, 1, 1, 1, 1), u10 = (0, 0, 0, 0, 1, 0, 1, 0);
y11 = (0, 0, 1, 1, 0, 0, 1, 1), u11 = (0, 0, 1, 0, 0, 0, 1, 0);
y12 = (0, 1, 0, 1, 0, 1, 0, 1), u12 = (0, 1, 1, 0, 0, 1, 1, 0);
y13 = (0, 0, 1, 1, 1, 1, 0, 0), u13 = (0, 0, 1, 0, 1, 0, 0, 0);
y14 = (0, 1, 0, 1, 1, 0, 1, 0), u14 = (0, 1, 1, 0, 1, 1, 0, 0);
y15 = (0, 1, 1, 0, 0, 1, 1, 0), u15 = (0, 1, 0, 0, 0, 1, 0, 0);
y16 = (0, 1, 1, 0, 1, 0, 0, 1), u16 = (0, 1, 0, 0, 1, 1, 1, 0).
67
Для кода RM0,3 выполняется 18 = u + π(u), где вектор u = (0, 1, 0, 1, 0, 1, 0, 1)
принадлежит RM1,3.
Пусть при m - 1 лемма верна, т.е. для каждого кодового слова x произвольного
кода Рида - Маллера длины 2m-1 порядка не более m - 2 существует u ∈ RMr,m-1,
удовлетворяющий x = u + π(u). Докажем справедливость леммы для m и любого
0 ≤ r ≤ m - 1.
Согласно конструкции Плоткина для линейных кодов Рида - Маллера имеем
RMr,m = {(x + y, x) : x ∈ RMr,m-1, y ∈ RMr-1,m-1}.
(4)
По предположению индукции для кодовых слов кодов RMr,m-1 и RMr-1,m-1 вы-
полняется утверждение леммы.
Обозначим через Π подстановку на 2m координатных позициях, являющуюся
циклическим сдвигом на одну координатную позицию вправо.
Рассмотрим произвольный вектор (x + y, x) кода RMr,m. Возможны следующие
случаи.
Случай 1. Пусть x = 0n/2, x ∈ RMr,m-1, y = 0n/2, y ∈ RMr-1,m-1, где n = 2m.
В этом случае согласно (4) имеем (x, x) ∈ RMr,m для любого x из RMr,m-1. По
предположению индукции для вектора x найдется вектор u, такой что x = u + π(u).
Отсюда
(x, x) = (u + π(u), u + π(u)) = (u, u) + (π(u), π(u)) = (u, u) + Π((u, u)).
(5)
Случай 2. Пусть x = 0n/2, x ∈ RMr,m-1, а y = 0n/2, y ∈ RMr-1,m-1. По предполо-
жению индукции для вектора y найдется вектор u ∈ RMr,m-1, такой что y = u+π(u).
Рассмотрим подслучай, когда последняя координата вектора u равна 0. Тогда
первая координата вектора π(u) равна 0. Следовательно,
(y, 0n/2) = (u + π(u), 0n/2) = (u, 0n/2) + (π(u), 0n/2) =
(6)
= (u, 0n/2) + Π((u, 0n/2)),
где (u, 0n/2) ∈ RMr,m.
Если последняя координата вектора u равна 1, то первая координата вектора π(u)
кода π(RMr,m-1) равна 1. В этом случае воспользуемся антиподальностью кода
π(RMr,m-1), согласно которой вектор π(u) + 1n/2 принадлежит коду π(RMr,m-1),
и следовательно, (u, 1n/2) ∈ RMr,m. Отсюда
(y, 0n/2) = (u + π(u), 1n/2 + π(1n/2)) = (u, 1n/2) + (π(u), π(1n/2)) =
= (u, 1n/2) + Π((u, 1n/2)).
(7)
Случай 3. Пусть x = 0n/2, где x ∈ RMr,m-1 и y = 0n/2, y ∈ RMr-1,m-1. По
предположению индукции для кодовых слов x и y найдутся два вектора u и v,
соответственно, удовлетворяющих x = u + π(u) и y = v + π(v). Отсюда
(x + y, x) = (u + π(u) + v + π(v), u + π(u)) =
= [(u, u) + (π(u), π(u))] + [(v, 0n/2) + (π(v), 0n/2)].
Таким образом здесь, как и в случае 1, для вектора (x, x) справедливо (5). Для
вектора (y, 0n/2) аналогично случаю 2 имеем (6) при vn/2 = 0, а при vn/2 = 1
справедливо (7). Отсюда при vn/2 = 0 вытекает требуемое, а именно:
(x + y, x) = (u + v, u) + Π((u + v, u)).
68
При vn/2 = 1 с учетом антиподальности кода Рида - Маллера RMr,m-1 имеем
(x + y, x) = (u, u) + Π((u, u)) + (y, 0n/2) =
= (u, u) + Π((u, u)) + (v, 1n/2) + Π((v, 1n/2)) =
= (u + v, u + 1n/2) + Π((u + v, u + 1n/2)).
▴
Пусть RMr-1,m-1 = P0 ∪ P1, где P0 и P1 - подкоды кода RMr-1,m-1 с одина-
ковыми и различными первыми двумя координатными позициями соответственно.
Пусть ν - транспозиция первых двух координатных позиций векторов из Fn/2. Тогда
ν(RMr-1,m-1) = P0 ∪ ν(P1),
так как ν(P0) = P0.
Рассмотрим вектор
z = (1,0,1,0,...,1,0)
(8)
длины n/2 с чередующимися координатами, равными 1 и 0. Этот вектор принад-
лежит коду Адамара RM1,m-1, заданному порождающей матрицей, столбцы кото-
рой представлены в лексикографическом порядке, и следовательно, принадлежит
любому коду Рида - Маллера ненулевого порядка, содержащему этот код Адамара.
В частности, z ∈ RMr-1,m-1, и следовательно, вектор z может быть взят в качестве
представителя класса смежности P1 по подкоду P0, т.е. P1 = z + P0. Значит, вектор
ν(z) = (0, 1, 1, 0, . . . , 1, 0) ∈ ν(P1)
(9)
может быть взят в качестве представителя класса смежности ν(P1) по подкоду P0,
т.е. ν(P1) = ν(z) + P0.
Лемма 3. Пусть y и y′ - произвольные кодовые слова кодов P0 и ν(P1) либо
P1 и ν(P1) соответственно. Тогда существуют ровно два различных вектора u и
u = u + 1n/2, удовлетворяющих y + y′ = u + π(u) и y + y′ = u + π(u). Более того,
оба вектора u и u имеют нечетный вес.
Доказательство. Случай 1. Пусть y ∈ P0 и y′ ∈ ν(P1). Поскольку 0n/2 ∈ P0,
достаточно рассмотреть доказательство для ν(z) = (0, 1, 1, 0, . . . , 1, 0) - представите-
ля класса смежности ν(P1), поскольку для P0 справедлива лемма 2. Решая систему
линейных уравнений ν(zi) = ui + ui+1, i = 1, 2, . . . , n/2, полагая u1 = 0, однозначно
находим u = (u1, . . . , un/2) и π(u):
u = (0,1,0,0,1,1,...,1,1,0,0), π(u) = (0,0,1,0,0,1,1,...,1,1,0),
где u и π(u) - векторы нечетного веса. Аналогично ищем u, полагая в этом случае
u1 = 1:
u = (1,0,1,1,0,0,...,1,1), π(u) = (1,1,0,1,1,0,...,0,1),
где u и π(u) - векторы нечетного веса.
Случай 2. Рассмотрим y ∈ P1 и y′ ∈ ν(P1). Векторы y ∈ P1 и y′ ∈ ν(P1) предста-
вимы в виде y = y+ z и y′ = y′′ + ν(z) соответственно, где z и ν(z) определены выше
в (8) и (9). Здесь y, y′′ ∈ P0. Тогда
y + y′ = y+ y′′ + ν(z) + z,
где y+y′′ ∈ P0. Отсюда с учетом случая 1 данной леммы имеем y+y′′+ν(z) = u+π(u),
где u - вектор нечетного веса. В силу того, что вектор z ∈ P1 ⊂ RM1,m-1, по лемме 2
69
справедливо z = u′ + π(u′), где u′ ∈ RM2,m-1, в частности, u′ имеет четный вес.
Следовательно, для y + y′ верно требуемое. ▴
Определим коды Dλ(RMr-1,m-1) и Dλ′(ν(RMr-1,m-1)) длины n, используя кон-
струкцию Пулатова для расширенных кодов типа Рида - Маллера.
Первый код имеет вид
Dλ(RMr-1,m-1) = D0 ∪ D1,
⋃
D0 =
{(x + y, x) : x ∈ RMr,m-1, y ∈ RMr-1,m-1},
y∈RMr-1,m-1, λ(y)=0
⋃
D1 =
{(x + y + ei, x + ei) : x ∈ RMr,m-1, y ∈ RMr-1,m-1},
y∈RMr-1,m-1, λ(y)=1
где λ - произвольная функция, действующая из множества кодовых слов кода
RMr-1,m-1 в множество {0, 1}, а i - произвольный элемент множества {1, 2, . . ., n/2}.
Код Dλ′(ν(RMr-1,m-1)) = D′0 ∪ D′1 определим, используя подстановки π, ν и
произвольную функцию λ′, действующую из кода ν(RMr-1,m-1) в множество {0, 1}:
⋃
D′0 =
{(x + y, π(x)) : x ∈ RMr,m-1, y ∈ ν(RMr-1,m-1)},
y∈ν(RMr-1,m-1),
λ′(y)=0
⋃
D′1 =
{(x + y + ei, π(x + ei)) : x ∈ RMr,m-1, y ∈ ν(RMr-1,m-1)},
y∈ν(RMr-1,m-1),
λ′(y)=1
здесь i - то же самое число, что и для кода Dλ(RMr-1,m-1).
Используя отображение ϕ, свойства которого описаны в лемме 1, и подстановку ν,
введем следующие обозначения:
N0 = |RMr-1,m-1 ∩ ϕ(RMr,m-1)|, N1 = |RMr-1,m-1 ∩ ϕ(Fn/21)|,
M0 = |ν(RMr-1,m-1) ∩ ϕ(RMr,m-1)|, M1 = |ν(RMr-1,m-1) ∩ ϕ(Fn/21)|.
Кроме того, далее нам потребуются связанные с сужениями функций λ и λ′ на
введенные подкоды кодов RMr-1,m-1 и ν(RMr-1,m-1) следующие числа:
{
}
μ0 =
y ∈ RMr-1,m-1 ∩ ϕ(RMr,m-1) : λ(y) = 0
,
{
}
μ1 =
y ∈ RMr-1,m-1 ∩ ϕ(Fn/21) : λ(y) = 0
,
{
}
γ0 =
y ∈ ν(RMr-1,m-1) ∩ ϕ(RMr,m-1) : λ′(y) = 0
,
{
}
γ1 =
y ∈ ν(RMr-1,m-1) ∩ ϕ(Fn/21) : λ′(y) = 0
.
Лемма 4. Число векторов, лежащих в пересечении кодов Dλ(RMr-1,m-1) и
Dλ′(ν(RMr-1,m-1)), равно
(
)
2
μ0γ0 + μ1γ1 + (N0 - μ0)(M1 - γ1) + (N1 - μ1)(M0 - γ0)
,
где m ≥ 4.
Доказательство. Рассмотрим произвольные кодовые слова этих кодов. В си-
лу определения обоих кодов для совпадения этих кодовых слов имеются только
следующие две возможности. Если (x + y, x) ∈ Dλ(RMr-1,m-1) и (x′ + y′, π(x′)) ∈
∈ Dλ′(ν(RMr-1,m-1)), где x, x′ - векторы четного веса, то
(x + y, x) = (x′ + y′, π(x′)).
(10)
70
Если (x+y+ei, x+ei) ∈ Dλ(RMr-1,m-1) и (x′+y′+ei, π(x′+ei)) ∈ Dλ′ (ν(RMr-1,m-1)),
где векторы x + ei, x′ + ei имеют нечетный вес, то справедливо
(x + y + ei, x + ei) = (x′ + y′ + ei, π(x′ + ei)),
(11)
где x, x′ ∈ RMr,m-1, y ∈ RMr-1,m-1 и y′ ∈ ν(RMr-1,m-1). В первом случае имеем
λ(y) = λ′(y′) = 0, во втором случае λ(y) = λ′(y′) = 1.
Рассмотрим первый случай. В этой ситуации имеем x = π(x′), и значит,
y + y′ = x + x′ = x′ + π(x′) = ϕ(x′).
Следовательно, равенство (10) эквивалентно системе линейных уравнений
{x = x′ + y + y′,
(12)
ϕ(x′) = y + y′.
Возможны следующие подслучаи.
а) Пусть y, y′ ∈ P0 либо y ∈ P1, а y′ ∈ P0, где множества P0 и P1 определены
выше, RMr-1,m-1 = P0 ∪ P1. Тогда в обоих ситуациях имеем y + y′ ∈ RMr-1,m-1,
и по лемме 2 для вектора y + y′ ∈ P0 существуют два кодовых слова кода RMr,m-1,
удовлетворяющих второму уравнению в (12), т.е. ϕ(x′) = y + y′. Следовательно,
система уравнений (12) имеет ровно два различных решения относительно x, x′ при
фиксированном кодовом слове y + y′ из RMr-1,m-1.
б) Пусть y ∈ P0, y′ ∈ ν(P1) либо y ∈ P1, а y′ ∈ ν(P1), где подстановка ν опре-
делена выше (является транспозицией первых двух координат кодовых слов кода
RMr-1,m-1), ν(RMr-1,m-1) = P0 ∪ ν(P1). Тогда по лемме 3 для фиксированного
вектора y + y′ найдутся ровно два решения u, таких что ϕ(u) = y + y′, причем оба
вектора имеют нечетный вес. Но поскольку y + y′ = x + x′, где x + x′ ∈ RMr,m-1,
и в частности, этот вектор имеет четный вес, то система уравнений (12) не имеет
решений относительно x, x′ ∈ RMr,m-1.
Во втором случае, т.е. при λ(y) = λ′(y′) = 1, имеем x + ei = π(x′ + ei), следова-
тельно,
y + y′ = x + x′ = x′ + ei + x + ei = x′ + ei + π(x′ + ei) = ϕ(x′ + ei).
С учетом этого равенство (11) эквивалентно системе линейных уравнений
{x = x′ + y + y′,
(13)
ϕ(x′ + ei) = y + y′.
Аналогично рассуждениям, проведенным в первом случае, имеется два различных
решения системы (13) относительно x + ei, x′ + ei в случае y + y′ ∈ ν(P1) и нет
решений в противном случае. ▴
Лемма 5. Для кодов Dλ(RMr-1,m-1) и Dλ′(ν(RMr-1,m-1)), m ≥ 4, справедливо
1
N0 = |RMr-1,m-1|, N1 = 0, M0 = M1 =
|RMr-1,m-1|.
2
Доказательство. Из леммы 2 вытекает, что RMr-1,m-1 ⊂ ϕ(RMr,m-1), зна-
чит, N0 = |RMr-1,m-1|, и как следствие, получаем N1 = 0.
1
Докажем, что M0 = M1 =
|RMr-1,m-1|. С этой целью рассмотрим векторы u =
2
= (0, 1, 0, 0, 1, 1, . . . , 1, 1, 0, 0) и π(u) = (0, 0, 1, 0, 0, 1, 1, . . . , 1, 1, 0), полученные в дока-
зательстве леммы 3, а также их сумму ϕ(u) = u + π(u) = (0, 1, 1, 0, . . ., 1, 0). Вектор
u+π(u) равен вектору ν(z) из леммы 3, т.е. представителю класса смежности ν(P1),
поскольку ν-1(u + π(u)) = (1, 0, 1, 0, . . . , 1, 0) = z ∈ RM1,m-1 ⊂ RMr-1,m-1 для
71
любого 1 < r ≤ m - 1. Так как вектор u имеет нечетный вес, то по лемме 3 выполня-
ется ν(RMr-1,m-1) ∩ ϕ(Fn/21) = ν(P1). Отсюда M1 =1|ν(RMr-1,m-1)|, и поскольку
2
1
|ν(RMr-1,m-1)| = |RMr-1,m-1|, то M0 = M1 =
|RMr-1,m-1|. ▴
2
Теорема 2. Для любого четного k в интервале
∑
2
(m-1i)
0≤k≤2i=0
существуют два кода типа Рида - Маллера порядка r длины 2m, m ≥ 4, пересечение
которых равно k.
Доказательство. Для кодов типа Рида-Маллера C = Dλ(RMr-1,m-1) и
C′ = Dλ′(ν(RMr-1,m-1)), имеющих порядок r и длину n = 2m, из лемм 4 и 5 полу-
чаем следующую формулу для числа их пересечения η:
(
))
(1
η(C, C′) = 2 μ0γ0 + (|RMr-1,m-1| - μ0)
|RMr-1,m-1| - γ1
2
Варьируя значения функций λ и λ′ произвольным образом, т.е. выбирая числа μ0, γi
произвольным образом в пределах
1
0 ≤ μ0 ≤ |RMr-1,m-1|,
0≤γi ≤
|ν(RMr-1,m-1|, i = 1, 2,
2
с учетом |ν(RMr-1,m-1)| = |RMr-1,m-1| получаем требуемое. ▴
Полагая код C′ равным Dλ′(RMr-1,m-1) и оставляя код C = Dλ(RMr-1,m-1) без
изменения, согласно лемме 5 имеем
N0 = M0 = |RMr-1,m-1|, N1 = M1 = 0,
т.е. в этом случае выполняется μ1 = γ1 = 0. Отсюда и из леммы 4 вытекает
Теорема 3. Для любых чисел k1 и k2, удовлетворяющих условиям
∑
(m-1i)
1≤ks ≤2i=0
,
s ∈ {1,2},
существуют два кода типа Рида - Маллера порядка r длины 2m, m ≥ 4, пересечение
которых равно 2k1k2.
Нетрудно убедиться в том, что множества чисел пересечений кодов типа Рида -
Маллера порядка r длины 2m, полученных в теоремах 2 и 3, не покрывают друг
друга.
Автор выражает свою признательность И.Ю. Могильных за плодотворные дис-
куссии и рецензенту за ряд полезных замечаний, позволивших улучшить изложение
настоящей статьи.
СПИСОК ЛИТЕРАТУРЫ
1. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.:
Связь, 1979.
2. Liu C.L., Ong B.G., Ruth G.R. A Construction Scheme for Linear and Non-linear Codes //
90080-0
3. Пулатов А.К. Нижняя оценка сложности схемной реализации для одного класса ко-
дов // Дискретный анализ. Вып. 25. Новосибирск: Ин-т матем. СО АН СССР, 1974.
С. 56-61.
72
4.
Соловьева Ф.И. О двоичных негрупповых кодах // Методы дискретного анализа в изу-
чении булевых функций и графов. Вып. 37. Новосибирск: Ин-т матем. СО АН СССР,
1981. С. 65-76.
5.
Соловьева Ф.И. О Z4-линейных кодах с параметрами кодов Рида - Маллера // Пробл.
6.
Pujol J., Rifà J., Solov’eva F.I. Construction of Z4-Linear Reed-Muller Codes // IEEE
2008143
7.
Solov’eva F.I. Minimum Weight Bases for Quaternary Reed-Muller Codes // Сиб. элек-
18.103
8.
Etzion T., Vardy A. Perfect Binary Codes: Constructions, Properties and Enumeration //
335887
9.
Соловьева Ф.И. Обзор по совершенным кодам // Математические вопросы кибернети-
ки. Вып. 18. М.: Физматлит, 2013. С. 5-34.
10.
Etzion T., Vardy A. On Perfect Codes and Tilings: Problems and Solutions // SIAM J. Dis-
11.
Bar-Yahalom E., Etzion T. Intersection of Isomorphic Linear Codes // J. Combin. Theory.
12.
Avgustinovich S.V., Heden O., Solov’eva F.I. On Intersections of Perfect Binary Codes //
Bayreuth. Math. Schr. 2005. № 71. P. 1-6.
13.
Avgustinovich S.V., Heden O., Solov’eva F.I. On Intersection Problem for Perfect Binary
s10623-005-4982-8
14.
Phelps K.T., Villanueva M. Intersection of Hadamard Codes // IEEE Trans. Inform. Theory.
15.
Rifá J., Solov’eva F.I., Villanueva M. On the Intersection of Z2Z4-Additive Perfect Codes //
TIT.2007.915917
16.
Rifá J., Solov’eva F.I., Villanueva M. On the Intersection of Z2Z4-Additive Hadamard
Codes // IEEE Trans. Inform. Theory. 2009. V. 55. № 4. P. 1766-1774. https://doi.org/
10.1109/TIT.2009.2013037
17.
Васильев Ю.Л. О негрупповых плотно упакованных кодах // Проблемы кибернетики.
Т. 8. М.: Физматлит, 1962. С. 337-339.
18.
Solov’eva F.I. Switchings and Perfect Codes // Numbers, Information and Complexity.
Соловьева Фаина Ивановна
Поступила в редакцию
Институт математики им. С.Л. Соболева
25.06.2021
СО РАН, Новосибирск
После доработки
sol@math.nsc.ru
10.11.2021
Принята к публикации
10.11.2021
73
