ТеорИнфМетоды / metod_1

4.3. Выбор метода вычисления свертки / корреляции

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

и импульсной характеристики фильтра (ядра свертки)

где . Подобные вычисления могут быть вычислены как на основе прямого алгоритма (см. раздел 1.7), так и через спектральные дискретные преобразования Фурье и Хартли (см. разделы 2.1 и 2.2). Возникает естественный вопрос, какой метод предпочтителен, исходя из меньшего объёма вычислений, а следовательно, и времени, необходимого для реализации данного метода.

Если размер “окна” или ядра свёртки равен , а длина вектора исходных данных, то для полученияотсчётов результата апериодической свёртки необходимо выполнить:

Q_св= MN (БО), (4.4)

где БО – базовая операция, включающая операцию умножения и сложения действительных чисел. Сложность БО составляет:

q_БО= q_умн + q_сл .

Отсюда можно получить, что время вычисления свертки по прямому алгоритму

T_св = Q_св *Δt = MN(q_умн + q_сл) *Δt

где Δt - длительность такта В.У.

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

При вычислении свёртки на основе спектрального преобразования выполняются следующие действия:

Прямые спектральные преобразования Фурье или Хартли исходного вектора.
При вычислении свёртки на основе ДПХ выполняются перекомпоновка полученного спектра (см. раздел 2.6., т.е. формируется и вычисляютсяи.
Поэлементное перемножение спектров для ДПФ :или вычисление всогласно методике в разделе 2.2 - для ДПХ.
Обратное преобразование для функции на основе ДПФ или ДПХ.

Таким образом, если свёртка при вычисляется через ДПФ на основе быстрых алгоритмов:

(4.5)

где

При расчёте свёртки необходимо учитывать, что

где и- сложность операций сложения и умножения комплексных чисел, причём

аналогичных действий с действительными числами, т.е.

Тогда получим

(4.6)

Отсюда нетрудно получить с учетом выражения (4.4), что прямой метод вычисления свёртки предпочтителен, если:

(4.7)

Из (4.7) следует, например, что дляпредельный размердля вычисления по прямому алгоритму, а дляпредельный размер окна составляет

Если свёртка вычисляется на основе БПХ, то при том же числе БО их сложность умножается:

для действительных чисел, однако требуется выполнить операции по вычислению функции , что потребует примерно. С учетом сложности базовых операций при прямом и спектральном алгоритме можно получить, что прямой алгоритм предпочтительнее алгоритма вычисления свертки через БПХ, если :

(4.8)

Что же касается БДОП типа Уолша - Адамара, то базис этих функций для вычисления свёртки мало пригоден, поскольку в отличии от ДПХ для подобных преобразований нет простых формул для связи с ДПФ и не справедлива теорема о свёртке. Известны алгоритмы вычисления свёртки и на основе указанных ДОП [18, 19], однако отсутствие операции умножения при выполнении БДОП не компенсируется сложностью вычисления .

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

Содержание