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

Том 55

2019

Вып. 2

УДК 621.391.15

В.А. Давыдов

О ПРИМЕНЕНИИ МОДУЛЬНОЙ МЕТРИКИ К РЕШЕНИЮ ЗАДАЧИ

ДЕКОДИРОВАНИЯ ПО МИНИМУМУ ЕВКЛИДОВОГО РАССТОЯНИЯ

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

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

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

двоичных кодов для рассмотренного канала, исправляющих t двоичных оши-

бок в метрике Хэмминга. Построенные коды исправляют ошибки на выходе

демодулятора с Q уровнями квантования как (t + 1)(Q - 1) - 1 ошибок в мо-

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

сложность декодирования.

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

канал с двоичным входом и Q-ичным выходом, коды в модульной метрике.

DOI: 10.1134/S0555292319020037

§ 1. Модель симметричного канала без памяти с двоичным входным

и Q-ичным выходным алфавитами

Симметричным каналом с двоичным входом и непрерывным выходом будем на-

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

• Входной алфавит U ≡ {0, 1} состоит из двух символов, обозначаемых 0 и 1.

Обозначим через Uⁿ множество векторов длины n с элементами из множества U;

• Выходной алфавит F представлен как множество вещественных чисел;

• Выход f ∈ F в заданный отсчет времени зависит только от одного входного

символа;

• Для всех выходов f выполняется свойство симметрии: Pr(f |0) = Pr(f +1|1). Под

Pr(f | x) понимается плотность распределения условной вероятности получения

из канала символа f при условии того, что по каналу передавался символ x ∈ U.

Пример функций Pr(f | 0) и Pr(f | 1) показан на рисунке.

Под вектором ошибки для кодового слова u = (u₁, u₂, . . . , u_n), u_i ∈ U, длины n

будем понимать вектор e = (e₁, e₂, . . . , e_n), e_i ∈ F , такой же длины, соответствующие

элементы которого равны разностям между вектором f = (f₁, f₂, . . . , f_n), принятым

из канала, и передаваемым словом: e_i = f_i - u_i, 1 ≤ i ≤ n.

Декодирование по максимуму правдоподобия кода G ⊂ Uⁿ означает нахождение

по заданному принятому вектору f такого кодового слова u ∈ G, которое макси-

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

тора f: P(u|f) → max [1]. Канал без памяти с аддитивным белым гауссовским

шумом согласован с метрикой Евклида. Декодирование по максимуму правдоподо-

бия в этом случае заключается в поиске такого вектора u = (u₁, u₂, . . . , u_n) ∈ G,

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

f = (f₁,f₂,...,f_n).

0,8

0,6

Pr(f | 1)

0,4

Pr(f | 0)

0,2

−1,0

-0,5

0,0

0,5

1,0

1,5

2,0

Пример зависимости Pr(f | 0) и Pr(f | 1) от f

В [2] рассматривается задача мягкого декодирования для канала с двоичным

входом и Q-ичным выходом. В такой постановке значения компонент вектора f =

= (f₁, f₂, . . . , f_n) остаются вещественными, но могут принимать ограниченное чис-

ло значений, которое будем называть выходным алфавитом. Размерность выходно-

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

фильтра. Схема квантования с Q = 8 часто применяется в системах декодирования

с мягким решением. Как отмечается в [2], характеристика такой схемы близка к

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

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

ется в поиске вектора u = (u₁, u₂, . . . , u_n) ∈ G, который находится на минимальном

расстоянии Евклида от принятого вектора f = (f₁, f₂, . . . , f_n).

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

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

vi ∈ {0, 1, . . ., Q - 1}, которому соответствует значение fi. В результате вектору

f = (f₁,f₂,...,f_n) ставится в соответствие Q-ичный вектор v = (v₁,v₂,...,v_n).

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

Q-ичным выходным алфавитом. Данный канал полностью задается множеством пе-

реходных вероятностей Pr(j | x), где Pr(j | x) - условная вероятность того, что вы-

ходной символ равен j при условии, что входной символ равен x. Будем считать,

что канал симметричен и Pr(j | 0) = Pr(Q - 1 - j | 1).

Если по каналу был передан двоичный вектор u = (u₁, u₂, . . . , u_n) ∈ Uⁿ, то ве-

роятность того, что на выходе был получен вектор v = (v₁, v₂, . . . , v_n), вычисляется

по формуле

∏

Pr(v | u) = Pr(v_i | u_i).

i=1

Логарифмируя данное выражение, получим

∑

log(Pr(v | u)) =

log(Pr(v_i | u_i)).

(1)

i=1

Декодер должен максимизировать величину Pr(v |u), которая будет максималь-

ной, если отрицательная сумма в правой части (1) минимальна. В [2] вводится ап-

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

мягком решении, которое называется символьной метрикой. Соответствующие зна-

чения в такой метрике определяются по формуле m_j = -A - B log(Pr(j | 0)). Кон-

станты A и B выбираются так, чтобы минимальное значение m_j равнялось нулю,

а остальные были положительны.

Наиболее часто используется схема, в которой m_j = j. Если число уровней рав-

но Q, то метрика принимает значения из множества {0, 1, 2, . . . , Q - 1}. Как отмеча-

ется в [2], такой выбор метрики хорошо описывает многие используемые на практике

декодеры.

Далее в данной статье рассматриваются только согласованные с евклидовой мет-

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

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

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

§2. Взаимосвязь модульной и евклидовой метрики в канале с двоичным

входным и Q-ичным выходным алфавитами

Рассмотрим канал из § 1, для которого выполняется условие Q = 2^z + 1. Пусть

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

дачи по каналу.

Двоичный вектор u = (u₁, u₂, . . . , u_n) ∈ G с элементами из множества {0, 1} при

использовании Q = 2^z + 1 уровней квантования и отсутствии ошибок рассматрива-

ется демодулятором как двоичный вектор v^∗ = (v₁, v₂, . . . , v_n) ∈ G^∗ с элементами из

множества v_i ∈ {0, 2^z} ≜ H. Таким образом, множество слов G из двоичного алфа-

вита {0, 1} будет рассматриваться демодулятором как множество двоичных слов G^∗

из двоичного алфавита {0, 2^z}.

В результате наложения ошибок в канале на вектор u^∗ = (u∗1, u∗2, . . . , u^∗n) на вы-

ходе демодулятора получается Q-ичный вектор y^∗ = (y₁, y₂, . . . , y_n) с элементами из

множества {0, 1, 2, . . . , 2^z} ≜ Z. Обозначим через Zⁿ множество векторов длины n

с элементами из множества Z.

Задача декодирования кода G^∗ по максимуму правдоподобия с использованием

2^z+1 подуровней для канала без памяти с гауссовским шумом осуществляется путем

нахождения ближайшего кодового слова v^∗ = (v₁, v₂, . . . , v_n) ∈ G^∗ к полученному

слову y^∗ = (y₁, y₂, . . . , y_n) ∈ Zⁿ с использованием расстояния в метрике Евклида

∑

d_E(y^∗; v^∗) =

√

(y_i - v_i)².

(2)

i=1

Расстояние в модульной метрике d_M (u; v) между векторами u = (u₁, u₂, . . . , u_n) ∈

∈ Zⁿ и v = (v₁,v₂,...,v_n) ∈ Zⁿ вычисляется по формуле

∑

d_M (u; v) =

|u_i - v_i|.

(3)

i=1

Вес w_M (u) вектора u = (u₁, u₂, . . . , u_n) в модульной метрике определяется как

расстояние d_M (u; 0), где 0 - нулевой вектор длины n. Если выполняется условие

d_M (u; v) = t, то будем говорить, что вектор u = (u₁, u₂, . . . , u_n) получен t-кратными

ошибками из вектора v = (v₁, v₂, . . . , v_n).

Введем отношение частичного порядка на множестве Zⁿ векторов длины n. По-

ложим u ≫ v, если для всех 1 ≤ i ≤ n выполняется неравенство v_i ≤ u_i. В том

случае, если указанное неравенство выполнено не для всех 1 ≤ i ≤ n, будем назы-

вать u и v несравнимыми векторами. Пусть d_M (u; v) = t и выполняется условие

u ≫ v. Тогда будем говорить, что вектор u получен из вектора v путем t однона-

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

уменьшающие ошибки.

Обозначим через J множество векторов длины n, компоненты которых принад-

лежат множеству {0, 1, 2, . . . , 2^z}. Для мощности множества J выполняется условие

|J| = (2^z + 1)ⁿ.

Пусть u^∗ и v^∗ - векторы длины n, компоненты которых принадлежат множеству

{0, 2^z} = H. Обозначим через W множество таких векторов. Заметим, что для

мощности данного множества выполняется условие |W | = 2ⁿ . Фактически векторы

из множества W являются вершинами n-мерного куба, а вектор y^∗ - произвольной

точкой такого куба. Для кода B^∗ и множеств W и J выполняется условие B^∗ ⊂

⊂W ⊂J.

Теорема. Для любого вектора y^∗ = (y₁,y₂,...,y_n) ∈ J и любой пары векторов

u^∗ ∈ W и v^∗ ∈ W выполняется равенство

d2E(y^∗; v^∗) - d2E(y^∗; u^∗) = 2^z(d_M (y^∗; v^∗) - d_M (y^∗; u^∗)).

(4)

Доказательство. Рассмотрим векторы u^∗ ∈ W и v^∗ ∈ W . Заметим, что

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

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

данные векторы различны. Без потери общности будем считать, что на первых ℓ

позициях вектора u^∗ расположен символ 2^z, а на следующих m позициях - сим-

вол 0. Соответственно, на первых ℓ позициях вектора v^∗ расположен символ 0, а на

следующих m позициях - символ 2^z. Оставшиеся n-ℓ-m позиций данных векторов

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

левой части соотношения (4) имеет место тождество

(

)

∑

d2E(y^∗; v^∗) - d2E(y^∗; u^∗) =

y2i

+ m22z - 2z+1

y_i +

y²

i=1

i=ℓ+1

(

)

∑

y2i

+ ℓ22z - 2z+1

y_i +

y²

i=1

i=ℓ+1

((

) (

))

∑

= 2^z m2^z

−2

y_i

- ℓ2^z

-2

y_i

(5)

i=ℓ+1

i=1

Рассмотрим теперь правую часть соотношения (4) в модульной метрике. Исходя

из (3), получаем

∑

d_M (y^∗; v^∗) - d_M (y^∗; u^∗) =

y_i + m22z -

y_i -

i=1

i=ℓ+1

(

) (

)

∑

−

- y_i + ℓ2^z

y_i

= m2^z

−2

y_i

- ℓ2^z

-2

y_i

(6)

i=1

i=ℓ+1

i=1

Сравнивая (5) и (6), убеждаемся, что тождество (4) выполняется. ▴

Следствие. Для любого вектора y^∗ = (y₁,y₂,...,y_n) ∈ J и любой пары век-

торов u^∗ ∈ W и v^∗ ∈ W имеет место равносильность неравенств

d_E(y^∗; v^∗) > d_E(y^∗; u^∗) ⇐⇒ dM(y∗; v∗) > dM (y∗; u∗).

(7)

Доказательство. Пусть для вектора y^∗ = (y₁,y₂,...,y_n) ∈ J и любой пары

векторов u^∗ ∈ W и v^∗ ∈ W выполняется неравенство

d_E(y^∗; v^∗) > d_E(y^∗; u^∗).

Тогда возведение обеих частей в квадрат не меняет знак неравенства, т.е. имеет

место неравенство

d2E(y^∗; v^∗) > d2E(y^∗; u^∗).

Данное утверждение следует из того, что множество {0, 1, 2, . . ., 2^z}, которому при-

надлежат все компоненты векторов u^∗, v^∗ и y^∗, состоит из целых неотрицательных

чисел.

Разделим обе части полученного неравенства на 2^z. Получим неравенство с неиз-

менным знаком

d2E(y^∗; v^∗)

d2E(y^∗; u^∗)

2^z

из которого следует

d2E(y^∗; v^∗)

d2E(y^∗; u^∗)

> 0.

(8)

2^z

Из доказанного тождества (4) получаем, что неравенство (8) равносильно неравен-

ству

d_M (y^∗; v^∗) - d_M (y^∗; u^∗) > 0.

Таким образом, требуемая эквивалентность (7) доказана. ▴

При получении вектора y^∗ = (y₁, y₂, . . . , y_n) ∈ J мягкое декодирование кода B^∗

по максимуму правдоподобия с использованием 2^z + 1 подуровней для канала без

памяти с гауссовским шумом осуществляется путем нахождения ближайшего в ев-

клидовой метрике к полученному слову y^∗ слова v^∗ = (v₁, v₂, . . ., v_n) ∈ W ⊂ J,

которое также должно быть кодовым словом B^∗ ∈ W .

С учетом доказанной эквивалентности (7) получаем, что использование модуль-

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

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

§3. Коды в модульной метрике

Множество G(n, t) ⊂ Zⁿ называется кодом, исправляющим t однонаправленных

увеличивающих ошибок, если для любой пары различных векторов u ∈ G(n, t) и

v ∈ G(n,t) не существует вектора c, такого что c ≫ u, c ≫ v, d_M(c;v) ≤ t и

d_M (c; u) ≤ t.

Выберем конечное поле GF (q^m), где q - простое число, m - натуральное и вы-

полняется неравенство q^m > n. Пусть α - примитивный элемент поля. Определим

отображение F множества Zⁿ в множество полиномов от формальной переменной x

над полем GF (q^m). Для этого поставим в соответствие i-й позиции (1 ≤ i ≤ n) век-

торов множества Zⁿ ненулевой элемент αⁱ поля GF(q^m). Из неравенства q^m > n

следует, что такое сопоставление возможно. Определим отображение F вектора

u = (u₁,u₂,...,u_n) в многочлен u(x) по правилу

∏(

)ui

F (u) ≜ u(x) =

αⁱ

i=1

Заметим, что для любых векторов u, v ∈ Zⁿ выполняется условие F(u) ≡ F(v) ≡

≡ 1 mod x.

Обозначим через GF[x] кольцо многочленов от формальной переменной x над

полем GF (q^m). Пусть s(x) ∈ GF [x] - многочлен степени не выше t, младший коэф-

фициент которого равен 1. В [3] доказывается, что множество слов

C ≜ {u | u ∈ Zⁿ, F(u) ≡ s(x) mod xt+1}

(9)

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

дульной метрике. В [3] доказывается, что код C, исправляющий t однонаправленных

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

ных уменьшающих ошибок. В [3] доказывается, что для любого 0 ≤ σ ≤ 2t подмно-

жество слов

{

}



∑



B≜ u

u∈C,

u_i ≡ σ mod (2t + 1)

⊂C

(10)

i=1

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

мимо конструкций самих кодов, в [4] был также предложен алгоритм декодирования

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

ключевого уравнения методом Евклида.

§4. Использование кодов в модульной метрике для мягкого декодирования

в канале с двоичным входным и Q-ичным выходным алфавитами

Пусть заданы двоичные векторы u ∈ 2ⁿ и v ∈ 2ⁿ. Обозначим через d_H (u; v) рас-

стояние между данными векторами в метрике Хэмминга. Тогда для любых векторов

u и v справедливо тождество

d_M (u; v) = d_H(u; v).

Пусть задано множество слов

C ≜ {u | u ∈ 2ⁿ, F(u) ≡ s(x) mod xt+1}.

Тогда подмножество слов

{

}



∑



B≜ u

u∈C,

u_i ≡ σ mod 2(t + 1)

⊂C

i=1

является двоичным кодом, исправляющим t ошибок в метрике Хэмминга и в мо-

дульной метрике.

Будем строить для B схему мягкого декодирования. Выпишем в явном виде

условие для кода C:

∏(

)ui

F (u) ≜ u(x) =

= s(x) + f(x)xt+1.

(11)

αⁱ

i=1

Будем считать, что n < 2^m и αⁱ ∈ GF (2^m) при 1 ≤ i ≤ n. Предположим, что

декодер кода имеет Q = 2^z + 1 подуровней. Другими словами, на выходе демодуля-

тором по каждому символу кода принимается решение, принадлежащее множеству

{0, 1, 2, . . ., 2^z}.

Возведем левую и правую части уравнения (11) в степень 2^z. Поскольку действия

производятся в поле характеристики 2, получим

(

)₂z

∏(

x )ui

u^∗(x) =

= s(x)2z + f(x)2z x(t+1)2z .

α_i

i=1

Это означает, что двоичный вектор u = (u₁, u₂, . . . , u_n) ∈ C с элементами из множе-

ства {0, 1} преобразовался в двоичный вектор u^∗ = (u∗1, u∗2, . . . , u^∗n) с элементами из

множества {0, 2^z} = H.

Заметим, что степень полинома s(x)2z удовлетворяет неравенству deg(s(x)2z ) ≤

≤ 2^zt. Таким образом, s(x)2z - многочлен степени не выше 2^zt, младший коэффи-

циент которого равен 1.

Заметим, что 2^z(t + 1) = 1 + (2^zt + 2^z - 1). Следовательно, из (9) получаем, что

{

}

C^∗ ≜

u^∗ | u^∗ ∈ Hⁿ, F(u^∗) ≡ s(x)2z mod x2z(t+1)

является кодом, исправляющим 2^zt + 2^z - 1 однонаправленных увеличивающих

ошибок в модульной метрике, если за единичную ошибку считать изменение на

один уровень из множества уровней {0, 1, 2, . . . , 2^z} в одном из n символов векто-

ра u^∗ = (u∗1, u∗2, . . . , u^∗n).

Если для вектора u = (u₁, u₂, . . . , u_n) ∈ C выполняется условие

∑

u_i ≡ σ mod (2t + 1),

i=1

то для вектора u^∗ = (u∗1, u∗2, . . ., u^∗n) ∈ C^∗ с элементами из множества {0, 2^z} = H

выполняется условие

∑

2^zu_i ≡ σ2^z mod (2^z(2t + 1)).

i=1

Тогда из равенства 2^z(t + 1) = 1 + (2^zt + 2^z - 1) с учетом (10) получаем, что код

{

}



∑



B^∗ ≜ u^∗

u^∗ ∈C^∗,

u^∗i ≡ σ2^z mod (2^z(2t + 1))

⊂C^∗

i=0

является кодом, исправляющим 2^zt + 2^z - 1 произвольных ошибок в модульной мет-

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

уровней {0, 1, 2, . . . , 2^z} в одном из n символом вектора u^∗ = (u∗1, u∗2, . . . , u^∗n).

Алгебраическая структура полученного кода B^∗ может быть использована c при-

менением алгоритма из [4] для нахождения с полиномиальной сложностью части

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

стояния 1 + (2^zt + 2^z - 1). При нахождении всех остальных ошибок, исправляемых

кодом B^∗ в модульной метрике, получаем мягкое декодирование кода B^∗ по мак-

симуму правдоподобия для канала с двоичным входным алфавитом и выходным

алфавитом из Q = 2^z + 1 символов.

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

1. Колесник В.Д., Мирончиков Е.Т. Декодирование циклических кодов. М.: Связь, 1968.

2. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой

связи. М.: Радио и Связь, 1987.