Método de superposición y adición

En el procesamiento de señales , el método de superposición-suma es una forma eficiente de evaluar la convolución discreta de una señal muy larga con un filtro de respuesta de impulso finito (FIR) : ${\displaystyle x[n]}$ ${\displaystyle h[n]}$

donde para fuera de la región   Este artículo utiliza notaciones abstractas comunes, como o en las que se entiende que las funciones deben considerarse en su totalidad, en lugar de en instantes específicos (ver Convolución#Notación ). ${\displaystyle h[m]=0}$ ${\displaystyle m}$ ${\displaystyle [1,M].}$ ${\textstyle y(t)=x(t)*h(t),}$ ${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$ ${\textstyle t}$

Fig. 1: Una secuencia de cinco gráficos representa un ciclo del algoritmo de convolución de superposición-adición. El primer gráfico es una secuencia larga de datos que se procesarán con un filtro FIR de paso bajo. El segundo gráfico es un segmento de los datos que se procesarán por partes. El tercer gráfico es el segmento filtrado, incluidos los transitorios de subida y bajada del filtro. El cuarto gráfico indica dónde se añadirán los nuevos datos con el resultado de los segmentos anteriores. El quinto gráfico es el flujo de salida actualizado. El filtro FIR es un filtro de paso bajo de vagón de tren con muestras, la longitud de los segmentos es de muestras y la superposición es de 15 muestras. ${\displaystyle M=16}$ ${\displaystyle L=100}$

El concepto es dividir el problema en múltiples convoluciones con segmentos cortos de : ${\displaystyle h[n]}$ ${\displaystyle x[n]}$

${\displaystyle x_{k}[n]\ \triangleq \ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\text{otherwise}},\end{cases}}}$

donde es una longitud de segmento arbitraria. Entonces : ${\displaystyle L}$

${\displaystyle x[n]=\sum _{k}x_{k}[n-kL],\,}$

y puede escribirse como una suma de convoluciones cortas : ^[1] ${\displaystyle y[n]}$

${\displaystyle {\begin{aligned}y[n]=\left(\sum _{k}x_{k}[n-kL]\right)*h[n]&=\sum _{k}\left(x_{k}[n-kL]*h[n]\right)\\&=\sum _{k}y_{k}[n-kL],\end{aligned}}}$

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 con dentro de la región   La ventaja es que la convolución circular se puede calcular de manera más eficiente que la convolución lineal, de acuerdo con el teorema de convolución circular : ${\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]\,}$ ${\displaystyle [1,L+M-1].}$ ${\displaystyle N\geq L+M-1,\,}$ ${\displaystyle N}$ ${\displaystyle x_{k}[n]\,}$ ${\displaystyle h[n]\,}$ ${\displaystyle [1,N].}$

dónde :

• DFT _N e IDFT _N se refieren a la transformada de Fourier discreta y su inversa, evaluadas sobre puntos discretos, y ${\displaystyle N}$
• ${\displaystyle L}$Se elige habitualmente como una potencia entera de 2, y las transformaciones se implementan con el algoritmo FFT , para lograr eficiencia. ${\displaystyle N=L+M-1}$

Pseudocódigo

El siguiente es un pseudocódigo del algoritmo :

( Algoritmo de superposición y adición para convolución lineal )h = filtro FIRM = longitud(h)Nx = longitud(x)N = 8 × 2^ceiling( log2(M) ) (8 veces la potencia más pequeña de dos mayor que la longitud del filtro M. Consulte la siguiente sección para una opción ligeramente mejor).
step_size = N - (M-1) (L en el texto anterior)H = DFT(h, N)posición = 0y(1 : Nx + M-1) = 0mientras posición + tamaño de paso ≤ Nx hacer y(posición+(1:N)) = y(posición+(1:N)) + IDFT(DFT(x(posición+(1:tamaño_de_paso)), N) × H) posición = posición + tamaño de pasofin

Consideraciones de eficiencia

Fig. 2: Un gráfico de los valores de N (una potencia entera de 2) que minimizan la función de costo ${\displaystyle {\tfrac {N\left(\log _{2}N+1\right)}{N-M+1}}}$

Cuando la DFT y la IDFT se implementan mediante el algoritmo FFT, el pseudocódigo anterior requiere aproximadamente N (log ₂ (N) + 1) multiplicaciones complejas para la FFT, el producto de matrices y la IFFT. ^[B] Cada iteración produce N-M+1 muestras de salida, por lo que la cantidad de multiplicaciones complejas por muestra de salida es aproximadamente :

Por ejemplo, cuando y la ecuación 3 es igual a , 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 tanto y tienen valores complejos. Observe también que para cualquier ecuación 3 dada tiene un mínimo con respecto a La figura 2 es un gráfico de los valores de que minimizan la ecuación 3 para un rango de longitudes de filtro ( ). ${\displaystyle M=201}$ ${\displaystyle N=1024,}$ ${\displaystyle 13.67,}$ ${\displaystyle 201}$ ${\displaystyle x}$ ${\displaystyle h}$ ${\displaystyle M,}$ ${\displaystyle N.}$ ${\displaystyle N}$ ${\displaystyle M}$

En lugar de la ecuación 1 , también podemos considerar la aplicación de la ecuación 2 a una secuencia larga de muestras de longitud. La cantidad total de multiplicaciones complejas sería: ${\displaystyle N_{x}}$

${\displaystyle N_{x}\cdot (\log _{2}(N_{x})+1).}$

Comparativamente, el número de multiplicaciones complejas requeridas por el algoritmo de pseudocódigo es:

${\displaystyle N_{x}\cdot (\log _{2}(N)+1)\cdot {\frac {N}{N-M+1}}.}$

Por lo tanto, el costo del método de superposición-adición es casi igual, 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 proporción constante de los tiempos que lleva realizar ambos métodos. Cuando el método de superposición-adición es más rápido, la proporción supera 1 y se ven proporciones tan altas como 3. ${\displaystyle O\left(N_{x}\log _{2}N\right)}$ ${\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}$

Fig. 3: Ganancia del método de superposición-suma en comparación con una única convolución circular grande. Los ejes muestran los valores de la longitud de la señal N _x y la longitud del filtro N _h .

Véase también

• Método de superposición y ahorro
• Convolución circular#Ejemplo

Notas

1. Esta condición implica que el segmento tiene al menos ceros agregados, lo que evita la superposición circular de los transitorios de subida y bajada de salida. ${\displaystyle x_{k}}$ ${\displaystyle M-1}$
2. El algoritmo FFT de Cooley–Tukey para N=2 ^k necesita (N/2) log ₂ (N) – ver FFT – Definición y velocidad

Referencias

1. Rabiner, Lawrence R.; Gold, Bernard (1975). "2.25" . Teoría y aplicación del procesamiento de señales digitales . Englewood Cliffs, NJ: Prentice-Hall. págs. 63–65. ISBN. 0-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. Horace (1999). Procesamiento de señales digitales . Serie Schaum's Outline. Nueva York: McGraw Hill. ISBN 0-07-027389-8.
• Senobari, Nader Shakibay; Funning, Gareth J.; Keogh, Eamonn; Zhu, Yan; Yeh, Chin-Chia Michael; Zimmerman, Zachary; Mueen, Abdullah (2019). "Correlación cruzada supereficiente (SEC-C): un código de filtrado rápido y adaptado adecuado para computadoras de escritorio" (PDF) . Seismological Research Letters . 90 (1): 322–334. doi :10.1785/0220180122. ISSN  0895-0695.