ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ
Том 58
2022
Вып. 1
УДК 621.391.1 : 519.725
© 2022 г.
Л.А. Бассалыго, В.А. Зиновьев, В.С. Лебедев
СЛАБО РАЗРЕШИМЫЕ БЛОК-СХЕМЫ И НЕДВОИЧНЫЕ КОДЫ,
ЛЕЖАЩИЕ НА ГРАНИЦЕ ДЖОНСОНА1
Указаны два новых семейства разрешимых блок-схем. Дано определение сла-
бо разрешимой блок-схемы и доказана эквивалентность такой схемы и недвоич-
ных кодов, лежащих на границе Джонсона. Построено новое семейство таких
кодов.
Ключевые слова: разрешимая блок-схема, слабо разрешимая блок-схема, недво-
ичный код, граница Джонсона.
DOI: 10.31857/S0555292322010016
1. Блок-схемой B(v, k, λ) называется такое размещение v различных элементов
a1, . . . , av по b блокам B1, . . ., Bb, при котором каждый блок содержит ровно k раз-
личных элементов, каждый элемент принадлежит ровно r блокам, и каждая пара
различных элементов ai, aj , i = j, принадлежит ровно λ блокам. Параметры v, k, λ
блок-схемы однозначно определяют параметры b и r (см. [1]):
λv(v - 1)
λ(v - 1)
b=
,
r=
k(k - 1)
k-1
Блок-схема полностью описывается своей матрицей инцидентности A = [aij ], где
{1, если ai ∈ Bj,
aij =
0, если ai ∈ Bj,
i = 1,...,v, j = 1,...,b.
Блок-схема B(v, k, λ) называется разрешимой и обозначается через RB(v, k, λ),
если ее матрица инцидентности может быть приведена перестановкой строк (что
соответствует перенумерации элементов блок-схемы) и столбцов (что соответствует
перенумерации блоков) к следующему виду:
A = [A1 |A2 |...|Ar],
(1)
v
где каждая подматрица Aj размера v ×
состоит из строк веса 1. Построение новых
k
разрешимых блок-схем зиждется на следующем результате из [2].
Теорема 1. Существование RB(v,k,λ)-схемы эквивалентно существованию
q-ичного эквидистантного кода мощности N длины n с расстоянием d, лежащего
1 Работа выполнена в ИППИ РАН при финансовой поддержке Российского фонда фундамен-
тальных исследований (номер проекта 19-01-00364) и Национального научного фонда Болгарии
(номер гранта 20-51-18002).
3
на границе Плоткина
qd
N ≤
,
qd - (q - 1)n
где
v
λ(v - 1)
λ(v - k)
q=
,
N =v, n=r=
,
d=r-λ=
k
k-1
k-1
Доказательство этой теоремы в [2] использует естественное преобразование мат-
рицы инцидентности схемы в q-ичный код и столь же естественное обратное пре-
образование. Поэтому построение новых разрешимых схем эквивалентно построе-
нию новых q-ичных кодов, лежащих на границе Плоткина. Здесь мы предложим
процедуру построения нового класса таких четверичных кодов из B(v, k, λ)-схем,
являющуюся обобщением процедуры из работы [3].
Утверждение 1. Любая блок-схема B(v,k,λ) порождает четверичный рав-
новесный эквидистантный код с параметрами
)
(b
r(b - 2)(b - r)
N =v, n=
,
w=
,
d = (b - 2)(r - λ)(b - 2(r - λ)).
(2)
3
2
Доказательство. Построение кода весьма просто: выбираются любые три
(b)
столбца матрицы инцидентности блок-схемы (таковых
) и заменяются на один
3
столбец q-ичного кода по следующему правилу:
(0, 0, 0), (1, 1, 1) → 0,
(0, 0, 1), (1, 1, 0) → 1,
(0, 1, 0), (1, 0, 1) → 2,
(1, 0, 0), (0, 1, 1) → 3,
так что в результате получаем четверичный код. Очевидно, что построенный код
(b)
имеет дину n =
и число слов N = v. Нетрудно проверить, что расстояние
3
между любыми двумя кодовыми словами равно
(b - 2(r - λ))(2(r - λ))
(b - 2(r - λ))(2(r - λ))
+
=
2
1
1
2
= (b - 2)(r - λ)(b - 2(r - λ),
а вес кодовых слов равен
(b)
(r)
(b - r)
r(b - 2)(b - r)
-
-
=
▴
3
3
3
2
Если в качестве схемы B(v, k, λ) выбрать симметричную (т.е. такую, в которой
b = v и r = k) схему B(4t - 1,2t,t) (полученную из (0,1)-матрицы Адамара с ну-
левой строкой и нулевым столбцом выкидыванием этой строки и этого столбца), то
получим четверичный код с параметрами
(4t - 1)(2t - 1)(4t - 3)
N = 4t - 1, n =
,
w = d = t(2t - 1)(4t - 3).
(3)
3
Присоединив к коду нулевое слово, получим эквидистантный код, лежащий на
границе Плоткина:
4t(2t - 1)(4t - 3)
4t =
4t(2t - 1)(4t - 3) - (4t - 1)(2t - 1)(4t - 3)
4
В [3], а еще ранее в [4] с помощью выбора любых двух столбцов матрицы инци-
дентности из схемы B(4t - 1, 2t, t) был построен другой четверичный код, лежащий
на границе Плоткина, с параметрами
N = 4t, n = (4t - 1)(2t - 1), d = 3t(2t - 1).
Воспользовавшись теоремой 1 из [2], получаем следующее
Утверждение 2. Любая блок-схема B(4t-1,2t,t) порождает две разрешимые
блок-схемы:
RB(4t, t, (t - 1)(2t - 1)) и RB(4t, t, (t - 1)(2t - 1)(4t - 3)/3).
Замечание 1. Казалось естественным продолжить такую конструкцию, выбирая
любые четыре (или даже больше) столбца матрицы инцидентности симметричной
схемы B(4t - 1, 2t, t), но уже выбор четырех столбцов не привел к кодам, лежащим
на границе Плоткина, а следовательно, и к новым разрешимым схемам.
2. Теорема 1 указывает на взаимосвязь разрешимой схемы и недвоичных кодов,
лежащих на границе Плоткина. Теперь мы хотим слегка обобщить понятие разре-
шимой схемы, чтобы установить аналогичную взаимосвязь между этим обобщением
и недвоичными равновесными кодами, лежащими на границе Джонсона [5]
(q - 1)dn
N ≤
,
(4)
qw2 - (q - 1)(2w - d)n
где N - мощность кода, n - его длина, d - кодовое расстояние, w - вес кодового
слова.
Предлагаемое обобщение отличается от разрешимой схемы RB(v, k, λ) только
в одном: в разрешимой схеме каждый столбец подматриц Aj , j = 1, 2, . . . , r, содер-
жит ровно k единиц, а в слабо разрешимой WRBm(v, k, λ)-схеме один столбец под-
матрицы Aj , j = 1, 2, . . . , r, содержит m единиц, m ≥ 1. Очевидно, что при m = k
слабо разрешимая схема превращается в разрешимую. В слабо разрешимой схеме
v-m+k
каждая подматрица Aj , j = 1, 2, . . . , r, имеет размер v ×
, а параметр r
k
(число блоков, которым принадлежит каждый элемент, что для разрешимых схем
совпадает с числом подматриц Aj или, что то же самое, с весом каждой строки
матрицы A) определяется следующим соотношением:
)
(v
((m)
v-m
(k))
λ
=r
+
(5)
2
2
k
2
Это соотношение доказывается стандартным образом: скалярное произведение лю-
бых д(х)различных строк матрицы A по определению равно λ, а число пар строк
v
равно
. С другой стороны, сумма скалярных произведений попарных строк в лю-
2
бой подматрице Aj равна
(m)
v-m
(k)
+
,
2
k
2
а число матриц Aj равно r. Следовательно,
(v)
λ
2
r=
(6)
(m)
v-m
(k).
+
2
k
2
Теперь мы уже можем сформулировать аналог теоремы 1.
5
Теорема 2. Существование слабо разрешимой WRBm(v,k,λ)-схемы эквива-
лентно существованию q-ичного эквидистантного кода мощности N длины n
с расстоянием d, лежащего на границе Джонсона (4), где параметры схемы и кода
связаны следующими равенствами:
v-m+k
λv(v - 1)
q=
,
n=r=
,
k
m(m - 1) + (v - m)(k - 1)
(7)
r(v - m)
N = v, d = r - λ, w =
v
Доказательство. Доказательство теоремы очевидно. Без ограничения общ-
ности можно считать, что в каждой подматрице Aj столбец с m единицами стоит на
первом месте. Установим следующее взаимно-однозначное соответствие между стро-
ками подматриц (их длина равна (v-m+k)/k) и символами алфавита 0, 1, . . . , q-1 =
= (v-m)/k: строке (1, 0, . . . , 0) поставим в соответствие 0, а строке с единицей на i-м
месте - символ i - 1, где i > 1. При таком соответствии каждый ненулевой символ
встретится в столбце кода k раз, а нуль - m раз (такой код мы назвали посимвольно
равномерным [3]). Очевидно, что полученный код эквидистантен и d = r-λ. Соглас-
но [3, утверждение 1] код лежит на границе Джонсона тогда и только тогда, когда
он посимвольно равномерен и эквидистантен, а при m = k он к тому же равновесен
(см. [3, утверждение 2]). Это же соответствие переводит каждый столбец q-ичного
кода в подматрицу слабо разрешимой WRBm(v, k, λ)-схемы. ▴
Следствие. Так как четверичный код с параметрами (3) лежит на границе
Джонсона, то существует слабо разрешимая WRBt-1(4t - 1, t, (t - 1)(2t - 1) ×
× (4t - 3)/3)-схема. Параметры схемы легко вычисляются по параметрам кода:
N (n - w)
Nw
v = N, λ = n - d, m =
,
k=
n
n(q - 1)
Замечание 2. Теорема 1 является частным случаем теоремы 2 при m = k. Надо
r(v - m)
только помнить, что при m = k код не является равновесным, а величина
v
является средним весом w кодовых слов, при котором также верна граница Джон-
сона (см. [3]).
Замечание 3. Введенная в [6] m-квазиразрешимая NRBm(v, k, λ)-схема эквива-
лентна слабо разрешимой WRBm(v, k, λ′)-схеме, столбцы которой с m единицами
образуют B(v, m, ξ)-схему, где
λm(m - 1)
ξ=
(v - m)(k - 1)
Эквивалентность здесь такова: квазиразрешимая схема получается из слабо разре-
шимой удалением из каждой матрицы Aj (см. (1)) столбца с m единицами, а слабо
разрешимая из квазиразрешимой - вставкой в каждую матрицу Aj столбца с m еди-
ницами на позициях, соответствующих нулевым строкам матрицы Aj. При этом,
очевидно, λ′ = λ + ξ.
3. Рассмотрим теперь другой частный случай слабо разрешимой схемы: k = 2,
λ = 1. Так как вес кодовых слов (см. (7)) является целым числом
2
n(N - m)
r(v - m)
m(m - 1)
w=
=
=r-m+
,
N
v
v + m(m - 2)
6
то целочисленной является дробь
m(m - 1)2
(8)
v + m(m - 2)
Таким образом, целочисленность дроби (8) является необходимым условием для
существования слабо разрешимой WRBm(v, 2, 1)-схемы, и следовательно, для суще-
ствования кода, лежащего на границе Джонсона, параметры которого определены
в теореме 2. Впрочем, иногда это необходимое условие является и достаточным,
примеры чему будут приведены ниже.
Нетрудно проверить, что если мы ищем знаменатель дроби (8) в виде произве-
дения сомножителей ее числителя, то единственным таким решением (при m ≥ 3)
является
v = m(m - 1)2 - m(m - 2) = m(m2 - 3m + 3) = (m - 1)3 + 1.
(9)
Конечно, существует много других значений параметра v, при которых дробь (8)
является целым числом. Мы приведем только два таких примера - по одному для
нечетного и четного m:
{2m(m - 1) - m(m - 2) = m2,
m - нечетное,
v=
(10)
2(m - 1)2 - m(m - 2) = m2 - 2m + 2, m - четное.
Выпишем для всех трех случаев допустимые значения параметров кодов, лежащих
на границе Джонсона:
(I) N = m(m2 - 3m + 3), n = (m - 1)(m2 - 3m + 3), d = n - 1, w = n - m + 1,
N -m
q=
+ 1;
2
N -1
N -m
(II) N = m2, n =m(m+1), d = n - 1, w =
, q=
+ 1, m - нечетное;
2
2
2
N-m
N-m
(III) N = m2 - 2m + 2, n =m2 -2m+2, d = n - 1, w =
, q =
+ 1,
2
2
2
m - четное.
Во всех трех случаях удалось для некоторых значений m построить коды с та-
кими параметрами.
4. Начнем со случая (II), для которого удалось построить семейства кодов с ука-
занными параметрами.
Предложение 1. Для любого нечетного простого m существует код со зна-
чениями параметров (II).
Доказательство. Представим код C в виде матрицы размера m2× m(m+ 1):
2
⎡
⎤
B1
A1,1
... A1,(m-1)/2
⎢B2
A2,1
... A2,(m-1)/2
⎥
C =
⎣
⎦,
Bm Am,1 . . . Am,(m-1)/2
где каждая из матриц Br, r = 1, . . . , m, и Ar,s, r = 1, . . . , m, s = 1, . . . , (m - 1)/2,
является циркулянтной (по модулю m) матрицей размера m × m (строки и столб-
цы любой квадратной матрицы размера p × p всюду далее будем нумеровать от 0
до p-1). Следовательно, каждая из этих матриц определяется своей первой строкой.
Сначала зададим первые строки матриц Br:
b0,0(r) = 0, b0,t(r) = (r - 1)(m - 1)/2 + min{t, m - t}, t = 1, 2, . . ., m - 1.
(11)
7
Для пояснения приведем простой пример при m = 7, а именно выпишем первые
строки матриц B1, B2 и B7 (q = 22, символы алфавита обозначаем числами от 0
до 21):
(0 1 2 3 3 2 1),
(0 4 5 6 6 5 4),
(0 19 20 21 21 20 19).
m-1
Так как в каждой первой строке матриц Br используется
различных нену-
2
левых символов, в двух разных строках используются различные ненулевые сим-
волы алфавита, а число первых строк равно m, то мощности алфавита, равной
m(m - 1)/2 + 1, достаточно для первых строк всех матриц. Нетрудно видеть, что
расстояние между словами матрицы Br равно m - 1 при любом r, r = 1, 2, . . ., m.
Обозначим через PB матрицу первых строк матриц Br, r = 1, . . ., m.
Далее требуется построить первые строки матриц Ar,s, r = 1, . . ., m, s = 1, . . .,
(m - 1)/2. Обозначим через Ps, s = 1, . . . , (m - 1)/2, матрицу, образованную первы-
ми строками матриц Ar,s, r = 1, . . . , m, и укажем способ ее построения (координаты
в матрице на пересечении i-й строки и ℓ-го столбца будем обозначать через (i, ℓ)).
Сначала определим расположение нулей в матрице Ps: в каждой строке и каждом
столбце матрицы встретится ровно один 0 в позиции (i, is mod m), i = 0, 1, . . . , m-1,
(m)
(напомним, что m - простое число и s ≤ (m-1)/2). Всего в матрице Ps имеется
2
пар нулей. Каждая такая пара нулей с координатами (i, is mod m) и (j, js mod m)
определяет координаты (i, js mod m) и (j, is mod m), i = j, и на этих позициях рас-
полагается некоторый ненулевой символ, причем различным парам нулей соответ-
ствуют различные ненулевые символы (это возможно, так как число ненулевых сим-
волов алфавита и число пар нулей одно и то же: m(m - 1)/2).
Приведем в качестве примера такого построения матрицы P1 и P2 при m = 5:
⎡
⎤
⎡
⎤
0
1
2
3
4
0
3
1
4
2
⎢1
0
5
6
7
⎥
⎢1
6
0
7
5⎥
⎢
⎥
⎢
⎥
P1 =
⎢2
5
0
8
9
⎥,
P2 =
⎢2
8
5
9
0⎥
⎣
⎦
⎣
⎦
3
6
7
0
10
3
0
6
10
8
4
8
9
10
0
4
10
7
0
9
Так как все символы в первой строке матриц Ar,s, r = 1, . . . , m, s = 1, . . . , (m - 1)/2,
различны, а сами матрицы циркулянтны, то расстояние между строками каждой
матрицы равно m, и следовательно, расстояние между кодовыми словами внутри
r-го слоя кода C равно n - 1. Осталось доказать, что расстояние между любыми
двумя кодовыми словами матрицы C из разных слоев равно n - 1. Определим сле-
дующую матрицу P (C) размера m × m(m + 1)/2:
P (C) = [PB | P1 | . . . | Ps| . . . | P(m-1)/2].
Нетрудно видеть, что расстояние между кодовыми словами матрицы C из раз-
ных слоев в силу циркулянтности матриц Br и Ar,s совпадает с расстоянием меж-
ду некоторыми фиксированными сдвигами соответствующих строк матрицы P(C).
Естественно, эти сдвиги определяются выбранными кодовыми словами, а сами сдви-
ги (по модулю m) происходят в каждой из матриц PB, Ps, s = 1, . . . , (m-1)/2, разме-
ра m × m. Опять же в силу циркулянтности матриц Br и Ar,s можно зафиксировать
одну строку матрицы P (C) и сдвигать лишь другую. Отметим прежде всего, что по
построению в любых двух строках каждой матрицы Ps, s = 1, . . . , (m-1)/2, имеется
ровно два одинаковых символа алфавита: один нулевой, а другой ненулевой, причем
никакой сдвиг одной строки матрицы Ps, s = 1, . . . , (m - 1)/2, относительно другой
не может привести к совпадению этих двух символов на соответствующих позициях
этих двух строк.
8
Зафиксируем теперь две строки матрицы P (C) с номерами i и j и рассмот-
рим эти строки в матрицах Ps и Ps′, s = s′. По построению нули в этих стро-
ках находятся в позициях (i, si mod m) и (j, sj mod m) в матрице Ps и в позициях
(i, s′i mod m) и (j, s′j mod m) в матрице Ps′ , а позиции одинаковых ненулевых сим-
волов - (i, sj mod m) и (j, si mod m) в матрице Ps и (i, s′j mod m) и (j, s′i mod m)
в матрице Ps′ .
Чтобы при сдвиге j-й строки совпали позиции нулей в обеих матрицах, должно
выполняться следующее условие:
(i - j)s ≡ (i - j)s′ (mod m),
т.е.
(i - j)(s - s′) ≡ 0 (mod m),
что невозможно, так как m - простое число, а i = j и s = s′. Напомним, что
i < m, j < m, s ≤ (m - 1)/2, s′ ≤ (m - 1)/2.
Чтобы при сдвиге j-й строки совпали позиции нулей в одной матрице (например,
в Ps) и позиции одинаковых ненулевых символов в другой матрице, должно выпол-
няться следующее условие:
(i - j)s ≡ (j - i)s′ (mod m),
т.е.
(i - j)(s + s′) ≡ 0 (mod m),
что невозможно, так как m - простое число, а i = j и s + s′ ≤ (m - 1). Совпадение
при сдвиге j-й строки позиций одинаковых ненулевых символов в одной матрице
и одинаковых ненулевых символов в другой матрице невозможно по той же причине,
что и совпадение двух нулевых символов.
Так как число различных матриц Ps равно (m - 1)/2, в каждой матрице Ps всего
для двух сдвигов j-й строки относительно i-й происходит совпадение символов в i-й
и j-й строках (одного нулевого и одного ненулевого), а число различных ненулевых
сдвигов j-й строки относительно i-й равно m - 1, то при каждом сдвиге происходит
совпадение символов этих двух строк ровно в одной позиции. При нулевом сдвиге,
т.е. при отсутствии сдвига, совпадают нулевые символы в i-й и j-й строках матри-
цы PB . Следовательно, расстояние между любыми кодовыми словами матрицы C
равно n - 1. ▴.
Приведенное доказательство не применимо к случаю, когда m - не простое число.
Однако в теории кодирования редко бывает, чтобы некоторое утверждение было
верным только для простого поля, а не любого конечного поля (в нашем случае
для m, являющегося степенью простого). И действительно, справедливо
Предложение 2. Для любого нечетного m, являющегося степенью простого
числа, существует код со значениями параметров (II).
Доказательство. Известно [7], что для любого m, являющегося степенью
простого, существует МДР-код с параметрами
N′ = m2, n′ = m + 1, d′ = m, q = m.
(12)
Так как размерность этого МДР-кода равна 2, то любые две позиции кода явля-
ются информационными, т.е. любые два столбца кода содержат каждую пару сим-
волов алфавита ровно один раз (символы алфавита обозначим через 0, 1, . . ., m-1).
Обратимся теперь к матрицам Br, введенным в предложении 1 (заметим, что их
9
определение не зависит от простоты числа m). Это циркулянтные матрицы, первая
строка которых определяется равенствами (11). Обозначим j-ю строку матрицы Br
через bj(r) и зададим отображение
f (j, r) = bj (r),
переводящее каждую пару символов МДР-кода (j, r), j = 0, 1, . . . , m - 1, r = 0, 1, . . . ,
m-1, в j-ю строку bj(r) длины m матрицы Br. Разобьем теперь столбцы МДР-кода
на пары и, используя отображение f(j, r), поставим в соответствие каждой паре
столбцов матрицу размера m2 × m. В результате получим матрицу кода с парамет-
рами (II). Действительно, число кодовых слов равно числу кодовых слов МДР-кода,
т.е. N = m2, длина кода равна числу пар столбцов (m + 1)/2, умноженному на m,
т.е. n = m(m + 1)/2, алфавит кода равен объединению алфавитов, используемых
во всех матрицах Br в предложении 1, т.е. q = 1 + m(m - 1)/2 = 1 + (N - m)/2,
а вес кодовых слов равен числу пар столбцов (m+1)/2, умноженному на вес строки
матриц Br, равный m - 1, т.е. (N - 1)/2. Осталось вычислить кодовое расстояние.
Очевидно, что для (j, r) = (j′, r′)
(
)
{m,
если j = j′ и r = r′,
d
f (j, r), f(j′, r′)
=
(13)
m - 1, если j = j′ или r = r′.
Так как у любых двух слов МДР-кода символы совпадают лишь в одной пози-
ции (и эти символы, естественно, принадлежат лишь одной паре столбцов разбиения
МДР-кода), то согласно (13) расстояние между соответствующими словами постро-
енного нами кода равно m(m - 1)/2 + m - 1 = n - 1. ▴
Замечание 4. Конечно, предложение 1 представляет собой частный случай пред-
ложения 2, но авторам показалась достаточно своеобразной и заслуживающей из-
ложения конструкция кода в предложении 1.
5. При рассмотрении случая (II) в предыдущем пункте мы ограничились нечет-
ными m, так как при четных m слабо разрешимая схема WRBm(m2, 2, 1) не суще-
N-1
ствует, ибо не выполнено необходимое условие, что w =
- целое число. По-
2
этому, если мы хотим оставить первые два параметра схемы неизменными (v = m2,
k = 2), то мы должны перейти к схеме WRBm(m2,2,2). При этом согласно теореме 2
параметры кода должны быть следующими:
N = m2, n = m(m + 1), d = n - 2, w = N - 1,
N-m
(14)
q=
+ 1, m - четное.
2
И при m, равном степени числа 2, такие коды удается построить.
Предложение 3. Для любого m, являющегося степенью числа 2, существу-
ет код со значениями параметров (14).
Доказательство. Построение таких кодов, по существу, весьма близко к то-
му, которое использовалось в предложении 2 для m, равного степени нечетного про-
стого числа. Отличие связано с тем, что при четных m длина МДР-кода с парамет-
рами (12) нечетна, и следовательно, он не может быть разбит на пары столбцов.
Поэтому в строки матриц, весьма схожих с матрицами Br из предложения 1, отоб-
ражается каждый столбец МДР-кода.
Сначала для любого элемента a алфавита нашего будущего кода (a = 0, 1, . . . ,
m(m - 1)/2) определим циркулянтную матрицу D(a) размера (m - 1) × (m - 1),
первая строка которой имеет вид
a, a + 1, a + 2, . . ., a + (m - 2)/2, a + (m - 2)/2, a + (m - 2)/2 - 1, . . ., a + 2, a + 1.
10
Затем превратим эту матрицу в матрицу D(a, ℓ) размера m × m, присоединив к ней
сначала снизу строку a, a, . . . , a длины m - 1, а затем вставив нулевой столбец в ℓ-й
позиции, ℓ = 0, 1, . . . , m - 1. Приведем пример такого построения при m = 8:
⎡
⎤
a a+1 a+2 a+3 a+3 a+2 a+1
⎢a+1
a a+1 a+2 a+3 a+3 a+2⎥
⎢
⎥
D(a) =
⎢
⎥
⎣
⎦
a+2
a+3
a+3
a+2
a+1
a a+1
a+1
a+2
a+3
a+3
a+2
a+1
a
и
⎡
⎤
a a+1 a+2
0
a+3
a+3
a+2
a+1
⎢a+1
a a+1
0
a+2
a+3
a+3
a+2⎥
⎢
⎥
⎢
⎥
D(a, 3) =
⎢
⎥.
⎢a+2
a+3
a+3
0
a+2
a+1
a a+1⎥
⎦
⎣a + 1 a+2
a+3
0
a+3
a+2
a+1
a
a
a
a
0
a
a
a
a
Нетрудно видеть, что расстояние между строками матрицы D(a, ℓ) равно m - 2.
Положим A = {1 + rm/2 : r = 0, 1, . . ., m - 2}. Очевидно, что для любых a, a′ ∈ A,
a = a′, расстояние между строками матриц D(a,ℓ) и D(a′,ℓ′) равно m, если ℓ = ℓ′.
Теперь уже мы можем определить матрицы Dr: Dr = D(1 + rm/2, r), r = 0, 1, . . . ,
m-2. Матрицу Dm-1 определим несколько иным способом: положим ее r-й столбец
равным (r + 1)-му столбцу матрицы Dr, r = 0, 1, . . . , m - 2, а последний ((m - 1)-й)
столбец положим нулевым.
Нетрудно видеть, что расстояние между строками матрицы Dr, r = 0, 1, . . ., m-1,
равно m - 2, а между строками матриц Dr и Dr′, r = r′, равно m.
Проиллюстрируем построение матриц Dr на примере m = 4. Первые три матри-
цы имеют вид
⎤
⎤
⎤
⎡0
1
2
2
⎡3
0
4
4
⎡5
6
0
6
⎢0
2
1
2⎥
⎢4
0
3
4⎥
⎢6
5
0
6⎥
D0 =
⎣
⎦, D1 =
⎣
⎦, D2 =
⎣
⎦,
0
2
2
1
4
0
4
3
6
6
0
5
0
1
1
1
3
0
3
3
5
5
0
5
а последняя -
⎤
⎡1
4
6
0
⎢2
3
6
0⎥
D3 =
⎣
⎦.
2
4
5
0
1
3
5
0
Отображение МДР-кода (12) в код с параметрами (14) совсем просто: каждый
символ r этого кода, r = 0, 1, . . . , m - 1, заменяется на строку матрицы Dr с вы-
полнением единственного требования - два одинаковых символа в одном столбце
МДР-кода должны заменяться на разные строки соответствующей матрицы (на-
помним, что каждый символ МДР-кода (12) в каждом столбце встречается m раз,
а каждая матрица Dr состоит из m строк). Формально такое отображение можно за-
дать, например, следующим образом. Обозначим j-ю строку матрицы Dr через dj(r)
и зададим отображение
ϕ(j, r) = dj (r),
переводящее каждую пару (j, r), j = 0, 1, . . . , m - 1, r = 0, 1, . . . , m - 1, в j-ю стро-
ку dj (r) длины m матрицы Dr. Перенумеруем строки матрицы МДР-кода числами
от 1 до m2. В каждом столбце матрицы МДР-кода каждый из его m символов
11
{0, 1, . . ., m - 1} встречается m раз. Пусть i0(r) < i1(r) < . . . < im-1(r) - номера
строк МДР-кода, в которых встречается фиксированный символ r этого кода. Если
этот символ стоит в строке с номером ij(r), то применим к этому символу отобра-
жение ϕ(j, r), т.е. поставим в соответствие этому символу j-ю строку матрицы Dr.
Тем самым, каждый столбец матрицы МДР-кода отобразится в некоторую матри-
цу размера m2 × m, состоящую из строк матриц D0, . . . , Dm-1. Матрица размера
m2 × m(m + 1), полученная в результате такого отображения всех m + 1 столбцов
МДР-кода, представляет собой код с параметрами (14). Вычисление параметров по-
лученного кода аналогично соответствующему вычислению в предложении 2. ▴
Продолжим иллюстрацию примера при m = 4:
⎡
⎤
⎡
⎤
0
0
0
0
0
0
1
2
2
0
1
2
2
0
1
2
2
0
1
2
2
0
1
2
2
⎢0
1
1
1
1⎥
⎢0
2
1
2
3
0
4
4
3
0
4
4
3
0
4
4
3
0
4
4⎥
⎢
⎥
⎢
⎥
⎢0
2
2
2
2⎥
⎢0
2
2
1
5
6
0
6
5
6
0
6
5
6
0
6
5
6
0
6⎥
⎢
⎥
⎢
⎥
⎢0
3
3
3
3⎥
⎢0
1
1
1
1
4
6
0
1
4
6
0
1
4
6
0
1
4
6
0⎥
⎢
⎥
⎢
⎥
1
0
1
2
3
3
0
4
4
0
2
1
2
4
0
3
4
6
5
0
6
2
3
6
0
⎢
⎥
⎢
⎥
⎢1
1
0
3
2⎥
⎢4
0
3
4
4
0
3
4
0
2
1
2
2
3
6
0
6
5
0
6⎥
⎢
⎥
⎢
⎥
⎢1
2
3
0
1⎥
⎢4
0
4
3
6
5
0
6
2
3
6
0
0
2
1
2
4
0
3
4⎥
⎢
⎥
⎢
⎥
⎢1
3
2
1
0⎥
⎢3
0
3
3
2
3
6
0
6
5
0
6
4
0
3
4
0
2
1
2⎥
⎢
⎥,
⎢
⎥
⎢2
0
2
3
1⎥
⎢5
6
0
6
0
2
2
1
6
6
0
5
2
4
5
0
4
0
4
3⎥
⎢
⎥
⎢
⎥
⎢2
1
3
2
0⎥
⎢6
5
0
6
4
0
4
3
2
4
5
0
6
6
0
5
0
2
2
1⎥
⎢
⎥
⎢
⎥
2
2
0
1
3
6
6
0
5
6
6
0
5
0
2
2
1
4
0
4
3
2
4
5
0
⎢
⎥
⎢
⎥
⎢2
3
1
0
2⎥
⎢5
5
0
5
2
4
5
0
4
0
4
3
0
2
2
1
6
6
0
5⎥
⎢
⎥
⎢
⎥
⎢3
0
3
1
2⎥
⎢1
4
6
0
0
1
1
1
1
3
5
0
3
0
3
3
5
5
0
5⎥
⎢
⎥
⎢
⎥
⎢3
1
2
0
3⎥
⎢2
3
6
0
3
0
3
3
5
5
0
5
0
1
1
1
1
3
5
0⎥
⎣
⎦
⎣
⎦
3
2
1
3
0
2
4
5
0
5
5
0
5
3
0
3
3
1
3
5
0
0
1
1
1
3
3
0
2
1
1
3
5
0
1
3
5
0
0
1
1
1
5
5
0
5
3
0
3
3
Левая матрица представляет собой исходный [5, 2, 4]4-МДР-код, а правая - семе-
ричный код мощности 16 с длиной 20, расстоянием 18 и весом 15, полученный при
описанном выше отображении МДР-кода с помощью матриц D0, D1, D2, D3.
6. Перейдем теперь к случаю (I), где удалось построить соответствующий код
лишь при m = 4 и m = 5; при m = 3 соответствующий код совпадает с кодом,
построенным в случае (II), и давно известен (см., например, [8]) - это четверичный
код мощности 9 с длиной 6, расстоянием 5 и весом кодовых слов 4. Построение
обоих кодов основано, как и в предыдущем пункте, на использовании циркулянтных
матриц, но само построение циркулянтных матриц произведено “вручную”, так что
нам не удалось распространить его на большие значения m.
При m = 4 это код C1 над алфавитом из 13 символов мощности 28 с длиной 21,
расстоянием 20 и весом кодовых слов 18. Матрица размера 28 × 21 кодовых слов
кода C1 строится по тому же правилу, что и матрицы в случае (II):
⎡
⎤
B1
A1,1
A1,2
⎢B2
A2,1
A2,2⎥
C1 =
⎣
⎦,
B3
A3,1
A3,2
B4
A4,1
A4,2
где каждая из квадратных матриц размера 7 × 7 циркулянтна и поэтому, как и в
случае (II), можно определить матрицу P (C1) размера 4 × 7, состоящую из первых
строк всех матриц Br, Ars, r = 1, 2, 3, 4, s = 1, 2:
P (C1) = [PB | P1 | P2].
12
Здесь матрица PB строится так же, как и в случае (II):
⎤
⎡0
1
2
3
3
2
1
⎢0
4
5
6
6
5
4
⎥
PB =
⎣
⎦.
0
7
8
9
9
8
7
0
10
11
12
12
11
10
Матрица P1 задается в следующем виде:
⎤
⎡0
1
2
5
6
3
4
⎢
1
9
0
7
8
10
2
⎥
P1 =
⎣
⎦,
4
8
7
3
0
11
12
10
6
9
12
11
5
0
а строками матрицы P2 являются строки матрицы P1, записанные в обратном по-
рядке. Нетрудно проверить непосредственно, что расстояние кода C1 равно 20.
При m = 5 это код C2 над алфавитом из 31 символа мощности 65 с длиной 52,
расстоянием 51 и весом кодовых слов 48. Матрица кодовых слов C2 размера 65 × 52
выглядит так:
⎡
⎤
A1,1
A1,2
A1,3
A
1,4
⎢
A
2,1
A2,2
A2,3
A2,4⎥
⎢
⎥
C2 =
⎢
A3,1
A3,2
A3,3
A3,4⎥
,
⎣
⎦
A4,1
A4,2
A4,3
A4,4
A5,1
A5,2
A5,3
A5,4
где каждая из квадратных матриц размера 13 × 13 циркулянтна. Поэтому можно
определить матрицу P (C2) размера 5 × 13, состоящую из первых строк всех мат-
риц Ars, r = 1, 2, 3, 4, 5, s = 1, 2, 3, 4:
P (C2) = [P1 | P2 | P3 | P4].
Матрицы Ps задаются в следующем виде:
⎡
⎤
1
6
11
16
0
21
22
23
24
16
11
6
1
⎢
2
7
12
17
21
0
25
26
27
17
12
7
2⎥
⎢
⎥
P1 =
⎢
3
8
13
18
22
25
0
28
29
18
13
8
3⎥,
⎣
⎦
4
9
14
19
23
26
28
0
30
19
14
9
4
5
10
15
20
24
27
29
30
0
20
15
10
5
⎡
⎤
1
21
6
22
11
16
23
16
11
0
9
24
4
⎢
2
0
7
25
12
17
26
17
12
21
10
27
5⎥
⎢
⎥
P2 =
⎢
3
26
8
28
13
18
0
18
13
23
6
29
1⎥,
⎣
⎦
4
27
9
29
14
19
30
19
14
24
7
0
2
5
25
10
0
15
20
28
20
15
22
8
30
3
⎡
⎤
0
1
6
21
5
16
22
20
11
23
8
12
24
⎢
21
2
7
0
12
16
25
18
1
26
9
13
27⎥
⎢
⎥
P3 =
⎢
22
3
8
25
13
17
0
18
2
28
10
14
29⎥,
⎣
⎦
23
4
9
26
14
17
28
19
3
0
6
15
30
24
5
10
27
15
20
29
19
4
30
7
11
0
⎡
⎤
1
6
0
11
21
10
22
12
23
17
24
20
3
⎢
2
7
21
12
0
6
25
15
26
18
27
16
4⎥
⎢
⎥
P4 =
⎢
3
8
22
11
25
9
0
16
28
19
29
15
5⎥
⎣
⎦
4
9
23
13
26
8
28
14
0
18
30
20
1
5
7
24
14
27
10
29
13
30
19
0
17
2
13
Непосредственная, но достаточно утомительная проверка показывает, что рас-
стояние кода C2 равно 51.
Хотя нам и не удалось для случая (I) построить бесконечное семейство кодов
с заданными параметрами, но три указанных кода оставляют надежду на то, что
такое семейство существует.
7. Осталось рассмотреть случай (III). Вначале отметим, что если в транспони-
рованной матрице кодовых слов заменить все ненулевые символы на 0, а нулевой
символ на 1, то эта матрица будет представлять собой двоичный код, лежащий на
границе Джонсона, с параметрами
m2 - 2m + 2
N =
,
n = m2 - 2m + 2, d = 2(m - 1), w = m,
2
или, что то же самое, блок-схему B(v = 2k2 - 2k + 1, k, 1), где k = m/2. Следователь-
но, существование таких блок-схем является необходимым условием существования
кода с параметрами (III), но далеко не достаточным. Ведь наличие блок-схемы поз-
воляет лишь правильно расположить нулевые символы в кодовой матрице, а пра-
вильное расположение пар ненулевых символов в каждом столбце - это отдельная
нелегкая задача. Мы знаем, например, что указанные блок-схемы построены при
k = 2,3,4,5 (т.е. при m = 4,6,8,10), но лишь при m = 4 соответствующий рав-
новесный четверичный код длины 5 мощности 10 с расстоянием 4 давно известен
(см., например, [8]).
8. В [3] была поставлена задача построения посимвольно равномерных эквиди-
стантных кодов минимальной длины при заданных параметрах q, k, m (напомним,
что каждый ненулевой символ встретится в столбце кодовой матрицы k раз, а нуле-
вой символ - m раз; очевидно, что число кодовых слов N = (q - 1)k + m). Согласно
теореме 2 длина такого кода равна
λN(N - 1)
n=
,
(15)
m(m - 1) + (N - m)(k - 1)
где через λ = n - d обозначена разность между длиной кода и его расстоянием.
Так как n - целое число, то очевидно, что минимальная длина достигается при
наименьшем λ, таком что правая дробь в (15) становится целым числом. Обозначим
через (a, b) наибольший общий делитель чисел a и b. Ясно, что минимальное λ, при
λa
b
котором дробь
становится целым числом, равно
. Следовательно, имеет
b
(a, b)
место
Предложение 4. Минимальная длина n посимвольно равномерного эквиди-
стантного кода с параметрами q, k, m удовлетворяет неравенству
N (N - 1)
n≥
,
(16)
(N(N - 1), m(m - k) + N(k - 1))
где N = (q - 1)k + m.
Нетрудно непосредственно проверить, что все коды, приведенные в пп. 3, 4, 6, 7,
имеют минимальную длину.
СПИСОК ЛИТЕРАТУРЫ
1. Beth T., Jungnickel D., Lenz B. Design Theory. Cambridge: Cambridge Univ. Press, 1999.
2. Семаков Н.В., Зиновьев В.А. Эквидистантные q-ичные коды с максимальным расстоя-
нием и разрешимые уравновешенные неполные блок-схемы // Пробл. передачи информ.
14
3. Бассалыго Л.А., Зиновьев В.А., Лебедев В.С. Симметричные блок-схемы и оптимальные
эквидистантные коды // Пробл. передачи информ. 2020. Т. 56. № 3. С. 50-58. https:
//doi.org/10.31857/S055529232003002X
4. Sinha K., Sinha N. A Class of Optimal Quaternary Codes // Ars Combin. 2010. V. 94.
P. 61-64.
5. Бассалыго Л.А. Новые верхние границы для кодов, исправляющих ошибки // Пробл.
6. Бассалыго Л.А., Зиновьев В.А., Лебедев В.С. Об m-квазиразрешимых блок-схемах и
q-ичных равновесных кодах // Пробл. передачи информ. 2018. Т. 54. № 3. С. 54-61.
7. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь,
1979.
8. Todorov T., Bogdanova G., Yorgova T. Lexicographic Constant-Weight Equidistant Codes
over the Alphabet of Three, Four and Five Elements // Intell. Inf. Manag. 2010. V. 2. № 3.
Бассалыго Леонид Александрович
Поступила в редакцию
Зиновьев Виктор Александрович
16.04.2021
Лебедев Владимир Сергеевич
После доработки
Институт проблем передачи информации
11.09.2021
им. А.А. Харкевича РАН
Принята к публикации
bass@iitp.ru
01.10.2021
vazinov@iitp.ru
lebedev37@mail.ru
15
