Быстрая свертка дискретных сигналов, как? Опции

[phantom]

Надо написать алгоритм КИХ фильтрации. Особенность процесса такова, что сигнал выдается фрагментами (начиная от 64 отсчетов).Светрку реализовили через БПФ в нескольких вариантах (overlap&save, overlap&add), но необходимой производительности достичь не удалось (получается в 2-8раз медленнее чем у существующих программ). Причем у программ-аналогов загрузка процессора практически не зависит от длины импульсной характеристики, а у нас - чем больше длина ИХ, тем больше времени требуется на обработку. Думали может БПФ медленное, заменили на Intel FFT которое в 10 раз быстрее общепринятых алгоритмов, но это существенно не помогло. Осталось попаробовать метод блоков переменной длины, но не совсем понятно как это работает. Что можно было бы сделать?

[thermit]

phantom:
Во-первых, прямое БПФ размера 2*М, где М-длина блока, у меня вычисляется всего один раз - для каждого входного блока, т.к. БПФ импульсной характеристики я считаю перед началом процесса (импульсная характеристика разбивается на перекрывающиеся блоки длины 2*М).

Cправедливо. Я описал общий алгоритм.В частности БПФ исходного сигнала можно вычислять 1 раз, а вторая компонента свертки, если она константа, может храниться уже в виде спектра.

Во-вторых, обратное БПФ того же размера у меня вычисляется, как ни удивительно это звучит, тоже всего один раз - за счет суммирования перекрывающихся результатов сверток в частотной области (см. статью: http://www.ramsete.com/Public/Presentations/mohonk_2003.pdf)

Ничего удивительного. Результат, который Вы получаете не свертка, а ее маленький кусок.

Таким образом, для каждого входного блока имеем при М=64:
1) БПФ+ОБПФ размера 128 по основанию 2: 1792 комплексных умножений-сложений
2) Умножение спектров: 2032*128*(6 вещ *, 4 вещ+) = 1560576*, 1040384+
3) Суммирование перекрытий в частотной области: 2031*128=259968+
Ну так и сколько там того БПФ?

Да. БПФ-а тут мало. Если сигналы вещественные, то спектры их сопряжены относительно 0.
Из 128-и отсчетов спектра можно использовать 65.
Кроме того, комплексное умножение хочет 4 вещественных умножения и 2 сложения.

Сообщение отредактировал thermit - Feb 1 2010, 15:29