Алгоритм коррекции коэффициентов обобщенной полиадической системы

Тип работы:
Реферат
Предмет:
Общие и комплексные проблемы естественных и точных наук


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 681. 3
алгоритм коррекции коэффициентов обобщенной полиадической системы
Калмыков М. И., 1дунин А.В., 2Ашихмин С.В., 2Любенко д.В.
'-ФГАОУ ВПО «Северо-Кавказский федеральный университет», Ставрополь,
e-mail: kia762@yandex. ru-
2Филиал Московского государственного университета приборостроения и информатики в городе Ставрополе, e-mail: kia762@yandex. ru
Коды полиномиальной системы классов вычетов позволяют проводить вычисления и обработку сигналов в реальном масштабе времени. Такое свойство непозиционных модулярных кодов связано с независимой параллельной обработкой остатков по основаниям системы. Если в состав оснований ввести дополнительные модуля, то коды классов вычетов способны обнаруживать и исправлять ошибки, которые возникают из-за отказа оборудования. В работе представлена нейросетевая реализация алгоритма вычисления коэффициентов обобщенной полиадической системы, позволяющая корректировать ошибки в модулярного коде.
Ключевые слова: модулярные коды, полиномиальная система классов вычетов, коэффициентов обобщенной полиадической системы, обнаружение и коррекция ошибок, нейронная сеть
COEFFICIENTS OF A GENERALIZED CORRECTION ALGORITHM POLYADIC SYSTEM 1Kalmykov M.I., 1Dunin A.C., 2Ashikhmin S.V., 2Lyubenko D.V.
'-Federal state Autonomous educational institution higher professional education «North-Caucasian federal university, Stavropol, e-mail: kia762@yandex. ru- 2Filial Moscow state University of instrument engineering and informatics in the city of Stavropol, e-mail: kia762@yandex. ru
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.
Keywords: 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] доказана возможность реализации обобщенного дискретного преобразования Фурье (ДПФ) в кольце полиномов. При этом вычисления организуются в кольце полиномов Рф с коэффициентами в виде
элементов поля GF (p), представляющем собой сумму
P (z) = P (z) + P2(z) + … + Pm (z), (1)
где P (z) — локальное кольцо полиномов, образованное неприводимым полиномом p (z) над полем GF (p) — j = 1, 2,…, m.
В этом случае целесообразно использовать полиномиальную систему классов вычетов (ПСКВ), в которой вычисления организуются параллельно, помодульно и независимо друг от друга, так как операции сложения, вычитания и умножения сводятся к соответствующим операциям над остатками по модулям p^z) над полем
lA (z)®адЦ) =|а,(z)®(z)| jz), (2)
где ® — операции сложения, вычитания и умножения в GF (p) — A (z) = (a^z), a2(z),…, a (z)) и B (z) = (^(z), ?2(z),., b (z)) — модулярный код в кольце полиномов- a (z) = A (z) mod p/z) — b (z) = B (z) modp/z) — l = 1, …, m.
Как показано в работах [1,2,4] обобщенное ДПФ в кольце полиномов, предназначенное для вычисления d спектральных составляющих, будет реализовано в следующем виде
Xk (z)modpj = Мг xn (z)ekn (z) 1 modp], (3)
где { Хк (г), хП (г), вк (г) }ер (г)-Р -порождающий элемент- ] = 1,2,…, т- k = 0,1,.^ - 1.
После выполнения вычислений в СП ПСКВ необходимо осуществить обратное преобразование из модулярного кода в позиционный код. Одним из наиболее привле-
кательных с точки зрения схемных затрата является алгоритм обратного преобразования использующий промежуточную систему — обобщенную полиадическую систему. При этом могут, благодаря параллелизму алгебраической системы, вычисления могут быть реализованы с помощью нейронных сетей [1−3].
В работе [10] приведена нейронная сеть для перевода из модулярного кода ПСКВ в обобщенную полиадическую систему, в которой используется 5 неприводимых полиномов р^) = z + 1, р2^) = z2 + z + 1, р3^) = z4 + z3 + z2 + z + 1, p4(z) = ^ + z3 + 1, p5(z) = z4 + z + 1. Если положить, что первые три основания являются информационными, т. е. k = 3, то рабочий диапазон будет определяться согласно
= П Р№ = г7+г6+г5+г2+г + 1
г=1
Оставшиеся два основания p4(z) = = z4 + z3 + 1 и р5^) = z4 + z + 1, будем считать контрольными модулями, с помощью которых будет производиться поиск и коррекция ошибок, возникающих в кодах ПСКВ.
В этом случае, любой полином, представленный в коде ПСКВ, чья степень будет меньше семи, то есть deg А (г) & lt- 7, является разрешенным, а его кодовая комбинация не содержит ошибки. В противном случае -кодовая комбинация содержит ошибки.
Коэффициенты обобщенной полиадической системы позволяют осуществить поиск и коррекцию ошибок в кодах ПСКВ. Для данного примера полином Аможно представить в обобщенной полиадической системе как
A (z) = a, (z) + a2 (z) p (z) + a3 (z) P* (z) + a4 (z) P* (z) + a5 (z) P4* (z), (4)
где P,'-(z) = p,(z) = z +1- P* (z) = z3 +1-
= f[Pi (z) = Ppa6 (z) = z7+z6+z5+z2+z +1-
& lt-•=1
К (*) = Па (*) = А (г)Рраб (z) = zn+z8+z7+z5+z3+z2+z + l.
i=1
Представим ортогональные базисы выбранной системы в виде коэффициентов ОПС
_, 14 4. т13 4_, 12 4., ll 4., 10 4., 94., 8 z7 + z6 + z5 4-, 44. тЗ 4-, 2
Bj (z) = z14 + z13 + z1 B2(z) = z14 + z13 + z
Biz) = z14 + z13 + z12 + z11 + z 9 + z8 + z7 + z1
— z + 1 = [1, z, z3 + z, z3, z3
— z]-
¦ z10 + z8 + z7 + z 5 + z4 + z2 + z = [0, z, z3 + z2 + 1, z3 + z + 1, z3 + z2]-
4 4_, з, 2 _i_ , —
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]- Biz) = z12 + z9 + z8 + z6 + z4 + z3 + z2 + z = [0, 0, 0, 0, z].
2
Согласно китайской теореме об остатках (КТО) полином Л^) определяется
А (г) = ?а,. (г)ВДто ?Р"шн (г), (5)
?=1
5
где Рполн{2) = П = +1 — полный диа-
?=1
пазон ПСКВ.
Если в качестве ортогональных базисов В. ф взять их представления в ОПС, то при умножении остатков а'-(г) на последние, можно получить коэффициенты ОПС



(6)
PjM
где У'-«ер (, 2) — коэффициенты ОПС /-го ортогонального базиса с учетом переполнения (/-1)-го основания.
Если полином Л^), представленный в ПСКВ, не содержит ошибки, то его степень не превысит степень рабочего диапазона. Следовательно, значения старших
коэффициентов ОПС должны равняться нулю, т. е. а (т) = 0 и а5^) = 0.
Если полином Л*^), представленный в ПСКВ, содержит ошибку, то его значение будет определяться
А'- (г) = (а! (г),…, а,. (г) + а* (г),…, аи (г)) =
= (?(г) + а^Я^пю^Сг) (7)
где а'-^) — глубина ошибки по у-му основанию П скв.
При переводе из ПСКВ в позиционный код ошибочный код Л*(^) окажется за пределами рабочего диапазона Рбф. Тогда, значения старших коэффициентов ОПС будут отличаться от нуля. При этом по величине значений старших коэффициентов ОПС можно однозначно определить местоположение и глубину ошибки.
Чтобы осуществлять коррекцию ошибочного значения коэффициентов ОПС была разработана схема нейросетевого устройства, которая представлена на рисунке.
10…
. -
12
13
14
15
9
10
1, 2,3
2, 4,6
1, 4,5,6,7
2, 3,4,5,7
1, 2,5
2, 4,7,10
2, 3,5,8,11
3, 4,6,8,9
1, 2,3,4,5,6,9 5, 9,11,15
1, 3,5,7,8,9,11,12,15
1, 2,4,5,6,8,9,10,13_
1, 2,3,4,5,6,7,8,9,10,11,14
?
€ €
(28
€ {зо
16
(l7
(5 6

21
22
23 23 32
24 24 33
25 25 34
26 26 35
27 27 36
28 28 37
29 29 38
30 30 39
31
16. 40
17. 41
18. 42
40 40
41 41
42 42
43 43
44 44
45 45
46 46
19,43
20. 44
21. 45
22,46
47
48
49
50
51
52
53
Нейросетевое устройство для коррекции коэффициентов ОПС
Устройство состоит из двухслойной нейронной сети (нейроны 1−15 образуют первый слой, нейроны 16−30 создают второй слой), блока памяти 31, имеющего восемь входов 32−39 и семь выходов 40−46, семи двухвходовых корректирующих сумматоров 47−53.
Каждый слой нейронной сети содержит по 15 нейронов. Входной слой состоит из 15 нейронов, распределенных в соответствии с размерностью разрядных сеток модулей -1−2-4−4-4. Данные нейроны осуществляют разветвление входного вектора кода ПСКВ Л (^) = (а,^), а2^), а3^), а4^), а5^)), представленного в двоичной форме. Второй слой нейронной сети содержит также 15 нейронов, распределенных в соответствии с размерностью разрядных сеток коэффициентов (а / = 1,2,3,4,5) ОПС-1−2-4−4-4. Нейроны 16−30 второго слоя выполняют базовую операцию суммирования по модулю два значений разрядов, поступающих с выходов соответствующих нейронов первого слоя. Синаптические веса связей равны единице.
Выход нейрона 16 соответствует нулевому разряду первого коэффициента ОПС а,^). Нейроны 17, 18 осуществляют вычисление нулевого и первого а0(г), а2(г) разрядов второго коэффициента ОПС соответственно. Нейроны 19, 20, 21, 22 осуществляют вычисление нулевогопервого, второго и третьего разрядов °3 (г ^ 3 (г ^ а32(г), а33(г) третьего коэффициента ОПС а3^) соответственно. Нейроны 23, 24, 25, 26 осуществляют вычисление нулевого, первого, второго и третьего разрядов а°(г), а (г), а2^(г), а34(г) четвертого коэффициента ОПС а4(г) соответственно.
Нейроны 27, 28, 29, 30 осуществляют вычисление нулевого, первого, второго и третьего разрядов а50(г), а5(г), а5(г), а53(г) пятого коэффициента ОПС а5^) соответственно.
Блок памяти 31 имеет 8 входов. На входы 32−35 блока памяти поступают разряды коэффициента ОПС а4^). Значения нулевого, первого, второго и третьего разрядов а5 (г), а5 (г), а5 (г), а| (г) пятого коэффициента ОПС а5^) поступают соответственно на 36−39 входы блока памяти.
Корректирующие сумматоры 47−53 подключены к соответствующим выходам нейронов второго слоя и выходам блока памяти. С выходов этих сумматоров снимаются откорректированные значения коэффициентов ОПС.
Блок памяти предназначен для хранения констант коррекции, значение которых зависит от вычисленных величин старших коэффициентов ОПС. Зависимость значений коэффициентов ОПС а4^) и а5^) от местоположения и глубины ошибки в коде ПСКП приведены в табл. 1.
Зависимость между значениями старших коэффициентов а4^), а5^) и корректирующими значениями коэффициентов ОПС а,^), а2^), а3^) приведена в табл. 2.
Рассмотрим работу устройства. Пусть задан полином Л (2) = zб+z5+z4+z+l, который принадлежит рабочему диапазону Рраб^). Тогда его код в ПСКВ, который не содержит ошибки, имеет вид А (^) = (1, z+1, z3+z2+z+1, z3+z2+z, Воспользуемся
выражением (6) и произведем вычисление коэффициентов ОПС. В результате были получены значения
а (т) = 1, ар) = z+1, а3(z) = z3+z2+z+1, а4^) = 0, а (?) = 0.
Таблица 1
Зависимость значений коэффициентов ОПС от местоположения и глубины ошибки для поля GF (24)
Величина ошибки Коэффициенты ОПС
а, (г) а& lt- (г)
а,*(г) = 1 г3 г3 + г2 + г
аДг) = 1 г3 + г + 1 г3 + г2
аДг) = г г3 + г2 +г г3 + г
а3*(г) = 1 г2 + 1 г3 + г2+ г
а3*(г) = г г3 + г г3 + г2 + г + 1
а3*(г) = г2 г3 + г2 г3 + г2
а3*(г) = г3 1 г3 + г
Таблица 2
Зависимость значений коррекции коэффициентов ОПС от значений старших
коэффициентов а4(г) и а5(г)
Коэффициенты ОПС Коррекция коэффициентов ОПС
a^ (z) (z) Aa,(z) Aa,(z) Aa3(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(г) = 0, а5(х) = 0. В результате этого с выходов 40−46 также снимается нулевой результат, который подается на корректирующие сумматоры 47−53. В соответствии с этим на выходах этих корректирующих сумматоров, выполняющих операцию суммирования по модулю, значения коэффициентов ОПС, а (г) = 1, а2(г) = z+1, а3(г) = z3+z2+z+1, не будут корректироваться.
Пусть произошла ошибкав первом остатке кода ПСКВ и ее глубина равна а1& quot-(г) = 1. В этом случае Л*(г)=(0, z+1, z3+z2+z+1, г3+г2+г, г3+г). Тогда на выходах нейронов 16−30 второго слоя получатся значения коэффициентов ОПС
а1(г) = 0, а (г) = 1, а3(г) = г2+1, а4(г) = г3, а5(г) = г3+г2+г.
В соответствии с полученными значениями а4(г) = г3, а (г) = г3+г2+г с выходов блока памяти, согласно данным приведенным в табл. 2, будут сниматься корректирующие значения Да (г) = 1, Ла2(г) = г, Ла3(г) = г3 + г. Эти значения будут поданы на входы соответствующих сумматоров по модулю два 47−53, где и произойдет коррекция коэффициентов ОПС. В результате на выходе первого 47 корректирующего сумматора получаем
а0(г) + Ао10(г) = 0 + 1 = 1.
На выходе третьего 49 корректирующего сумматора получаем сигнал
4(г) + Л4(г) = 0 + 1 = 1.
Произошло исправление ошибки. Теперь откорректированное значение второго коэффициента ОПС Ла2(г) = г + 1. На выходе четвертого 50 корректирующего сумматора получаем исправленное значение сигнал
а3°(г) + Ла3°(г) = 0 + 1 = 1.
На выходе пятого 51 корректирующего сумматора получаем сигнал
о!(г) + Ла1(г) = 0 + 1 = 1.
Ошибка в разряде исправлена.
На выходе шестого 52 корректирующего сумматора получаем сигнал
а32(г) + Ла32(г) = 0 + 1 = 1.
Ошибка в разряде исправлена.
На выходе седьмого 53 корректирующего сумматора получаем сигнал
а33(г) + Ла33(г) = 1 + 0 = 1.
Ошибка исправлена. Теперь откорректированное значение третьего коэффициента ОПС равно а3(г) = г3+г2+г+1.
Выводы
Повысить скорость выполнения цифровой обработки сигналов можно за счет перехода к параллельным вычислениям. В работе показана целесообразность реализации ЦОС с помощью ПСКВ. Такжего в работе приведен пример реализации алгоритма поиска и коррекции ошибки, который использует старшие коэффициенты обобщенной полиадической системы. Представлена схема нейросетевого устройства, способного исправлять значения коэффициентов ОПС при возникновении ошибки в коде ПСКВ.
СПИСОК ЛИТЕРАТУРЫ
1. Калмыков И. А., Резеньков Д. Н., Горденко Д. В., Саркисов А. Б. Методы и алгоритмы реконфигурации непозиционных вычислительных структур для обеспечения отказоустойчивости спецпроцессоров. — Ставрополь, Фабула. 2014. — 180 с.
2. Калмыков И. А., Саркисов А. Б., Макарова А. В. Технология цифровой обработки сигналов с использованием модулярного полиномиального кода // Известия Южного федерального университета. Технические науки. — 2013. -№ 12 (149). — С. 234−241.
3. Бережной В. В., Калмыков И. А., Червяков Н. И., Щелкунова Ю. О., Шилов А. А. Нейросетевая реализация в полиномиальной системе классов вычетов операций ЦОС повышенной разрядности // Нейрокомпьютеры: разработка и применение. — 2004. — № 5−6. — С. 94.
4. Калмыков И. А., Калмыков М. И. Структурная организация параллельного спецпроцессора цифровой обработки сигналов, использующего модулярные коды // Теория и техника радиосвязи. — 2014. — № 2. — С. 60−66.
5. Калмыков И. А., Зиновьев А. В., Резеньков Д. Н., Га-хов В. Р. Применение систолических ортогональных преобразований в полиномиальной системе классов вычетов для повышения эффективности цифровой обработки сигналов //
Инфокоммуникационные технологии. — 2010. — Т. 8, № 3. -С. 4−11.
6. Калмыков И. А., Хайватов А. Б. Математическая модель отказоустойчивых вычислительных средств, функционирующих в полиномиальной системе классов вычетов // Инфокоммуникационные технологии. — 2007. — Т. 5, № 3. — С. 39−42.
7. Мартиросян А. Г., Калмыков М. И. Основные методы обеспечения отказоустойчивости специализированных вычислительных устройств цифровой обработки сигналов Современные наукоемкие технологии. — 2014. — № 3. -С. 62−67.
8. Калмыков И. А., Саркисов А. Б., Яковлева Е. М., Калмыков М. И. Модулярный систолический процессор цифровой обработки сигналов с реконфигурируемой структурой// Вестник Северо-Кавказского федерального университета. -2013. — № 2 (35). — С. 30−35.
9. Калмыков И. А. Метод пересчета коэффициентов обобщенной полиадической системы для спецпроцессоров с деградируемой структурой // Известия ЮФУ. Технические науки. — 2005. — № 4 (48). — С. 35−42.
10. Стрижков Н. С., Калмыков М. И. Алгоритм преобразования из модулярного кода в полиадическую систему оснований для систем обнаружения и коррекции ошибок // Международный журнал экспериментального образования. — 2014. — № 3−1. — С. 127−131.

ПоказатьСвернуть
Заполнить форму текущей работой