Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

APPLICATION OF POLYNOMIAL SYSTEM OF RESIDUE CLASS IN PROBLEMS DIGITAL FILTERING

Rezenkov D.N. 1 Shaposhnikov A.V. 2 Kalmykov I.A. 2 Shlaev D.V. 1 Ermakova A.N. 1
1 Federal State Educational Institution of Higher Professional Education Stavropol State Agrarian University
2 Federal State Autonomous Educational Institution of Higher Professional Education North-Caucasus Federal University
Application of polynomial system of residue class allows to detect and correct errors in the operation non-positional special processor and provides fault tolerance. Failover specialized digital signal processors are to ensure continuity of operation due to testing and restarting the reconfiguration. Thus, for the construction of digital filter implementation requires an effective ratio of discrete convolution type, which in turn is decomposed into a weighted summation operation at regular intervals delayed input signal. Furthermore, the polynomial system of residue class extended Galois field has the capacity to variations in accuracy, speed and reliability of information in the process of calculation. This ability is based on the exchange transactions polynomial system of residue classes.
polynomial system of residue classes
fault tolerance
digital signal processing
Gordenko D.V., Gordenko N.V. Lokalizacija oshibok v ustrojstvah cifrovoj obrabotki signalov na osnove algebry polinomov [Localization errors in digital signal processing devices based on the algebra of polynomials], Vestnik SevKavGTI [Herald NCSTU], 2009, no. 9, pp. 56–61.
Gordenko D.V., Gordenko N.V. Nejronnaja realizacija lokalizacii oshibok v moduljarnom kode [Neural implementation of localization errors in the modular code], Issledovanija v oblasti estestvennyh nauk [Research in Natural Sciences], 2013, no. 7(19), pр. 1.
Slyusarev G.V., Fedorenko I.V. Modelirovanie podsistemy sbora i obrabotki izmeritelnoj informacii v scada-sisteme [Modeling subsystem for collecting and processing the measurement information in the scada-system], Avtomatizacija, telemehanizacija i svjaz v neftjanoj promyshlennosti [Automation and remote control of the connection in the oil industry], 2010, no. 6, pp. 26–28.
Timoshenko L.I. Analiz osnovnyh metodov prjamogo preobrazovanija iz pozicionnoj sistemy schislenija v moduljarnyj polinomialnyj kod [Analysis of the main methods of direct conversion of positional number system to the modular polynomial code], Sovremennye naukoemkie tehnologii [Modern high technologies], 2007, no. 9, pp. 23–24.
Timoshenko L.I. Primenenie matematicheskoj modeli obladajushhej svojstvom kolca, dlja realizacii cifrovoj obrabotki signalov [The application of the mathematical model with the property of the ring, for the implementation of digital signal processing], Sovremennye naukoemkie tehnologii [Modern high technologies], 2007, no. 9, pp. 22–23.
Kharechkina Yu.O., Malofey O.P. Algoritm rasshirenija dinamicheskogo diapazona polinomialnoj sistemy klassa vychetov [Algorithm of dynamic range expansion of a polynomial system of residue class], Nejrokompjutery: razrabotka i primenenie [Neurocomputers: development and application], 2014, no. 9, pp. 88–91.

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

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

Рассмотрим функционирование цифрового фильтра с конечной импульсной характеристикой, отклик которого задается уравнением

rezen73.wmf (1)

или, иначе,

yn = b0xn + b1xn–1 + b2xn–2 + … + bnxn–N + 1. (2)

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

Для конечных последовательностей обычно применяется линейная свертка y(n), которая для двух конечных последовательностей x(n) и h(n) длины N1 и N2 будет содержать N1 + N2 – l отсчетов

rezen74.wmf, (3)

для отрицательных значений индексов значение h берется равным нулю.

Для описания процессов фильтрации можно применить алгебру полиномов, приняв отсчеты импульсной характеристики h и входного сигнала x соответствующими полиномиальными коэффициентами. Если длину последовательностей принять равной N, то вычисление линейной свертки будет представлять собой произведение полиномов

rezen75.wmf

rezen76.wmf (4)

Одним из методов вычисления свертки является применение различных ортогональных преобразований. При этом образы, полученные при ортогональных преобразованиях последовательностей x(m) и h(n), перемножаются, затем осуществляется обратное преобразование. Во многих практических задачах последовательности обрабатываемых данных представляют собой целые числа, в остальных случаях можно этого добиться путем масштабирования.

Пример 1. Пусть требуется вычислить линейную свертку двух последовательностей x = {1, 3, 2} и h = {3, 2, 1}. Полиномы при этом будут представлять собой

X(z) = z2 + 3z + 2

и

H(z) = 3z2 + 2z + 1.

Перемножив X(z) и H(z), получим полином

Y(z) = H(z) X(z) = (z2 + 3z + 2)(3z2 + 2z + 1) = = 3z4 + 11z3 + 13z2 + 7z + 1,

коэффициенты которого равны отсчетам линейной свертки.

В предположение того, что входной сигнал и импульсная характеристика фильтра ограничены и не превышают некоторого простого числа p/2, для вычислений можно применить поля Галуа GF(pn). Если полином P(z) приводим над полем GF(pn) и раскладывается в произведение d неприводимых полиномов Pi(z)

rezen77.wmf (5)

то вычисления можно распараллелить по модулю каждого из полиномов Pi(z), вычислив

Yi(z) = Hi(z) Xi(z) mod Pi(z), (6)

где Hi(z) и Xi(z) вычеты полиномов H(z) и X(z) по модулю Pi(z).

Восстановление результата Y(z) производится на основе Китайской теоремы об остатках (КТО) для системы взаимно простых полиномов Pi(z)

rezen78.wmf (7)

где rezen79.wmf

rezen80.wmf – ортогональные базисы,

rezen81.wmf – веса базисов.

Вычисления по модулю каждого полинома можно проводить параллельно, это говорит о равноправности остатков. Малоразрядность остатков подразумевает более простую реализацию вычислений, чем при прямом вычислении свертки (3). Если полином P(z) раскладывается на d полиномов первого порядка вида z – α, где α Î GF(p), то вычисления по модулю каждого из таких полиномов сводятся к умножению двух констант по модулю простого p.

Модель вычисления свертки в системе взаимно простых полиномов Pi(z) предполагает:

1. Приведение двух полиномов H(z) и X(z) по модулю pi(z).

2. Умножение вычетов полиномов Hi(z) и Xi(z)по модулю pi(z) (6).

3. Восстановление результата при помощи КТО (7).

Пример 2. Пусть требуется вычислить непериодическую свертку последовательностей x = {1, 3, 1} и h = {2, 0, 1}. Полиномы при этом будут представлять собой X(z) = z2 + 3z + 1 и H(z) = 2z2 + 1. Перемножив X(z) и H(z), получим полином

Y(z) = H(z) X(z) = (z2 + 3z + 1)(2z2 + 1) = 2z4 + 6z3 + 3z2 + 3z + 1,

коэффициенты которого равны отсчетам линейной свертки.

Значения последовательностей не превосходят 3, полиномиальные преобразования можно определить по модулю 7 в поле GF(7). Порядок полинома преобразования должен быть больше 4. Пусть

P(z) = z5 + z4 + z3 + z2 + z + 1,

который в поле GF(76) может быть факторизован

Y(z) = H(z) X(z) = (z + 1) (z + 2) (z + 3) (z + 4) (z + 5).

Воспользуемся описанной ранее методикой для вычисления линейной свертки. Для этого:

Приведем полиномы H(z) и X(z) по модулю pi(z).

Найдем Hi(z) = H(z) mod pi(z):

H1(z) = H(z) mod p1(z) = (2z2 + 1) mod (z + 1) = 3;

H2(z) = H(z) mod p2(z) = (2z2 + 1) mod (z + 2) = 2;

H3(z) = H(z) mod p3(z) = (2z2 + 1) mod (z + 3) = 5;

H4(z) = H(z) mod p4(z) = (2z2 + 1) mod (z + 4) = 5;

H5(z) = H(z) mod p5(z) = (2z2 + 1) mod (z + 5) = 2.

Найдем Xi(z) = X(z) mod Pi(z):

X1(z) = X(z) mod p1(z) = (z2 + 3z + 1) mod (z + 1) = 6;

X2(z) = X(z) mod p2(z) = (z2 + 3z + 1) mod (z + 2) = 6;

X3(z) = X(z) mod p3(z) = (z2 + 3z + 1) mod (z + 3) = 1;

X4(z) = X(z) mod p4(z) = (z2 + 3z + 1) mod (z + 4) = 5;

X5(z) = X(z) mod p5(z) = (z2 + 3z + 1) mod (z + 5) = 4.

Умножим вычеты полиномов Hi(z) и Xi(z) по модулю p

Yi(z) = Hi(z)⋅Xi(z) mod 7:

Y1(z) = H1(z)⋅X1(z) mod 7 = 6⋅3 mod 7 = 4;

Y2(z) = H2(z)⋅X2(z) mod 7 = 6⋅2 mod 7 = 5;

Y3(z) = H3(z)⋅X3(z) mod 7 = 1×5 mod 7 = 5;

Y4(z) = H4(z)⋅X4(z) mod 7 = 5×5 mod 7 = 4;

Y5(z) = H5(z)⋅X5(z) mod 7 = 4⋅2 mod 7 = 1.

Восстановим результаты при помощи КТО. Для этого найдем ортогональные базисы (7):

S1(z) = 5z4 + 5z2 + 5, S2(z) = z4 + 6z3 + 3z2 + 2z + 4,

S3(z) = 2z4 + 3z3 + 2z + 3, S4(z) = z4 + 4z3 + 6z2 + 5z + 2, S5(z) = 5z4 + z3 + 5z + 1.

Обратное преобразование дает

Y(z) = 4(5z4 + 5z2 + 5) + 5(z4 + 6z3 + 3z2 + 2z + 4) + 5(2z4 + 3z3 + 2z + 3) + + 4(z4 + 4z3 + 6z2 + 5z + 2) + 5z4 + z3 + 5z + 1 mod 7 = 2z4 + 6z3 + 3z2 + 3z + 1,

что соответствует ранее вычисленному полиному.

Устройства, функционирующие в полиномиальной системе класса вычетов, обладают следующими достоинствами:

1. Независимость разрядов обуславливает возможность построения автономных вычислительных трактов (каналов) по каждому основанию и позволяет считать последние независимыми элементами.

2. Равноправность разрядов дает возможность изменения функциональных назначений последних, выражающуюся в переводе информационных вычислительных каналов в множество избыточных и наоборот.

3. Использование табличных методов реализации арифметических операций обуславливает малый разброс надежных характеристик вычислительных каналов.

4. Отсутствие межразрядных переносов по основаниям полиномиальной системы классов вычетов.

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

Кроме того, полиномиальная система классов вычетов расширенного поля Галуа обладает способностью к варьированию точностью, быстродействием и информационной надежностью в процессе вычисления. Данная способность базируется на обменных операциях полиномиальной системы классов вычетов. В настоящее время проявляется повышенный интерес к возможности варьирования корректирующей способностью модулярного кода за счет изменения точности и производительности вычислений в пределах одного цифрового устройства. В первую очередь это объясняется тем, что учет указанного свойства полиномиальной системы классов вычетов является мощным средством повышения надежности, т.е. при отказе r каналов их можно просто удалить из процессора, не оказывая влияния на точность выполнения задания. Но, с другой стороны, данные r избыточных каналов предопределяют корректирующие способности вычислительной системы, другими словами – гарантию защиты от недостоверного результата.

Таким образом, изменяя количество информационных и избыточных оснований в заданной структуре специализированных процессоров полиномиальной системы классов вычетов, можно варьировать его основными показателями – точностью, информационной надежностью вычислительной системы. Если некоторая упорядоченная полиномиальная система классов вычетов расширяется путем добавления оснований, каждое из которых больше основания исходной полиномиальной системы классов вычетов, то минимальное кодовое расстояние автоматически увеличивается [1].

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

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

Рецензенты:

Пашинцев В.П., д.т.н., профессор кафедры информационной безопасности автоматизированных систем, Институт информационных технологий и телекоммуникаций, ФГАОУ ВПО «Северо-Кавказский федеральный университет», г. Ставрополь;

Линец Г.И., д.т.н., профессор, заведующий кафедрой инфокоммуникаций, Институт информационных технологий и телекоммуникаций, ФГАОУ ВПО «Северо-Кавказский федеральный университет», г. Ставрополь.