ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ
Том 55
2019
Вып. 4
УДК 621.391.1 : 519.2
© 2019 г.
М.В. Бурнашев
О ГРАНИЦАХ СНИЗУ ДЛЯ СПЕКТРА ДВОИЧНОГО КОДА1
Уточняется оценка снизу для спектра двоичного кода. Дается простой вывод
известной границы для вероятности необнаружения ошибки двоичного кода.
Ключевые слова: спектр двоичного кода, код постоянного веса, вероятность
необнаружения ошибки.
DOI: 10.1134/S055529231904003X
§ 1. Введение
Рассмотрим двоичное пространство En = {0, 1}n векторов {x} с расстоянием
Хэмминга d(x, u) = ∥x - u∥. Для заданного параметра R, 0 < R < 1, выберем
множество XM = {x1, . . . , xM } ⊂ En из M = 2Rn различных векторов {xi}, и будем
называть его (M, n)-кодом C. Для (M, n)-кодов C введем величины
d(C) = min
d(x, y), d(M, n) =
max d(C).
(1)
x,y∈C
C⊆En, |C|=M
Мощность множества A обозначаем через |A|. Спектр кода (распределение рассто-
яний) B(C) = (B0, B1, . . ., Bn) - это (n + 1)-вектор с компонентами
Bi = |C|-1|{(x, y) : x, y ∈ C, d(x, y) = i}|, i = 0, 1, . . ., n.
(2)
Введем шары и сферы в En
Bx(r) = {u : d(x, u) ≤ r}, Sx(r) = {u : d(x, u) = r}, x, u ∈ En.
(3)
Всюду далее log z = log2 z, h(z) = h2(z) = -z log2 z - (1 - z)log2(1 - z).
§2. Граница снизу для спектра кода
Введем функцию [1] (0 ≤ τ ≤ α ≤ 1/2)
α(1 - α) - τ(1 - τ)
G(α, τ) = 2
√
≥ 0.
(4)
1+2
τ (1 - τ)
Для α, τ, таких что 0 ≤ τ ≤ α ≤ 1/2 и h2(α) - h2(τ) = 1 - R, введем функцию [2]
∫
√
P +
P2 - 4Qy2
(α - ω/2)
μ(R, α, ω) = h2(α) - 2 log
dy - (1 - ω)h2
,
Q
1-ω
(5)
0
P = α(1 - α) - τ(1 - τ) - y(1 - 2y), Q = (α - y)(1 - α - y).
1 Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных
исследований (номер проекта 19-01-00364).
76
Определим функцию δGV(R) ≤ 1/2 (границу Варшамова - Гилберта) как
1 - R = h2(δGV(R)),
0 ≤ R ≤ 1.
(6)
Важность функции μ(R, α, ω) и ее связь со спектром кода {Bi} определяет сле-
дующий вариант теоремы 5 из [2] (см. также доказательство теоремы 2 в [3]).
Теорема 1. Для любого (R,n)-кода и любого α ∈ [δGV(R),1/2] существует ω,
0 ≤ ω ≤ G(α,τ), где h2(τ) = h2(α) - 1 + R, а G(α,τ) определено в (4), такое что
n-1 log Bωn ≥ μ(R, α, ω) + o(1), n → ∞,
(7)
где функция μ(R, α, ω) > 0, определенная в (5), имеет также представление (13).
Отметим, что параметр α определяет код постоянного веса αn, которым заменя-
ется исходный код (с помощью леммы Элайеса - Бассалыго) [1-3].
Введем величину R0 формулой [4, 5]
R0 = h2(τ0) ≈ 0,30524,
(8)
где τ0 ≈ 0,054507 - единственный корень уравнения
[
]
1
1-τ
(1 - 2τ) 1 +
√
- ln
= 0.
(9)
2
τ (1 - τ)
τ
Для 0 ≤ R ≤ R0 наилучшей в теореме 1 является величина α = 1/2 [5, за-
мечание 4], так как такое α одновременно минимизирует G(α, τ) и максимизирует
μ(R, α, ω) для всех ω. При α = 1/2 имеем [6, формула (33)]
μ(R, 1/2, ω) = -2(1 - ω) log(1 - ω) - log τ - 2(1 - τ) log(1 - τ) +
+ (1 - 2τ) log(τ - ω + g) + log[1 - ω - (1 - 2τ)g] - 2ω log g - 2,
(10)
где
√
1 - 2τ +
(1 - 2τ)2 - 4ω(1 - ω)
τ = τ(R) = h-12(R), g = g(τ,ω) =
2
Из (10) также следует полезное выражение [3, формула (16)]
μ(h2(τ), 1/2, G(1/2, τ)) = h2(τ) + h2(G(1/2, τ)) - 1, τ ≥ 0.
(11)
Введем функцию T (A, B, ω), 0 < A ≤ B:
2
v2 - A
v+B
v+A
T (A, B, ω) = ω log(v - 1) - (1 - ω) log
+ B log
- Alog
-
v2 - B2
v-B
v-A
√
2
(v - 1)(B2 - A2)
B2ω2 - 2a1ω + a21 + a1
B2 - A
-
,
v=
,
a1 =
(12)
(v2 - B2) ln 2
ω
2
Предложение 1 [6, предложение 3]. Для функции μ(R,α,ω) имеет место
представление
(α - ω/2)
2ω
μ(R, α, ω) = (1 - ω)h2
- h2(α) + 2h2(ω) + ω log
- T(A,B,ω),
(13)
1-ω
e
где
h2(α) - h2(τ) = 1 - R, A = 1 - 2α, B = 1 - 2τ,
0 ≤ τ ≤ α ≤ 1/2.
(14)
77
§ 3. Граница снизу для спектра кода постоянного веса
Следующий результат является естественным аналогом теоремы 1 для кодов по-
стоянного веса. Его доказательство можно извлечь из доказательства теоремы 1.
Для w ≤ n/2 рассмотрим код C(w) = C(n, w) длины n и постоянного веса w, состо-
ящий из различных кодовых векторов {x}. Обозначим через B(w)i его спектральные
величины, определенные в (2).
Теорема 2. Для любого (R,n)-кода постоянного веса αn, α ≤ 1/2, и любого
τ ≤ α существует ω, 0 ≤ ω ≤ G(α,τ), такое что
n-1 log B(αn)ωn ≥ μ(R, α, τ, ω) + o(1), n → ∞,
(15)
где (см. (12))
μ(R, α, τ, ω) = R + h2(τ) - 2q0(α, τ, ω/2), q0(α, τ, ω/2) =
)
)
( ω
( ω
ω
ω
1
= h2(τ) - αh2
- (1 - α)h2
-
log
+
T (A, B, ω),
(16)
2α
2(1 - α)
2
e
2
A = 1 - 2α, B = 1 - 2τ.
Замечание 1. Для небольших w имеет смысл сначала заменить C(w) на код C(w1)
с w1 < w (как это делается в доказательстве теоремы 1 [2,3]), а затем исследовать
код C(w1). Мы не делаем этого, чтобы не усложнять формулы.
§ 4. Уточнение границы снизу для спектра кода
Граница снизу (7) из теоремы 1 с ω ∈ [0, G(α, τ)] была ориентирована на ана-
лиз функции надежности E(R, p) канала ДСК(p) [2, 3, 5, 6]. При этом можно бы-
ло пренебречь малыми величинами ω (важной являлась только максимальная ве-
личина G(α, τ)). Однако в некоторых других применениях теоремы 1 (например,
в проверке гипотез с информационными ограничениями [7, 8]) нельзя пренебрегать
малыми величинами ω. Поэтому там требуется результат, аналогичный теореме 1,
но для ω, достаточно отделенных от 0. Следующий результат - один из возможных
(см. доказательство в Приложении).
Теорема 3. Для любого (R,n)-кода постоянного веса αn, α ≤ 1/2, любых τ ≤
≤ α и r1 < G(α,τ)/2, таких что
max {2q0(α, τ, v) + h2(2v)} - h2(τ) ≤ R,
(17)
0≤v≤r1
или, если выполнено более простое условие
h2(2r1) + h2(τ) ≤ R,
(18)
существует ω, 2r1 ≤ ω ≤ G(α, τ), такое что выполняется неравенство (15).
При r1 = 0 теорема 3 переходит в теорему 2.
§5. Об одной полезной формуле
В [6, лемма 4] было показано, что для любых α, τ, таких что h2(α)-h2(τ) = 1-R,
справедлива формула
μ(R, α, G(α, τ)) = L(G(α, τ)) + R - 1,
(19)
где
[2t1(ω) - ω]
1-
√1 - 2ω
L(ω) = 2h2[t1(ω)] - ω - (1 - ω)h2
,
t1(ω) =
(20)
2(1 - ω)
2
78
На самом деле, для L(ω) из (20) имеется простая формула (22), из которой следует
Лемма 1. Для любых α,τ, таких что h2(α) - h2(τ) = 1 - R, верна формула
μ(R, α, G(α, τ)) = h2(G(α, τ)) + R - 1.
(21)
Доказательство. После замены в (20) переменной 1 - 2ω = u2 имеем
)
[
]
2
(1-u
(1-u)
1-u2
(1 + u2)
(1 - u)2
L(ω) = L
= 2h2
-
-
h2
2
2
2
2
2(1 + u2)
После некоторых преобразований получаем для L(ω) формулу
L(ω) = h2(ω).
(22)
Из (19) и (22) следует формула (21). ▴
Формула (22) обобщает формулу (11) на случай α < 1/2.
Замечание 2. Формула (21) весьма упростила бы некоторые вычисления в [6].
§ 6. Еще одна граница снизу для спектра кода
Еще одна граница снизу для спектра кода принадлежит Левенштейну и менее
известна, так как она содержится внутри доказательства теоремы из [4]. Приятной
особенностью этой простой границы является ее очень короткое и изящное доказа-
тельство. При этом она может быть полезной в некоторых применениях. Например,
с ее помощью Левенштейн получил (упрощенный) аналог границы (35). Представ-
ляется полезным привести эту границу. Для этого введем функцию (см. (2))
∑
Ti(C) =
Bj(C) = |C|-1|{(x, y) : x, y ∈ C, d(x, y) ≤ i}|, i = 0, 1, . . ., n.
(23)
j=0
Иными словами, Ti(C) - среднее число кодовых слов y на расстоянии не более чем i
от кодового слова x.
Следующий результат является частью доказательства теоремы из [4].
Предложение 2. Для любого (M,n)-кода C и любого натурального K, 2 ≤
K ≤ M, справедливо неравенство (см. (1))
M-K+1
Td(K,n)(C) ≥
(24)
2(K - 1)
Доказательство. Рассмотрим код C как граф G с M вершинами x ∈ C. Каж-
дую пару x, y ∈ G соединим ребром, если d(x, y) ≤ d(K, n). Тогда из определе-
ния (1) величины d(K, n) следует, что не существует подмножество A ⊆ En, такое
что |A| = K и все расстояния между вершинами A больше d(K, n). Это означает,
что максимальное независимое подмножество графа G содержит менее K вершин.
Тогда по теореме Турана [9, теорема 13.4.1] граф G содержит не менее (M - K +
+ r+1)(M -r)/[2(K -1)] ребер, где r - остаток от деления M -1 на K -1. Так как
0 ≤ r < K - 1, то эта оценка снизу достигает минимума при r = 0, откуда следует
формула (24). ▴
Известно, что если d(K, n) = δn и K = 2γn, то [1, формула (1.5)]
√
]
[1
γ ≤h
-
δ(1 - δ) ,
0 ≤ δ ≤ 1/2.
(25)
2
Граница сверху (25) - наилучшая известная для 0,273 ≤ δ ≤ 1/2. При δ < 0,273
известна оценка лучше (см. [1]).
79
Если d(K, n) = δn, M = 2Rn и K = 2γn-1, γ ≤ R, то из (24) и (25) получаем
√
]
1
[1
lim
log Tδn(C) ≥ R - γ ≥ R - h
-
δ(1 - δ) ,
0 ≤ δ ≤ 1/2.
(26)
n→∞ n
2
Из определений (2) и (23) следует
1
1
lim
log Tδn(C) = max
lim
log Bωn(C).
(27)
n→∞ n
0≤ω≤δ
n→∞ n
Поэтому из (26) и (27) получаем
Предложение 3. Для любого (M,n)-кода C и любого 0 ≤ δ ≤ 1/2, такого что
[
√
]
h
1/2 -
δ(1 - δ)
≤ R, существует ω, 0 ≤ ω ≤ δ, такое что
√
]
1
[1
lim
log Bωn(C) ≥ R - h
-
δ(1 - δ)
(28)
n→∞ n
2
Аналогичный результат можно получить и для кодов постоянного веса. Также
при δ < 0,273, используя вместо (25) лучшую оценку из [1], можно несколько усилить
границу (28).
Замечание 3. Можно проверить, что граница снизу (7) (даже при α = 1/2) силь-
нее, чем (28), при всех R > 0.
§7. Вероятность необнаружения ошибки
Вероятность необнаружения ошибки Pue(C, n) для (n, R)-кода C в канале ДСК(p)
возникает в системах передачи с обратной связью и переспросом [2,4,10,11]. В таких
системах, если приемник получает сигнал, отличный от кодового слова, он требует
повторной передачи сигнала. Вероятность Pue(C, n) связана со спектром {Bi} кода
(см. (2)) формулой
∑
Pue(C, n) =
Bipi(1 - p)n-i.
(29)
i=1
При заданной скорости передачи R нас будет интересовать функция надежности
Eue(R, p), связанная с Pue(C, n)
1
1
Eue(R, p) = limsup
log
,
(30)
n→∞ n
Pue(R, n, p)
где Pue(R, n, p) - минимально возможная при заданной скорости R вероятность необ-
наружения ошибки Pue(C, n). Тогда с помощью оценки (7) имеем
1
1
Eue(R, p) = lim
log
= -logq -
n→∞ n
max[Bipi(1 - p)n-i]
i
1
− lim
max{log Bi - i log z} ≤ - log q - max
min V (R, α, ω, p),
(31)
n→∞ n
i
α≤1/2
ω≤G(α,τ)
где
V (R, α, ω, p) = μ(R, α, ω) - ω log z, z = q/p, q = 1 - p,
(32)
и (см. (4))
0 ≤ τ ≤ α ≤ 1/2, h(α) - h(τ) = 1 - R.
80
Для функции μ(R, α, ω) также имеем [5, предложение 1]
√
(1 - ω)
(2α - ω)(2 - 2α - ω)
μ′ω(R, α, ω) = log
√
,
a1 - ω(1 - ω) +
(1 - 2τ)2ω2 - 2a1ω + a2
1
1-G
μ′ω(R, α, ω)
= log
,
μ′′ωω(R, α, ω) < 0,
ω=G
(33)
G
G = G(α,τ), a1 = 2[α(1 - α) - τ(1 - τ)],
dμ(R, α, ω)
dV (R, α, ω, p)
=
> 0, α0(R) = h-12(1 - R) ≤ α < 1/2, ω > 0,
dα
dα
и тогда
(1 - G)p
V ′ω(R,α,ω,p)
= log
,
V ′′ωω(R,α,ω,p) < 0.
(34)
ω=G
Gq
Так как функция V (R, α, ω, p) вогнута по ω (см. (34)), то в силу формулы (21)
оптимизация в правой части (31) становится, по существу, технической задачей.
Естественно ожидать, что минимум по ω в (31) достигается при ω = G(α, τ), и тогда
останется только максимизация по α ≤ 1/2. В результате мы должны получить
Предложение 4. Для функции Eue(R,p) справедлива оценка сверху
{1 - R - log q - h(G0(R)) + G0(R) log z, p ≤ G0(R),
Eue(R, p) ≤
(35)
1-R,
p ≥ G0(R),
где
G0(R) = min G(α, τ), z = q/p,
(α,τ )∈A(R)
(36)
A(R) = {(α, τ) : 0 ≤ τ ≤ α ≤ 1/2, h(α) - h(τ) = 1 - R}.
Замечание 4. Граница сверху (35) усиливает границу из [4]. Она появлялась уже
в [2, теорема 1], однако ее доказательство (без аналитических свойств (33) функции
μ(R, α, ω) и формулы (21)) довольно запутано и вызывает некоторые вопросы. На-
шей целью является только простой вывод границы (35) из этих свойств.
Доказательство. Для R ∈ (0,1) и α ∈ [δGV(R),1/2] введем величину
τR(α) = h-12 (h2(α) - 1 + R) ≤ α.
(37)
Так как V′′ωω < 0, то минимум по ω в (31) достигается в граничной точке ω = 0
или в граничной точке ω0 = G(α, τR(α)). Так как μ(R, α, 0) = V (R, α, 0, p) = 0, то
из (31) имеем
min V (R, α, ω, p) = min {0, V (R, α, G(α, τ), p)} , h2(α) - h2(τ) = 1 - R.
ω≤G(α,τ)
Поэтому в силу формулы (21)
{
}
Eue(R, p) ≤ - logq - min
0, max V (R, α, G(α, τ), p)
=
(α,τ )∈A(R)
{
}
= -logq - min
0, R - 1 + max
{h(G(α, τ)) - G(α, τ)log z}
≤
(38)
(α,τ )∈A(R)
{
}
≤ -logq - min
0, R - 1 + max f(ω, p)
,
ω≥G0(R)
81
где
f (ω, p) = h(ω) - ω log z.
Имеем f′′ωω < 0 для ω ∈ [0, 1/2). Уравнение f′ω(ω, p) = 0 имеет единственный корень
ω = p, причем f(p,p) = -logq. Поэтому наилучшим ω = ω1(R,p) в (38) является
ω1(R, p) = max{p, G0(R)}.
Тогда (38) принимает вид
Eue(R, p) ≤ - logq - min{0, R - 1 + h(ω1(R, p)) - ω1(R, p)log z}.
(39)
Заметим, что если p ≥ G0(R) и R-1+h(p)-p logz ≤ 0 (т.е. если R ≤ 1+log(1-p)),
то из (39) получаем
Eue(R, p) ≤ 1 - R, если G0(R) ≤ p ≤ 1 - 2R-1.
(40)
Так как функция Eue(R, p) монотонно убывает по p, то неравенство (40) остается
верным для всех p ≥ G0(R). Аналогично (но проще) рассматривается случай p ≤
≤ G0(R). В результате получаем формулу (35). ▴
ПРИЛОЖЕНИЕ
Доказательство теоремы 3. Для того чтобы объяснить, откуда возникает
условие (17), нам придется повторить часть доказательства теоремы 1 из [3, теоре-
ма 2]. Для w ≤ n/2 рассмотрим код C(w) = C(n, w) постоянного веса w, состоящий из
различных кодовых слов {x}. Используя многочлены Хана Qj (i) = Q(n,w)j(i), введем
многочлен
∑
f (x) =
fjQj(x),
(41)
j=0
где f0 > 0 и fi ≥ 0, i = 1, . . . , w. Введем целое r ≥ 1. Тогда (см. (3))
∑
∑
( d(x, y))
( d(x, y))
{
}
C(w)
f
≤
f
+ 2r
max
|S0(j)|f(j/2)
(42)
2
2
0≤j<2r
x,y∈C(w)
x,y∈C(w)
d(x,y)≥2r
Замечание 5. Так как рассматривается код постоянного веса C(w), то величину
|S0(j)| в правой части формулы (42) можно было бы заменить более точным выра-
жением. Мы не стали этого делать, так как формулировка теоремы 3 излишне бы
усложнилась.
Для кода C(w) справедливо неравенство ([11, формула (1.7) и § 6.4])
∑
( d(x, y))
f
≥
C(w)
2f0.
(43)
2
x,y∈C(w)
Из (42) и (43) получаем
∑
( d(x, y))
{
}
C(w)
C(w)
f
≥
2f0 - 2r
max
|S0(j)|f(j/2)
(44)
2
0≤j<2r
x,y∈C(w)
d(x,y)≥2r
82
Для f(x) из (41) и r ≥ 1 введем множество
I(r) = {i ∈ {r, . . . , w} : f(i) > 0}.
(45)
Обозначим через B(w)i спектральные величины кода C(w), определенные в (2).
Тогда из (44) и (45) имеем
∑
{
}
( d(x, y))
f
≥
C(w)
2f0 - 2r
C(w)
max
|S0(j)|f(j/2)
(46)
2
0≤j<2r
x,y∈C(w)
d(x,y)/2∈I(r)
Так как d(x, y) принимает только четные значения, то из (46) следует
Лемма 2. Если |I(r)| > 0, то существует i ∈ I(r), такое что
{
}
f0|C(w)| - 2r max
|S0(j)|f(j/2)
0≤j<2r
B(w)2i ≥
(47)
|I(r)|f(i)
Пусть xwt - минимальный корень многочлена Q(n,w)t(x). Тогда xwt+1 < xwt. Исполь-
зуем в (47) тот же многочлен f(x), что и в [1, формулы (4.4) и (4.6)]:
1
f (x) =
Q2t(a)[Qt(x) + Qt+1(x)]2 ,
(48)
(a - x)
где величина t ≤ w будет выбрана позже, а параметр a ∈ (xwt+1, xwt) выбран так,
что Qt(a) = -Qt+1(a). Тогда f(a) = 0 и f(x) ≤ 0, a < x ≤ w. Коэффициенты
разложения f(x) в базисе многочленов {Qj} неотрицательны. Тогда имеем [1]
)
(
))
((n
n
(n - 2t)(n - 2t - 1)
f0 =
-
Q2t(a),
t
t-1
(t + 1)(w - t)(n - w - t)
((
)
(
))2
(49)
1
n
n
f (0) =
-
Q2t(a).
a t+1
t-1
Выберем t, так что
{
}
2r max
|S0(j)|f(j/2)
≤ f0|C(w)|/2.
(50)
0≤j<2r
Возможность выбора такого t обеспечивается условием (17) и показывается далее.
Если выполнено (50), то (см. (47))
{
}
f0|C(w)| - 2r max
|S0(j)|f(j/2)
≥ f0|C(w)|/2.
0≤j<2r
В силу (42) для r ≤ a - 1 множество I(r) имеет вид
I(r) = {i ∈ {r, . . . , w} : f(i) > 0} = {r, . . . , a - 1},
и тогда в силу (47) и (50) для некоторого i ∈ [r, a - 1] имеем
f0|C(w)|
f0|C(w)|
B(w)2i ≥
≥
(51)
2|I|f(i)
2xwtf(i)
Оценим величины f0, f(i), xwt в правой части (51). Из (48) и (49) имеем
f0
(n)
(n - 2t + 1)(n - 2t)(n - 2t - 1)(a - i)
=
(52)
f (i)
t (n - t + 1)(t + 1)(w - t)(n - w - t) [Qt(i) + Qt+1(i)]2
83
Рассмотрим асимптотический случай, когда w = αn, i = ξn, t = τn, где τ ≤ α ≤
≤ h-12(R), n → ∞. Известно [1, формула (B.21); 11], что
xαnτn
G(α, τ)
=
+ o(1) для всех τ ≤ α ≤ 1/2.
(53)
n
2
Обозначим
1
q(α, τ, ξ) = lim
log Q(n,αn)τn(ξn).
(54)
n→∞ n
Тогда из (52) следует
1
f0
lim
log
= h2(τ) - 2q(α, τ, ξ).
(55)
n→∞ n
f (i)
Для функции q(α, τ, ξ) из (54) справедлива оценка сверху [2; 3, лемма 4]
G(α, τ)
q(α, τ, ξ) ≤ q0(α, τ, ξ), ξ <
,
(56)
2
где q0(α, τ, ξ) определено в (16) и (12).
Замечание 6. Возможно, в формуле (56) выполняется равенство, но это требует
дополнительного исследования (см. [3, замечание 5]).
Из (50), (55) и (56) для w = αn, j = ηn, t = τn имеем
1
f0
lim
log
≥ h2(τ) - 2q0(α, τ, η/2), η < G(α, τ).
(57)
n→∞ n
f (j/2)
Так как a ∈ (xwt+1, xwt) и i ∈ [r, a - 1], то при r = r1n в силу (53) достаточно иметь
a-1
xαnτn
G(α, τ)
r1 ≤
=
+ o(1) =
+ o(1), τ ≤ α ≤ 1/2.
(58)
n
n
2
Заметим, что |S0(ηn)| = 2h(η)n[1+o(1)], n → ∞. Поэтому, используя (57) при j = ηn,
t = τn, получаем, что для того чтобы можно было выбрать t (т.е. τ), такое что
справедливо (50), достаточно чтобы при n → ∞ выполнялось условие (17). Тогда
в силу (51) для любых τ ≤ α и r1 < G(α, τ)/2, таких что выполняется условие (17),
для некоторого ξ ∈ [r1, G(α, τ)/2] имеем
1
lim
log B(αn)2ξn ≥ R + h2(τ) - 2q0(α, τ, ξ).
(59)
n→∞ n
Из (59) следует теорема 3, если выполняется условие (17).
Остается показать, что условие (17) выполнено, если справедливо (18). Заметим,
что для левой части условия (17) имеем (так как 2r1 < G(α, τ) ≤ 1/2)
max
{2q0(α, τ, v) + h2(2v)} - h2(τ) ≤ 2 max {q0(α, τ, v)} + h2(2r1) - h2(τ).
(60)
0<v≤r1
0<v≤r1
Для функции q0(α, τ, u) в (60) выполняется следующий результат.
Лемма 3. Имеем
[q0(α, τ, u)]′u ≤ 0, если u ≤ α;
(61)
[q0(α, τ, u)]′u ≥ 0, если u ≥ α,
и поэтому
maxq0(α, τ, u) = q0(α, τ, 0) = h2(τ).
(62)
u≤α
84
Доказательство. Представление (16) функции q0(α,τ,u) идет из ее первона-
чального вида [2; 3, лемма 4] (см. обозначения в (12))
)
(u)
( u
2u
q0(α, τ, u) = h2(τ) - αh2
- (1 - α)h2
- 2u log
+I1,
α
1-α
e
2u
∫
√
(63)
1
I1 =
log f1(y)dy, f1(y) = y2 - y + a1 + B2y2 - 2a1y + a21.
2
0
Тогда из (63) имеем
[
√
]
[q0(α, τ, u)]′u = - log[y2 - 2y + 1 - A2] + log y2 - y + a1 + B2y2 - 2a1y + a2
,
1
где y = 2u. После стандартного анализа получаем (61) и (62). ▴
Заметим, что G(α, τ)/2 ≤ 2α для любых α, τ. Поэтому в силу (62) для любого
r1 < G(α, τ)/2 формула (60) принимает вид
max {2q0(α, τ, v) + h2(2v)} - h2(τ) ≤ h2(2r1) + h2(τ).
(64)
0<v≤r1
Это завершает доказательство теоремы 3. ▴
Автор благодарит рецензента за конструктивные критические замечания, улуч-
шившие статью.
СПИСОК ЛИТЕРАТУРЫ
1. McEliece R.J., Rodemich E.R., Rumsey H., Jr., Welch L.R. New Upper Bounds on the
Rate of a Code via the Delsarte-MacWilliams Inequalities // IEEE Trans. Inform. Theory.
1977. V. 23. № 2. P. 157-166.
2. Litsyn S. New Upper Bounds on Error Exponents // IEEE Trans. Inform. Theory. 1999.
V. 45. № 2. P. 385-398.
3. Бурнашев М.В. Спектр кода и функция надежности: двоичный симметричный канал //
Пробл. передачи информ. 2006. Т. 42. № 4. С. 3-22.
4. Левенштейн В.И. О прямолинейной границе для экспоненты вероятности необнару-
женной ошибки // Пробл. передачи информ. 1989. Т. 25. № 1. С. 33-37.
5. Бурнашев M.В. Усиление оценки сверху для функции надежности двоичного симмет-
ричного канала // Пробл. передачи информ. 2005. Т. 41. № 4. С. 3-22.
6. Бурнашев M.В. О функции надежности ДСК: расширение области, где она известна в
точности // Пробл. передачи информ. 2015. Т. 51. № 4. С. 3-22.
7. Бурнашев M.В., Амари Ш., Хан Т.С. О некоторых задачах проверки гипотез с инфор-
мационными ограничениями // Теория вероятностей и ее применения. 2000. Т. 45. № 4.
С. 625-638.
8. Shimokawa H., Han T.S., Amari S. Error Bounds of Hypothesis Testing with Data Com-
pression // Proc. 1994 IEEE Int. Sympos. on Information Theory (ISIT’94). Trondheim,
Norway. June 27 - July 1, 1994. P. 114.
9. Оре О. Теория графов. М.: Наука, 1980.
10. Левенштейн В.И. О границах вероятности необнаружения ошибки // Пробл. передачи
информ. 1977. Т. 13. № 1. С. 3-18.
11. Левенштейн В.И. Границы для упаковок метрических пространств и некоторые их
приложения // Проблемы кибернетики. Вып. 40. М.: Наука, 1983. С. 43-110.
Бурнашев Марат Валиевич
Поступила в редакцию
Институт проблем передачи информации
11.09.2019
им. А.А. Харкевича РАН
После доработки
burn@iitp.ru
05.11.2019
Принята к публикации
12.11.2019
85
