¿Por qué los resultados de convolución tienen diferentes longitudes cuando se realiza en el dominio del tiempo vs en el dominio de frecuencia?

Question

No soy un experto en DSP, pero entiendo que hay dos maneras en que puedo aplicar un filtro de dominio de tiempo discreto a una forma de onda de dominio de tiempo discreto. La primera es para convolucionar ellos en el dominio del tiempo, y el segundo es para tomar la FFT de ambos, se multiplican los dos espectros complejos, y tomar IFFT del resultado. Una diferencia clave en estos métodos es el segundo enfoque está sujeto a convolución circular.

Como un ejemplo, si el filtro y las formas de onda son ambos N puntos de largo, la primera aproximación (es decir convolución) produce un resultado que es N + N-1 puntos de largo, donde el primer medio de esta respuesta es el filtro de llenar y el segundo medio es el vaciado del filtro. Para obtener una respuesta en estado estacionario, las necesidades de filtro tengan un menor número de puntos de la forma de onda que va a filtrarse.

Continuando con este ejemplo, con el segundo enfoque, y suponiendo que los datos de forma de onda de dominio de tiempo discreto es todo real (no complejo), la FFT del filtro y la forma de onda Ambos producen FFT de N puntos de largo. Multiplicando ambos espectros IFFT'ing el resultado produce un resultado de dominio de tiempo también N puntos de largo. Aquí la respuesta que el filtro se llena y se vacía se solapan entre sí en el dominio del tiempo, y no hay respuesta de estado estacionario. Este es el efecto de la convolución circular. Para evitar esto, típicamente el tamaño del filtro sería más pequeño que el tamaño de la forma de onda y ambas sería cero acolchado para dejar espacio para la convolución de frecuencia para expandir en el tiempo después de IFFT del producto de los dos espectros.

Mi pregunta es, a menudo veo el trabajo en la literatura de expertos / empresas bien establecidas en los que tienen una discreta (real) de forma de onda de dominio de tiempo (N puntos), que FFT ella, se multiplica por algún filtro (también N puntos), y IFFT el resultado para el procesamiento posterior. Mi pensamiento es ingenuo este resultado debe contener ninguna respuesta en estado estable y por lo tanto debe contener artefactos del llenado del filtro / vaciado que daría lugar a errores en la interpretación de los datos resultantes, pero debe estar pasando algo. ¿En qué circunstancias puede esto ser un enfoque válido?

Cualquier penetración sería muy apreciada

Answer 1

El problema básico no es aproximadamente cero relleno vs la periodicidad supuesta, pero que el análisis de Fourier descompone la señal en ondas sinusoidales que, en el nivel más básico, se supone que son una extensión infinita. Ambos enfoques son correctos en el que la IFFT usando la FFT completa devolverá la forma de onda de entrada exacto, y ambos enfoques son incorrectos en el que el uso de menos de espectro completo puede dar lugar a efectos en los bordes (que por lo general se extienden una pocas longitudes de onda). La única diferencia está en los detalles de lo que usted asume rellenos en el resto del infinito, no en si usted está haciendo una suposición.

Volver a su primer párrafo: Por lo general, en el DSP, el mayor problema que topan con las FFT es que son no causal, y por esta razón por la que a menudo prefieren permanecer en el dominio del tiempo, utilizando, por ejemplo, FIR y filtros IIR.

Actualización:

En la declaración cuestión, el OP señala correctamente algunos de los problemas que pueden surgir cuando se utiliza FFT a las señales de filtro, por ejemplo, los efectos de borde, que puede ser particularmente problemático cuando se hace una convolución que es comparable en la longitud (en el dominio del tiempo) a la forma de onda muestreada. Es importante tener en cuenta sin embargo, que no todo el filtrado se realiza mediante FFT, y en el documento citado por el PO, que no están usando filtros FFT, y los problemas que surgirían con una implementación de filtro FFT no surgen usando su enfoque .

Consideremos, por ejemplo, un filtro que implementa un promedio simple a través de 128 puntos de muestra, utilizando dos implementaciones diferentes.

FFT : En el enfoque FFT / convolución uno tendría una muestra de, por ejemplo, 256, puntos y convolucionar esto con un wfm que es constante para la primera mitad y tiende a cero en el segundo medio. La pregunta aquí es (incluso después de este sistema se ha quedado unos pocos ciclos), lo que determina el valor del primer punto del resultado? La FFT se supone que el WFM es circular (es decir, infinitamente periódica), de manera o bien: el primer punto del resultado se determina por las muestras última 127 (es decir, el futuro) de la WFM (pasando por alto el medio de la WFM), o por 127 ceros si con ceros. Tampoco es correcta.

FIR : Otro enfoque es aplicar el promedio con un filtro FIR. Por ejemplo, aquí se podría utilizar el promedio de los valores en una cola FIFO 128 registradora. Es decir, como cada punto de muestra entra, 1) poner en la cola, 2) dequeue el elemento más antiguo, 3) Media de todos los 128 elementos restantes en la cola; y esto es el resultado de este punto de la muestra. Este enfoque funciona de forma continua, el manejo de un punto a la vez, y devolver el resultado filtrado después de cada muestra, y no tiene ninguno de los problemas que se producen a partir de la FFT como se le aplica a trozos muestras finitas. Cada resultado es la media de la muestra actual y las 127 muestras que había antes de él.

El papel que la OP cita tiene un enfoque mucho más similar al filtro FIR de que el filtro FFT (nota sin embargo que el filtro en el papel es más complicada, y todo el trabajo es básicamente un análisis de este filtro.) Ver por ejemplo, este libro libre que describe cómo analizar y aplicar diferentes filtros, y la nota también que el enfoque de Laplace para análisis de la FIR y IIR filtros es bastante similar lo que lo que se encuentra en el documento citado.

Answer 2

Aquí está un ejemplo de convolución sin relleno cero para la DFT (convolución circular) vs convolución lineal. Esta es la convolución de una longitud M = 32 secuencia con una longitud L = 128 secuencia (utilizando Numpy / Matplotlib):

f = rand(32); g = rand(128)
h1 = convolve(f, g)
h2 = real(ifft(fft(f, 128)*fft(g)))
plot(h1); plot(h2,'r')
grid()

Los primeros M-1 puntos son diferentes, y es corto por M 1-puntos ya que no era cero acolchado. Estas diferencias son un problema si está haciendo bloque de convolución, pero las técnicas tales como la superposición y guardar o solapamiento y suma se utilizan para superar este problema. De lo contrario, si sólo está calculando una sola vez el filtrado de la operación, el resultado válido se iniciará a M-1 y al final del índice en L-1 índice, con una longitud de L-M + 1.

En cuanto al papel citado, que se veía en su código de MATLAB en el apéndice A. Creo que cometió un error en la aplicación de la función de transferencia Hfinal a las frecuencias negativas sin antes conjugar ella. De lo contrario, se puede ver en sus gráficas que la fluctuación de reloj es una señal periódica, por lo que el uso de convolución circular está muy bien para un análisis en estado estacionario.

Editar: En cuanto a la conjugación de la función de transferencia, los PLL tener una respuesta de impulso de valor real, y cada señal de valor real tiene un espectro simétrico conjugado. En el código se puede ver que sólo están utilizando Hfinal [N-i] para obtener las frecuencias negativas sin tomar el conjugado. He tracé su función de transferencia de -50 MHz a 50 MHz:

N = 150000                    # number of samples. Need >50k to get a good spectrum. 
res = 100e6/N                 # resolution of single freq point  
f = res * arange(-N/2, N/2)   # set the frequency sweep [-50MHz,50MHz), N points
s = 2j*pi*f                   # set the xfer function to complex radians 

f1 = 22e6       # define 3dB corner frequency for H1 
zeta1 = 0.54    # define peaking for H1 
f2 = 7e6        # define 3dB corner frequency for H2 
zeta2 = 0.54    # define peaking for H2    
f3 = 1.0e6      # define 3dB corner frequency for H3 

# w1 = natural frequency   
w1 = 2*pi*f1/((1 + 2*zeta1**2 + ((1 + 2*zeta1**2)**2 + 1)**0.5)**0.5)  
# H1 transfer function 
H1 = ((2*zeta1*w1*s + w1**2)/(s**2 + 2*zeta1*w1*s + w1**2))            

# w2 = natural frequency 
w2 = 2*pi*f2/((1 + 2*zeta2**2 + ((1 + 2*zeta2**2)**2 + 1)**0.5)**0.5)  
# H2 transfer function  
H2 = ((2*zeta2*w2*s + w2**2)/(s**2 + 2*zeta2*w2*s + w2**2))            

w3 = 2*pi*f3        # w3 = 3dB point for a single pole high pass function. 
H3 = s/(s+w3)       # the H3 xfer function is a high pass

Ht = 2*(H1-H2)*H3   # Final transfer based on the difference functions

subplot(311); plot(f, abs(Ht)); ylabel("abs")
subplot(312); plot(f, real(Ht)); ylabel("real")
subplot(313); plot(f, imag(Ht)); ylabel("imag")

Como se puede ver, el componente real tiene simetría par y el componente imaginario tiene simetría impar. En su código sólo se calculan las frecuencias positivas para una parcela loglog (bastante razonable). Sin embargo, para el cálculo de la transformada inversa que utilizan los valores de las frecuencias positivas para las frecuencias negativas mediante la indexación de Hfinal [N-i] pero se olvidó de conjugar a él.

Answer 3

Aunque habrá artefactos de suponiendo que una ventana rectangular de datos es periódica en la anchura de la abertura FFT, que es una interpretación de lo que hace convolución circular sin relleno suficiente cero, las diferencias pueden o pueden no ser lo suficientemente grande para inundar la El análisis de datos en cuestión.

Answer 4

Me puede arrojar algo de luz a la razón por la "visualización" se aplica antes de la aplicación de la FFT.

Como ya se señaló la FFT asume que tenemos una señal infinita. Cuando tomamos una muestra durante un tiempo finito T este es matemáticamente equivalente a multiplicar la señal con una función rectangular.

Multiplicar en el dominio del tiempo se convierte en convolución en el dominio de la frecuencia. La respuesta de frecuencia de un rectángulo es la función de sincronización es decir, sin (x) / x. La x en el numerador es el kicker, porque esto se extingue la O (1 / N).

Si tiene componentes de frecuencia que son exactamente múltiplos de 1 / T esto no importa ya que la función de sincronización es cero en todos los puntos, excepto que la frecuencia donde es 1.

Sin embargo, si usted tiene una condición sine que caen entre 2 puntos, verá la función de sincronización de la muestra en el punto de frecuencia. Se lloks como una versión ampliada de la función de sincronización y las señales de 'fantasma' causadas por la matriz de convolución abajo con 1 / N o 6 dB / octava. Si usted tiene una señal de 60 dB por encima del ruido de fondo, que no verá el ruido de frecuencias 1000 a izquierda y derecha de su señal principal, que será inundado por las "faldas" de la función de sincronización.

Si utiliza una ventana de tiempo diferente se obtiene una respuesta de frecuencia diferente, un coseno, por ejemplo, se apaga con ventanas 1 / x ^ 2, no están especializadas en diferentes mediciones. La ventana Hanning se utiliza a menudo como una ventana de propósito general.

El punto es que la ventana rectangular utiliza cuando no se aplica ninguna "función ventana" crea mucho peores que los artefactos de una ventana bien elegido. es decir por "distorsionar" las muestras de tiempo que obtienen una imagen mucho mejor en el dominio de la frecuencia que se asemeja más estrechas "realidad", o más bien la "realidad" que esperan y quieren ver.