Автоматика и телемеханика, № 1, 2020

(Институт проблем передачи информации им. А.А. Харкевича РАН, Москва;

Национальный исследовательский университет

“Высшая школа экономики”, Москва)

ВЕРХНЯЯ ГРАНИЦА ВЕРОЯТНОСТИ ОШИБКИ В СИСТЕМАХ

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

НА ОСНОВЕ ПОРЯДКОВЫХ СТАТИСТИК¹

Рассматривается модель канала, описывающая передачу информации

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

нове порядковых статистик. Рассматривается передача информации по

такому каналу с использованием линейного блокового кода. Целью рабо-

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

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

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

Ключевые слова: верхняя граница, вероятность ошибки, порядковые

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

недвоичные линейные коды.

DOI: 10.31857/S0005231020010092

1. Введение

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

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

выполнение требований к качеству (т.е. надежности) и скорости связи для

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

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

тоды приема (например, “жесткий” посимвольный прием или традиционные

методы “мягкого” приема, т.е. вычисления оценок надежности для каждого

из символов) оказываются неэффективными (например, если передача про-

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

ственно выше, чем мощность полезного сигнала, или если параметры канала

не известны приемнику или оценки этих параметров существенно отлича-

ются от истинных значений). Для такого рода случаев необходимы специа-

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

и ошибкам в определении параметров распределений решающих статистик.

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

зовании порядковых статистик [1-3]. Настоящая работа является результатом

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

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

¹ Исследование выполнено в ИППИ РАН за счет гранта Российского научного фонда

(проект № 14-50-00150).

134

системах в Санкт-Петербурге. Ниже будет рассмотрен метод приема, являю-

щийся обобщением метода, предложенного автором в [1]. Для описания си-

стем связи, использующих такой метод, в [4] была предложена модель канала.

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

зи, соответствующей такой модели канала, и связь этой модели с моделями

каналов, рассмотренными другими авторами. В разделе 3 будут описаны схе-

ма кодирования и правило декодирования. В разделе 4 получен вывод верх-

ней границы на вероятность ошибки (на кодовое слово) для случая, в кото-

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

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

дирования, введенное в разделе 3. Наконец, в разделе 5 приведены резуль-

таты имитационного моделирования, свидетельствующие об эффективности

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

2. Описание модели канала

Пусть q и α — натуральные числа такие, что α ≥ 2, q > α. Введем следую-

щие обозначения:

(1)

B^xq = {b = (b₁,... ,b_q)^⊺ : ∀ i ∈ {1 : q} b_i ∈ {0,1} ,w_H

(b) = x}

— множество всех двоичных векторов-столбцов веса x (здесь w_H (z) — вес

Хэмминга вектора z).

Кроме того, для любого вектора-столбца z такого, что w_H (z) < α, опре-

делим множества

{

}

S¹ (z,α) =

s:s∈B^αq,s∧z=z

(2)

{

}

S⁰ (z,α) =

s:s∈B^αq,s∧z=z

— множество двоичных векторов-столбцов веса α, покрывающих вектор-

столбец z, и множество двоичных векторов-столбцов веса α, не покрывающих

вектор-столбец z (здесь ∧ — символ поэлементной конъюнкции). Рассмот-

рим векторный канал, входом которого является вектор-столбец x, а выходом

вектор-столбец y. Канал задается условиями

∀ α ≥ 2; q > α; x ∈ B1q, y ∈ B^αq,

< p < 1,

∑

(3)

p (x) ≜

p (y | x) = p,

y∈S¹(x,α)

т.е. входом канала всегда является двоичный вектор веса 1, а выходом дво-

ичный вектор веса α (α ≥ 2), и каким бы ни был входной вектор, вектор на

выходе покрывает его с вероятностью p (¹² < p < 1). Кроме того, потребуем

выполнения дополнительных условий

∀x ∈ B1q, y_a ∈ S¹(x,α), y_b ∈ S¹(x,α), a = b : p (y_a | x) = p (y_b | x) = p₁,

(4)

∀x ∈ B1q, y_n ∈ S⁰(x,α), y_l ∈ S⁰(x,α), n = l : p (y_n | x) = p (y_l | x) = p₀.

135

Выражения (3) могут быть интерпретированы следующим образом. Пред-

ставим себе систему связи, использующую канал, состоящий из q непересе-

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

ла соответствует передаче одного q-ичного символа, причем каждому симво-

лу взаимно однозначно ставится в соответствие некоторый вектор веса 1 и

длины q (такое отображение рассматривалось во многих работах, в частно-

сти, в [5]) и передача ведется по подканалу, соответствующему позиции нену-

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

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

ные помехи различного рода (сигналы от других пользователей, преднаме-

ренные помехи, фоновые шумы и т.п.). Приемник измеряет значения неко-

торого заранее определенного параметра (например, мощности) сигнала на

выходе каждого из подканалов (будем называть такие величины “решающи-

ми статистиками”) и выбирает α номеров подканалов, которым соответствуют

“лучшие” (в смысле некоторого критерия) значения решающих статистик (на-

пример, α подканалов, у которых мощность сигнала на выходе максимальна).

Вероятность p в этом случае интерпретируется как вероятность того, что под-

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

приемника. Условия (4) выполняются в случае, если аддитивные помехи пере-

даются по тем или иным подканалам случайно и равновероятно. Для обеспе-

чения выполнения этого условия достаточно использовать псевдослучайную

перестановку на входе при передаче каждого символа (при этом перестановка

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

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

выходе.

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

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

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

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

помехами различного рода. Заметим, что описанная выше модель отличает-

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

ские каналы [6] и каналы с аддитивными помехами [7], и модифицированной

модели канала, предложенной в [8], так как вес вектора на выходе канала

канала описываемого типа фиксирован. С другой стороны, как видно из (3)

и (4), исследуемый канал принадлежит к классу дискретных симметричных

(в смысле определения [9]) каналов без памяти. Переходные вероятности, ха-

рактеризующие этот канал, равны

1-p

(5)

p₁ =

p₀ =

σ₁

σ₀

где

)

⁽q-1

⁽q - 1⁾

(6)

σ₁ = |S¹(x,α)| =

σ₀ = |S⁰(x,α)| =

α-1

Отличие модели канала рассматриваемого типа от обычных моделей дис-

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

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

136

с каким-либо символом на входе, т.е. не существует понятия “ошибочного”

(и, соответственно, “правильного”) приема одиночного символа. Сказанное, в

частности, означает, что для рассматриваемого случая невозможно исполь-

зовать классические границы, такие как [10, 11].

3. Кодирование и декодирование

Опишем теперь схему кодирования и декодирования для канала рассмат-

риваемого типа. Будем считать, что информация кодируется линейным ко-

дом C(N, K, d) над полем GF (q). Кроме того, будем считать, что известен

спектр кода, т.е. для любого веса w (d ≤ w ≤ N) известно A_w — число слов

данного веса в коде C:

∀w : d ≤ w ≤ N A_w = |v ∈ C : w_H(v) = w|.

Передача t-го символа v^mt кодового слова v^m сводится к передаче по ка-

налу соответствующего этому символу двоичного вектора x^mt. Таким об-

разом, передача кодового слова v^m = [vm1, . . . , v^mN] в рассматриваемом слу-

чае сводится к передаче соответствующей этому кодовому слову матрицы

X^m = [xm1,... ,x^mN]. Поэтому в дальнейшем будем говорить о “передаче кодо-

вого слова” и “передаче матрицы, соответствующей кодовому слову”, подра-

зумевая, что эти выражения синонимичны.

Так как выход канала всегда представляет собой вектор веса α, каждой

матрице X^m = [xm1, . . . , x^mN] (и, соответственно, каждому кодовому слову v^m)

на входе канала на выходе соответствует матрица Y^j = [yj1, . . . , y^jN ], такая

что Y^j ∈ Y, где

{

}

(7)

Y = Y : Y = [y₁,...,y_N],∀t : t = 1,...,N y_t ∈ B^α

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

Пусть определена Θ

Yj |X^l

— функция достоверности гипотезы о том, что

в результате передачи матрицы X^l была принята матрица Y ^j. Тогда декоди-

рование сводится к поиску кодового слова v^t, соответствующего матрице X^t

такой, что выполняется

(

)

(

)

(8)

∀ l = 1,...,M l = t Θ Y ^j | X^t

≥Θ Y^j |X^l

поэтому ниже для краткости будем именовать эту функцию функцией де-

кодирования. Декодирование, таким образом, сводится к поиску матрицы,

для которой выполняется (8). То, что неравенство в (8) нестрогое, означает,

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

ние функции может достигаться на различных матрицах X^l. В дальнейшем

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

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

выполняется (8).

137

Так как канал, задаваемый (3), (4), является каналом без памяти и для

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

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

(

∏ (

)

(9)

Θ Y^j|X^l

= θ y^jt,x^l

t=1

где X^l = [xl1, . . . , x^lN ] и Y^j = [yj1, . . . , y^jN ]. Выберем

{

ηθ y ∈ S¹ (x,α),

(10)

θ (x, y) =

θ y ∈ S0 (x,α),

где η > 1, θ > 0.

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

дующим образом: считается, что гипотеза о том, что вектор-столбец, соответ-

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

столбцом в принятой матрице (т.е. подканал, по которому передавался сиг-

нал, попал в список α “лучших”), имеет в η раз более высокую достоверность,

чем конкурирующая гипотеза. Заметим, что при выборе параметров функ-

σ₀ описанный выше

ции декодирования в форме θ = p₀ =1-pσ0 , η =p1p₀

1-p

σ₁

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

системах связи вероятность p не может быть точно оценена приемником, по-

этому важно отметить, что в настоящей работе будет получена граница для

произвольного η > 1. Ниже будет показано, что при использовании описанно-

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

параметра η.

4. Верхняя граница вероятности ошибки декодирования

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

декодирования для рассматриваемого случая, а именно для случая, в кото-

ром для передачи по каналу, заданному (3), (4), используется линейный код

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

правило. Задача отыскания границ для кодированной передачи с использо-

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

(по сравнению, например, с двоичным случаем, случаем случайных кодов и

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

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

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

налов, удовлетворяющих специфическим дополнительными условиям [12, 13].

Ниже будет приведен вывод верхней границы для канала, заданного (3), (4) и

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

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

использованы классические подходы, предложенные Галлагером [11] и Фа-

но [14], и граница Думана-Салехи [15], что позволит аналитически решить

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

138

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

кодирования, воспользуемся техникой, восходящей к работам Галлагера [11]

и Фано [14]: разобьем все множество матриц, которые могут быть приняты из

канала, на два непересекающихся подмножества. Первое подмножество, кото-

рое будем условно именовать “плохим” (и обозначать как Y_B), будет включать

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

рое, условно именуемое “хорошим” (и обозначаемое как Y_G), состоит из всех

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

дана матрица X^m. Тогда, учитывая, что Y_B ∩ Y_G = ∅, можно утверждать,

что

(11)

p (err |X^m ) = p (err, Y ∈ Y_B |X^m ) + p (err, Y ∈ Y_G |X^m



где p(errXm) - условная вероятность ошибки декодера, p(err, Y ∈ YBXm) -

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

множества и произошла ошибка, p(err, Y ∈ Y_G

^X^m) - условная вероятность

того, что на выходе канала матрица из “хорошего” подмножества и произошла

ошибка. Предполагается, что вероятность ошибки для матриц из “плохого”

подмножества высока, можно записать

(12)

p (err |X^m ) ≤ p (Y ∈ Y_b |X^m ) + p (err, Y ∈ Y_G |X^m

Оценим первое слагаемое в правой части (12). Рассмотрим матрицы X⁰ =

= [x⁰¹, . . . , x0N ] (соответствующую переданному кодовому слову, которое без

ограничения общности будем считать нулевым) и Y = [y₁, . . . , y_N ] (соответ-

ствующую принятой последовательности). Кроме того, рассмотрим множе-

ство

{

(

)

(

)}

(13)

I_c

Y,X⁰

≜ t : t ∈ {T,...,N},y_t ∈ S¹

x0t,α

— множество номеров столбцов матрицы Y( кот)рые покрывают соответст-

вующие столбцы матрицы X⁰ (здесь S¹

x0t,α

— множество векторов-

столбцов веса α, покрывающих t-й вектор-столбец матрицы X⁰). Введем обо-

значение



(

)

(14)

I_c

Y,X⁰

.

Заметим, что, так как функция декодирования задана в форме (9), (10), ве-

роятность ошибочного декодирования убывает с ростом i. Определим мно-

жество Y_B следующим образом:

{

}



(

)

(15)

Y_B = Y : Y ∈ Y,Ic

Y,X⁰

_<T

где T — параметр, зависящий от p и удовлетворяющий условиям

(16)

T ∈ N,

1 ≤ T ≤ N - K.

139

При таком определении первое из двух слагаемых в правой части (12) может

быть вычислено по формуле

∑

⁽N⁾

(17)

p(Y ∈ Y_b |X^m ) =

pⁱ(1 - p)^N-i.

i=0

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

рый применялся во многих работах (в частности, в [11, 15]). Суть этого подхо-

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

ло передано нулевое кодовое слово (или, точнее, матрица, соответствующая

нулевому кодовому слову). Разобьем используемый код на подкоды, каждый

из которых будет включать нулевое кодовое слово и все слова некоторого ве-

са w. Обозначим множество матриц, соответствующих кодовым словам тако-

го подкода, через S_w, а все множество матриц, соответствующих различным

кодовым словам кода C, через S_C. В силу границы объединения верна оценка

p (err, Y ∈ Y_G |X^m ) =

(

)

(

))

= P X^l = arg max

Y |X^t

=X⁰,Y ∈ Y_G

|X⁰

≤

t:X^t∈S_C

(18)

(

)

∑

(

))

≤

P X^l = arg max

Y |X^t

=X⁰,Y ∈ Y_G

|X⁰

t:X^t∈Sw

w=d

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

Салехи [15]. Для каждого из слагаемых в правой части (18) получим

(

)

(

))

P X^l = arg max

Y |X^t

=X⁰,Y ∈ Y_G

|X⁰

≤

t:X^t∈Sw

⎛

⎞

(



)_s

(19)

⎜∑

∑

(



(

)1-1

Θ(Y

^X^l )

⎟

⎜

⎟

≤

p_N(Y

_X0 )

ψ0N (Y )

⎝

⎠ ,

Θ(Y |X⁰ )

l∈Sw Y ∈YG

l=0

где ρ и s — параметры, которые будут выбираться с учетом ограничений

(20)

1 ≥ ρ > 0, s > 0

таким образом, чтобы минимизировать оценку (19), а ψ^mN(Y ) — функция пе-

рекоса, которая зависит от принятой матрицы Y и (в общем случае) от мат-

рицы X^m, соответствующей переданному слову, и удовлетворяет условиям

∑

(21)

∀ Y ∈ Y ψ^mN(Y ) > 0,

ψ^mN

(Y ) = 1.

Y ∈Y_G

Параметры ρ и s имеют тот же смысл, что и соответствующие параметры в

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

чтобы минимизировать правую часть (19). Функция перекоса также долж-

на выбираться таким образом, чтобы минимизировать правую часть (19).

140

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

бору функции перекоса, учитывающему специфику модели канала (3), (4).

В силу требований, предъявляемых к функции ψ0N (Y ), эта функция долж-

на зависеть только от Y и, возможно, от X⁰, поэтому естественно потребо-

вать, чтобы значение этой функции для каждой матрицы Y зависело от числа

столбцов в матрице X⁰, которые покрывает матрица Y^j . В дальнейшем будем

полагать, что функция ψ0N (Y ) имеет вид

{

(

)}



(22)

∀ Y = [y₁,...,y_N] : i =

t:y_t ∈S¹

x0t,α

 ψ0N(Y ) = Ψ_i,

где Ψ_i — переменные, оптимальные значения которых будут найдены ниже.

Введем обозначение

(



))_N

(

)

∏ (

)

^X^l

(23)

Ω Y,X⁰,X^l

= ω x0j,x^l

,y_j

Θ(Y^j |X⁰ )

j=1

(

)

где ω x0j, x^lj , y_j имеет вид

(

)

(

)

θ x^lj,y_j

(24)

ω x0j,x^l,yj

(

θ x0j,y_j

(

)

Заметим, что в силу (10) каждый из сомножителей ω

x0j,x^lj,y_j

в правой ча-

сти (23) отличен от единицы в том и только том случае, если j-й столбец мат-

рицы Y покрывает соответствующий столбец одной из матриц (X⁰ или X^l)

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

щие обозначения: k — число столбцов матрицы Y таких, что эти столбцы Y

покрывают соответствующие столбцы матрицы X^l и не покрывают соответ-

ствующие столбцы матрицы X⁰; g — число столбцов матрицы Y таких, что

эти столбцы Y покрывают соответствующие столбцы матрицы X⁰ и не по-

крывают соответствующие столбцы матрицы X^l.

(

)

Тогда функция Ω

Y,X⁰,X^l

принимает значение

(

)

(25)

Ω Y,X⁰,X^l

=η^k-g.

Пусть матрицы X⁰ и X^l отличаются в w столбцах. Обозначим переменной h

число столбцов таких, что матрицы X⁰ и X^l различаются в этих столбцах,

а матрица Y покрывает в этих столбцах матрицу X⁰. Заметим, что верно

неравенство max(i + w - n, 0) ≤ h ≤ min(i, w). Для каждого набора значений

четверки параметров i, h, g и k число матриц Y , для которых эти параметры

имеют соответствующие значения, равно

H(N, w, i, h, g, k) =

)

(

)

(26)

⁽N - w

σi-h1σN-w-i+h

υh-g〈1,1〉υg〈1,0〉υk〈0,1〉υw-h-k〈0,0〉,

i-h

h-g,g,k

141

где σ₁ и σ₀ задаются (6), а υ〈1,1〉, υ〈1,0〉, υ〈0,1〉 и υ〈0,0〉 задаются выражениями

)

⁽q-2

⁽q-2⁾

⁽q -2⁾

(27)

υ〈1,1〉 =

υ〈1,0〉 =

υ〈0,1〉 =

υ〈0,0〉 =

α-2

α-1

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

канала зависит только от i (количества столбцов X⁰, которые покрывает Y )

и равна

)N-i

⁽ p)i(1-p

(28)

p(Y | X⁰) = pi1pN-i0 =

σ₁

σ₀

Заметим, что

(

)

a) значения Ω

Y,X⁰,X^l

пробегают одни и те же значения для любых пар

X⁰ и X^l, зависят от числа столбцов, в которых X⁰ и X^l различаются

(это число фиксировано для конкретного подкода, из которого выбира-

ются кодовые слова, соответствующие X^l), и не зависят от конкретной

матрицы X^l;

б) для любых X^l число матриц на выходе канала Y , которым для тройки

X⁰, X^l, Y соответствуют конкретные значения g и k, пробегает одни и те

же значения H(N, w, i, h, g, k) и не зависит от конкретной матрицы X^l.

Таким образом, ни один из сомножителей в правой части (19) не зависит от

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

полученных выше соотношений (26), (28), (25), (22) выражение (19) можно

записать в виде

⎛

⎞

(

)

⎜ ∑

∑

1-¹

⎟

(29)

p (err, Y ∈ Y_G |X^m ) ≤

⎜

β_i (s,ρ) Ψ

⎟

⎝

⎠ ,

X^l∈Swi=T

l=0

где β_i(s, ρ) имеет вид

(

) (

)

∑

∑(

N-i

(30)

β_i(s,ρ) =

H(N, w, i, h, g, k)p1ρ p₀

^ρ ηs(k-g)

h=h_l g=0 k=0

Подчеркнем, что ни коэффициенты β_i(s, ρ), ни значения функции перекоса Ψ_i

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

находятся на расстоянии w от переданного кодового слова). Следовательно,

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

(

)

)_ρ

∑

1-¹

(31)

p (err, Y ∈ Y_G |X^m ) ≤ (A_w)^ρ

β_i(s,ρ)Ψ

i=T

Отметим, что A_w не зависит от s и ρ (и вообще от каких-либо параметров

системы, кроме выбора кода C и величины веса w), а функция вида z(ξ) = ξ^ρ

142

является монотонно возрастающей функцией ξ при 0 > ρ ≥ 1. Поэтому для

того, чтобы минимизировать правую часть (31) при любых фиксированных

значениях w, s и ρ, удовлетворяющих исходным условиям (1 ≥ ρ > 0, s > 0),

достаточно выбрать вектор Ψ = [Ψ₀, Ψ₁, . . . , Ψ_N ] значений функции ψ0N (Y )

таким образом, чтобы минимизировать функцию

(

)

(

)

∑

1-¹

(32)

f₀

w,ψ0N (Y )

= β_i(s,ρ)Ψ

i=T

С учетом (22) и ограничений (21) эта оптимизационная задача может быть

записана в следующем виде

(

)

∑

1-¹

(33a)

β_i(s,ρ)Ψ

→

min,

i=T

∑

(33b)

∀ i=T,...,N Ψ_i >0

ψ0N (Y ) =

γ_iΨ_i

= 1,

Y ∈Y_G

i=T

где

)

⁽N

(34)

γ_i =

σi1σN-i0.

Записав условия Каруша - Куна - Таккера для этой задачи, можно пока-

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

(

)-1 (

)^ρ

∑

β_i

(35)

∀i=T,...,N Ψ_i =

γ1-ρiβ^ρ

γ_i

i=0

Найденное аналитическое выражение (35) для функции перекоса (22) мини-

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

фиксированных ρ и s (удовлетворяющих (20)). Подставляя (35) в (31) и учи-

тывая (12) и (17), получим границу:

(

)

∑

⁽N⁾

(36)

P_e ≤

pⁱ(1 - p)^N-i +

A^ρ

(β_i (s,ρ,w))^ρ γ1-ρ

i=0

w=d

i=T

Параметры ρ, s и T находятся численной оптимизацией для каждого кон-

кретного значения p (с учетом ограничений (20), (16)), как это традиционно

делается для границы Галлагера и других границ, полученных с использова-

нием техник из [11, 14]. В следующем параграфе будут приведены результаты

имитационного моделирования.

143

5. Моделирование

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

зультатов было проведено имитационное моделирование. При моделирова-

нии использовались МДР коды со скоростями R = 1/6, R = 1/7 и R = 1/8

над GF (2⁴), полученные из кода Рида - Соломона (15,2,14) выкалыванием

проверочных символов (для скоростей R = 1/6 и R = 1/7) или, напротив, до-

бавлением общей проверки на четность (для скорости R = 1/8). В качестве

примера на рис. 1 приведено сравнение кривых вероятности ошибки (на ко-

довое слово) WER в зависимости от вероятности p для скоростей R = 1/6 и

R = 1/8 для различных значений α (α = 3, α = 4 и α = 5).

Как видно их приведенных графиков, предложенное выше выражение дей-

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

оценки падает с ростом вероятности p. На рис. 2 приведено сравнение кривых

вероятности ошибки (на кодовое слово) WER в зависимости от вероятности p

для скорости R = 1/7 для α = 4 и различных значений параметра η.

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

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

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

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

довательно, не требует информации о распределении решающих статистик и

о параметрах таких распределений. Та же особенность присуща и вычислен-

ным с использованием (36) оценкам вероятности.

моделир. (

= 40)

верхн. гр (

= 40)

моделир. (

= 12)

верхн. гр (

= 12)

0,1

моделир. (

= 8)

верхн. гр (

= 8)

0,01

0,001

0,0001

0,75

0,80

0,85

0,90

0,95

Рис. 2. Зависимость вероятности ошибки WER от вероятности p для α = 4,

R = 1/7.

6. Заключение

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

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

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

145

каналу предложено использовать конструкцию Каутса-Синглтона. Предло-

жен метод декодирования, не требующий информации о характеристиках

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

ятности ошибки декодирования (на кодовое слово). Состоятельность предло-

женной верхней границы и устойчивость предлагаемой стратегии приема и

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

онного моделирования.

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

Osipov D. Reduced-Complexity Robust Detector in a DHA FH OFDMA System

under Mixed Interference Multiple Access Communications // MACOM - 7th Int.

Work. on Mult. Acc. Comm., Halmstad, Sweden, John Wiley & Sons, 2014. P. 29-34.

Viswanathan R., Gupta S., Nonparametric Receiver for FH-MFSK Mobile Radio //

IEEE Trans. Commun. 1985. V. 33. No. 2. P. 178-184.

Kreshchuk A., Potapov V. On applying one-sample goodness-of-fit statistics to coded

FSK decoding // REDUNDANCY 2016 - XV Int. Symp. Probl. Redund. Inf. Contr.

Syst., St. Petersburg, Russia, IEEE, 2016. P. 66-70.

Osipov D. An upper bound on the error probability of a communication system with

nonparametric detection // REDUNDANCY 2016 - XV Int. Symp. Probl. Redund.

Inf. Contr. Syst., St. Petersburg, Russia, IEEE, 2016. P. 100-104.

Kautz W.H., Singleton R.C. Nonrandom Binary Superimposed Codes // IEEE

Transact. Inform. Theory. 1964. No. 4. P. 363-377.

Chang S.C., Wolf J.К. On the T-User М-Frequency Noiseless Multiple-Access

Channels with and without Intensity Information // IEEE Trans. Inform. Theory

1981. V. 27. No. 1. P. 41-48.

Зигангиров К.Ш., Попов С.А., Чепыжов В.В. Недвоичное сверточное кодирова-

ние в канале с преднамеренными помехами // ППИ. 1995. Т. 31. № 2. С. 84-101.

Осипов Д.С., Фролов А.А., Зяблов В.В. О пропускной способности для поль-

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

при наличии ошибок // ППИ. 2013. Т. 49. № 4. С. 13-27.

Cover T.M., Thomas J.A. Elements of Information Theory. N.Y.: Wiley, 2006.

10.

Herzberg H., Poltyrev G. Techniques of bounding the probability of decoding error

for block coded modulation structures // IEEE Trans. Inform. Theory. 1994. V. 40.

No. 3. P. 903-911.

11.

Gallager R.G. A simple derivation of the coding theorem and some applications //

IEEE Trans. Inform. Theory. 1965. V. 11. No. 1. P. 3-18.

12.

Bennatan A., Burshtein D. On the application of LDPC codes to arbitrary discrete-

memoryless channels // IEEE Trans. Inform. Theory. 2004. V. 50. No. 3. P. 417-438.

13.

Erez U., Miller G. The ML decoding performance of LDPC ensembles over Z_q //

IEEE Trans. Inform. Theory. 2005. V. 51. No. 5. P. 1871-1879.

14.

Fano R.M. Transmission of Information. M.I.T Press and John Wiley & Sons, 1961.

15.

Duman T.M., Salehi M. New performance bounds for turbo codes // IEEE Trans.

Commun. 1998. V. 46. No. 6. P. 717-723.

Статья представлена к публикации членом редколлегии В.М. Вишневским.

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

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

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

146