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

Том 58

2022

Вып. 3

УДК 621.391 : 519.72

УЛУЧШЕНИЕ ВЕРХНИХ ГРАНИЦ СКОРОСТЕЙ РАЗДЕЛЯЮЩИХ

И ПОЛНОСТЬЮ РАЗДЕЛЯЮЩИХ КОДОВ

Двоичный код называется (s, ℓ)-разделяющим кодом, если для любых двух

непересекающихся наборов его слов мощности не более s и ℓ соответственно

существует координата, в которой все слова из одного набора имеют символ 0,

а все слова из другого набора имеют символ 1. Если же вдобавок для любых на-

боров существует вторая координата, в которой у первого набора во всех словах

стоят 1, а у второго стоят 0, то такой код называется (s, ℓ)-полностью разделя-

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

полностью разделяющих кодов.

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

тическая скорость, граница Плоткина.

DOI: 10.31857/S0555292322030044, EDN: EADNOC

§ 1. Введение

Впервые задача построения двоичных разделяющих систем возникла при иссле-

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

ми элементов памяти автомата при его переходе из одного устойчивого внутреннего

состояния в другое Ю.Л. Сагаловичем было предложено использовать двоичные

(2, 2)-разделяющие коды [1]. В работе [2] было введено общее определение (s, ℓ)-раз-

деляющих кодов. Отметим, что хотя изначально исследование разделяющих кодов

было мотивировано задачами из теории автоматов, позднее они нашли применение

при разработке способов защиты информации от нелегального копирования [3] и при

построении хэш-функций [4].

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

случайного кодирования в работе [2]. В [5] с помощью случайного кодирования с вы-

брасыванием были получены нижние оценки скоростей (2, 2)- и (2, 1)-разделяющих

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

кой скорости линейных (2, 2)-разделяющих кодов из [6]. Отметим, что доказатель-

ство с выбрасыванием точно так же работает и для случая (s, ℓ)-разделяющих и

полностью разделяющих кодов.

Также отметим неожиданное улучшение этих границ для (2, 1)-разделяющих ко-

дов [7].

Верхние границы для скорости (2, 2)-разделяющих кодов впервые были получены

Сагаловичем в [8] с помощью следующей идеи. Возьмем два кодовых слова на мини-

мальном расстоянии (Хэмминга) d и ограничим исходный код на соответствующие d

¹ Исследование выполнено за счет гранта Российского научного фонда (номер проекта 22-41-

02028).

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

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

координат, предварительно удалив из кода эти два слова. Новый код длины d будет

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

не превосходит 2^d + 2. Это позволяет оценить сверху скорость (2, 2)-разделяющих

кодов с помощью известных верхних оценок скорости кода (см. [9, 10]).

Идея, что этот подход можно обобщать на случай (s, ℓ)-кодов, высказывалась са-

мим Ю.Л. Сагаловичем, а также Л.А. Бассалыго и Г.А. Кабатянским на семинарах

ИППИ РАН по теории кодирования. Этот подход был реализован для хэш-кодов

в [11], а для (s, ℓ)-свободных от перекрытий кодов, которые тесно связаны с разде-

ляющими кодами, - в [12, 13].

В [14] были предложены рекуррентные верхние границы скоростей (s, ℓ)-разделя-

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

раметрами (s - 1, ℓ - 1). Отметим, что в [14] (s, ℓ)-разделяющие коды сводились

к (s - 1, ℓ - 1)-полностью разделяющим кодам, что позволило получить более силь-

ные оценки, чем если бы коды сводились к разделяющим.

В [15] получены рекуррентные неравенства, связывающие верхние границы для

(s, ℓ)-разделяющих и полностью разделяющих кодов со скоростями кодов с пара-

метрами (s - u, ℓ - v). Эти границы, в частности, позволили показать, что скорость

t-IPP-кодов [16] экспоненциально мала по t (см. [17]).

В данной статье мы доказываем новые рекуррентные неравенства, которые свя-

зывают скорости разделяющих кодов и кодов, свободных от перекрытий. Эти нера-

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

многих параметров s и ℓ. Кроме того, мы улучшаем известную верхнюю границу для

(2, 1)-полностью разделяющих кодов. Так как наилучшие верхние границы выража-

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

границы для (2, 1)-полностью разделяющих кодов приводит к улучшению для ши-

рокого набора параметров.

§ 2. Определения и обозначения

Пусть N, M, s, ℓ - натуральные числа, символ ≜ обозначает равенство по опре-

делению, |A| - мощность множества A, [N] ≜ {1, 2, . . . , N} - множество целых чисел

от 1 до N. Произвольное подмножество булева куба {0, 1}^N называется двоичным

кодом длины N. Будем обозначать двоичную энтропию через

h(x) = -x log₂(x) - (1 - x) log₂(1 - x).

Определение 1 [2]. Двоичный код C называется (s,ℓ)-разделяющим, если для

любых двух непересекающихся множеств кодовых слов S и L, |S| ≤ s, |L| ≤ ℓ,

существует координата i, такая что:

либо x_i = 0 для любого x ∈ S и y_i = 1 для любого y ∈ L,

либо x_i = 1 для любого x ∈ S и y_i = 0 для любого y ∈ L.

Определение 2. Двоичный код C называется (s,ℓ)-свободным от перекры-

тий, если для любых двух непересекающихся множеств кодовых слов S и L, |S| ≤ s,

|L| ≤ ℓ, существует координата i, для которой

x_i = 0 для любого x ∈ S и y_i = 1 для любого y ∈ L.

Определение 3. Двоичный код C называется (s,ℓ)-полностью разделяющим,

если для любых двух непересекающихся множеств кодовых слов S и L, |S| ≤ s,

|L| ≤ ℓ, существуют две координаты i и j, такие что:

x_i = 0 для любого x ∈ S и y_i = 1 для любого y ∈ L, и

x_j = 1 для любого x ∈ S и y_j = 0 для любого y ∈ L.

Отметим, что

определение 3

=⇒ определение 2

=⇒ определение 1,

а также что при s = ℓ определения (s, ℓ)-полностью разделяющих и (s, ℓ)-свободных

от перекрытий кодов совпадают. Кроме того, напомним, что (s, 1)-свободные от пе-

рекрытий коды известны как s-дизъюнктивные коды [18]. Полезно заметить, что

если код C разделяющий, то и код C + a тоже разделяющий для любого двоичного

вектора a. Если же код C полностью разделяющий, то и код C + 1 обладает тем же

свойством.

Принято думать, что (s, ℓ)-свободные от перекрытий коды были впервые опре-

делены в работе [19] в 1988 г., а полностью разделяющие системы - в работе [20]

в 1973 г. На самом деле, в [20] были определены свободные от перекрытий коды (за 15

лет до работы [19]), но они были при этом названы полностью разделяющими.

Обозначим через N_s(M, s, ℓ), N_cf(M, s, ℓ) и N_cs(M, s, ℓ) минимальную длину ко-

дов из определений 1-3 при заданной мощности M. Определим асимптотические

скорости кодов

log₂ M

R_s(s, ℓ) ≜ lim

(1)

M→∞ N_s(M, s, ℓ)

log₂ M

R_cf(s, ℓ) ≜ lim

(2)

M→∞ N_cf (M, s, ℓ)

log₂ M

R_cs(s, ℓ) ≜ lim

(3)

M→∞ N_cs(M, s, ℓ)

В этой статье мы улучшаем верхние границы скоростей R_s и R_cs. Заметим, что

в силу симметрии определений 1 и 3 справедливы равенства R_s(s, ℓ) = R_s(ℓ, s) и

R_cs(s, ℓ) = R_cs(ℓ, s).

§ 3. Известные результаты

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

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

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

Для (s, 1)-свободных от перекрытий кодов, которые также называются s-дизъ-

юнктивными кодами, известна [21] верхняя граница

R_cf(s, 1) ≤ R_cf(s, 1),

(4)

где последовательность R_cf (s, 1) определена следующим образом: R_cf (1, 1) ≜ 1,

R_cf(2, 1) ≜ max

f₂(v), а R_cf(s, 1) при s > 2 является единственным решением урав-

0<v<1

нения

(

)

R_cf(s, 1)

R_cf(s, 1) = f_s

R_cf(s - 1, 1)

где f_s(v) ≜ h(v/s) - vh(1/s).

В [22] было доказано, что

(

)-1

R_cf(s, ℓ) ≤

(5)

R_cf(s, ℓ - 1)

R_cf(s - 1, ℓ)

В [12] (см. также [23]) было доказано рекуррентное неравенство

u^uv

R_cf(s, ℓ) ≤ R_cf(s - u, ℓ - v)

1 ≤ u ≤ s - 1,

1 ≤ v ≤ ℓ - 1.

(6)

(u + v)u+v

В [24] (см. также [13]) были доказаны более сильные неравенства

R_cf(s - u, ℓ - v)

R_cf(s, ℓ) ≤

u+v

(7)

(u + v)

R_cf(s - u, ℓ - v) +

u^uv^v

(

√

(

))

2R_cf(s, ℓ)

R_cf(s, ℓ) ≤ h

1/2 -

(8)

R_cf(s - 1, ℓ - 1)

В [14, 25] было доказано, что скорость (s, 1)-разделяющих кодов удовлетворяет

неравенству

R_s(s, 1) ≤

(9)

Для разделяющих и полностью разделяющих кодов в [14] были получены следу-

ющие результаты:

(

)

R_s(s, ℓ)

R_s(s, ℓ) ≤

(10)

R_cs(s - 1, ℓ - 1)

(

)

2R_cs(s, ℓ)

R_cs(s, ℓ) ≤

(11)

R_cs(s - 1, ℓ - 1)

где

^R(τ)- произвольная верхняя асимптотическая оценка скорости кода с относи-

тельным расстоянием Хэмминга τ = d/n.

В [15] для разделяющих кодов были доказаны рекуррентные неравенства, ана-

логичные неравенствам (6). А именно,

1. Для любых u ∈ [s - 1], v ∈ [ℓ - 1]

R_s(s, ℓ) ≤ R_s(s - u, ℓ - v) max {z^u(1 - z)^v + (1 - z)^uz^v}.

(12)

0≤z≤1

2. Для любого v ∈ [ℓ - 1] и u = v + s - ℓ, 1 ≤ u ≤ s - 1,

R_s(s, ℓ) ≤ R_cs(s - u, ℓ - v) max {z^u(1 - z)^v + (1 - z)^uz^v}.

(13)

0≤z≤1

3. Для любого v ∈ [min(s, ℓ) - 1]

R_cs(s, ℓ) ≤ R_cs(s - v, ℓ - v)

(14)

22v

Кроме того, было доказано неравенство

R_s(s, ℓ) ≤ min(R_cf(s, ℓ - 1), R_cf(s - 1, ℓ)).

(15)

§4. Новые неравенства

Мы начнем с улучшения верхней границы для скорости (2, 1)-полностью разделя-

ющих кодов. Отметим, что известная наилучшая верхняя оценка совпадала с верх-

ней границей скорости (2, 1)-свободных от перекрытий кодов и равнялась 0,321929.

Теорема 1. Справедлива оценка

R_cs(2, 1) = R_cs(1, 2) ≤ h(0,25) - 0,5 = 0,311278 . . .

(16)

Доказательство. Рассмотрим произвольный (2,1)-полностью разделяющий

код C длины N и мощности M. Найдем вес w, такой что количество кодовых слов

веса w максимально. Без ограничения общности можно считать, что w ≥ N/2, так

как в противном случае можно заменить код C на C + 1.

Так как (2, 1)-полностью разделяющий код является (2, 1)-свободным от пере-

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

веса, доказанные в [21,26]. Лемма 3 из [21] или теорема 1 из [26] позволяют оценить

количество слов веса w как

(

)

⌊w/2⌋

⁽ 2⌊w/2⌋).

⌊w/2⌋

Тогда общее количество кодовых слов не превосходит

(

)

⌊w/2⌋

⁽ 2⌊w/2⌋),

⌊w/2⌋

(

)

что в силу хорошо известной асимптотики

= 2N(h(w)+o(1)) приводит к оценке

R_cs(2, 1) ≤ max (h(w/2) - w) = h(1/4) - 1/2.

▴

0,5≤w≤1

Теорема 2. Пусть s,ℓ ≥ 2. Тогда

(

)

R_cs(s, ℓ) ≤

min

R_cf(s, ℓ - 1), R_cf(s - 1, ℓ)

(17)

Доказательство. Так как R_s(s,ℓ) = R_s(ℓ,s) и R_cf(s,ℓ) = R_cf(ℓ,s), то мы

докажем только неравенство

R_cs(s, ℓ) ≤

R_cf(s, ℓ - 1).

Рассмотрим произвольный (s, ℓ)-полностью разделяющий код C длины N и мощ-

ности M и некоторое его слово c веса w. Без ограничения общности можно считать,

что w ≤ N/2, ибо в противном случае мы рассмотрим код C + 1. Построим новый

код C^′, удалив все координаты, в которых выбранное слово c имеет нули. Удалим

также и само слово c. Проекция кода C \ c на код C^′ инъективна. Действительно,

пусть два слова a = b из кода C\c при проекции на координаты, где вектор c имеет 1,

совпали. Тогда в исходном коде нет координаты j, такой что a_j = c_j = 1 и b_j = 0,

что противоречит тому, что исходный код был (2, 1)-полностью разделяющим. Та-

ким образом, длина кода C^′ равна w ≤ N/2, а мощность равна M - 1. Покажем, что

код C^′ является (s, ℓ - 1)-свободным от перекрытий.

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

вых слов S и L, |S| = s, |L| = ℓ - 1, S, L ⊂ C^′. Этим множествам соответствуют

множества

S и

L исходного кода C. Так как код C является (s, ℓ)-полностью разде-

ляющим, то для множеств

S и

L ∪ c найдется координата i, такая что

x_i = 0 для любого x ∈

S и y_i = 1 для любого y ∈

L ∪ c.

Так как c_i = 1, то при построении кода C^′ эта координата не была удалена, и значит,

в этой координате в коде C^′ выполнено

x_i = 0 для любого x ∈ S и y_i = 1 для любого y ∈ L.

А это и означает, что код C^′ является (s, ℓ - 1)-свободным от перекрытий. Отсюда

получаем искомое неравенство

R_cs(s, ℓ) ≤

R_cf(s, ℓ - 1).

▴

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

множеств кодовых слов U, V ⊂ C определим разделяющее “расстояние” D(U, V ) как

количество координат, в которых все слова из одного множества имеют символ 0,

а все слова из другого множества - символ 1. Будем говорить, что такие коорди-

наты разделяют множества U и V . Отметим, что (1, 1)-разделяющее расстояние -

это обычное расстояние Хэмминга, но при других параметрах u и v неравенство

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

Будем называть (u, v)-разделяющим расстоянием кода C величину

d_uv(C) =

min

D(U, V ),

U,V ⊂C

U∩V =∅

|U|=u, |V |=v

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

u и v ясны из контекста.

Определим величину

Δ(u, v) = max {z^u(1 - z)^v + (1 - z)^uz^v}.

(18)

0≤z≤1

Следующее утверждение является обобщением классической границы Плоткина.

Лемма 1. Для произвольного кода C длины N с (u,v)-разделяющим расстоя-

нием d справедливо

u+v-1

|C| ≤

⁽NΔ)1/(u+v-1),

если d/N > Δ = Δ(u, v).

Доказательство. Рассмотрим код C длины N и мощности M и оценим сум-

му S всех (u, v)-разделяющих расстояний по всем парам непересекающихся кодовых

подмножеств U, V таких, что |U| = u, |V | = v. Очевидно, что

(

∑

⁾⁽u + v⁾

M (M - u - v + 1)u+v-1

S =

D(U, V ) ≥

d≥

u+v

u! v!

U,V ⊂C

|U|=u, |V |=v

С другой стороны, если в i-й координате слов кода имеется A единиц (и M - A

нулей), то вклад этой координаты в S равен

⁽A⁾⁽M - A⁾

и следовательно,

)

^{(A⁾⁽M - A

⁽A⁾⁽M - A^)}

Mu+v

S ≤ N max

≤N

Δ.

0≤A≤M

u! v!

Объединяя верхнюю и нижнюю оценки величины S, получаем

(M - u - v + 1)u+v-1d ≤ NMu+v-1Δ.

Отсюда следует

)1/(u+v-1)

u+v-1

⁽NΔ

≤

и так как d/N > Δ по условиям леммы, то

u+v-1

M ≤

▴

⁽NΔ)1/(u+v-1).

Как уже отмечалось выше, (1, 1)-разделяющее расстояние - это расстояние Хэм-

минга, Δ(1, 1) = 1/2, и доказанная граница превращается в этом случае в классиче-

скую границу Плоткина: если 2d > N, то |C| ≤

2d - N

Максимальную мощность кода длины N с (u, v)-разделяющим расстоянием d

будем обозначать через M_u,v(N, d). Следующая лемма является аналогом асимпто-

тической границы Плоткина.

Лемма 2. Для любого τ, 0 < τ < Δ = Δ(u,v), справедливо

(

)

log₂ M_u,v(N, ⌊τN⌋) ≤ N

+ o(1)

(19)

Доказательство. Сначала докажем неравенство

M_u,v(N, d) ≤ 2M_u,v(N - 1, d).

(20)

Пусть C - код максимальной мощности M_u,v(N, d) длины N с (u, v)-разделяющим

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

дем считать, что в словах кода C в ней больше нулей, чем единиц. Удалим эту ко-

ординату и все кодовые слова, имеющие единицу в этой координате. У полученного

кода C^′ его (u, v)-разделяющее расстояние не уменьшится, длина кода уменьшится

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

ство (20).

Применяя неравенство (20) i раз, получаем

log₂ M_u,v(N, d) ≤ i + log₂ M_u,v(N - i, d).

(21)

Теперь возьмем минимальное целое i, такое что

≥

для некоторого

⌋

N-i

1-ε

^⌊d(1 - ε)

ε > 0, т.е. i = N -

. Тогда из леммы 1 получаем

u+v-1

M_u,v(N - i, d) ≤

⁽(N - i)Δ)1/(u+v) ≤

1 - (1 - ε)1/(u+v-1)

Полагая ε = 1/N, получаем, что

M (N - i, d) ≤ c(u, v)N + o(N),

где c(u, v) - некоторая константа, зависящая от u и v, но не зависящая от N. Теперь

оценку (21) можно переписать в виде

d(1 - ε)

log₂ M_u,v(N, d) ≤ N -

+ log₂((c(u, v) + o(1))N) =

(

)

+ o(N).

▴

(22)

NΔ

Замечание 1. Из леммы, в частности, следует, что не существует разделяющих

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

расстоянием ≥ Δ. Несложно доказать, что для любого τ < Δ разделяющие коды

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

стоянием τ существуют, а значит, Δ является критической точкой. Доказательство

этого факта мы приводим в Приложении.

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

ется на обобщении упомянутой во введении идеи Ю.Л. Сагаловича на случай произ-

вольных (s, ℓ)-разделяющих кодов и на доказанной выше асимптотической границе

Плоткина для разделяющих кодов.

Теорема 3. Для любых u ∈ [s - 1], v ∈ [ℓ - 1]

R_cf(s - u, ℓ - v)·

R_s(s, ℓ) ≤

(23)

R_cf(s - u, ℓ - v) + Δ-1(u, v)

Доказательство. Докажем, что у любого (s,ℓ)-разделяющего кода C его ми-

нимальное (u, v)-разделяющее расстояние d = d_u,v(C) достаточно велико, а именно

d_u,v(C) ≥ N_cf(|C| - u - v, s - u, ℓ - v).

(24)

Возьмем два непересекающихся множества кодовых слов U, V

⊂ C, |U| = u,

|V | = v, на которых достигается минимальное (u, v)-разделяющее расстояние d ко-

да C. Обозначим через I ⊂ [N] множество координат, разделяющих U и V . Как

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

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

множества I слова из U имеют нули, а слова из V - единицы. Рассмотрим код C^′

длины d, полученный из кода C \{U ∪V } его укорочением (проекцией) на множество

координат I. Покажем, что код C^′ является (s - u, ℓ - v)-свободным от перекрытий

кодом мощности |C| - u - v.

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

вых слов S^′, L^′ ⊂ C^′, такие что |S^′| = s - u, |L^′| = ℓ - v, и соответствующие им

множества S и L исходного кода C. Рассмотрим множества

S =S∪U и

L=L∪V.

Так как код C является (s, ℓ)-разделяющим, то найдется координата i ∈ [N], ко-

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

S и

L, а значит, она разделяет и множества U и V ,

а следовательно, i ∈ I. Так как во всех координатах из множества I слова из U

имеют нули, а слова из V - единицы, то код C^′ является (s - u, ℓ - v)-свободным

от перекрытий. Отсюда, в частности, следует, что при укорочении кода C \ {U ∪ V }

никакие два слова не могли совпасть, т.е. |C^′| = |C| - u - v, и неравенство (24) дока-

зано.

В силу неравенства (24) перепишем асимптотическую границу Плоткина (19) при

τ < Δ = Δ(u,v) в виде

(

)

log₂ M_u,v(N, ⌊τN⌋) ≤ N

+ o(1)

≤

(

)

N_cf(M_u,v(N, ⌊τN⌋) - u - v, s - u, ℓ - v)

≤N

+ o(1)

NΔ

Таблица 1

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

sℓ

1,000000

0,500000

0,321929

0,199282

0,140457

0,105641

0,083000

0,067305

0,500000

0,283477

0,116879

0,066265

0,038684

0,024305

0,016336

0,011569

0,321929

0,116879

0,066265

0,028695

0,015326

0,008215

0,005271

0,003270

0,199282

0,066265

0,028695

0,015326

0,007088

0,003703

0,001912

0,001090

0,140457

0,038684

0,015326

0,007088

0,003703

0,001761

0,000912

0,000463

0,105641

0,024305

0,008215

0,003703

0,001761

0,000912

0,000439

0,000226

0,083000

0,016336

0,005271

0,001912

0,000912

0,000439

0,000226

0,000110

0,067305

0,011569

0,003270

0,001090

0,000463

0,000226

0,000110

0,000056

Таблица 2

Способ получения верхних границ скоростей кодов из табл. 1

sℓ

Н9

Н15

Н9

Н10

Н10 + Т1

Н10 + Т2

T3 (1, 3) T3 (1, 3) T3 (1, 4) T3 (1, 4)

Н15

Н10 + Т1

Н15

Н10 + Т1

Н15

T3 (1, 3) T3 (2, 5) T3 (2, 5)

Н15

Н10 + Т2

Н10 + Т1

Н15

Н10 + Т1

Н15

T3 (1, 3) T3 (2, 5)

Н15

T3 (3, 1)

Н15

Н10 + Т1

Н15

Н10 + Т1

Н15

T3 (1, 3)

Н15

T3 (3, 1) T3 (3, 1)

Н15

Н10 + Т1

Н15

Н10 + Т1

Н15

T3 (4, 1) T3 (5, 2) T3 (3, 1)

Н15

Н10 + Т1

Н15

Н10 + Т1

Н15

T3 (4, 1) T3 (5, 2) T3 (5, 2) T3 (3, 1)

Н15

Н10 + Т1

Н15

Подставив туда очевидное соотношение N_cf (M, a, b) ≥ log₂ M(R_cf + o(1))-1, полу-

чим, что

(

)

log₂ M_u,v(N, ⌊τN⌋)

log₂ M_u,v(N, ⌊τN⌋) ≤ N

+ o(1)

N Δ(R_cf

+ o(1))

или, что равносильно,

(

)

log₂ M_u,v(N, ⌊τN⌋)

+ o(1)

≤ N(1 + o(1)).

▴

R_cfΔ

Подчеркнем, что эта теорема ограничивает скорость разделяющих кодов че-

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

в правой части неравенства присутствует скорость разделяющих кодов. В неравен-

стве (13) скорость разделяющих кодов ограничивается через скорость полностью

разделяющих кодов, однако неравенство выполняется лишь для u = v + s - ℓ, тогда

как теорема 3 выполняется для всех u и v.

§ 5. Сравнения и таблицы

В этом параграфе мы приводим численные значения верхних границ асимптоти-

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

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

именно теоремы (Т) или неравенства (Н) был получен тот или иной результат.

Результаты для разделяющих кодов приведены в табл. 1, 2. В табл. 2 в скобках

указаны значения параметров u и v из теоремы 3, дающие наилучшие значения.

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

для многих значений параметров s и ℓ.

Таблица 3

Верхние границы скоростей полностью разделяющих кодов

sℓ

1,000000

0,311278

0,160964

0,099641

0,070228

0,052820

0,041500

0,033652

0,311278

0,160964

0,064317

0,033133

0,021507

0,014338

0,010192

0,007299

0,160964

0,064317

0,033133

0,014895

0,007663

0,004861

0,003166

0,002115

0,099641

0,033133

0,014895

0,007663

0,003601

0,001852

0,001133

0,000719

0,070228

0,021507

0,007663

0,003601

0,001852

0,000887

0,000456

0,000265

0,052820

0,014338

0,004861

0,001852

0,000887

0,000456

0,000220

0,000113

0,041500

0,010192

0,003166

0,001133

0,000456

0,000220

0,000113

0,000055

0,033652

0,007299

0,002115

0,000719

0,000265

0,000113

0,000055

0,000028

Таблица 4

Способ получения верхних границ скоростей кодов из табл. 3

sℓ

Н11 + Т1

Для полностью разделяющих кодов (табл. 3, 4) мы улучшаем все значения, кро-

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

кодов.

Для свободных от перекрытий кодов (табл. 5, 6) мы не получаем новых резуль-

татов, все оценки получены с помощью ранее известных теорем. Но, как отмечалось

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

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

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

не публиковались.

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

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

неравенства (7).

ПРИЛОЖЕНИЕ: НИЖНЯЯ ГРАНИЦА СКОРОСТИ

КОДОВ С РАЗДЕЛЯЮЩИМ РАССТОЯНИЕМ

Теорема 4. Максимальная мощность M_u,v(N,d) кода с (u,v)-разделяющим

расстоянием d = ⌊τN⌋ удовлетворяет неравенству

-h(τ) - τ log₂ Δ(u, v) - (1 - τ)log₂(1 - Δ(u, v)) + o(1)

log₂ M_u,v(N, d) ≥ N

(25)

u+v-1

при 0 ≤ τ < Δ(u, v), где величина Δ(u, v) определена в (18).

Отметим, что правая часть положительна при τ < Δ(u, v) и стремится к нулю

при τ → Δ(u, v). При u = v = 1 точка Δ(1, 1) = 1/2, и наша нижняя граница

превращается в границу Варшамова - Гильберта.

Таблица 5

Верхние границы скоростей свободных от перекрытий кодов

sℓ

1,000000

0,321929

0,199282

0,140457

0,105641

0,083000

0,067305

0,055905

0,321929

0,160964

0,066265

0,043015

0,028677

0,020384

0,014598

0,011019

0,199282

0,066265

0,033133

0,015326

0,009722

0,006332

0,004230

0,003011

0,140457

0,043015

0,015326

0,007663

0,003703

0,002265

0,001438

0,000937

0,105641

0,028677

0,009722

0,003703

0,001852

0,000912

0,000529

0,000333

0,083000

0,020384

0,006332

0,002265

0,000912

0,000456

0,000226

0,000128

0,067305

0,014598

0,004230

0,001438

0,000529

0,000226

0,000113

0,000056

0,055905

0,011019

0,003011

0,000937

0,000333

0,000128

0,000056

0,000028

Таблица 6

Номер неравенства, из которого получены значения в табл. 5

sℓ

Н4

Н5

Н8

Н7 (1, 2) Н7 (1, 2) Н7 (1, 3) Н7 (1, 3)

Н4

Н8

Н5

Н8

Н7 (1, 2) Н7 (1, 2) Н7 (1, 2) Н7 (1, 2)

Н4

Н8

Н5

Н8

Н7 (1, 2) Н7 (1, 2) Н7 (1, 2)

Н4

Н7 (2, 1) Н7 (2, 1)

Н8

Н5

Н8

Н7 (2, 3) Н7 (3, 5)

Н4

Н7 (2, 1) Н7 (2, 1) Н7 (2, 1)

Н8

Н5

Н8

Н7 (2, 3)

Н4

Н7 (3, 1) Н7 (2, 1) Н7 (2, 1) Н7 (3, 2)

Н8

Н5

Н8

Н4

Н7 (3, 1) Н7 (2, 1) Н7 (2, 1) Н7 (5, 3) Н7 (3, 2)

Н8

Н5

Доказательство. Рассмотрим случайный код длины N и мощности M, где

каждый элемент каждого кодового слова выбирается независимо и равен 1 с веро-

ятностью p.

Вероятность того, что фиксированная координата разделяет два набора кодовых

слов размера u и v равна

q = p^u(1 - p)^v + p^v(1 - p)^u.

Параметр p мы выберем так, чтобы максимизировать q. Отметим, что максимум

вероятности разделения равен в точности величине Δ(u, v), определенной в фор-

муле (18). Число ξ координат, разделяющих два фиксированных набора кодовых

слов, имеет биномиальное распределение с параметрами N и Δ = Δ(u, v). Оценим

вероятность того, что ξ < d в предположении Δ(u, v) > τ:

∑

⁽N⁾

P =

Δ^k(1 - Δ)^N-k ≤ N2N(h(τ)+τlog2 Δ+(1-τ)log2(1-Δ)+o(1)).

k=0

Таким образом,

N-1 log₂ P = h(τ) + τ log₂ Δ + (1 - τ)log₂(1 - Δ) + o(1).

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

стояние между которыми меньше d, не превосходит P · Mu+v. Стандартное рассуж-

дение с выбрасыванием приводит к оценке

-h(τ) - τ log₂ Δ - (1 - τ)log₂(1 - Δ) + o(1)

log₂ M_u,v(N, d) ≥ N

u+v-1

что и требовалось доказать. ▴

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

Сагалович Ю.Л. Метод повышения надежности конечного автомата // Пробл. переда-

чи информ. 1965. Т. 1. № 2. С. 27-35. http://mi.mathnet.ru/ppi734

Friedman A.D., Graham R.L., Ullman J.D. Universal Single Transition Time Asynchronous

State Assignments // IEEE Trans. Comput. 1969. V. 18. № 6. P. 541-547. https://doi.

org/10.1109/T-C.1969.222707

Barg A., Blakley G.R., Kabatiansky G.A. Digital Fingerprinting Codes: Problem State-

ments, Constructions, Identification of Traitors // IEEE Trans. Inform. Theory. 2003. V. 49.

№ 4. P. 852-865. https://doi.org/10.1109/TIT.2003.809570

Stinson D.R., Wei R., Chen K. On Generalized Separating Hash Families // J. Combin.

Theory Ser. A. 2008. V. 115. № 1. P. 105-120. https://doi.org/10.1016/j.jcta.2007.

04.005

Сагалович Ю.Л. Полностью разделяющие системы // Пробл. передачи информ. 1982.

Т. 18. № 2. С. 74-82. http://mi.mathnet.ru/ppi1227

Пинскер М.С., Сагалович Ю.Л. Нижняя граница мощности кода состояний автомата //

Пробл. передачи информ. 1972. Т. 8. № 3. С. 58-66. http://mi.mathnet.ru/ppi854

Randriambololona H. (2, 1)-Separating Systems beyond the Probabilistic Bound // Israel J.

Math. 2013. V. 195. № 1. P. 171-186. https://doi.org/10.1007/s11856-012-0126-9

Сагалович Ю.Л. Верхняя граница мощности кода состояний автомата // Пробл. пере-

дачи информ. 1973. Т. 9. № 1. С. 73-83. http://mi.mathnet.ru/ppi884

Körner J., Simonyi G. Separating Partition Systems and Locally Different Sequences //

SIAM J. Discrete Math. 1988. V. 1. № 3. P. 355-359. https://doi.org/10.1137/0401035

10.

Сагалович Ю.Л. Новые верхние границы мощности разделяющих систем // Пробл.

передачи информ. 1993. Т. 29. № 2. С. 109-111. http://mi.mathnet.ru/ppi182

11.

Bassalygo L.A., Burmester M., Dyachkov A., Kabatianskii G. Hash Codes // Proc. 1997

IEEE Int. Sympos. on Information Theory (ISIT’97). Ulm, Germany. June 29 - July 4, 1997.

P. 174. https://doi.org/10.1109/ISIT.1997.613089

12.

D’yachkov A.G., Vilenkin P.A., Yekhanin S.M. Upper Bounds on the Rate of Superimposed

(s, ℓ)-Codes Based on Engel’s Inequality // Proc. 8th Int. Workshop on Algebraic and

Combinatorial Coding Theory (ACCT-8). Tsarskoe Selo, Russia. Sept. 8-14, 2002. P. 95-99.

13.

Лебедев В.С. Асимптотическая верхняя граница для скорости кодов, свободных от

(w, r)-перекрытий // Пробл. передачи информ. 2003. Т. 39. № 4. С. 3-9. http://mi.

mathnet.ru/ppi311

14.

Cohen G.D., Schaathun H.G. Asymptotic Overview on Separating Codes // Tech. Rep.

№ 248. Dept. of Informatics, Univ. of Bergen. Bergen, Norway, 2003. Available at http:

//www.ii.uib.no/~georg/sci/inf/coding/hyperpdf/cs03rep.pdf.

15.

Воробьев И.В. Границы скоростей разделяющих кодов // Пробл. передачи информ.

2017. Т. 53. № 1. С. 34-46. http://mi.mathnet.ru/ppi2225

16.

Hollmann H.D.L., van Lint J.H., Linnartz J.-P., Tolhuizen L.M.G.M. On Codes with the

Identifiable Parent Property // J. Combin. Theory Ser. A. 1998. V. 82. № 2. P. 121-133.

https://doi.org/10.1006/jcta.1997.2851

17.

Кабатянский Г.А. Идентифицирующие коды и их обобщения // Пробл. передачи ин-

форм. 2019. Т. 55. № 3. С. 93-105. https://doi.org/10.1134/S0555292319030070

18.

Kautz W., Singleton R. Nonrandom Binary Superimposed Codes // IEEE Trans. Inform.

Theory. 1964. V. 10. № 4. P. 363-377. https://doi.org/10.1109/TIT.1964.1053689

19.

Mitchell C.J., Piper F.C. Key Storage in Secure Networks // Discrete Appl. Math. 1988.

V. 21. № 3. P. 215-228. https://doi.org/10.1016/0166-218X(88)90068-6

20.

Magó G. Monotone Functions in Sequential Circuits // IEEE Trans. Comput. 1973. V. 22.

№ 10. P. 928-933. https://doi.org/10.1109/T-C.1973.223620

21.

Дьячков А.Г., Рыков В.В. Границы длины дизъюнктивных кодов // Пробл. передачи

информ. 1982. Т. 18. № 3. С. 7-13. http://mi.mathnet.ru/ppi1232

22. Stinson D.R., Wei R., Zhu L. Some New Bounds for Cover-Free Families // J. Combin.

Theory Ser. A. 2000. V. 90. № 1. P. 224-234. https://doi.org/10.1006/jcta.1999.3036

23. D’yachkov A., Vilenkin P., Macula A., Torney D. Families of Finite Sets in Which No

Intersection of ℓ Sets Is Covered by the Union of s Others // J. Combin. Theory Ser. A.

2002. V. 99. № 2. P. 195-218. https://doi.org/10.1006/jcta.2002.3257

24. Lebedev V.S. Some Tables for (w, r)-Superimposed Codes // Proc. 8th Int. Workshop on

Algebraic and Combinatorial Coding Theory (ACCT-8). Tsarskoe Selo, Russia. Sept. 8-14,

2002. P. 185-189.

25. Blackburn S.R. Frameproof Codes // SIAM J. Discrete Math. 2003. V. 16. № 3. P. 499-510.

https://doi.org/10.1137/S0895480101384633

26. Erdős P., Frankl P., Füredi Z. Families of Finite Sets in Which No Set Is Covered by

the Union of Two Others // J. Combin. Theory Ser. A. 1982. V. 33. № 2. P. 158-166.

https://doi.org/10.1016/0097-3165(82)90004-8

Воробьев Илья Викторович

Поступила в редакцию

Сколковский институт науки и технологий (Сколтех), Москва

14.04.2022

vorobyev.i.v@yandex.ru

После доработки

Лебедев Владимир Сергеевич

28.07.2022

Институт проблем передачи информации

Принята к публикации

им. А.А. Харкевича РАН, Москва

30.07.2022

lebedev37@mail.ru