Objetivos de aprendizaje
- Aprende métodos para hacer convolución por FFT de manera más eficiente.
Una de las principales aplicaciones de la FFT es hacer convolución de manera más eficiente que el cálculo directo a partir de la definición que es:
\[y(n)=\sum h(m)x(n-m) \nonumber \]
que, con un cambio de variables, también se puede escribir como:
\[y(n)=\sum x(m)h(n-m) \nonumber \]
Esto se usa a menudo para filtrar una señalx(n)x(n)“role="presentation” style="position:relative;” tabindex="0"> \(x(n)\)con un filtro cuya respuesta de impulso esx(n)x(n)“role="presentación” style="position:relative;” tabindex="0">\(h(n)\)h(n)h(n)“role="presentación” style="position:relative;” tabindex="0">. Cada valor de salidax(n)x(n)“role="presentación” style="position:relative;” tabindex="0">\(y(n)\)y(n)y(n)“role="presentation” style="position:relative;” tabindex="0"> requiere\(N\) multiplicaciones yN-1N-1“role="presentation” style="position:relative;” tabindex="0">\(N-1\) adiciones six(n)x(n)“role="presentation” style="position:relative;” tabindex="0">\(y(n)\) yx(n)x(n)“role="presentation” style="position:relative;” tabindex="0">\(h(n)\) tienen\(N\) términos. Entonces, para los valores de\(N\) salida, en el orden deN2N2“role="presentation” style="position:relative;” tabindex="0"> se requieren operaciones\(N^2\) aritméticas.
Debido a que el DFT convierte la convolución en multiplicación:
\[\text{DFT}y(n)=\text{DFT}\left \{ h(n)\text{DFT}x(n)\right \} \nonumber \]
se puede calcular con la FFT y reducir el orden de las operaciones aritméticas aNregistro(N)Nregistro(N)“role="presentation” style="position:relative;” tabindex="0"> \(N\log (N)\)que puede ser significativo para grandes\(N\).
NN“role="presentation” style="position:relative;” tabindex="0"> Este enfoque, que se llama “convoluciones rápidas”, es una forma de procesamiento de bloques ya que todo un bloque o segmento dex(n)x(n)“role="presentation” style="position:relative;” tabindex="0">\(x(n)\) debe estar disponible para calcular incluso un valor de salida,x(n)x(n)“role="presentación” style="position:relative;” tabindex="0">\(y(n)\). Entonces, siempre se requiere un retardo de tiempo de una longitud de bloque. Otro problema es que el uso de filtrado de convolución suele ser no cíclico y la convolución implementada con la DFT es cíclica. Esto se trata añadiendo ceros ax(n)x(n)“role="presentation” style="position:relative;” tabindex="0">\(x(n)\) yx(n)x(n)“role="presentation” style="position:relative;” tabindex="0"> \(h(n)\)tal que la salida de la convolución cíclica da un bloque de la salida de la convolución no cíclica deseada.
Para el filtrado y algunas otras aplicaciones, uno quiere convolución “en marcha” donde la respuesta del filtrox(n)x(n)“role="presentation” style="position:relative;” tabindex="0">\(h(n)\) puede ser finito en longitud o duración, pero la entradax(n)x(n)“role="presentation” style="position:relative;” tabindex="0"> \(x(n)\)es de longitud arbitraria. Tradicionalmente se han utilizado dos métodos para romper la entrada en bloques y utilizar la FFT para convolucionar el bloque de manera que la salida que habría sido calculada implementando directamente las ecuaciones anteriores, se pueda construir de manera eficiente. Estos se llaman “overlap-add” y “overlap save”.
h(n)h(n)“role="presentación” style="position:relative;” tabindex="0"> Colaborador