Método de superposición y adición

En el procesamiento de señales , el método de superposición-suma es una forma eficaz 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]}$

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 ). ${\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 y adición. El primer gráfico es una larga secuencia 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á 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 agregará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 paso bajo de furgón 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 se puede escribir 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 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 : ${\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 discreta de Fourier y su inversa, evaluada sobre puntos discretos, y ${\displaystyle N}$
• ${\displaystyle L}$se elige habitualmente de manera que sea una potencia entera de 2, y las transformaciones se implementan con el algoritmo FFT , para mayor 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^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

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

Cuando el algoritmo FFT implementa DFT e IDFT, el pseudocódigo anterior requiere aproximadamente N (log ₂ (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 ( ). ${\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 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: ${\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 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. ${\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 y adición en comparación con una única convolución circular grande. Los ejes muestran valores de longitud de señal Nx _y longitud de filtro _Nh .

Ver también

• Método de superposición y guardado
• Convolución_circular#Ejemplo

Notas

1. 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. ${\displaystyle x_{k}}$ ${\displaystyle M-1}$
2. Algoritmo Cooley-Tukey FFT para N = 2 ^k necesita (N/2) log ₂ (N) - ver FFT - Definición y velocidad

Referencias

1. 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. ISBN 0-13-914101-4.

Otras lecturas

• 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.