Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 1,021

АЛГОРИТМ КОРРЕКЦИИ КОЭФФИЦИЕНТОВ ОБОБЩЕННОЙ ПОЛИАДИЧЕСКОЙ СИСТЕМЫ

Калмыков М.И. 1 Дунин А.В. 1 Ашихмин С.В. 2 Любенко Д.В. 2
1 ФГАОУ ВПО «Северо-Кавказский федеральный университет»
2 Филиал Московского государственного университета приборостроения и информатики в городе Ставрополе
Коды полиномиальной системы классов вычетов позволяют проводить вычисления и обработку сигналов в реальном масштабе времени. Такое свойство непозиционных модулярных кодов связано с независимой параллельной обработкой остатков по основаниям системы. Если в состав оснований ввести дополнительные модуля, то коды классов вычетов способны обнаруживать и исправлять ошибки, которые возникают из-за отказа оборудования. В работе представлена нейросетевая реализация алгоритма вычисления коэффициентов обобщенной полиадической системы, позволяющая корректировать ошибки в модулярного коде.
модулярные коды
полиномиальная система классов вычетов
коэффициентов обобщенной полиадической системы
обнаружение и коррекция ошибок
нейронная сеть
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.

Для обеспечения максимальной скорости цифровой обработки сигналов (ЦОС) используют специализированные процессоры (СП). Как правило, такие СП имеют параллельную архитектуру. Чтобы обеспечить предельные показатели при обработке сигналов в ряде работ [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.

Выводы

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


Библиографическая ссылка

Калмыков М.И., Дунин А.В., Ашихмин С.В., Любенко Д.В. АЛГОРИТМ КОРРЕКЦИИ КОЭФФИЦИЕНТОВ ОБОБЩЕННОЙ ПОЛИАДИЧЕСКОЙ СИСТЕМЫ // Современные наукоемкие технологии. – 2015. – № 1-1. – С. 36-41;
URL: http://top-technologies.ru/ru/article/view?id=34987 (дата обращения: 06.12.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074