Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,899

COEFFICIENTS OF A GENERALIZED CORRECTION ALGORITHM POLYADIC SYSTEM

Kalmykov M.I. 1 Dunin A.C. 1 Ashikhmin S.V. 2 Lyubenko D.V. 2
1 Federal state Autonomous educational institution higher professional education «North-Сaucasian federal university
2 Filial Moscow state University of instrument engineering and informatics in the city of Stavropol
Codes polynomial system of residue classes allow calculations and signal processing in real time. This property nonpositional modular codes associated with independent parallel processing residues on the grounds of the system. If the composition of the bases to introduce additional, module, class codes deductions are able to detect and correct errors that fuss, mess because of equipment failure. The paper presents a neural network implementation of the algorithm for calculating the coefficients of the generalized co-polyadic system that allows you to correct errors in a modular code.
modular codes polynomial system of residue classes
the coefficients of the generalized-gap of polyadic system
detection and correction of errors
the neural

Для обеспечения максимальной скорости цифровой обработки сигналов (ЦОС) используют специализированные процессоры (СП). Как правило, такие СП имеют параллельную архитектуру. Чтобы обеспечить предельные показатели при обработке сигналов в ряде работ [1–5] предлагается использовать непозиционные коды. Известно, что такие коды позволяют эффективно реализовать операции сложения, умножения и вычитания по модулю, которые широко применяются во многих алгоритмах ЦОС. Кроме того, модулярные коды, которые построены с использованием алгебраических систем, обладающих свойством кольца и поля, способны обнаруживать и исправлять ошибки, которые могут возникать из-за отказов или сбоя оборудования [1, 6, 7, 8, 9]. При этом такие процедуры проводятся при выполнении обратного преобразования из модулярного кода в позиционный. Поэтому разработка алгоритма позволяющего исправлять ошибки на основе обобщенной полиадической системы (ОПС), которая используется в блоке обратного преобразования, является актуальной задачей.

В подавляющем большинстве задачи ЦОС сводятся к нахождению значений ортогонального преобразования конечной реализации сигнала для большого числа точек в реальном масштабе времени, что предопределяет повышенные требования к скорости и разрядности вычислительного устройства. Для эффективной решении данной задачи целесообразно перейти от одномерной обработке сигналов к многомерной в кольце полиномов. Такой переход к параллельной обработке сигналов базируется на изоморфизме, порожденном китайской теоремой об остатках (КТО). В работах [2–4] доказана возможность реализации обобщенного дискретного преобразования Фурье (ДПФ) в кольце полиномов. При этом вычисления организуются в кольце полиномов P(z) с коэффициентами в виде элементов поля GF(p), представляющем собой сумму

kalm01.wmf, (1)

где Pj(z) – локальное кольцо полиномов, образованное неприводимым полиномом pj(z) над полем GF (p); j = 1, 2,…,m.

В этом случае целесообразно использовать полиномиальную систему классов вычетов (ПСКВ), в которой вычисления организуются параллельно, помодульно и независимо друг от друга, так как операции сложения, вычитания и умножения сводятся к соответствующим операциям над остатками по модулям pl(z) над полем

kalm02.wmf, (2)

где kalm03.wmf – операции сложения, вычитания и умножения в GF(p); A(z) = (α1(z), α2(z),…, αn(z)) и B(z) = (b1(z), b2(z),…, bn(z)) – модулярный код в кольце полиномов; αl(z) ≡ A(z) mod pl(z); bl(z) ≡ B(z) mod pl(z); l = 1, …,m.

Как показано в работах [1,2,4] обобщенное ДПФ в кольце полиномов, предназначенное для вычисления d спектральных составляющих, будет реализовано в следующем виде

kalm04.wmf, (3)

где kalm05.wmf; b – порождающий элемент; j = 1,2,…,m; k = 0,1,…d – 1.

После выполнения вычислений в СП ПСКВ необходимо осуществить обратное преобразование из модулярного кода в позиционный код. Одним из наиболее привлекательных с точки зрения схемных затрата является алгоритм обратного преобразования использующий промежуточную систему – обобщенную полиадическую систему. При этом могут, благодаря параллелизму алгебраической системы, вычисления могут быть реализованы с помощью нейронных сетей [1–3].

В работе [10] приведена нейронная сеть для перевода из модулярного кода ПСКВ в обобщенную полиадическую систему, в которой используется 5 неприводимых полиномов p1(z) = z + 1, p2(z) = z2 + z + 1, p3(z) = z4 + z3 + z2 + z + 1, p4(z) = z4 + z3 + 1, p5(z) = z4 + z + 1. Если положить, что первые три основания являются информационными, т.е. k = 3, то рабочий диапазон будет определяться согласно

kalm06.wmf.

Оставшиеся два основания p4(z) = = z4 + z3 + 1 и p5(z) = z4 + z + 1, будем считать контрольными модулями, с помощью которых будет производиться поиск и коррекция ошибок, возникающих в кодах ПСКВ.

В этом случае, любой полином, представленный в коде ПСКВ, чья степень будет меньше семи, то есть deg A(z) < 7, является разрешенным, а его кодовая комбинация не содержит ошибки. В противном случае – кодовая комбинация содержит ошибки.

Коэффициенты обобщенной полиадической системы позволяют осуществить поиск и коррекцию ошибок в кодах ПСКВ. Для данного примера полином A(z) можно представить в обобщенной полиадической системе как

kalm07.wmf (4)

где kalm08.wmf; kalm09.wmf;

kalm10.wmf;

kalm11.wmf.

Представим ортогональные базисы выбранной системы в виде коэффициентов ОПС

B1(z) = z14 + zl3 + zl2 + zll + zl0 + z9 + z8 + z7 + z6 + z5 + z4 + z3 + z2 + z + 1 = [1, z, z3 + z, z3, z3 + z2 + z];

B2(z) = z14 + z13 + z11 + z10 + z8 + z7 + z 5 + z4 + z2 + z = [0, z, z3 + z2 + 1, z3 + z + 1, z3 + z2];

B3(z) = zl4 + zl3 + zl2 + zll + z 9 + z8 + z7 + z6 + z4 + zз + z2 + z = [0, 0, z2 + z + 1, z2 + 1, z3 + z2 + z];

B4(z) = z14 + z13 + z12 + z11 + z9 + z7 + z6 + z3 = [0, 0, 0, z2 + z, z3 + z2 + z];

B5(z) = zl2 + z9 + z8 + z6 + z4 + z3 + z2 + z = [0, 0, 0, 0, z].

Согласно китайской теореме об остатках (КТО) полином A(z) определяется

kalm12.wmf, (5)

где kalm13.wmf – полный диапазон ПСКВ.

Если в качестве ортогональных базисов Bi(z) взять их представления в ОПС, то при умножении остатков kalm14.wmf на последние, можно получить коэффициенты ОПС

kalm15.wmf (6)

где kalm16.wmf – коэффициенты ОПС i-го ортогонального базиса с учетом переполнения (i-1)-го основания.

Если полином A(z), представленный в ПСКВ, не содержит ошибки, то его степень не превысит степень рабочего диапазона. Следовательно, значения старших коэффициентов ОПС должны равняться нулю, т.е. a4(z) = 0 и a5(z) = 0.

Если полином A*(z), представленный в ПСКВ, содержит ошибку, то его значение будет определяться

kalm17a.wmf

kalm17b.wmf (7)

где αj*(z) – глубина ошибки по j-му основанию ПСКВ.

При переводе из ПСКВ в позиционный код ошибочный код A*(z) окажется за пределами рабочего диапазона Рраб(z). Тогда, значения старших коэффициентов ОПС будут отличаться от нуля. При этом по величине значений старших коэффициентов ОПС можно однозначно определить местоположение и глубину ошибки.

Чтобы осуществлять коррекцию ошибочного значения коэффициентов ОПС была разработана схема нейросетевого устройства, которая представлена на рисунке.

kalmik1.wmf

Нейросетевое устройство для коррекции коэффициентов ОПС

Устройство состоит из двухслойной нейронной сети (нейроны 1–15 образуют первый слой, нейроны 16–30 создают второй слой), блока памяти 31, имеющего восемь входов 32–39 и семь выходов 40–46, семи двухвходовых корректирующих сумматоров 47–53.

Каждый слой нейронной сети содержит по 15 нейронов. Входной слой состоит из 15 нейронов, распределенных в соответствии с размерностью разрядных сеток модулей -1-2-4-4-4. Данные нейроны осуществляют разветвление входного вектора кода ПСКВ A(z) = (α1(z), α2(z), α3(z), α4(z), α5(z)), представленного в двоичной форме. Второй слой нейронной сети содержит также 15 нейронов, распределенных в соответствии с размерностью разрядных сеток коэффициентов (аi(z), i = 1,2,3,4,5) ОПС-1-2-4-4-4. Нейроны 16-30 второго слоя выполняют базовую операцию суммирования по модулю два значений разрядов, поступающих с выходов соответствующих нейронов первого слоя. Синаптические веса связей равны единице.

Выход нейрона 16 соответствует нулевому разряду первого коэффициента ОПС а1(z). Нейроны 17, 18 осуществляют вычисление нулевого и первого kalm18.wmfkalm19.wmf разрядов второго коэффициента ОПС соответственно. Нейроны 19, 20, 21, 22 осуществляют вычисление нулевого, первого, второго и третьего разрядов kalm20.wmf kalm21.wmf kalm22.wmf kalm23.wmf третьего коэффициента ОПС а3(z) соответственно. Нейроны 23, 24, 25, 26 осуществляют вычисление нулевого, первого, второго и третьего разрядов kalm24.wmf kalm25.wmf kalm26.wmf kalm27.wmf четвертого коэффициента ОПС а4(z) соответственно. Нейроны 27, 28, 29, 30 осуществляют вычисление нулевого, первого, второго и третьего разрядов kalm28.wmf kalm29.wmf kalm30.wmf kalm31.wmf пятого коэффициента ОПС а5(z) соответственно.

Блок памяти 31 имеет 8 входов. На входы 32–35 блока памяти поступают разряды коэффициента ОПС а4(z). Значения нулевого, первого, второго и третьего разрядов kalm32.wmf, kalm33.wmf, kalm34.wmf, kalm35.wmf пятого коэффициента ОПС а5(z) поступают соответственно на 36–39 входы блока памяти.

Корректирующие сумматоры 47–53 подключены к соответствующим выходам нейронов второго слоя и выходам блока памяти. С выходов этих сумматоров снимаются откорректированные значения коэффициентов ОПС.

Блок памяти предназначен для хранения констант коррекции, значение которых зависит от вычисленных величин старших коэффициентов ОПС. Зависимость значений коэффициентов ОПС а4(z) и а5(z) от местоположения и глубины ошибки в коде ПСКП приведены в табл. 1.

Зависимость между значениями старших коэффициентов а4(z), а5(z) и корректирующими значениями коэффициентов ОПС а1(z), а2(z), а3(z) приведена в табл. 2.

Рассмотрим работу устройства. Пусть задан полином A(z) = z6+z5+z4+z+1, который принадлежит рабочему диапазону Pраб(z). Тогда его код в ПСКВ, который не содержит ошибки, имеет вид A(z) = (1, z+1, z3+z2+z+1, z3+z2+z, z3+z). Воспользуемся выражением (6) и произведем вычисление коэффициентов ОПС. В результате были получены значения

a1(z) = 1, a2(z) = z+1, a3(z) = z3+z2+z+1, а4(z) = 0, a5(z) = 0.

Таблица 1

Зависимость значений коэффициентов ОПС от местоположения и глубины ошибки для поля GF(24)

Величина ошибки

Коэффициенты ОПС

a4 (z)

a5 (z)

α1*(z) = 1

z3

z3 + z2 + z

α2*(z) = 1

z3 + z + 1

z3 + z2

α2*(z) = z

z3 + z2 +z

z3 + z

α3*(z) = 1

z2 + 1

z3 + z2+ z

α3*(z) = z

z3 + z

z3 + z2 + z + 1

α3*(z) = z2

z3 + z2

z3 + z2

α3*(z) = z3

1

z3 + z

Таблица 2

Зависимость значений коррекции коэффициентов ОПС от значений старших коэффициентов a4(z) и a5(z)

Коэффициенты ОПС

Коррекция коэффициентов ОПС

a4 (z)

a5 (z)

Δa1(z)

Δa2(z)

Δa3(z)

z3

z3 + z2 + z

1

z

z3 + z

z3 + z + 1

z3 + z2

 

z

z3 + z2 + 1

z3 + z2 +z

z3 + z

 

z+1

z2

z2 + 1

z3 + z2+ z

 

 

z2 + z+1

z3 + z

z3 + z2 + z + 1

 

 

z3 + z2 + z

z3 + z2

z3 + z2

 

 

z+1

1

z3 + z

 

 

z2 + z

Так как старшие коэффициенты ОПС равны нулю, то это свидетельствуют, что кодовая комбинация ПСКВ не содержит ошибку, и ее не надо корректировать. В этом случае на входы блока памяти 31 поступают нулевые сигналы с выходов нейронов 23-26 и 27-30, которые соответствуют двоичному представлению коэффициентов а4(z) = 0, a5(z) = 0. В результате этого с выходов 40-46 также снимается нулевой результат, который подается на корректирующие сумматоры 47-53. В соответствии с этим на выходах этих корректирующих сумматоров, выполняющих операцию суммирования по модулю, значения коэффициентов ОПС a1(z) = 1, a2(z) = z+1, a3(z) = z3+z2+z+1, не будут корректироваться.

Пусть произошла ошибкав первом остатке кода ПСКВ и ее глубина равна α1*(z) = 1. В этом случае A*(z)=(0, z+1, z3+z2+z+1, z3+z2+z, z3+z). Тогда на выходах нейронов 16-30 второго слоя получатся значения коэффициентов ОПС

a1(z) = 0, a2(z) = 1, a3(z) = z2+1, а4(z) = z3, a5(z) = z3+z2+z.

В соответствии с полученными значениями а4(z) = z3, a5(z) = z3+z2+z с выходов блока памяти, согласно данным приведенным в табл. 2, будут сниматься корректирующие значения ∆a1(z) = 1, ∆a2(z) = z, ∆a3(z) = z3 + z. Эти значения будут поданы на входы соответствующих сумматоров по модулю два 47-53, где и произойдет коррекция коэффициентов ОПС. В результате на выходе первого 47 корректирующего сумматора получаем

kalm36.wmf.

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

kalm37.wmf.

Произошло исправление ошибки. Теперь откорректированное значение второго коэффициента ОПС ∆a2(z) = z + 1. На выходе четвертого 50 корректирующего сумматора получаем исправленное значение сигнал

kalm38.wmf.

На выходе пятого 51 корректирующего сумматора получаем сигнал

kalm39.wmf.

Ошибка в разряде исправлена.

На выходе шестого 52 корректирующего сумматора получаем сигнал

kalm40.wmf.

Ошибка в разряде исправлена.

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

kalm41.wmf.

Ошибка исправлена. Теперь откорректированное значение третьего коэффициента ОПС равно a3(z) = z3+z2+z+1.

Выводы

Повысить скорость выполнения цифровой обработки сигналов можно за счет перехода к параллельным вычислениям. В работе показана целесообразность реализации ЦОС с помощью ПСКВ. Такжего в работе приведен пример реализации алгоритма поиска и коррекции ошибки, который использует старшие коэффициенты обобщенной полиадической системы. Представлена схема нейросетевого устройства, способного исправлять значения коэффициентов ОПС при возникновении ошибки в коде ПСКВ.