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

Автор: Деундяк Владимир Михайлович, Могилевская Надежда Сергеевна

Журнал: Владикавказский математический журнал @vmj-ru

Статья в выпуске: 4 т.18, 2016 года.

Бесплатный доступ

Теоретически изучаются условия корректности работы нового декодера мягких решений кодов Рида - Маллера второго порядка над полем F3, экспериментальное исследование которого показало, что по корректирующей способности он значительно превосходит декодер по минимальному кодовому расстоянию Хемминга. Для дискретного канала передачи данных выделено условие гладкости, при выполнении которого доказано, что исследуемый декодер гарантировано исправляет все ошибки, число которых не превышает допустимое количество ошибок, предусмотренное конструкцией кода.

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

Короткий адрес: https://sciup.org/14318551

IDR: 14318551

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

Рассмотрим схему прохождения данных в моделях помехоустойчивых каналов связи с дискретным входом: источник сообщений, кодер канала, передатчик, линия связи с шумом, приемник, декодер канала, и получателв сообщений [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 = 3m зафиксируем линейное упорядочение

1 ; . . . ; On } (aj (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 + У^ aaxa p(a)=1

.

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

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

о m—1

d = 3m—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 СП-Эти векторы передатчик отправляет в ЛСШ, где в силу искажений они модифицируются в векторы Л0 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.

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

Отметим, что вне зависимости от настроек с выхода приемника вектор Y E ЕП направляется в декодер мягких решений, конструкция которого представлена ниже. Этот декодер вычисляет некоторый информационный вектор m0 E Fk и передает его в ПС. Очевидно, что с учетом искажений в ЛСШ вектор m0 может отличаться от исходного вектора 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(chnd(C (D-bf ))).                    (10)

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

Лемма 2. Рассмотрим гладкий дискретный помехоустойчивый канал. Пусть f G F32)[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(2,m) и tRM 3(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 = (ya1 ,... ,yan ) 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 ,Р-2 ,...,Рдп ) = 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

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

  • Деундяк В. М., Маевский А. Э., Могилевская Н. С. Методы помехоустойчивой защиты данных: Учеб. Ростов н/Д.: Изд-во Южного федерального ун-та, 2014. 309 с.
  • Прокис Дж. Цифровая связь. М.: Радио и связь, 2000. 800 c.
  • Сидельников В. М., Першаков А. С. Декодирование кодов Рида Маллера при большом числе ошибок//Проблемы передачи информации. 1992. Т. 28, № 3. С. 80-94.
  • Loidreau P., Sakkour B. Modified version of Sidel'nikov-Pershakov decoding algorithm for binary second order Reed-Muller codes//Ninth International Workshop on Algebraic and Combinatorial Coding theory, ACCT-9, Kranevo. 2004. Р. 266-271.
  • Могилевская Н. С., Скоробогат В. Р., Чудаков В. С. Экспериментальное исследование декодеров кодов Рида Маллера второго порядка//Вестн. Донского гос. тех. ун-та. 2008. Т. 8, № 3. С. 231-237.
  • Деундяк В. М., Могилевская Н. С. Модель троичного канала передачи данных с использованием декодера мягких решений кодов Рида Маллера второго порядка//Изв. вузов. Северо-Кавк. регион. Техн. науки. 2015. № 1(182). С. 3-10.
  • Тейлор М. Псевдодифференциальные операторы. М.: Мир, 1985. 25 с.
  • Могилевская Н. С. Корректирующая способность декодера мягких решений троичных кодов Рида Маллера второго порядка при большом числе ошибок//Вестн. Донского гос. тех. ун-та. 2015. № 1. С. 121-130.
  • Деундяк В. М., Косолапов Ю. В. О стойкости кодового зашумления к статистическому анализу наблюдаемых данных многократного повторения//Модел. и анализ информ. систем. 2012. Т. 19, № 4. С. 110-127.
  • Букашкин С. А. Метод случайного кодирования//Радиотехника. 2014. № 4. С. 30-36.
  • Косолапов Ю. В. Коды для обобщенной модели канала с подслушиванием//Проблемы передачи информации. 2015. Т.51, № 1. С. 23-28.
  • Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004. 470 с.
  • Pellikaan R., Wu X.-W. List decoding of q-ary Reed-Muller codes//IEEE. Trans. Infor. Theory. 2004. Vol. 50(4). P. 679-682.
  • Хирш М. Дифференциальная топология. М.: Мир, 1979. 280 с.
Еще
Статья научная