Transformación de Fourier discreta: Efectos del acolchado cero comparado con la interpolación del dominio del tiempo

Question

Mientras estudiaba las varias implementaciones de algoritmos disponibles en línea del algoritmo de la Transformada Rápida de Fourier, he llegado a una pregunta relacionada con la forma en que el DFT funciona en teoría.

Supongamos que tienes una secuencia de $N$ puntos $x_0, ..., x_{N-1}$ . Para $ k = 0, ..., N-1 $ que $ X_k = \sum_ {n=0}^{N-1} x_n e^{-2ik \pi \frac {n}{N}} $ .

He notado que muchos algoritmos son más fáciles de implementar, o más rápidos, cuando el tamaño de la entrada puede ser expresado como una potencia de 2. Para rellenar la señal, he visto dos enfoques.

• Acompañe la señal con $0$ s, ajustes $x_N, ..., x_{2^p-1} = 0$ y $X_k = \sum_ {n=0}^{N-1} x_n e^{-2ik \pi \frac {n}{2^p}}$
• Interpolar los valores originales, estableciendo $ \tau =N/2^p$ el nuevo espacio entre los puntos consecutivos y luego adivinar los valores en $0, \tau , 2 \tau , ..., (2^p-1) \tau $ a través de la interpolación lineal.

He oído a la gente decir cosas diferentes:

Algunas personas se oponen muy fuertemente al primer enfoque (recientemente tuve una discusión con un profesor de física sobre esto). Dicen que rellenar la señal con ceros adicionales te da los coeficientes de Fourier de una función diferente, que no tendrá ninguna relación con los de la señal original. Por otro lado, dicen que la interpolación funciona muy bien.

Por otro lado, la mayoría de las bibliotecas, si no todas, que he revisado usan la segunda solución.

Todas las referencias que pude encontrar en Internet eran bastante vagas sobre este tema. Algunos dicen que la mejor interpolación de banda limitada que se puede hacer en el dominio de la frecuencia se obtiene a través del acolchado del dominio del tiempo, pero no pude encontrar ninguna prueba de tal afirmación.

¿Podría ayudarme a averiguar qué ventajas e inconvenientes tienen ambos enfoques? Idealmente, estoy buscando algo con un fondo matemático, no sólo ejemplos visuales =)

¡Gracias!

Answer 1

Cero acolchado en el dominio del tiempo corresponde a la interpolación en el dominio de Fourier . Se usa frecuentemente en audio, por ejemplo para recoger picos en el análisis sinusoidal.

Aunque no aumenta la resolución, lo que realmente tiene que ver con la La forma de la ventana y la longitud. Como mencionó @svenkatr, tomar la transformación de una señal que no es periódica en el tamaño del DFT es como multiplicar con un ventana rectangular equivalente a su vez a la convolución de su espectro con la transformación de la función de rectángulo (a sinc), que tiene una alta energía en los lóbulos laterales (frecuencias descentradas), haciendo que los verdaderos picos sinusoidales sean más difíciles de encontrar. Esto se conoce como fuga espectral.

Pero no estoy de acuerdo con @svenkatr que el relleno cero está causando la ventana rectangular, son cuestiones separadas. Si multiplicas tu señal no periódica por una ventana adecuada (como la de Hann o Hamming) que tenga la longitud apropiada para tener la resolución de frecuencia que necesitas y luego el relleno cero para la interpolación en la frecuencia, las cosas deberían funcionar bien.

Por cierto, el acolchado cero no es el único método de interpolación que se puede utilizar. Por ejemplo, en la estimación de los parámetros de los picos sinusoidales (amplitud, fase, frecuencia) en el DFT, se puede utilizar la interpolación cuadrática local (tomar 3 puntos alrededor de un pico y ajustar una parábola) porque es más eficiente desde el punto de vista computacional que el acolchado a la resolución de frecuencia exacta que se desea (significaría un tamaño de DFT mucho mayor).

Answer 2

Intentaré dar una respuesta intuitiva que pueda ser matemáticamente precisa con un análisis cuidadoso.

Primero, imagina que alguien te da el DFT de una función, y resulta ser una constante en todas partes (es decir, para $k = 0,1,2, \ldots N-1$ ). ¿Qué función en el dominio del tiempo tiene tal DFT? La respuesta es una "función delta", es decir, $f(n) = C$ para $n=0$ y $f(n)= 0$ para $n \neq 0$

Estos argumentos funcionan cuando se invierten los dominios, de modo que si se tiene una función constante en el dominio del tiempo, se tendrá una función "delta" en el dominio de la frecuencia. Si decides rellenar tu secuencia de dominio del tiempo con ceros y luego tomar DFT, obtendrás una función sinc en lugar de una función delta. Por lo tanto, estrictamente hablando, al rellenar con ceros, estás distorsionando el DFT de la función.

Sin embargo, hay otra forma de ver esto. Su operación de acolchado por ceros es esencialmente la misma que tomar un conjunto extendido de puntos de la serie temporal original y multiplicarlo por una función rectangular (cuya región no cero está limitada a los puntos $x_0, \ldots x_{N-1}$ ). Por lo tanto, en el dominio de la frecuencia su DFT original es convolucionado por una función sincera. Lo ideal sería que el DFT de la señal original fuera convolucionado con algo que esté cerca de una función delta (ya que esto no distorsiona nada). En nuestro caso, esto significa que debemos al menos asegurarnos de que el sinc tiene un lóbulo principal muy agudo y lóbulos laterales que decaen muy rápido (para aproximarse a una función delta).

Si su función sincera tiene un lóbulo principal muy extendido, su DFT estará muy distorsionado mientras que si el lóbulo principal tiene un pico agudo, la distorsión es muy pequeña. En otras palabras, si usted trató de acolchar su serie de tiempo original por un gran número de ceros, el efecto de la convolución es mucho más pronunciado porque el lóbulo principal del sinc será muy extendido. Si lo rellenas con un pequeño número de ceros, estás muy cerca de hacer convivir el DFT con una función delta, y la distorsión es pequeña.

En cuanto a la interpolación, supongo que ese método también podría funcionar sin dar mucha distorsión, pero el enfoque correcto sería utilizar un filtro de interpolación en lugar de hacer una simple interpolación lineal (como se explica en http://en.wikipedia.org/wiki/Upsampling ). En la práctica, no estoy seguro de que haya una diferencia significativa cuando se trata de señales de buen comportamiento que se muestre adecuadamente.