Convolución rápida por superposición-adición
Para utilizar la FFT para convolucionar (o filtrar) una secuencia de entrada largax(n)x(n)“role="presentation” style="position:relative;” tabindex="0"> \(x(n)\)con una respuesta de impulso finita Length-m,x(n)x(n)“role="presentation” style="position:relative;” tabindex="0">\(h(n)\), particionamos la secuencia de entrada en segmentos o bloques de longitudx(n)x(n)“role="presentación” style="position:relative;” tabindex="0">\(L\)LL“role="presentación” style="position:relative;” tabindex="0">. Debido a que la convolución (o filtrado) es lineal, la salida es una suma lineal del resultado de convolucionar el primer bloque conx(n)x(n)“role="presentation” style="position:relative;” tabindex="0">\(h(n)\) más el resultado de convolucionar el segundo bloque conx(n)x(n)“role="presentation” style="position:relative;” tabindex="0">\(h(n)\) más el resto. Cada una de estas circunvoluciones de bloque se puede calcular usando la FFT. La salida es la FFT inversa del producto de la FFT dex(n)x(n)“role="presentation” style="position:relative;” tabindex="0">\(x(n)\) y la FFT dex(n)x(n)“role="presentación” style="position:relative;” tabindex="0">\(h(n)\). Dado que el número de operaciones aritméticas para calcular la convolución directamente está en el orden de\(M^2\) y, si se hace con la FFT, está en el orden de\(M\log (M)\), puede haber un gran ahorro al usar la FFT para grandesx(n)x(n)“role="presentación” style="position:relative;” tabindex="0">\(M\)LL“role="presentación” style="position:relative;” tabindex="0">. MM“role="presentación” style="position:relative;” tabindex="0">
La razón por la que este procedimiento no es totalmente sencillo, es la longitud de la salida de convolucionar un bloque Length-L con un filtro Length-M es de longitud\(L+M-1\). Esto significa que los bloques de salida no pueden ser simplemente concatenados sino que deben superponerse y agregarse, de ahí que el nombre de este algoritmo sea “Superpuso-Agregar”.
El segundo tema que se debe tomar en cuenta es el hecho de que los pasos de superposición-adición necesitan una convolución no cíclica y la convolución por la FFT es cíclica. Esto se maneja fácilmente agregandoL-1L-1“role="presentation” style="position:relative;” tabindex="0">\(L-1\) ceros a la respuesta al impulso yL-1L-1“role="presentación” style="position:relative;” tabindex="0">\(M-1\)M-1M-1“role="presentation” style="position:relative;” tabindex="0"> ceros a cada bloque de entrada para que todos los FFT sean de longitud\(M+L-1\). Esto significa que no hay aliasing y la convolución cíclica implementada da la misma salida que la convolución no cíclica deseada.
El ahorro en aritmética puede ser considerable al implementar convolución o realizar filtrado digital FIR. No obstante, hay dos penaltis. El uso de bloques introduce un retardo de una longitud de bloque. Ninguno del primer bloque de salida se puede calcular hasta que todo el primer bloque de entrada esté disponible. Esto no es un problema para el procesamiento “fuera de línea” o “por lotes”, pero puede ser serio para el procesamiento en tiempo real. La segunda penalización es la memoria requerida para almacenar y procesar los bloques. La reducción continua del costo de memoria a menudo elimina este problema.
La eficiencia en términos de número de operaciones aritméticas por punto de salida aumenta para bloques grandes debido a los\(M\log (M)\) requerimientos de la FFT. Sin embargo, los bloques se vuelven muy grandes (\(L> > M\)), gran parte del bloque de entrada serán los ceros añadidos y se pierde la eficiencia. Para cualquier aplicación en particular, tomando el filtro particular y el algoritmo FFT que se está utilizando y el hardware particular que se está utilizando, una gráfica de eficiencia vs longitud de bloque,x(n)x(n)“role="presentation” style="position:relative;” tabindex="0">\(L\) debe hacerse yx(n)x(n)“role="presentation” style="position:relative;” tabindex="0"> \(L\)elegido para maximizar la eficiencia dada cualquier otra restricción que sea aplicable.
LL“role="presentation” style="position:relative;” tabindex="0"> Por lo general, las convoluciones de bloque las realiza la FFT, pero podrían realizarse mediante cualquier método eficiente de longitud finita. Se podrían usar “transformadas rectangulares” o “transformadas teóricas de números”. Una generalización de este método se presenta posteriormente en las notas.
LL“role="presentation” style="position:relative;” tabindex="0"> Convolución rápida por Overlap-SaveLL“role="presentación” style="position:relative;” tabindex="0">
Se puede desarrollar un enfoque alternativo para la superposición-adición comenzando con la segmentación de la salida en lugar de la entrada. Si se considera el cálculo de un bloque de salida, se ve que no solo se necesita el bloque de entrada correspondiente, sino que también se necesita parte del bloque de entrada anterior. De hecho, se puede demostrar que se necesita un\(M+L-1\) segmento de longitud de la entrada para cada bloque de salida. Entonces, se guarda la última parte del bloque anterior y la concatena con el bloque de entrada actual, luego convoluciona eso conx(n)x(n)“role="presentation” style="position:relative;” tabindex="0"> \(h(n)\)para calcular la salida de corriente.