Cómo calcular eficientemente solo los coeficientes bajos de una FFT con relleno de cero

14

Tengo un algoritmo que pone a cero una secuencia de 4N, hace una FFT y solo usa los puntos N de frecuencia más baja del 4N generado.

Esto parece mucho trabajo desperdiciado, ¿alguna idea de cómo se puede hacer esto más rápido?

Mark Borgerding
fuente
@Dilip. Usaré las bibliotecas FFTW o IMKL. Por supuesto, podría usar mi biblioteca kissfft, pero está comenzando con una desventaja de velocidad frente a los demás
Mark Borgerding, el
2
Eliminé el comentario al que respondiste ya que quise decir decimación en frecuencia pero escribí decimación en tiempo. Pero mira el diagrama de mariposa aquí. Si escribe algún código para las dos primeras etapas para el 4N FFT para tener en cuenta la gran cantidad de ceros y omitir las multiplicaciones correspondientes, puede llamar a la subrutina de la biblioteca FFT 4 veces para N FFT en los que los vectores de entrada estan llenos". Por supuesto, solo necesita N/4 de las salidas de cada llamada de subrutina.
Dilip Sarwate

Respuestas:

2

Si solo tiene unos pocos contenedores, lo siguiente puede ser muy eficiente para usted:
1. Simplemente haga el DFT de cada frecuencia que necesite.
2. Utilice el algoritmo de Goertzel para cada frecuencia en cuestión.

Jacob
fuente
Mark dijo que necesitaba contenedores de 4 N , por lo que 1) parece no ser una opción razonable. El algoritmo de Goertzel tiene ventajas como el cálculo en línea a medida que se reciben los datos, un pequeño almacenamiento, etc., pero necesita 2 N + 4 multiplicaciones por contenedor, mientras que cada contenedor calculado como una evaluación polinómica a través de la regla de Horner necesita solo N multiplicaciones. Por lo tanto, 2) tampoco parece ser una opción particularmente razonable. N4N2N+4norte
Dilip Sarwate
Tienes razón, mientras leía la pregunta, de alguna manera extrañé los detalles. Mientras respondía, pensaba: "Caramba, sería bueno saber cuántos contenedores quiere ..." Supongo que debería volver a leer la pregunta antes de responder.
Jacob
2

Cero relleno a 4X de longitud, calculando la FFT más larga, y luego usando solo los contenedores de 1/4 de fondo produce resultados casi idénticos a la interpolación Sinc en ventana de la FFT de longitud original.

Tan solo use la longitud FFT original e interpolar usando un núcleo de interpolación Sinc trifásico con un ancho de ventana adecuado.

hotpaw2
fuente
0

El relleno cero en el dominio del tiempo le brinda una solución de mayor frecuencia pero no información nueva, por lo que proporciona esencialmente interpolación en el dominio de la frecuencia. Dependiendo de la naturaleza de sus señales y de la precisión requerida, puede obtener los puntos de frecuencia adicionales con una FFT regular de N puntos y realizar una interpolación adecuada (lineal, spline, pchip, sinc, etc.).

Hilmar
fuente
Sea sea ​​un polinomio (posiblemente con coeficientes complejos x i ) de grado N - 1 . Lo evaluamos en los N puntos α n , 0 n N - 1 donde α = exp ( - j 2 π / N ) es un Nx(z)=i=0N1xizixiN1Nαn,0nN1α=exp(j2π/N)N enésima raíz de la unidad, para obtener números X n = x ( α n ) . Estos son valores de x ( z ) en N puntos igualmente espaciados en el círculo unitario. Lo que nosotrosNXn=x(αn)x(z)Nrealmente quiero es los valores de x(z) en donde β = exp ( - j 2 π / 4 N ) , que sonβn,0nN1β=exp(j2π/4N) puntos en elprimer cuadrantedel círculo unitario. No veo cómo va a funcionar la interpolación lineal, spline, etc. Por favor explique. N
Dilip Sarwate
Lo siento, esa penúltima oración en mi comentario anterior debería haber dicho cuarto cuadrante del círculo de la unidad. Como , cada cuarto valor deseado x ( β 4 k ) ya ha sido calculado por la FFT: β4=αx(β4k) . x(β4k)=x(αk)
Dilip Sarwate
Sospecho que sería difícil hacer una interpolación decente más rápido que hacer la FFT más grande.
Mark Borgerding
Digamos que tiene una FFT de 128 puntos y una frecuencia de muestreo de 12800Hz. Un FFT de 128 puntos proporciona valores a 0Hz, 100Hz, 200 Hz, 300Hz, etc. Lo que hace el relleno cero es aumentar la resolución de frecuencia a 0 Hz, 25Hz, 50 Hz, 100Hz, etc. Esto puede verse como un problema de interpolación. Para mí, matemáticamente precisado, necesitas hacer una intoppolación circular sinc de 128 ° orden. Que sin duda no vale la pena la molestia, pero dependiendo de la aplicación y la precisión necesaria una gran parte de interpolación de orden inferior sería lo suficientemente bueno
Hilmar