НЕКОТОРЫЕ МОДЕЛИ ВЫЧИСЛЕНИЯ СВЕРТКИ

ВЕСТНИК
УДМУРТСКОГО
УНИВЕРСИТЕТА
КОМПЬЮТЕРНЫЕ НАУКИ
2008. Вып. 2
УДК 519.254
c
⃝Т. М. Спичкина
НЕКОТОРЫЕ МОДЕЛИ ВЫЧИСЛЕНИЯ СВЕРТКИ
Предложены три модели вычисления свертки: основанная на нахождении решения некоторой линейной алгебраической системы; содержащая сдвиги; основанная на билинейных формах. Приведена вычислительная эффективность этих
моделей по сравнению с имеющимися моделями.
Ключевые слова: свертка, число отсчетов сигнала.
Введение
Эффективность вычисления свертки для конкретной задачи зависит от
выбранной модели. Существует множество таких моделей, отличающихся
друг от друга, в том числе, числом отсчетов сигнала. Универсальных моделей значительно меньше, и их вычислительные затраты по-прежнему
высоки. В работе предложены три универсальные модели, первые две дают вычислительную выгоду относительно имеющихся универсальных моделей.
Линейная алгебраическая система
Пусть y  свертка функции x = (x0, x1, . . . , xn−1) с импульсной характеристикой h = (h0, h1, . . . , hn−1) является решением некоторой алгебраической системы Ay = b. Будем выбирать систему таким образом, чтобы вычислительные затраты были минимальны. Это возможно достичь
в случаях, когда при решении системы проводятся операции с числами
±1, ±0.5, ±2 , так как в этих случаях операции умножения фактически не выполняются. Данным условиям удовлетворяет система с матрицей
A = (aij)n−1
0
и вектором b = (bj)n−1
0
, где при i = 0, n −1, j = 0, n −1
aij = 1 −2(1 −δi0)δij
(δij  символ Кронекера),
xi
bj =
δ0j +
(1 −δ0j).
!
Ã
i=0
xi
i=0
hi
i=0
k=0
(−1)δ(i+k) mod n,jhk
!!
Ãn−1
X
! Ãn−1
X
n−1
X
Ãn−1
X
Оценка числа умножений при решении системы методом Гаусса дает нулевое число существенных умножений. Составляется система за k = n2−n+1
умножений, то есть на вычисление свертки требуется k умножений.