Filtro de paso bajo usando FFT en lugar de implementación de convolución

Question

Implementando un filtro FIR de paso bajo, ¿cuándo se debe usar FFT e IFFT en lugar de convolución de dominio de tiempo?

El objetivo es lograr el menor tiempo de CPU requerido para los cálculos en tiempo real. Como sé, FFT tiene una complejidad de O (n log n), pero la convolución en el dominio del tiempo es de complejidad O (n²). Para implementar un filtro de paso bajo en el dominio de frecuencia, uno debe usar FFT, luego multiplicar cada valor con coeficientes de filtrado (que se traducen en dominio de frecuencia), luego hacer IFFT.

Entonces, la pregunta es cuándo se justifica utilizar filtros basados ​​en frecuencia (FFT + IFFT) en lugar de usar un filtro FIR basado en convolución directa. Digamos, si uno tiene 32 coeficientes de punto fijo, ¿se debería usar FFT + IFFT o no? ¿Qué hay de 128 coeficientes? Y así sucesivamente ...

Tratando de optimizar un código fuente existente (filtro FIR basado en la convolución), estoy totalmente confundido, o debo usar FFT o simplemente optimizarlo para usar SSE o no.

Answer 1

Convolución es en realidad O (m * n) donde m es el ancho de la respuesta de impulso finito, y N la ventana de muestra.

Así que el punto de inflexión de m donde es útil cambiar a FFT + IFFT está relacionado con el registro (N) de la ventana de muestra.

operación en tiempo real podría ser más importante que la cantidad relativa de ciclos de reloj, ya que puede no ser aceptable esperar 1024 puntos de muestra antes de filtrar, si la aplicación está en un bucle de regulación, por ejemplo .

Ahora se ha avanzado mucho en esta área y hay muchos códigos disponibles, por lo que probar algunas soluciones y realizar comparaciones es la clave aquí.

Answer 2

Depende de la arquitectura que esté utilizando y de otros factores, pero la "regla de oro" general para 1D DSP es que si el tamaño del filtro es pequeño, digamos menos de 100, probablemente esté mejor con convolución directa, pero para tamaños de filtro más grandes puede valer la pena hacer una convolución rápida en el dominio de la frecuencia.

Por supuesto, debe estar seguro de que el filtrado es primero un cuello de botella de rendimiento, ya que no tiene sentido hacer todo el esfuerzo adicional de hacer una convolución rápida si su implementación en el dominio del tiempo ya es lo suficientemente rápida.

En pocas palabras: comience con convolución directa simple y luego cambie a convolución rápida más tarde si lo necesita. (Necesitará mantener la primera implementación para validar la segunda implementación, por lo que no es un esfuerzo desperdiciado, de ninguna manera).