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

Том 57

2021

Вып. 4

УДК 621.391 : 519.724

А.Г. Дьячков , Д.Ю. Гошкодер

НОВЫЕ НИЖНИЕ ГРАНИЦЫ ДЛЯ ДОЛИ ИСПРАВЛЯЕМЫХ ОШИБОК

ПРИ СПИСОЧНОМ ДЕКОДИРОВАНИИ В КОМБИНАТОРНЫХ

ДВОИЧНЫХ КАНАЛАХ СВЯЗИ

Целью данной статьи являются восстановление и развитие результатов нео-

публикованной рукописи А.Г. Дьячкова. Рассматривается дискретный канал

без памяти (ДКБП) и доказывается теорема об экспоненциальной границе вы-

брасывания при декодировании списком фиксированной длины L. Данный ре-

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

ности ошибки оптимальных кодов в ДКБП на модель списочного декодирова-

ния в ДКБП. В качестве приложений данного результата рассмотрены двоич-

ный симметричный канал (ДСК) без памяти и двоичный асимметричный канал

(Z-канал) без памяти. Для обоих рассматриваемых каналов выведена нижняя

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

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

ние списком фиксированной длины L. Для Z-канала эта граница получена при

произвольном распределении входного алфавита (1 - w, w), а также найдено

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

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

длины списка L к бесконечности.

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

нал, Z-канал, доля исправляемых ошибок, граница выбрасывания, декодирова-

ние списком.

DOI: 10.31857/S055529232104001X

§ 1. Введение и обзор результатов

Статья состоит из трех частей. В первой части (§ 2) мы приводим формулировку

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

списком фиксированной длины L в общем случае ДКБП с произвольными конеч-

ными входным и выходным алфавитами (теорема 1), а также исследуем логариф-

мическую асимптотику границы выбрасывания (теорема 2). Отметим, что во всех

известных нам публикациях других авторов (например, [1-5]), в которых изучались

коды со списочным декодированием, постановка задачи списочного декодирования

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

Во второй части статьи (§ 3) мы применяем построенную в первой части границу

выбрасывания к частному случаю ДСК, чтобы для соответствующего комбинатор-

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

через f_bs(L) нижнюю границу для максимально возможной доли симметричных

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

которого используется декодирование списком длины L. Данная нижняя граница

f_bs(L) со ссылкой на неопубликованную рукопись [6] как на первоисточник была

ранее приведена в работе [5].

В третьей части статьи (§ 4) мы применяем построенную в первой части грани-

цу выбрасывания при декодировании списком фиксированной длины L к важному

частному случаю ДКБП, называемому вероятностным Z-каналом, а затем к соответ-

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

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

двоичных входных символов.

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

значаемая нами через f_z(w, L) нижняя граница для максимально возможной доли

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

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

ны L, а на входном алфавите задано распределение вероятностей Q^∗ = (1 - w, w).

При любом натуральном L ≥ 1 и w ∈ [0, 1] нижняя граница f_z(w, L) вычисляется

по формуле

f_z(w, L) = w(1 - w^L).

Кроме того, нам удалось оптимизировать найденную величину, т.е. найти f_z(L) =

= max f_z(w, L) и соответствующую ей w_max(L), а также доказать, что

w∈[0,1]

(

)

lim

max f_z(w, L)

= 1.

L→+∞

w∈[0,1]

Приведем таблицу значений величин w_max(L) и f_z(L) при различных значениях

L ≥ 1:

w_max(L)

0,5

0,58

0,63

0,67

0,70

0,79

0,83

0,86

0,88

0,92

f_z(L)

0,25

0,38

0,47

0,53

0,58

0,72

0,78

0,82

0,84

0,91

Отметим, что в классическом случае L = 1 значение нижней границы f_z(1) = 1/4

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

нижней границы вероятности ошибки, называемой границей сферической упаков-

ки [7]. Также полученная граница совпадает с результатами работ [8, 9], в которых

были выведены аналогичные оценки и доказана их оптимальность.

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

о границе выбрасывания при декодировании списком фиксированной длины

в общем случае ДКБП, свойства экспоненты границы выбрасывания

Пусть на нашем канале входные и выходные слова - это последовательности

длины N из элементов конечных алфавитов:

x = (x₁,x₂,...,x_N) - входное слово, x_i ∈ [K];

y = (y₁,y₂,...,y_N) - выходное слово, y_i ∈ [J].

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

j ∈ [J] при условии отправки символа k ∈ [K] в канал. Обозначим эти вероятности

через W (k | j).

Вероятность получения слова y при передаче слова x задается следующим обра-

зом:

∏

W_N(y |x) = W(y_i |x_i).

i=1

Такой канал и называется дискретным каналом без памяти. Обозначим через X^NK

множество всевозможных слов x длины N над алфавитом [K], а через Y^NJ - мно-

жество всевозможных слов y длины N над алфавитом [J], и пусть x⁽¹⁾, . . . , x(M) -

фиксированные слова. Напомним, как в таком случае определяется декодирование

по максимуму правдоподобия (МП).

Определение 1 (МП-декодирование). При заданном y положим D_МП(y) =

= m, где m ∈ [M] - наименьшее среди всех чисел m^′ ∈ [M], для которых достигается

max W_N (y | x(m′)) = W_N (y | x(m)).

m^′∈[M]

Таким образом, при МП-декодировании возвращается статистически наиболее

вероятное для получения слово x(m).

При этом зачастую однозначно восстановить входное слово довольно сложно,

поэтому применяется декодирование списком.

Определение 2. Декодирование списком длины L - один из методов деко-

дирования кодов, при котором вместо одного кодового слова декодер возвращает

список из L возможных вариантов.

Определение 3. Декодирование списком фиксированного объема считается

успешным, если переданный кодовый вектор принадлежит набору L кодовых слов,

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

декодирования списком. Условная вероятность ошибки при передаче слова x(m) и

использовании декодирования списком длины L по методу максимума правдоподо-

бия обозначим через P(m, L). Определим набор всевозможных L-подмножеств кода,

которые не содержат слова x(m):

}

{(

)

= x(m1), . . . , x(mL)

: m_i ∈ [M^′] \ {m}, m_i = m_j, ∀i,j ∈ [L], i = j

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

следующей суммы:

∑

P (m, L) =

P_L(m,x),

x∈Xm,L

где P_L(m, x) - вероятность ошибки при передаче слова x(m), декодировании списком

длины L и возвращении декодером слов из набора x. Также определим естественным

образом максимальную вероятность ошибки:

= max P(m, L).

m∈[M]

В данной статье мы будем использовать декодирование списком длины L по ме-

тоду максимума правдоподобия (т.е. декодер будет возвращать L статистически наи-

более вероятных для получения слов).

Определение 4. Скорость кода с M кодовыми словами длины N определяет-

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

ln M

ln L

(1)

Для обычного декодирования, где L = 1, это стандартное определение скорости кода

(M = exp(RN)).

Целью § 2 является формулировка и доказательство теоремы о границе выбра-

сывания при декодировании списком фиксированной длины в общем случае ДКБП

с произвольными конечными входным и выходным алфавитами. Для этого зафикси-

руем распределение вероятностей Q = (Q(1), Q(2), . . . , Q(K)) на входном алфавите

∑

канала, такое что

Q(i) = 1, и введем следующее множество:

i=1

{

}

k = (k₁,k₂,...,kL+1) : k_i ∈ [K], i ∈ [L + 1]

|K| = KL+1.

Теорема 1. Пусть заданы дискретный канал без памяти с M^′ = 2M - 1 сло-

вами длины N и вероятности перехода W(j |k), 1 ≤ k ≤ K, 1 ≤ j ≤ J. Тогда для

любого распределения вероятностей на входном алфавите канала Q имеет место

следующая экспоненциальная верхняя граница максимальной вероятности ошибки

при декодировании списком длины L:

{

(

)}

(L + 1) ln 2

ln L

P_max(L) ≤ exp

-NE(L)

R+

(2)

где для любого R > 0 функция E^ex)(R, Q), называемая экспонентой границы выбра-

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

{

}

= sup

-ρRL + E(L)x(ρ, Q)

(3)

ρ≥1 ⎧

⎫

[

⎨

⎬

∑

∏

∑

∏

E(L)x(ρ, Q)=

-ρ ln

Q(k_i)

W (j | k_ℓ)L1

(4)

⎩

⎭

k∈K i=1

j=1 ℓ=1

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

ний, из которых в итоге и следует наша граница.

1. Рассмотрим код с M = L+1 словами x⁽¹⁾, x⁽²⁾, . . ., x(M) и схемой декодирования

списком длины L. Определим набор Y_L следующим образом:

{

}

Y_L = y ∈ Y^NJ : min W_N (y |x(i)) ≥ W_N (y |x⁽¹⁾) .

i∈[L+1], i=1

Тогда условная вероятность ошибки P_L при декодировании списком по методу мак-

симума правдоподобия, учитывая, что исходным словом является x⁽¹⁾, может быть

записана как

∑

P_L =

W_N(y |x⁽¹⁾).

y∈YL

Лемма 1. Для любого действительного числа σ ≥ 0

∑

∏

P_L ≤

W_N

(y | x⁽¹⁾)1-Lσ

W_N(y |x(i))^σ.

(5)

y∈Y^N

i=2

Доказательство. Заметим, что по определению множества Y_L получаем, что

∀y ∈ Y_L и i ∈ [L + 1], i = 1, верно неравенство W_N (y | x(i)) ≥ W_N (y | x⁽¹⁾). Тогда для

любого числа σ > 0 получаем, что

(

)_σ

W_N(y |x(i))

≥1

W_N(y |x⁽¹⁾)

и соответственно

(

)σ

∏

W_N(y |x(i))

≥ 1.

W_N(y | x(1))

i=2

Тогда справедлива следующая цепочка преобразований:

(

)_σ

∑

∏

W_N(y |x(i))

P_L =

W_N(y |x⁽¹⁾) ≤

W_N(y |x⁽¹⁾)

≤

W_N(y | x(1))

y∈YL

i=2

(

)_σ

∑

∏

W_N(y |x(i))

≤

W_N(y |x⁽¹⁾)

y∈Y^N

i=2

∑

∏

W_N

(y | x⁽¹⁾)1-Lσ

W_N(y |x(i))^σ.

y∈Y^N

i=2

Последнее равенство завершает доказательство леммы. ▴

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

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

ным выходным словам y длины N в отличие от определения условной вероятности

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

суммирование идет только по y из Y_L.

2. Рассмотрим ансамбль кодов с независимыми и одинаково распределенными

словами, число которых равно M^′ = 2M - 1, и имеющих распределение Q

(x),

x ∈ X^NK. Для m ∈ [M^′] и L ∈ [M^′ - 1] согласно определению 3 обозначим через

P (m, L) случайную величину в ансамбле, равную вероятности ошибки при передаче

слова x(m) и использовании декодирования списком по методу максимума правдопо-

добия. Отметим, что случайные величины P(m, L) при m ∈ [M^′] имеют одинаковое

распределение.

Пусть s > 0 - действительное число. Среднюю по ансамблю кодов с M^′ словами

вероятность ошибки P(m, L) в степени s будем обозначать через M_Q[P^s(m, L)]. Эта

величина равна математическому ожиданию P^s(m, L) по ансамблю, т.е.

M_Q[P^s(m, L)] =

∑

∏

[

]

(z(r))M

P^s(m, L) | x⁽¹⁾ = z⁽¹⁾, . . . , x(M′) = z(M′)

z⁽¹⁾,...,z(M′)∈X^N

r=1

Отметим, что величина M_Q[P^s(m, L)] равна некоторому действительному значению

при фиксированных L и Q и не зависит от m.

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

подкод с M словами x⁽¹⁾, x⁽²⁾, . . . , x(M), а также метод декодирования списком дли-

ны L этого кода, такой что для любого m ∈ [M] и любого s > 0 условная вероят-

ность ошибочного декодирования

P(m, L) при передаче слова x(m) удовлетворяет

неравенству

(

P (m, L) <

2M_Q[P^s(m, L)]

^s ,

(6)

где среднее значение M_Q[P^s(m, L)] не зависит от выбора значения m ∈ [M^′].

Доказательство. Напомним известное следствие из неравенства Маркова

для неотрицательной случайной величины с конечным математическим ожиданием:

Pr(η ≥ 2Mη) ≤

В качестве случайной величины η = P^s(m, L) возьмем случайную величину в ан-

самбле, равную s-й степени вероятности ошибки при передаче слова x(m) и исполь-

зовании декодирования списком по методу максимума правдоподобия. Тогда можно

использовать следствие неравенства Маркова для случайной величины η:

(

)

Pr P^s(m, L) ≥ 2M_Q[P^s(m, L)]

≤

или

(

)1⁾

Pr P(m, L) < 2^s

M_Q[P^s(m, L)]

≥

′

Последнее неравенство означает, что по крайней мере для половины слов (

) кода

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

Другими словами, последнее неравенство означает, что существуют подкод с M

кодовыми словами x⁽¹⁾, x⁽²⁾, . . . , x(M) и схема декодирования списком по методу мак-

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

любого переданного слова x(m), где m ∈ [M], условная вероятность ошибки декоди-

рования

P(m, L) удовлетворяет следующему неравенству для любого s > 0:

(

P (m, L) <

2M_Q[P^s(m, L)]

^s .

▴

3. Нашей следующей целью будет получение верхней границы средней вероят-

ности ошибки. Мы рассматриваем ансамбль кодов с M^′ = 2M - 1 независимыми и

одинаково распределенными словами. Пусть они имеют распределение Q

(x). Так-

же мы определили (см. определение 3) набор всевозможных L-подмножеств кода,

не содержащих слова x(m):

}

{(

)

X_m,L = x(m1), . . . , x(mL)

: m_i ∈ [M^′] \ {m}, m_i = m_j, ∀i,j ∈ [L], i = j

)

⁽M^′ -1

Заметим, что количество таких L-подмножеств кода равно

, так как мы

выбираем L слов из всех (всего их M^′), кроме x(m).

Лемма 3. Для ансамбля кодов с независимыми и одинаково распределенными

словами, число которых равно M^′ = 2M - 1, с распределением Q

(x) и для любого

0 < s ≤ 1 имеет место следующая оценка:

⎡

(

)σ^⎤s

∑

∏

P^s(m, L) ≤

⎣

W_N

(y | x(m))1-Lσ

W_N(y |x(mi))

⎦ ,

(7)

x∈Xm,L y∈Y^N

i=1

Более того, усредняя эту границу по ансамблю, мы получаем верхнюю границу

средней вероятности ошибки:

M_Q[P^s(m, L)] ≤

⎡

⎤_s

∑

∏

∑

∏

≤ [2(M - 1)]^L

(z(i)) ⎣

W_N(y |z(i))

1+L

⎦ ,

(8)

z⁽¹⁾,...,z(L+1)∈X^NK

i=1

y∈Y^N

i=1

где суммирование в правой части идет по всем (L + 1)-подмножествам слов из

множества с M^′ словами.

Доказательство. а) Выберем L слов из ансамбля с M^′-1 = 2M -2 словами

(т.е. выберем элемент x ∈ X_m,L) и добавим к ним слово x(m). Так мы получим под-

код из L + 1 слова, и будем рассматривать ошибку при передаче одного из этих слов

(слова x(m)). Таким образом, мы попадем в условие леммы 1, и получим верхнюю

границу вероятности ошибки декодирования списком по методу максимума правдо-

подобия при передаче слова x(m) из L + 1 данных (обозначаемую в определении 3

через P_L(m, x)). Далее, согласно определению 3 вероятность ошибки при передаче

слова x(m) из M^′ данных может быть записана в виде следующей суммы:

∑

P (m, L) =

P_L(m,x).

x∈Xm,L

Применим известное неравенство: для любого 0 < s ≤ 1

)_s

(∑

∑

a_i

≤ a^si,

i∈I

где мы берем множество X_m,L в качестве множества суммирования I, а вероятность

ошибки P_L(m,x) в качестве слагаемых a_i. Тогда получаем, что

∑

P^s(m, L) ≤

P^sL(m,x) ≤

x∈Xm,L

⎡

(

)σ^⎤

∑

∏

≤

⎣

W_N

(y | x(m))1-Lσ

W_N(y |x(mi))

⎦ .

x∈Xm,L y∈Y^N

i=1

Представленная цепочка неравенств завершает доказательство первого утвержде-

ния леммы 3.

б) Теперь усредним верхнюю границу условной вероятности ошибки при переда-

че слова x(m) по ансамблю. Мы определяем среднюю вероятность ошибки как ма-

тематическое ожидание P(m, L). По определению математического ожидания для

дискретной случайной величины и первому утверждению леммы (при σ =

1+L

1 - Lσ = σ)

M_Q[P^s(m, L)] ≤

⎡

⎤_s

)

⁽M^′ - 1

∑

∏

∑

∏

≤

(z(i)) ⎣

W_N(y |z(ℓ))

1+L

⎦ .

z⁽¹⁾,...,z(L+1)∈X^NK

i=1

y∈Y^N

ℓ=1

Первый множитель равен мощности множества X_m,L (количеству вариантов вы-

брать L слов из набора M^′ - 1 слова), а дальнейшая сумма включает вероятность

выбора множества из L + 1 слов (элемента x ∈ X_m,L и вектора x(m)) с распреде-

лением Q_N (x) и соответствующие границы вероятности ошибки. Затем, воспользо-

⁽n⁾

вавшись известным свойством биномиальных коэффициентов (

≤ n^m), можно

получить, что

M_Q[P^s(m, L)] ≤

⎡

⎤_s

∑

∏

∑

∏

≤ [2(M - 1)]^L

(z(i)) ⎣

W_N(y |z(ℓ))

1+L

⎦ ,

z⁽¹⁾,...,z(L+1)∈X^NK

i=1

y∈Y^N

ℓ=1

что завершает доказательство леммы 3. ▴

4. Далее покажем, что из лемм 2 и 3 вытекает справедливость теоремы 1. Рас-

смотрим канал без памяти, т.е. канал, для которого

∏

(x) = Q(x_i),

i=1

где x = (x₁, . . . , x_N ) - исходное слово, а Q = (Q(1), Q(2), . . . , Q(K)) - заданное рас-

пределение вероятностей на входном алфавите канала. Определим теперь макси-

мальную вероятность ошибки следующим естественным образом. Из определения 3

имеем

P_max(L) = max

P (m, L).

m∈[M]

Из оценки в лемме 2 следует, что верно следующее неравенство:

(

)

P_max(L) ≤

2M_Q[P^s(m, L)]

^s .

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

средней вероятности ошибки из леммы 3 для этого канала, полагая ρ =

при ρ ≥ 1:

(

)_ρ

P_max(L) ≤

2L+1(M - 1)^L

⎛

⎡

⎤1^⎞

∑

∏

∑

∏

⎜

⎝

(z(i)) ⎣

W_N(y |z(ℓ))

1+L

⎦ ⎟⎠.

z⁽¹⁾,...,z(L+1)∈X^NK

i=1

y∈Y^N

ℓ=1

Напомним обозначение K = {k = (k₁, k₂ . . ., kL+1) : k_i ∈ [K], i ∈ [L+1]}. Рассмотрим

следующую цепочку преобразований:

⎡

⎤1

∑

∏

∑

∏

1+L

⎦

(z(i)) ⎣

W_N(y |z(ℓ))

z⁽¹⁾,...,z(L+1)∈X^NK

i=1

y∈Y^N

ℓ=1

∑

∏

Q(z(i)v) ×

i=1 v=1

z⁽¹⁾¹,...,z(1)N∈[K]

z(L+1)1,...,z(L+1)N

∈[K]

⎡

⎤1

∑

∏

×^⎣

W (y_s | z(ℓ)s)

1+L

⎦

y1,...,yN ∈[J] ℓ=1

s=1

[

]

∑

∏

∑

∏

Q(k⁽¹⁾)_i

W (j₁ | k(N))

1+L

×...×

ℓ1

k⁽¹⁾∈K

i1=1

j1=1 ℓ1=1

[

]

∑

∏

∑

∏

Q(k(N))_i

W (j_N | k(N))1+

ℓN

k(N)∈K

iN =1

jN =1 ℓN =1

⎧

⎫

[

⎨∑

⎬

∏

∑

∏

Q(k_i)

W (j | k_ℓ)1+

⁼⎩

⎭

k∈K i=1

j=1 ℓ=1

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

⎧

⎫

[

ρN

⎨

⎬

(

)_ρ

∑

∏

∑

∏

P_max(L) ≤

2L+1(M - 1)^L

Q(k_i)

W (j | k_ℓ)1+

(9)

⎩

⎭

k∈K i=1

j=1 ℓ=1

Остается понять, почему границы (2) и (9) эквивалентны. Для этого рассмотрим

и преобразуем следующее выражение:

{

( (

))}

(L + 1) ln 2

ln L

exp

-N

-ρL R +

= exp{ρLRN + ρ(L + 1)ln2 +

+ ρL ln L} = (exp {RN})^ρL(exp {ln 2})ρ(L+1)(exp {ln L})^ρL =

)_ρL

⁽M

2ρ(L+1)L^ρL = M^ρL2ρ(L+1) ≥ (M - 1)^ρL2ρ(L+1) =

= (2L+1(M - 1)^L)^ρ,

где мы используем тот факт, что exp{RN} =

для декодирования списком дли-

ны L. Таким образом, первый член в E^ex)(R, Q) в экспоненциальной границе (2)

соответствует первым двум множителям в границе (9).

Из определения ExL)(ρ, Q) также следует, что выражение exp{-NExL)(ρ, Q)}

в экспоненциальной границе (2) соответствует коэффициенту в фигурных скобках

в границе (9). Из описанных рассуждений следует справедливость теоремы, и мы

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

декодирования списком по методу максимума правдоподобия. Теорема 1 полностью

доказана. ▴

Замечание. В частном случае L=1 имеет место следующее неравенство (см.

[7, с. 170]):

E^(1)ex(R, Q) ≥ E^(1)ran(R, Q),

где

= max

{-ρR + E₀(ρ, Q)}

0≤ρ≤1

– показатель экспоненты средней по Q-ансамблю вероятности ошибки при класси-

ческом МП-декодировании, когда длина списка L = 1, а

⎧

(

)ρ+1⎫

⎨∑

∑

⎬

E₀(ρ, Q)=

- ln

Q(k)W (j | k)ρ+

⎩

⎭

j=1

k=1

– функция Галлагера для ДКБП параметра ρ ≥ 0.

Открытой задачей остается доказательство (или опровержение) обобщения этого

неравенства на случай произвольного L ≥ 2, т.е. надо доказать или найти противо-

речащий пример ДКБП для выполнения неравенства

E(L)ex(R, Q) ≥ E(L)ran(R, Q),

где функция скорости передачи имеет вид

= max

{-ρR + E₀(ρ, Q)}.

0≤ρ≤L

В частном случае нулевой скорости передачи (R = 0) неравенство E^ex)(0, Q) ≥

≥E^r

n (0, Q) будет доказано в п. 2 теоремы 2. Решение представленной задачи в об-

щем виде принципиально важно, поскольку в работе [9] было показано, что правая

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

стей Q на входе ДКБП задает точную экспоненту средней по ансамблю вероятности

ошибки при декодировании списком длины L.

Опишем свойства полученной в теореме 1 экспоненты границы выбрасывания.

Теорема 2. Имеют место следующие свойства экспоненты границы выбра-

сывания:

1. ExL)(ρ, Q) является неубывающей функцией параметра ρ;

2. ExL)(1, Q) = E₀(L, Q). Более того, при нулевой скорости передачи имеет место

неравенство

{

}

E(L)ran(0, Q) = max

{E₀(ρ, Q)} ≤ sup

E(L)x(ρ, Q)

= E(L)ex (0, Q);

0≤ρ≤L

ρ≥1

3. E^ex)(R, Q) принимает бесконечные значения в следующем диапазоне скоростей:

ExL)(ρ, Q)

0 < R < lim

;

ρ→+∞

ρL

[

]

∑

∏

4. R^x

= limExL)(ρ,Q)

= -ln

Q(k_i)ϕ(k) , где

ρ→+∞

k∈K i=1

⎧

∑

∏

⎨

1, если

W (j | k_i) = 0,

ϕ(k) = ϕ(k₁, . . . , kL+1

j=1 i=1

⎩

в остальных случаях;

5. E^ex)(0, Q) = lim

E^ex)(R, Q) = lim

ExL)(ρ, Q);

R→0

ρ→+∞

6. Пусть ϕ(k) = 1 для любого k ∈ K. Тогда

[

]

∑

∏

∑

∏

E(L)ex(0, Q) = -

Q(k_i) ln

W (j | k_ℓ

L+1

k∈K i=1

j=1 ℓ=1

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

∑(

)

∑(

)_r

^s ≥

A_kB^sk

A_kB^rk

∏

справедливого при 0 < s ≤ r и |A_k| ≤ 1. Подставим

Q(k_i) из определения

i=1

∑

∏

ExL)(ρ, Q) вместо величин A_k из неравенства, величины

W (j | k_i

L+1 подста-

j=1 i=1

вим вместо величин B_k из неравенства, и затем применим к обеим частям неравен-

ства функцию - ln x. Такое преобразование известного неравенства и даст утвер-

ждение о монотонности функции ExL)(ρ, Q). Пункт 1 теоремы доказан.

2. Вычислим значение ExL)(ρ, Q) при ρ = 1:

⎧

⎫

⎨∑

∏(

)⎬

E(L)(1, Q) = - ln

Q(k_i)W (j | k_i)

L+1

⎩

⎭

k∈K j=1 i=1

⎧

(

)L+1⎫

∑

⎬

= -ln

Q(k)W (j | k)L1

= E₀(L, Q).

⎩

⎭

j=1

k=1

В сделанных преобразованиях величины ExL)(1, Q) стоит обосновать второе ра-

венство. Его проще понять, двигаясь по равенству справа налево: при возведении

суммы в степень L + 1 мы умножаем сумму по k на саму себя L + 1 раз. При этом

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

выбор соответствует некоторому элементу k ∈ K, т.е. при возведении суммы в сте-

пень мы получаем сумму по всевозможным k ∈ K произведений L + 1 элемента, как

в левой части рассматриваемого равенства.

Для доказательства неравенства из п. 2 теоремы воспользуемся свойствами моно-

тонности по параметру ρ функции Галлагера E₀(ρ, Q) и функции ExL)(ρ, Q) (из п. 1).

Тогда получаем, что

{

}

max

{E₀(ρ, Q)} = E₀(L, Q) = E(L)x(1, Q) ≤ sup

E(L)x(ρ, Q)

0≤ρ≤L

ρ≥1

Второй пункт теоремы полностью доказан.

3. Для доказательства п. 3 теоремы рассмотрим выражение -ρRL+ExL)(ρ, Q) =

= F(R) как линейную функцию от R с наклоном -ρ при ρ ≥ 1. Координата пересе-

чения такой функции с осью абсцисс равна

ExL)(ρ, Q)

ρL

Следовательно, при ρ → +∞ наша функция имеет вертикальную асимптоту (ко-

эффициент наклона линейной функции стремится к -∞, а сама наклонная прямая

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

ции F (R) с осью абсцисс):

(ρ, Q)

ExL)

R = lim

ρ→+∞

ρL

{

}

А тогда по определению ELex(R, Q) = sup

-ρRL + ExL)(ρ, Q)

принимает беско-

нечные значения при

ρ≥1

(ρ, Q)

ExL)

0 < R < lim

ρ→+∞

ρL

Пункт 3 доказан.

4. Для нахождения предела из п. 4 теоремы введем следующие обозначения:

∏

∑

∏

A_k = Q(k_i), B_k =

W (j | k_i

L+1 .

i=1

j=1 i=1

Тогда

)

(∑

E(L)x(ρ, Q) = -ρ ln

A_kB^ρ

k∈K

Перепишем искомый предел в новых обозначениях и сократим числитель и знаме-

натель на ρ:

(

)

∑

-ρ ln

A_kB^ρ

ExL)(ρ, Q)

k∈K

R(L)x,∞(Q) = lim

= lim

ρ→+∞

(

)

∑

- ln

(

))

A_kB^ρk

(∑

k∈K

= lim

- ln

A_kB^ρ

ρ→+∞

k∈K

Далее заметим, что

^{1, если B_k = 0,

lim

B^ρk=ϕ(k)=

ρ→+∞

в остальных случаях.

Из этого замечания и следует, что

⎡

⎤

∑

∏

R(L)x,∞(Q) = - ln⎣

Q(k_i)ϕ(k)^⎦ ,

k∈K i=1

где

⎧

∑

∏

⎨

1, если

W (j | k_i) = 0,

ϕ(k) = ϕ(k₁, . . . , kL+1

j=1 i=1

⎩

в остальных случаях.

Пункт 4 доказан.

5. По определению

{

}

{

}

= sup

-ρRL + E(L)x(ρ, Q)

≤ sup

E(L)x(ρ, Q)

= lim

E(L)x(ρ, Q),

ρ≥1

ρ→+∞

где последнее равенство вытекает из того, что функция ExL)(ρ, Q) является неубы-

вающей. Таким образом, получаем, что

E(L)ex(R, Q) ≤ lim

E(L)x(ρ, Q)

ρ→+∞

при всех R. Если lim

ExL)(ρ, Q) конечен, то для любого малого ε > 0 найдется

ρ→+∞

такое ρ, что

E(L)x(ρ, Q) ≥ lim

E(L)x(ρ, Q) - ε.

ρ→+∞

Тогда для достаточно малых R также будет выполнено неравенство

E(L)x(ρ, Q) - ρRL ≥ lim

E(L)x(ρ, Q) - ε.

ρ→+∞

Следовательно, при достаточно малых R имеет место двойное неравенство

lim

E(L)x(ρ, Q) ≥ E(L)ex(R, Q) ≥ lim

E(L)x(ρ, Q) - ε.

ρ→+∞

Отсюда и следует необходимое нам равенство пределов

lim

E(L)ex(R, Q) = lim

E(L)x(ρ, Q).

R→0

ρ→+∞

Пункт 5 доказан.

6. В предыдущем пункте теоремы мы доказали, что

E(L)ex(0, Q) = lim

E(L)ex(R, Q) = lim

E(L)x(ρ, Q).

R→0

ρ→+∞

Для доказательства данного пункта, т.е. поиска предела

⎧

⎫

[

⎨

⎬

∑

∏

∑

∏

lim

E(L)(ρ, Q) = lim

-ρ ln

Q(k_i)

W (j | k_ℓ)L1

ρ→+∞

⎩

⎭

k∈K i=1

j=1 ℓ=1

сделаем замену ρ =

и рассмотрим предел

{

}

[

]_σ

∑

∏

∑

∏

- ln

Q(k_i)

W (j | k_ℓ)L1

k∈K i=1

j=1 ℓ=1

lim

σ→0

который и будет в точности равен E^ex)(0, Q).

Для нахождения этого предела воспользуемся правилом Лопиталя. Для этого

найдем (и обозначим через γ) следующую производную:

⎛

⎧

⎞_′

[

]_σ⎫

⎨∑

∏

∑

∏

⎬

⎠

= ⎝− ln

Q(k_i)

W (j | k_ℓ)L1

⎩

⎭

k∈K i=1

j=1 ℓ=1

[

]_σ ×

∏

∑

∏

Q(k_i)

W (j | k_ℓ)L1

k∈K i=1

j=1 ℓ=1

⎛

[

]_σ

[

]⎞

∑

∏

∑

∏

∑

∏

×^⎝

Q(k_i)

W (j | k_ℓ)L1

⎠.

k∈K i=1

j=1 ℓ=1

Теперь найдем предел этой величины при σ → 0:

⎛

[

]⎞

∑

∏

∑

∏

lim

γ =-

⎝

Q(k_i)ϕ(k) ln

W (j | k_ℓ)L1

⎠.

σ→0

∏

Q(k_i)ϕ(k)k∈Ki=1

j=1 ℓ=1

k∈K i=1

В силу условия ϕ(k) = 1 для всех k ∈ K получаем, что

⎛

[

]⎞

∑

∏

∑

∏

lim

γ =-

⎝

Q(k_i) ln

W (j | k_ℓ)L1

⎠.

σ→0

∏

j=1 ℓ=1

Q(k_i)k∈Ki=1

k∈K i=1

∑

∏

Далее отметим тот факт, что

Q(k_i) = 1, так как это сумма по всевозмож-

k∈K i=1

ным элементам K вероятностей получить эти элементы, а вероятность наступления

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

[

]

∑

∏

∑

∏

lim γ = -

Q(k_i) ln

W (j | k_ℓ

L+1

σ→0

k∈K i=1

j=1 ℓ=1

Теперь можно перейти уже к нахождению величины E^ex)(0, Q). Напомним, что

предел мы считаем по правилу Лопиталя:

{

}

[

]_σ

∑

∏

- ln

Q(k_i)

W (j | k_ℓ)L1

k∈K i=1

j=1 ℓ=1

E(L)ex(0, Q) = lim

σ→0

[

]

∑

∏

∑

∏

= lim

= lim γ = -

Q(k_i) ln

W (j | k_ℓ

L+1

σ→0 1

σ→0

k∈K i=1

j=1 ℓ=1

Пункт 6 и теорема 2 полностью доказаны. ▴

§ 3. Нижняя граница для максимально возможной доли симметричных ошибок,

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

списком длины L в частном случае комбинаторного двоичного

симметричного канала связи (BS-канала)

Целью этого параграфа является применение экспоненты границы выбрасыва-

ния из теоремы 2 в частном случае ДСК для построения нижней границы для

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

че с нулевой скоростью и декодировании списком фиксированной длины в частном

случае комбинаторного BS-канала связи. Отметим тот факт, что в работе [4] именно

в частном случае ДСК построена нижняя граница вероятности ошибки, экспонента

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

Напомним, что для ДСК с вероятностью ошибки p переходные вероятности име-

ют вид W (1 | 1) = W (2 | 2) = 1 - p, W (1 | 2) = W (2 | 1) = p. Зафиксируем для данного

ДСК распределение вероятностей на входном алфавите Q^∗ = (1/2, 1/2), а также

введем следующие обозначения:

= E(L)ex(0, Q^∗),

E_ex(p, L)

= lim

p→0

- ln p

Теорема 3. Пусть -N

E_ex(p, L) - показатель экспоненты в верхней границе

вероятности ошибки при передаче слов длины N с нулевой скоростью по ДСК с

вероятностью ошибки p, а e(L)bs(R, N) - максимально возможное количество оши-

бок, исправляемых при передаче слов длины N по BS-каналу связи со скоростью R

с использованием на выходе BS-канала декодирования списком длины L.

Тогда при R = 0 справедливо следующее неравенство:

(L)

E_ex(p, L)

(0, N)

f_bs(L) = lim

≤ lim

p→0

- ln p

N →+∞

где e(L)bs(R, N) определяется в точке R = 0 по непрерывности.

Доказательство. Обозначим через P(L)(p,R,N) минимальную вероятность

ошибки при передаче слов длины N по ДСК со скоростью R с использованием

на выходе ДСК декодирования списком длины L для дискретного симметричного

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

peb

(0,N)+1(1 - p)N-eb

(0,N)-1 ≤ P(L)(p, 0, N) ≤ exp^-

Eex(p,L) .

Логарифмируя это неравенство, получим

(

)

(

)

e(L)bs(0, N) + 1

ln p +

N - e(L)bs (0,N) - 1

ln(1 - p) ≤ -NEex(p, L).

Поделим обе части на N ln p, но изменим знак неравенства, так как ln p < 0:

E_ex(p, L)

e(L)bs(0, N) + 1

N - e(L)bs (0,N) - 1 ln(1 - p)

≤

- ln p

ln p

Теперь дважды сделаем предельный переход при p → 0 и при N → +∞, учитывая

ln(1 - p)

что lim

= 0. Получаем требуемое неравенство теоремы, а именно

p→0

ln p

(L)

E_ex(p, L)

(0, N)

lim

≤ lim

▴

p→0

- ln p

N →+∞

Теорема 4. Для любого k = 1,2,...

(

)

(2k - 1)!!

f_bs(2k - 1) = f_bs(2k) =

(2k)!!

Доказательство. Воспользуемся формулой для E^ex)(0,Q^∗) из п. 6 теоремы 2

и найдем

E_ex(p, L):

[

]

∑

∏

∑

∏

= E(L)ex(0, Q^∗) = -

Q(k_i) ln

W (j | k_ℓ

L+1

k∈K i=1

j=1 ℓ=1

∑(L + 1)

[(

)

(

)

]

L+1

2-(L+1) ln

p^ℓ(1 - p)L+1-ℓ

L+1 +

(1 - p)^ℓpL+1-ℓ

ℓ

ℓ=1

[

(

) ℓ

) ℓ ]

∑

L+1

⁽L + 1⁾

⁽1-p

2-(L+1) ln (1 - p)

L+1 + p

ℓ

1-p

ℓ=1

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

количеству k_i, равных 1. Если ℓ = 0 или ℓ = L + 1, то значение величины под

знаком логарифма равно 1. Таким образом, остается суммирование по параметру

⁽L+1⁾

ℓ ∈ [L]. Под знаком суммы множитель

соответствует числу вариантов вы-

ℓ

брать элемент k ∈ K, в котором ровно ℓ элементов равны 1, и множитель 2-(L+1)

∏

равен

Q^∗(k_i).

i=1

Лемма 4. Справедливо равенство

[

]

(

) ℓ

⁽1-p⁾Lℓ

ln (1 - p)

L+1 + p

(

)

1-p

ℓ

lim

= min

,1-

p→0

ln p

L+1

Доказательство. Для нахождения этого предела воспользуемся правилом

Лопиталя:

[

]

(

) ℓ

⁽1-p⁾Lℓ

ln (1 - p)

L+1 + p

1-p

lim

p→0

ln p

(

ℓ

= lim

pL+1-1(1 - p)¹

L+1 -

L+1

p→0

L+1 (1 - p)¹

L+1 p1-Lℓ

ℓ

− (1 -

)(1 - p)

L+1

L+1 + (1 -

L+1 -

L+1

)

(

ℓ

L+1

-1p¹

L+1

= lim

pL+1-1 -

L+1

p→0

L+1 + p1-Lℓ

L+1

)

ℓ

- (1 -

)

L+1 + (1 -

L+1 -

p¹

L+1

(

)

ℓ

= lim

pL+1-1 + (1 -

L+1

p→0

L+1 + p1-Lℓ

(

)

ℓ

L+1

,1-ℓL+1 )

L+1

= lim

pL+1-1 + (1 -

p→0

L+1

(

)

ℓ

= min

,1-

L+1

Лемма 4 доказана. ▴

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

коэффициентов и результат леммы 4:

)

∑

⁽⁽2k⁾

ℓ

⁽2k⁾

f_bs(2k - 1) = 2

2-2k

2-(2k+1),

ℓ

ℓ=1

где последнее слагаемое соответствует ℓ = k. Аналогично при L = 2k получаем

(

)

∑(2k + 1)

ℓ

∑

f_bs(2k) = 2

2-(2k+1)

ℓ

2k + 1

22k

ℓ-1

ℓ=1

)

(

)

ℓ

⁽ 2k + 1

где последнее равенство следует из того, что

2k + 1

ℓ

ℓ-1

Затем отметим следующие свойства биномиальных коэффициентов:

∑

⁽2k - 1⁾

⁽2k - 1⁾⁽1)2k-1

22k-1 =

⇒

;

ℓ

ℓ=0

)

⁽ 2k

∑

22k -

⁽2k⁾

;

ℓ

(0 )

⁽2k - 1⁾

⁽2k⁾

⇒ 4

k-1

Преобразуем выражение для f_bs(2k - 1), используя свойства 1 и 3 биномиальных

коэффициентов:

∑

⁽2k - 1⁾⁽1)2k-1

⁽2k⁾⁽1)2k+1

f_bs(2k - 1) =

ℓ

ℓ=0

)

⁽ 2k - 1

⁽ 2k

⁽ 2k - 1⁾

⁽ 2k⁾

(

⁽ 2k

)

k-1

− k-1

+ k

1-^k

22k-1

22k+1

22k

Теперь применим свойство (2) и получим следующее равенство:

)

(

⁽ 2k

)

(

)

∑

f_bs(2k) =

1-^k

= f_bs(2k - 1).

22k

ℓ-1

22k

ℓ=1

Поэтому для любого числа k = 1, 2, 3, . . . справедливо следующее равенство:

)

(

⁽ 2k

)

(

)

(2k)!

f_bs(2k - 1) = f_bs(2k) =

1-^k

22k

k! k! 22k

(

)

(

)

(2k)!

(2k - 1)!!

(2k)!! (2k)!!

(2k)!!

Теорема 4 полностью доказана. ▴

Таким образом, теорема 3 утверждает, что f_bs(L) является нижней границей

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

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

двоичного симметричного канала связи и нулевой скорости передачи, а теорема 4

позволяет точно посчитать эту границу для любого наперед заданного L. Приведем

таблицу значений полученной границы:

f_bs(L)

1/4

5/16

11/32

93/256

193/512

Также можно отметить, что

(

)

(2k - 1)!!

lim

f_bs(2k - 1) = lim

f_bs(2k) = lim

k→+∞

k→+∞ 2

(2k)!!

(

)

∏

2k - 1

k=1

§4. Нижняя граница для максимальной доли асимметричных ошибок,

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

списком длины L в частном случае двоичного асимметричного Z-канала

Целью этого параграфа является применение построенной в § 2 границы выбра-

сывания при декодировании списком фиксированной длины L к важному частному

случаю ДКБП, называемому вероятностным Z-каналом, а затем к соответствующе-

му комбинаторному двоичному асимметричному каналу связи (Z-каналу), в ко-

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

двоичных входных символов.

Напомним, что для Z-канала с вероятностью ошибки p переходные вероятности

имеют вид W (1 | 1) = 1, W (1 | 2) = p, W (2 | 1) = 0, W (2 | 2) = 1 - p. Рассмотрим

для Z-канала более общий случай по сравнению с ДСК, а именно зафиксируем для

данного канала распределение вероятностей на входном алфавите Q^∗ = (1 - w, w).

Введем дополнительно следующие обозначения:

= E(L)ex(0, Q^∗),

E_ex(p, w, L)

= lim

p→0

- ln p

Теорема 5. Пусть -NEex(p, w, L) - показатель экспоненты в верхней грани-

це вероятности ошибки при передаче слов длины N по двоичному асимметричному

Z-каналу с вероятностью ошибки p, а ezL)(R, N) - максимально возможное коли-

чество ошибок, исправляемых при передаче слов длины N по Z-каналу связи со ско-

ростью R с использованием на выходе Z-канала декодирования списком длины L.

Тогда при R = 0 справедливо следующее неравенство:

E_ex(p, w, L)

ezL)(0, N)

f_z(w, L) = lim

≤ lim

p→0

- ln p

N →+∞

где ezL)(R, N) определяется в точке R = 0 по непрерывности.

Доказательство. Обозначим через P(L)(p,R,N) минимальную вероятность

ошибки при передаче слов длины N по Z-каналу со скоростью R с использованием на

выходе Z-канала декодирования списком длины L. Для двоичного асимметричного

Z-канала с нулевой скоростью передачи по условию имеем

pezL)(0,N)+11^k(1 - p)N-k-ezL)(0,N)-1 ≤ P(L)(p, 0, N) ≤ exp^-

Eex(p,w,L),

где k - число единиц, перешедших по каналу в единицы.

Логарифмируя это неравенство, получаем

(e(L)z(0, N) + 1) ln p + k ln 1 + (N - k - e(L)z(0, N) - 1) ln(1 - p) ≤ -NEex(p, w, L).

Поделим обе части на N ln p, но изменим знак неравенства, так как ln p < 0:

E_ex(p, w, L)

ezL)(0, N)

N - k - ezL)(0,N) - 1 ln(1 - p)

≤

- ln p

ln p

Теперь дважды сделаем предельный переход при p → 0 и при N → +∞, учитывая

ln(1 - p)

что lim

= 0. Получаем требуемое неравенство теоремы, а именно

p→0

ln p

E_ex(p, w, L)

ezL)(0, N)

lim

≤ lim

▴

p→0

- ln p

N →+∞

Теорема 6. Для любого натурального L и любого w ∈ [0,1] справедливо

(

)

f_z(w, L) = w

1-w^L

Более того,

(

)

f_z(L) = max

f_z(w, L) =

w∈[0,1]

L+1

(

)

lim

max f_z(w, L)

= 1.

L→+∞

w∈[0,1]

Доказательство. 1. Воспользовавшись формулой для E^ex)(0,Q^∗) из п. 6 тео-

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

[

]

∑

∏

∑

∏

= E(L)ex(0, Q^∗) = -

Q(k_i) ln

W (j | k_ℓ

L+1

k∈K i=1

j=1 ℓ=1

∑

[(

)

(

)

]

⁽L + 1⁾

L+1

(1 - w)^ℓwL+1-ℓ ln

1^ℓpL+1-ℓ

L+1 +

0^ℓ(1 - p)L+1-ℓ

ℓ

ℓ=0

где суммирование идет по параметру ℓ, который равен числу k_i, равных 1, а под

⁽L+1⁾

знаком суммы множитель

соответствует числу вариантов выбрать элемент

ℓ

∏

k ∈ K, в котором ровно ℓ единиц, а множитель (1 - w)^lwL+1-ℓ равен

Q^∗(k_i).

i=1

Если ℓ = 0 или ℓ = L + 1, то величина под знаком логарифма равна 1. Поэтому

суммирование остается лишь по ℓ ∈ [L]:

∑

[

]

⁽L + 1⁾

E_ex(p, w, L) = -

(1 - w)^lwL+1-ℓ ln pLL+1ℓ

ℓ

ℓ=1

Лемма 5. Справедливо равенство

L+1-ℓ

ln p

L+1

ℓ

lim

=1-

p→0

ln p

L+1

Доказательство. Для нахождения этого предела воспользуемся правилом

Лопиталя:

L+1-ℓ

ln p

L+1

L+1-ℓ

ℓ

lim

= lim

⁺¹ =

=1-

p→0

ln p

L+1

p→0 pLL+1ℓ

Лемма 5 доказана. ▴

Воспользуемся определением величины f_z(w, L), выражением

E_ex(p, w, L) для

асимметричного Z-канала и результатом леммы 5:

∑

⁽L + 1⁾

L+1-ℓ

f_z(w, L) =

(1 - w)^lwL+1-ℓ

ℓ

L+1

ℓ=1

∑

(L + 1)!

L+1-ℓ

(1 - w)^lwL+1-ℓ

ℓ!(L + 1 - ℓ)!

L+1

ℓ=1

∑

∑(L)

(1 - w)^lwL+1-ℓ =

(1 - w)^lwL+1-ℓ.

ℓ!(L - ℓ)!

ℓ

ℓ=1

Затем рассмотрим хорошо известное свойство биномиальных коэффициентов:

∑

⁽L⁾

1^L = ((1 - w) + w)^L =

(1 - w)^ℓw^L-ℓ =

ℓ

ℓ=0

(

)

∑

⁽L⁾

w^L +

(1 - w)^ℓw^L-ℓ = w^L +

(1 - w)^ℓw^L-ℓ.

ℓ

ℓ=1

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

личины f_z(w, L):

∑(L)

f_z(w, L) = w

(1 - w)^lw^L-ℓ = w(1 - w^L).

ℓ

ℓ=1

Первая часть теоремы доказана.

2. Найдем значение величины max f_z(w, L). Для этого решим уравнение

w∈[0,1]

(f_z(w, L))^′w = 1 - (L + 1)w^L = 0.

Отсюда получаем w_max = (L + 1)-L и

(

)

f_z(L) = max

f_z(w, L) = f_z(w_max, L) =

w∈[0,1]

L+1

(

)

Для нахождения lim

max f_z(w, L) вычислим сначала следующий предел:

L→+∞

w∈[0,1]

(

{

}

{

}

lim

= lim

exp

ln(1 + L)

= lim

exp

= 1.

L→+∞ L + 1

L→+∞

L+1

Тогда искомый предел будет равен

(

)

(

)

lim

max

f_z(w, L)

= lim

· lim

= 1 · 1 = 1.

L→+∞

w∈[0,1]

L→+∞ L + 1

L→+∞

L+1

Теорема 6 полностью доказана. ▴

Итак, теорема 5 утверждает, что значение f_z(w, L) является нижней границей до-

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

списком фиксированной длины в Z-канале с нулевой скоростью передачи, а теоре-

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

ний w и L. Таблица значений величин w_max и max f_z(w, L) (т.е. доли числа ошибок,

w∈[0,1]

исправляемых оптимальным кодом) приведена в § 1.

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

1. Elias P. List Decoding for Noisy Channels // Tech. Rep. № 335. Research Lab. of Electronics,

MIT. Cambridge, MA, USA. 1957. (Reprinted from: IRE WESCON Convention Record.

Part 2. P. 99-104). Available at https://dspace.mit.edu/handle/1721.1/4484

2. Wozencraft J.M. List Decoding. Quarterly Progress Report, Research Lab. of Electronics,

MIT. Cambridge, MA, USA. 1958. V. 48. P. 90-95.

3. Elias P. Error-Correcting Codes for List Decoding // IEEE Trans. Inform. Theory. 1991.

V. 37. № 1. P. 5-12. https://doi.org/10.1109/18.61123

4. Блиновский В.М. Нижняя граница вероятности ошибки декодирования списком фик-

сированного объема // Пробл. передачи информ. 1991. Т. 27. № 4. С. 17-33. http:

//mi.mathnet.ru/ppi578

5. Блиновский В.М. Границы для кодов при декодировании списком конечного объема //

Пробл. передачи информ. 1986. Т. 22. № 1. С. 11-25. http://mi.mathnet.ru/ppi839

6. Дьячков А.Г. Граница выбрасывания при декодировании списком фиксированной дли-

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

7. Gallager R.G. Information Theory and Reliable Communication. New York: Wiley, 1968.

8. Polyanskii N., Zhang Y. Codes for the Z-Channel, https://arXiv.org/abs/2105.01427

[cs.IT], 2021.

9. Lebedev A., Lebedev V., Polyanskii N. Two-Stage Coding over the Z-Channel, https://

arXiv.org/abs/2010.16362v2 [cs.IT], 2020.

Дьячков Аркадий Георгиевич

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

(29.09.1944 - 20.10.2021)

31.05.2021

Гошкодер Даниил Юрьевич

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

Московский государственный университет

07.11.2021

им. М.В. Ломоносова, механико-математический

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

факультет, кафедра теории вероятностей

08.11.2021

daniilgoshkoder@mail.ru