¿Por qué debería rellenar con cero una señal antes de tomar la transformada de Fourier?


77

En una respuesta a una pregunta anterior , se dijo que uno debería

rellene con cero las señales de entrada (agregue ceros al final para que al menos la mitad de la onda esté "en blanco")

¿Cuál es la razón de esto?


Depende de lo que estés haciendo. Esto podría haber sido un comentario sobre mi respuesta. Le agregué alguna explicación.
endolito el

@endolith: Inicialmente pensé en ponerlo como un comentario, pero creo que la pregunta puede ser de interés general, y que sería una lástima si una buena respuesta se ocultara en los comentarios en alguna parte. Si no está de acuerdo, eliminaré esta pregunta.
Jonas

99
Bueno, es una pregunta muy general. Usted puede poner a cero la almohadilla para hacer algo un poder-de-2, se puede poner a cero la almohadilla para hacer circular la transformada se comportan como no circular transformar, puede hacerlo volver a muestrear una señal, para cambiar la resolución de frecuencia, etc, etc
endolito

Respuestas:


82

El relleno cero le permite a uno usar una FFT más larga, lo que producirá un vector de resultado FFT más largo.

Un resultado FFT más largo tiene más intervalos de frecuencia que están más espaciados en frecuencia. Pero esencialmente proporcionarán el mismo resultado que una interpolación Sinc de alta calidad de una FFT más corta sin relleno de cero de los datos originales.

Esto podría dar como resultado un espectro de aspecto más suave cuando se traza sin más interpolación.

Aunque esta interpolación no ayudará con la resolución o la resolución de y / o entre frecuencias adyacentes o cercanas, podría facilitar la resolución visual del pico de una sola frecuencia aislada que no tenga señales adyacentes significativas o ruido en el espectro . Estadísticamente, la mayor densidad de los contenedores de resultados FFT probablemente hará que sea más probable que el bin de magnitud pico esté más cerca de la frecuencia de una frecuencia de entrada aislada aleatoria sinusoide y sin interpolación adicional (parabólico, et.al.).

Pero, esencialmente, el relleno cero antes de un DFT / FFT es un método computacionalmente eficiente de interpolar una gran cantidad de puntos.

El relleno de cero para el filtrado de correlación cruzada, autocorrelación o convolución se utiliza para no mezclar los resultados de convolución (debido a la convolución circular). El resultado completo de una convolución lineal es más largo que cualquiera de los dos vectores de entrada. Si no proporciona un lugar para poner fin a este resultado de convolución más largo, la convolución rápida FFT simplemente lo mezclará y desmenuzará el resultado deseado. El relleno cero proporciona un montón de ceros para mezclar el resultado más largo. Y es mucho más fácil desmezclar algo que solo se ha mezclado / sumado con un vector de ceros.


12
El último párrafo es la respuesta clave a la pregunta original, aunque creo que podría expresarse más claramente. El relleno cero en el contexto de correlación o convolución se puede hacer para garantizar que la implementación del proceso en el dominio de frecuencia produzca convolución / correlación lineal en lugar de circular . Sin embargo, hacerlo no es un requisito si está dispuesto a hacer un trabajo de contabilidad, como en los algoritmos overlap-save y overlap-add.
Jason R

44
@ Jason R: En realidad, ambos son convolución circular. Una FFT normal (sin podar) hace todas las multiplicaciones y agrega para la parte de ajuste del resultado. Es solo que en el caso suficientemente rellenado con cero, todas esas multiplicaciones y sumas son del valor cero, por lo que a nadie le importa nada de lo que se calcula y se envuelve alrededor del círculo.
hotpaw2

99
En efecto; La multiplicación de las DFT de dos señales siempre implementa una convolución circular. Debería haberlo expresado de manera diferente: rellena ceros al final de una señal para asegurarse de que el resultado obtenido al convolucionarlos circularmente es el mismo que el que obtiene si los convoluciona linealmente (suponiendo que la convolución lineal es lo que desea, que es generalmente el caso).
Jason R

27

Hay algunas cosas a considerar antes de que decidas poner a cero tu señal de dominio de tiempo. ¡Es posible que no necesite poner la señal en cero!

1) Alargue los datos del dominio del tiempo (no relleno de cero) para obtener una mejor resolución en el dominio de la frecuencia.

2) Aumente el número de puntos FFT más allá de la longitud de la señal de su dominio de tiempo (relleno de cero) si desea ver una mejor definición de los contenedores FFT, aunque no le ofrece más resolución verdadera. También puede rellenar para llegar a una potencia de 2 puntos FFT.

fs/NfsN

Hay algunas figuras agradables que ilustran estos puntos en http://www.bitweenie.com/listings/fft-zero-padding/

Una última cosa para mencionar: si pone a cero la señal en el dominio del tiempo y desea utilizar una función de ventana, asegúrese de abrir la señal antes de poner a cero la almohadilla. Si aplica la función de ventana después del relleno cero, no logrará lo que se supone que debe lograr la ventana. Más específicamente, todavía tendrá una transición brusca de la señal a cero en lugar de una transición suave a cero.


8

En general, el relleno cero antes de DFT es equivalente a la interpolación, o al muestreo más frecuente, en el dominio transformado.

Aquí hay una visualización rápida de cómo funciona lo contrario. Si muestreas una señal de banda limitada en el tiempo a una velocidad más alta, obtienes un espectro más 'aplastado', es decir, un espectro con más ceros en ambos extremos. En otras palabras, puede obtener más muestras a tiempo simplemente rellenando con cero la frecuencia después de DFT y luego IDFT haciendo el resultado con relleno de cero.

El mismo efecto se mantiene en reversa cuando el relleno de cero ocurre en el tiempo. Todo esto se debe a que la reconstrucción perfecta de la señal es posible siempre que una señal esté limitada en banda y muestreada al menos a la velocidad de Nyquist.

El término 'resolución' depende de cómo lo defina. Para mí, significa qué tan bien los dos puntos adyacentes de observación en tiempo o frecuencia pueden ser discriminados de manera confiable (estadísticamente). En este caso, la resolución realmente depende del tamaño de DFT debido a la fuga espectral. Es decir, más pequeño el tamaño de la ventana, más borrosa o manchada la señal transformada, y viceversa. Es diferente de la frecuencia con la que toma muestras o de lo que yo llamo "definición". Por ejemplo, puede tener una imagen muy borrosa muestreada a alta velocidad (alta definición), pero aún así no puede obtener más información que el muestreo a una velocidad más baja. En resumen, el relleno cero no mejora en absoluto la resolución, ya que no obtiene más información que antes.


6

Si uno tiene algún interés en el espectro de la función de ventana utilizada para aislar la muestra en el dominio del tiempo, entonces el relleno cero aumentará la resolución de frecuencia de la función de ventana.

x(t)w(t)w(t)X(f)W(f)

x(t)X(f), verá algunas muestras en lugares distintos del pico y los cruces por cero, lo que revela la forma de la función de sincronización en el espectro resultante. Entonces, ¿de qué sirve el relleno cero? Ciertamente es de uso educativo para revelar la naturaleza de la transformación discreta de las señales en ventanas, que es el caso habitual. En un sentido práctico, podría ser útil en cualquier caso en el que esté interesado en la forma espectral de una envoltura aislada que se desplaza sobre una onda portadora.


4

Puede haber diferentes razones para esto dependiendo de los procesos realizados antes y después de la transformación de Fourier. La razón más común es lograr una mayor resolución de frecuencia en cualquier transformación resultante. Es decir, cuanto mayor sea el número de muestras utilizadas en su transformación, menor será el ancho de bin en el espectro de potencia resultante. Recuerde: binwidth = sample_frequency / transform_size (a menudo llamado tamaño de ventana). Se puede imaginar a partir de esto, que a medida que aumenta el tamaño de su transformación, el ancho de bin se reduce (= mejor resolución de frecuencia). El relleno cero es una forma de aumentar el tamaño de la transformación sin introducir nueva información en la señal.

Entonces, ¿por qué no simplemente tomar una transformación más grande sin relleno cero? ¿No lograría eso el mismo efecto? Buena pregunta. En muchos casos, es posible que desee analizar una secuencia de datos de dominio de tiempo, para lo cual puede estar utilizando una transformación de Fourier (stft) de corta duración. Esto implica tomar una transformación cada N muestras de acuerdo con la resolución de tiempo que necesita para caracterizar los cambios en el espectro de frecuencia. Aquí en mentiras el problema. Una ventana demasiado grande y perderá resolución de tiempo, una ventana demasiado pequeña y perderá resolución de frecuencia. Entonces, la solución es tomar ventanas de dominio de tiempo pequeño que le brinden una buena resolución de tiempo y luego ponerlas en cero para obtener una buena resolución de frecuencia. Espero que esto sea útil para ti

Actualización
No expliqué esto bien. Debería haberlo aclarado mejor. Al referirse a una transformación en ventana, de hecho no se obtiene una resolución de frecuencia mayor 'real', pero para fines de visualización (lectura del espectro de potencia con el ojo) puede proporcionar resultados más claros. Usando la tasa de muestreo crítica, cada lóbulo lateral ocupa un solo contenedor, que dependiendo de la técnica de gráficos podría ser engañoso. El relleno cero proporciona un espectro de frecuencia interpolado que puede ser más revelador. Además, si está utilizando un método de selección de pico simple para la estimación de frecuencia, el efecto de interpolación espectral del relleno cero le dará una muestra espectral más cercana al pico verdadero del lóbulo principal. Este enlace proporciona algunos diagramas útiles: http://www.dsprelated.com/dspbooks/sasp/Practical_Zero_Padding.html


99
Esta respuesta no es correcta. El relleno cero no mejora en absoluto la resolución de frecuencia; simplemente interpola entre las salidas de la transformación más pequeña. Puede pensar que el relleno cero agrega más intervalos de frecuencia que tienen el mismo ancho de banda que con la transformación más pequeña; por lo tanto, desde una perspectiva de banco de filtros, sus bandas de paso se superponen.
Jason R

1
Si ayuda a comprender: También puede hacer lo contrario: tomar la FFT de una señal, luego poner a cero el resultado e invertir FFT. Esto tendrá el efecto de interpolar la señal original. Pero, por supuesto, la señal seguirá siendo la misma señal, con el mismo ancho de banda de Nyquist. La interpolación no le dará más información de frecuencia más alta que la que originalmente estaba allí.
endolito el

1
@ Jason R - Tienes razón, mi respuesta fue engañosa, he intentado aclarar lo anterior en la publicación original. No debería haber dicho que el relleno cero aumenta la resolución de frecuencia.
Dan Barry

2

No vi estos mencionados en las buenas respuestas anteriores, así que agregaré las siguientes razones importantes adicionales para el relleno cero:

Los algoritmos Radix-2 son más eficientes, por lo que el relleno cero a la siguiente potencia de 2 (o potencia de 4 en algunos casos para radix-4), o más significativamente, evitando cualquier factor primo grande puede mejorar el rendimiento en tiempo real. Además, cuando se utiliza la FFT para el análisis, a menudo se realiza un relleno cero para calcular muestras de la DTFT, como determinar la respuesta de frecuencia de un FIR: compare fft ([1 1 1 1]) con fft ([1 1 1 1], 512) que es idéntico a freqz ([1 1 1 1]).