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

Рассмотрим схему прохождения данных в моделях помехоустойчивых каналов связи с дискретным входом: источник сообщений, кодер канала, передатчик, линия связи с шумом, приемник, декодер канала, и получателв сообщений [1]. При этом если приемник выдает дискретные данные, то говорят о дискретных каналах и жестких решениях приемника, а. если приемник выдает аналоговые сигналы, то говорят о полунепрерывном канале и мягких решениях приемника. [2]. В последнем случае имеет смысл использовать декодер мягких решений (ДМР), который обычно дает лучшие результаты по сравнению с декодированием жестких решений; эффективность ДМР основана, на. том, что в отсутствии демодулятора, не накапливаются ошибки квантования. Обычно ДМР обладают большей сложностью [2, с. 357]. К декодерам такого типа, относится обладающий значительной корректирующей способностью декодер двоичных кодов Рида. — Малдера. второго порядка, с вещественным входом, предложенный В. М. Сидельниковым и А. С. Першаковым [3], который исследовался в работах [4, 5]. В [6] построен новый ДМР с входными данными из поля комплексных чисел, распространяющий алгоритмы декодирования из [3, 4] на. случай кодов Рида. — Маллера. второго порядка, над полем Галуа, F 3.

В настоящей работе исследуются условия корректности работы декодера, из [6]. Математическая суть этого декодера, состоит в том, что для поиска, верного кодового слова. с. соответствутошего информационному полиному нескольких переменных f. декодер по полученному из канала зашумленному слову z строит зашумленные версии кодовых слов для всех производных полинома f, а затем декодирует их в L1-MeTpHKe, пропорциональной метрике Хемминга, и на. основе полученных результатов восстанавливает слово с. Таким образом, поиск по слову z ближайшего по метр икс Хеммиига. слова, с

происходит в некотором смысле на основе применения аналога Соболевской нормы [7]. Для дискретного канала передачи данных выделено условие гладкости, при выполнении которого сформулирована и доказана теорема о корректности работы этого декодера в ситуации, когда число ошибок в кодовом слове не превосходит половину минимального кодового расстояния.

Отметим, однако, что этот декодер может исправлять часть ошибок и за границей половины минимального кодового расстояния, что подтверждается проведенными экспериментами [8]. Таким образом, естественной областью применения разработанного декодера являются каналы связи низкого качества, используемые для передачи ценных сообщений, какими являются, например, отводные каналы утечки информации [9-11].

1.    Коды RMз(2,m) и разностные операторы

Над полем Галуа, F3 рассмотрим алгсс5ру полиномов от m перем очных F3[xi,... , xm ]. при этом, не теряя общности, будем полагать, что все мономы имеют вид axY1 . . .xm", 0 6 Yj 6 2. Для npoi 13В0.ТЫЮГ0 <5 = (ai,..., am) из линейного пространства Fm через р(а) обозначим сумму координат как сумм у натуральных чисел. В пространстве Fm мощности n = 3^m зафиксируем линейное упорядочение

^{а1 ; . . . ; On ^{} (a}j ^(aj1 , ^aj2 , . . . , ^jm )) ,                                   (^ )

по параметру p(a) от меньшего к большему, а при одинаковых значениях р(а) предполагается лексикографический порядок слева, направо от большего к меньшему. Полиномы из F3[xi,... ,xm] будем записывать в каноническом виде f (х) = X fa xa, aeFm где a = (a1,...,am), x = (xi,...,xm), xa = xa1 . ..xmm, а порядок слагаемых в сумме соответствует упорядочению (1). Для ненулевого монома axa степень определяется как р(а), а степень deg(f) поли нома f определяется как максимальная степень составляющих его ненулевых мономов. Множество полиномов из F3[xi,..., xm] степени не выше r обозначим через F3r) [xi,..., xm]. По аналогии с определением производной в булевом случае (см. [12, с. 89]) определим оператор дифференцирования по направлению b (G Fm)

Db : F3r)[xi, • • • ,Xm] ^ F3r-1)[xi,••• A]

правилом

(Dbf)(x) = fb(x) - f(x), fb(x) = f (x + b).                       (2)

Легко видеть, что этот оператор определен корректно и является линейным.

Приведем необходимые сведения о кодах Рида — Маллера над полем F3:

RM3(r,m) = { (f(од),... ,f(an)) : f G F3r)[xi,... ,xm] }

(см., например, [13]). Параметр r (6 m) называется порядком кода RM3Д,m). Рассмотрим оператор кодирования C : F3r) [xi,..., xm] ^ Fn определяемый равенством

C(f) = (f (ai),..., f (an)), f G F3r)[xi, ...,xm].                     (3)

Полиномы и:з F^r)^,.

.

., xm] назовем информационными, а вектор, составленный из ко-

f ром и обозначать через f. Далее будем рассматривать коды Рида — Маллера порядка 1 и 2. Опишем параметры кода RM n(1,m): длин а кода n = 3m, размерность k = 1+ m, минимальное кодовое расстояние d = 2 • 3m—1, число гарантированно исправляемых ошибок t = 3m—1 — 1, информационные полиномы кода имеют вид

a(x) = ao + У^ a_ax^a p^(a)=1

.

Опишем параметры кода RM n(2,m):

n = 3m,   k = 1+ m + Cmm+1,

о m—1

d = 3^m—1, t =---2

-

,

информационные полиномы кода имеют вид f (xa) = aoo +      aao xaa +      aao xaa .

р(а)=1

Р(а)=2

f (xa)

ратичной формы, поэтому далее будем его записать следующим образом:

f (x) = ao + hx, ai + xAxT,

A =	^	f2oo..oo 2 f 11o...oo 2 f 1o1...oo 2 f 1oo...1o 2 f 1oo...o1	2 f 11o...oo f o2o..oo 2 f o11...oo * * * 2 f o1o...1o 2 f o1o...o1	2 f 1o1...oo 2 f o11...oo     • • • f oo2..oo * * * 2 f oo1...1o     • • • 2 f oo1...o1	2 f 1oo...1o 2 f o1o...1o 2 f oo1...1o * * * f ooo..2o 2 f ooo...11	2 f 1oo...o1 2 f o1o...o1 2 f oo1...o1 2 f ooo...11 f ooo..o2
Отметим, что в поле F3 выполняете я равенство 2—1 = 2. Прямыми выкладками проверяется, что для произвольного произвольного вектора b (Е Fm)						полинома
			(D0f)(x) =	2 x a A a b T + f (a b )	— foo...oo.

.

f

\

/

Чтобы ввести в пространстве Fn аналог оператора D;, рассмотрим сначала для b Е F™ оператор сдвига т о : Fn ^ Fn определяемый равенством

тb(a) = (aa1 +0,..., aan+b), где a = (aa1,..., aan) Е Fn (см. (1)). Отметим, что то является перемешивающим биективным отображением. Разностный оператор A; : Fn ^ Fn определим формулой

^A b^(a) = ^то^{(a) -} a.

Далее Ab(a) будем называть производным вектором вектора a по направлению b.

Установим связь между введенными выше операторами.

Лемма 1. Пусть f E F3 [ x1,... ,xm ], b E Fm Тогда

Tb(C ( f )) = C ( fb ) , C (Df ) = A b ( C ( f )) .

C Для проверки первого равенства следует использовать (3) и (6), а второе вытекает из линейности оператора кодирования C и равенств (2), (7). B

• 2.    Помехоустойчивый канал на кодах RMa (2 ,m).

Гладкость канала

Рассмотрим стандартную схему прохождения данных над алфавитом F3 в математической модели помехоустойчивого канала связи, основанного на применении описанных выше [n, k,d]3-KOдов RMз(2,ш): источник сообщений (ИС), кодер канала (КК), передатчик, линия связи с шумом (ЛСШ), приемник, декодер канала (ДК) и получатель сообщений (ПС) (см. [6]). Из ИС на вход КК поступают информационные векторы m E Fk, на выходе КК формируются кодовые векторы Л E НМз(2, m) (с F^. Чтобы описать работу передатчика рассмотрим мультипликативную группу С3 = {ei23""j}     (с C) корней j—U,1,2

третьей степени из 1, изоморфизм д группы С3 на аддитивную группу поля F3, который определяется равенством д-1(j) = eiзnj, j E F3, и соответствующее отображение пространств векторов дп : СП ^ ЕП.                                   (8)

Передатчик на физическом уровне конвертирует элементы поля F3 в комплексные числа из С3, например, с помощью модуляции с непрерывной фазой (см. [2, с. 170]), и полученные на выходе КК кодовые векторы с E RM3(2, m) (с ЕП) преобразует в Л = д_П(л) E СП-Эти векторы передатчик отправляет в ЛСШ, где в силу искажений они модифицируются в векторы Л⁰ E С^П с ненулевыми коор,динатами. Векторы Z = (z1,..., Zn ) поступают на вход приемника, который в зависимости от настроек может выдавать мягкие или жесткие решения о принятом сигнале.

В случае мягких решений приемник преобразует значение каждого сигнала Zs E С \ {0} с помощью фильтрующей функции

Z : С\{ 0 }^ Е = { е E С : е 6 |е| 6 е ^{- 1} } ,                      (9)

с параметром е E (0; 1]. которая определяется по (/лсдующсму правилу: если е 6 |е| 6 е ^{- 1}. ^т° z ( е ) = е ^сслп о < |е| <  е. то z ( е ) = е|е|^-1 е-. если е^-1 < |^|. т<> z ( е ) = е|е|^-1 е^-1.

В случае жестких решений приемник преобразует вектор Л⁰ E Cⁿ в вектор Y E СП, используя, например, для каждой координаты принцип решающих областей [2]. В этом случае преобразованный вектор Y также при надлежит ЕП, так как СП С ЕД

Отметим, что вне зависимости от настроек с выхода приемника вектор Y E ЕП направляется в декодер мягких решений, конструкция которого представлена ниже. Этот декодер вычисляет некоторый информационный вектор m⁰ E Fk и передает его в ПС. Очевидно, что с учетом искажений в ЛСШ вектор m⁰ может отличаться от исходного вектора m, отправленного ИС в канал, в таком случае говорят об ошибке декодирования. В зависимости от настроек приемника можно вести речь о помехоустойчивом полунепрерывном или дискретном канале передачи.

Внутри описанного выше помехоустойчивого канала связи можно выделить внутренний непомехоустойчивый канал, свойства которого влияют на корректирующую способность кодека исходного канала. Действительно, если в описанной выше модели помехоустойчивого канала связи убрать блоки КК и ДК, то в режиме жестких решений приемника реализуется дискретный непомехоустойчивый канал, а в режиме мягких решений приемника — полунепрерывный непомехоустойчивый канал. Тогда схема прохождения данных по каналу следующая: ИС, передатчик, ЛСШ, приемник и ПС. В отсутствии кодека канала предполагается, что ИС формирует векторы, а ПС получает векторы длины п. В случае мягких решений приемника совокупное воздействие передатчика, линии связи и приемника на сообщения назовем оператором внутреннего непомехоустойчивого полунепрерывного канала, который обозначим chn : Fn ^ Sn.

В случае жестких решений приемника на вход ПС помехоустойчивого канала поступают элементы из пространства СП. Соответствующий оператор внутреннего непомехоустойчивого дискретного канала обозначим chnd : Fn ^ СП.

Оператор chnd и породивший его дискретный помехоустойчивый канал будем называть гладкими, если зашумление вектора C(f ) (G RMa(2, m)) в канале тесно связано с зашумлением векторов C(D,f) (G RMa(1, m)) для всех b G Fm, а именно, если

^M(chnd(C (f)))) = ^n(chn_d(C (D-_bf ))).                    (10)

Разностный оператор A, является дискретной версией оператора дифференцирования Db поэтому условие (10) — это некоторый аналог свойства преобразования касательных расслоений, индуцированных гладким отображением многообразий (см., например, [14, с. 29]).

Лемма 2. Рассмотрим гладкий дискретный помехоустойчивый канал. Пусть f G F3²⁾[xi,...,xm]. b G Fm,

Ё = pn(chnd(C(f))) - C (f), Ё = pn(chnd(C(D-_bf))) - C(Df ).

Тогда, если вес Хемминга ошибки Ё не превосходит число ошибок, гарантированно исправляемых колом RMa(2,m). т. е.

wth(e) 6 tRM3(2,m) = ^ (3m 1 - 1) , то вес Хемминга ошибки Ё не превосходит число ошибок, гарантированно исправляемых колом RMa(1, m). т. е.

wth(e) 6 tRM3(1,m) = 3m 1.

C Отметим, что значения tRM3(₂,_m) и tRM ₃(1,_m) предъявлены в разделе 1. Используя условие (10), линейность оператора A- и лемму 1 получаем

Pn(chnd(C(D-f ))) = A-(pn(chnd(C (f)))) = A-_b(C (f) + ё)

= A,(C(f)) + Ab(e) = C(D-f ) + т _ь (ё) - ё.

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

Ё = chnd(C(Dbf)) - C(Dbf ) = т - (ё) - e.

По условию леммы wth(Tb(e)) = wth(e) 6 2 (3m-1 - 1) .

Следовательно, wth(e) = wth(Tb(e) - ё) 6 wth(Tb(ё)) + wth(e) 6 (3m-1 - 1). в

3.    Конструкция ДМР для кодов RMз(2,т)

Опишем в усовершенствованном виде конструкцию ДМР для кодов RMз(2,т) из работы [6]. Для этого в пространстве Е" по аналогии с (2), (7) введем операторы nn  nn

Sb -Se ^ Se , V b - Se ^ Se , которые действуют по правилам

Sb(Y ) = (Уь+ai, ••• ,Уь+ап) , Vb(Y ) = (Z (Уь+ai У-У) ^-Х (УЬ+йп У-n1))

соответственно, где Y = (y_a1 ,... ,y_an ) G ЕП, Z ~ фильтрующая функция (9).

Алгоритм. Вход: [n,k,d]3-KOд RM3(2,m), полученный из канала зашумленный ко довый вектор Y = (Ya1,•••, Yan) G Sn (c Cn)._

Выход: восстановленный информационный вектор f.

Шаг 1. Построим упорядоченный в соответствии с (1) набор векторов из ЕД

{Vy (Y) = (z (Yy+щ Y-11),...,Z (Yy+-n Y^))} ьТ-u. з , y 6^~ где Z ~ фильтрующая функция (9), Y-1 — число, co пряженное к Yy s.

Шаг 2. Рассмотрим в соответствии с (1) все Y G Fm, Y = 0, и для фиксированного Y определим

Р = (Р-1 ,Р-₂ ,...,Рдп ) = V- (Y).

Среди всех в(х) = во + в1 х1 + • • • + в_т xm ^из F31) [x1, • • •, xm] найдем полином, который минимизирует функционал:

Ф(Р,в) = XX PC - ei3^пв(оs) | (G R).

s=1

Минимальное значение функционала для текущего значения Y обозначим через ^, а вектор, на котором достигается минимум — через By = (в?, • • •, вт )•

Найдем значения Фу и B y для к аждого y G Fm, Y = 0- Сформируем упорядоченный в соответствии с (1) набор Ф = (Ф_о1 = 0, Ф_о2, Ф _о3 , • • •, Ф _yn ) и двумерный массив

Ba-i             0    •••    0 \

B = в -2      =    ea2 ••• вт2   •

...               ... ... ...

V в -n / Veyn ••• emn)

Шаг 3. Пусть © = B:

( 0 _о 1 \         ^11 * * * 9т1