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


ВЕСТНИК УДМУРТСКОГО УНИВЕРСИТЕТА


КОМПЬЮТЕРНЫЕ НАУКИ



2008. Вып.2

УДК 519.254

© Т. М. Спичкина




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




Предложены три модели вычисления свертки: основанная на нахождении решения некоторой линейной алгебраической системы; содержащая сдвиги; основанная на билинейных формах. Приведена вычислительная эффективность этих моделей по сравнению с имеющимися моделями.

Ключевые слова: свертка, число отсчетов сигнала.





                Введение





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





                Линейная алгебраическая система





   Пусть у — свертка функции x = (xо ,x i,... ,xₙ₋1) с импульсной характеристикой h = (hо, h ₁,..., hₙ₋1) является решением некоторой алгебраической системы Ay = b. Будем выбирать систему таким образом, чтобы вычислительные затраты были минимальны. Это возможно достичь в случаях, когда при решении системы проводятся операции с числами ± 1, ±0.5, ±2 , так как в этих случаях операции умножения фактически не выполняются. Данным условиям удовлетворяет система с матрицей A = (aij )П-¹ и век тором b = (bj )П-¹, где при i = 0 ,n — 1, j = 0 ,n — 1


  aij = 1 — 2(1 — bi о) bij (bij — символ Кронекера),


bj ⁼

     (n-1 \ n--1 \ n-1  / n-~1           \\
Lxi   Iehi ьоj+e  h  m—1)s(^+k>--jMJ


⁽¹ — b 0 j ).

Оценка числа умножений при решении системы методом Гаусса дает нулевое число существенных умножений. Составляется система за k = n²—n+1 умножений, то есть на вычисление свертки требуется k умножений.