Фильтр нижних частот с использованием БПФ вместо реализации свертки

Question

Внедряя низкочастотный FIR-фильтр, когда следует использовать FFT и IFFT вместо свертки во временной области?

Цель состоит в том, чтобы добиться наименьшего времени процессора, необходимого для расчетов в реальном времени. Как я знаю, FFT имеет около O (n log n) сложности, но свертка во временной области имеет O (n²) сложность. Для реализации фильтра нижних частот в частотной области следует использовать БПФ, затем умножить каждое значение на коэффициенты фильтрации (которые переводятся в частотную область), а затем сделать IFFT.

Итак, вопрос в том, когда оправдано использование частотной (FFT + IFFT) фильтрации вместо использования FIR-фильтра на основе прямой свертки? Скажем, если есть 32 коэффициента с фиксированной запятой, следует использовать FFT + IFFT или нет? Как насчет 128 коэффициентов? И так далее ...

Пытаясь оптимизировать существующий исходный код (FIR-фильтр на основе свертки), я совершенно запутался: мне следует использовать FFT или просто оптимизировать его для использования SSE или нет.

Answer 1

Свертка - это фактически O (m * n), где m - ширина конечной импульсной характеристики, а N - примерное окно.

Таким образом, точка перелома m, где полезно перейти на FFT +IFFT связан с log (N) окна образца.

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

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

Answer 2

Это зависит от того, какую архитектуру вы используете, и от различных других факторов, но общее «практическое правило» для 1D DSP заключается в том, что если размер фильтра небольшой, скажем, менее 100 терминов, вам, вероятно, будет лучше прямая свертка, но для фильтров большего размера, возможно, стоит выполнить быструю свертку в частотной области.

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

Итог: начните с простой прямой свертки, а затем переключитесь на быструю свертку , если вам это нужно. (Вам нужно будет сохранить первую реализацию для проверки второй реализации, чтобы не тратить усилия впустую.)