В области цифровой фильтрации различают фильтры с конечной импульсной характеристикой (КИХ-фильтры) и бесконечной импульсной характеристикой (БИХ-фильтры). Данные фильтры относятся к классу линейных систем с постоянными параметрами, в которых входная x_n и выходная y_n последовательности связаны отношениями типа свертки. Если обозначить через h_k отклик системы на единичный импульс (импульсную характеристику), то получим свертку вида

                                             (1)

где x_n и y_n-отсчеты входного и выходного сигналов; x_n-k – входной отсчет, задержанный на k интервалов дискретизации.

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

                                              (2)

где N, M – постоянные целые числа; b_k, a_k – постоянные коэффициенты, описывающие конкретную систему; x_n и y_n-отсчеты входного и выходного сигналов.

Отклик КИХ-фильтр задается уравнением

                                                 (3)

или иначе

                                      (4)

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

Вычисление свертки делится на вычисление циклической и линейной свертки. Циклическая свертка применяется для обработки периодических сигналов. Вычисление циклической y(n) последовательностей x(n) и h(n) может быть представлено в виде

                                         (5)

при этом индексы n, m и n-m определены в конечном кольце по модулю N.

Для конечных последовательностей обычно применяется линейная, а не циклическая свертка. Линейная свертка y(n) двух конечных последовательностей x(n) и h(n) длины N₁ и N₂ будет содержать N₁+N₂-1 отсчетов.

                                     (6)

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

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

Анализ вычислений линейной свертки конечных последовательностей показал, что при величинах (N₁+N₂-1)>80 сказываются преимущества в производительности быстрой свертки (свертки с применением преобразований).

Во многих практических задачах цифровой обработки сигналов (ЦОС) необходимо вычислять свертку двух конечных последовательностей, когда одна из них гораздо длиннее другой, например N₁>>N₂. При этом можно применить одно из ортогональных преобразований ЦОС, для двух конечных последовательностей, но такой подход не эффективен. Во-первых, перед вычислением свертки нужно иметь всю более длинную последовательность. На практике это условие не всегда выполнимо. Во-вторых, поскольку обработка начинается только после приема всей последовательности, то результат вычисляется с большой задержкой. Кроме того, при слишком больших значениях (N₁+N₂-1) выполнение преобразований значительно усложняется.

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

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

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

                                            (7)

Предположим теперь, что N элементов x_m и h_n представляются как полиномы H(z) и X(z) степени N-1 от z, где z-полиномиальная переменная. Тогда,

                                                (8)

                                                (9)

Если перемножить H(z) и X(z), то получится полином Y(z) степени 2N-2. Таким образом,

                                                (10)

При умножении полиномов каждый коэффициент a_l получается суммированием всех произведений h_nx_m, таких, что n+m=l. Следовательно, m=l-n и

                                                  (11)

                                                (12)

Это означает, что свертка двух последовательностей может рассматриваться как произведение двух полиномов. Более того, если свертка циклическая, то индексы l, m и n определены по модулю N. Так что в N-точечной циклической свертке N=0. Из этого следует, что z^N≡1 и тогда циклическая Светка может рассматриваться как произведение двух полиномов по модулю полинома z^N-1:

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

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

,                                                 (13)

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

                                            (14)

где H_i(z) и X_i(z) вычеты полиномов H(z) и X(z) по модулю P_u(z).

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

                                                 (15)

где

                                             (16)

,                                     (17)

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

Приведение H(z) и X(z) по модулю P_i(z), i=1,…, d

Вычисление произведений H_i(z) и X_i(z) по модулю P_u(z)

Восстановление результата по полученным произведениям используя КТО

Следовательно, приведения по модулю и обратные восстановления реализуются очень просто, и главной проблемой при вычислении сверток является вычисление произведений полиномов по модулю.

Предложенный алгоритм вычисления линейной свертки особенно эффективен при вычислении отклика многозвенного фильтра.

1. Горденко Д.В., Резеньков Д.Н., Яйлаханов С.В. Высоконадежные комплексы и средства связи на нейросетевых элементах. – Москва, 2010.
2. Горденко Д.В., Токарева Г.В. Принципы построения модулярных отказоустойчивых специализированных процессоров для обработки экономической информации. //Актуальные проблемы развития агробизнеса в условиях модернизации экономики// – Ставрополь, 2012. С. 71-77.
3. Горденко Д.В., Горденко Н.В., Павленко Н.А., Павлюк Д.Н., Ткачук Р.В. Коррекция ошибок в системе остаточных классов с минимальной временной сложностью на основе метода расширения оснований.//Известия высших учебных заведений. Северо-Кавказский регион. Серия: Технические науки//. 2007.№ 4. С. 12-14.
4. Горденко Д.В., Пономаренко М.В. Применение AN-кодов для коррекции ошибок в модулярных нейрокомпьютерах в области экономики.//Актуальные проблемы развития агробизнеса в условиях модернизации экономики.// – Ставрополь, 2012. С. 78-82.
5. Калмыков И.А., Резеньков Д.Н., Горденко Д.В., Саркисов А.Б. Методы и алгоритмы реконфигурации непозиционных вычислительных структур для обеспечения отказоустойчивости спецпроцессов. – Ставрополь, 2014.
6. Ткачук Р.В., Горденко Д.В., Павлюк Д.Н., Малофей А.О. Активная безопасность на основе криптографического мультинейропроцессора обработки данных. //Известия высших учебных заведений. Северо-Кавказский регион. Серия: Технические науки//. 2007.№ 4. С. 17-18.
7. Горденко Д.В., Горденко Н.В. Локализация ошибок в устройствах цифровой обработки сигналов на основе алгебры полиномов.//Вестник СевКавГТИ//. 2009. № 9. С. 56-61.
8. Горденко Д.В., Резеньков Д.Н., Сапронов С.В. Нормированный след полинома в процедурах поиска и локализации ошибок в модулярных кодах.// Вестник СевКавГТИ//. 2010. № 10. С. 72-73.
9. Горденко Д.В., Горденко Н.В. Нейронная реализация локализации ошибок в модулярном коде.//Исследования в области естественных наук//. 2013. № 7 (19). С. 1.
10. Червяков Н.И., Горденко Д.В. Нейронная сеть для округления и масштабирования чисел, представленных в системе остаточных классов.//Патент на изобретение RUS 2271570 26.05.2003//
11. Червяков Н.И., Горденко Д.В., Сивоплясов Д.В., Ткачук Р.В. Модулярный сопроцессор для обработки биометрической информации.//Известия Южного федерального университета. Технические науки//. 2003. № 4 (33). С. 240-242.
12. Горденко Д.В. Принципы построения модулярных отказоустойчивых специализированных процессоров для обработки информации.//Исследования в области естественных наук//. 2013. № 8 (20). С. 1.
13. Горденко Д.В., Токарева Г.В. Нейронная сеть для преобразования чисел, представленных в позиционном коде в систему остаточных классов.// Информационные системы и технологии как фактор развития экономики региона//. 2013. С. 60-63.
14. Горденко Д.В., Горденко Н.В. Нейронная сеть Хэмминга для преобразования модулярного кода в позиционный.//Исследования в области естественных наук//. 2013. № 11 (23). С. 5.
15. Горденко Д.В. Перспективное развитие вычислительной техники на основе непозиционного нейрокомпьютера.//Исследования в области естественных наук//. 2013. № 12 (24). С. 3.
16. Горденко Д.В., Резеньков Д.Н., Кондрашов А.В. Модулярные нейронные сети в автоматизированных системах управления.//Культура и общество: история и современность материалы II Всероссийской (с международным участием) научно-практической конференции. под редакцией: Колосовой О.Ю., Гударенко Р.Ф., Ряснянской Н.А., Красиковой Е.А.//. 2013. С. 63-67.
17. Горденко Д.В., Горденко Н.В. Неисправности в запоминающих устройствах и в нейронных сетях.// Культура и общество: история и современность материалы II Всероссийской (с международным участием) научно-практической конференции. под редакцией: Колосовой О.Ю., Гударенко Р.Ф., Ряснянской Н.А., Красиковой Е.А.//. 2013. С. 67-70.
18. Горденко Д.В., Резеньков Д.Н. Сравнительный анализ метода контроля арифметических операций в системе остаточных классах.// Современные проблемы науки и образования//. 2014. № 3. С. 148.
19. Кондрашов А.В., Горденко Д.В., Резеньков Д.Н. Контроль арифметических операций в системе остаточных классов.//Исследования в области естественных наук//. 2014. № 6 (30). С. 6.
20. Горденко Д.В., Кондрашов А.В. Обнаружение и коррекция ошибок в арифметических операциях.// Исследования в области естественных наук//. 2014. № 7 (31). С. 25-30.
21. Горденко Д.В., Кондрашов А.В., Дорошев А.В. контроль арифметических операций на основе применения AN-кодов. //Исследования в области естественных наук//. 2014. № 11 (35). С. 47-50.

Все статьи автора «Горденко Дмитрий Владимирович»