Фильтр низких частот с помощью FFT вместо реализации свертки
Реализация низких частот фильтр FIR, когда нужно использовать FFT и IFFT вместо пространственно-временной свертки?
Цель состоит в том, чтобы достигнуть самого низкого процессорного времени, требуемого для вычислений в реальном времени. Как я знаю, FFT имеет о O (n, регистрируют n), сложность, но свертка во временном интервале имеет O (n ²) сложность. Для реализации фильтра низких частот в частотной области нужно использовать FFT, затем умножить каждое значение с фильтрацией коэффициентов (которые переводятся в частотную область), затем сделайте IFFT.
Так, вопрос состоит в том, когда он выравнивается по ширине для использования основанный на частоте (FFT+IFFT) фильтрация вместо того, чтобы использовать прямой основанный на свертке фильтр FIR? Скажите, если у Вас есть 32 коэффициента фиксированной точки, FFT+IFFT должен использоваться или нет? Как насчет 128 коэффициентов? И так далее...
Пытаясь оптимизировать существовавший исходный код (основанный на свертке фильтр FIR), я полностью смущен, или я должен, чтобы использовать FFT или просто оптимизировать его для использования SSE или нет.
2 ответа
Свертка фактически равна O (m * n), где m - ширина конечной импульсной характеристики, а N - окно выборки.
Таким образом, критическая точка m, когда полезно перейти на БПФ + ОБПФ, связана с логарифмом (N) окна выборки.
При работе в реальном времени тот факт, что БПФ ориентирован на пакетную обработку, может быть более важным, чем относительное количество тактовых циклов, поскольку может быть неприемлемо ждать 1024 точки выборки перед фильтрацией, если приложение, например, находится в контуре регулирования.
Сейчас в этой области была проделана большая работа, и доступно большое количество кода, поэтому ключевым моментом здесь является попытка нескольких решений и сравнительный анализ.
Это зависит от того, какую архитектуру вы используете, и от различных других факторов, но общее «практическое правило» для 1D DSP состоит в том, что если размер фильтра небольшой, скажем, менее 100 членов, вам, вероятно, лучше использовать прямую свертку, но для фильтров большего размера, возможно, стоит выполнить быструю свертку в частотной области.
Конечно, вам нужно сначала убедиться, что фильтрация является узким местом производительности, поскольку нет смысла прилагать все дополнительные усилия для выполнения быстрой свертки, если ваша реализация во временной области уже достаточно быстра.
Итог: начните с простой прямой свертки, а затем переключитесь на быструю свертку , если вам это нужно. (Вам нужно будет сохранить первую реализацию для проверки второй реализации, чтобы не тратить зря усилия ни в коем случае.)