dónde para fuera de la región Este artículo utiliza notaciones abstractas comunes, como o en las que se entiende que las funciones deben pensarse en su totalidad, en lugar de en instantes específicos (consulte Convolución#Notación ).
El concepto es dividir el problema en múltiples convoluciones con segmentos cortos de :
donde es una longitud de segmento arbitraria. Entonces :
y se puede escribir como una suma de convoluciones cortas : [1]
donde la convolución lineal es cero fuera de la región Y para cualquier parámetro [A] es equivalente a la convolución circular de -punto de con en la región La ventaja es que la convolución circular se puede calcular de manera más eficiente que la convolución lineal, según la convolución circular teorema de convolución :
( Algoritmo de superposición y adición para convolución lineal )h = filtro_FIRM = longitud(h)Nx = longitud(x)N = 8 × 2^techo( log2(M) ) (8 veces la potencia más pequeña de dos mayores que la longitud del filtro M. Consulte la siguiente sección para obtener una elección ligeramente mejor).
step_size = N - (M-1) (L en el texto arriba)H = EPS(h, N)posición = 0y(1 : Nx + M-1) = 0mientras que posición + tamaño_paso ≤ Nx hacer y(posición+(1:N)) = y(posición+(1:N)) + IDFT(DFT(x(posición+(1:tamaño_paso)), N) × H) posición = posición + tamaño_pasofin
Consideraciones de eficiencia
Cuando el algoritmo FFT implementa DFT e IDFT, el pseudocódigo anterior requiere aproximadamente N (log 2 (N) + 1) multiplicaciones complejas para FFT, producto de matrices e IFFT. [B] Cada iteración produce N-M+1 muestras de salida, por lo que el número de multiplicaciones complejas por muestra de salida es aproximadamente :
Por ejemplo, cuando y la ecuación 3 es igual, mientras que la evaluación directa de la ecuación 1 requeriría hasta multiplicaciones complejas por muestra de salida, siendo el peor caso cuando ambos y tienen valores complejos. También tenga en cuenta que para cualquier Ec.3 dada tiene un mínimo con respecto a la Figura 2 es una gráfica de los valores de esa Ec.3 minimizada para un rango de longitudes de filtro ( ).
En lugar de la Ec.1 , también podemos considerar aplicar la Ec.2 a una secuencia larga de muestras de longitud. El número total de multiplicaciones complejas sería:
Comparativamente, el número de multiplicaciones complejas requeridas por el algoritmo de pseudocódigo es:
Por lo tanto, el costo del método de superposición y adición aumenta casi mientras que el costo de una sola convolución circular grande es casi . Los dos métodos también se comparan en la Figura 3, creada mediante simulación de Matlab. Los contornos son líneas de relación constante de los tiempos que se tarda en realizar ambos métodos. Cuando el método de superposición y suma es más rápido, la proporción excede 1 y se observan proporciones tan altas como 3.
^ Esta condición implica que el segmento tiene al menos ceros añadidos, lo que evita la superposición circular de los transitorios de subida y bajada de salida.
^ Rabiner, Lawrence R.; Oro, Bernard (1975). "2,25" . Teoría y aplicación del procesamiento de señales digitales . Englewood Cliffs, Nueva Jersey: Prentice-Hall. págs. 63–65. ISBN0-13-914101-4.
Lectura adicional
Oppenheim, Alan V.; Schafer, Ronald W. (1975). Procesamiento de señales digitales . Englewood Cliffs, Nueva Jersey: Prentice-Hall. ISBN 0-13-214635-5.
Hayes, M. Horacio (1999). Procesamiento de señales digitales . Serie de esquemas de Schaum. Nueva York: McGraw Hill. ISBN 0-07-027389-8.
Senobari, Nader Shakibay; Funning, Gareth J.; Keogh, Eamonn; Zhu, Yan; Sí, Chin-Chia Michael; Zimmerman, Zachary; Mueen, Abdullah (2019). "Correlación cruzada súper eficiente (SEC-C): un código de filtrado de coincidencia rápida adecuado para computadoras de escritorio" (PDF) . Cartas de Investigación Sismológica . 90 (1): 322–334. doi :10.1785/0220180122. ISSN 0895-0695.