En el procesamiento de señales , superposición-guardar es el nombre tradicional de una forma eficiente de evaluar la convolución discreta entre una señal muy largay un filtro de respuesta de impulso finito (FIR):
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/e/e4/Overlap-save_algorithm.svg/500px-Overlap-save_algorithm.svg.png)
( Ecuación 1 )
donde h [ m ] = 0 para m fuera de la región [1, M ] .
El concepto es calcular segmentos cortos de y [ n ] de una longitud arbitraria L y concatenar los segmentos juntos. Considere un segmento que comienza en n = kL + M , para cualquier número entero k , y defina :
Entonces, para kL + M ≤ n ≤ kL + L + M - 1, y de manera equivalente M ≤ n - kL ≤ L + M - 1 , podemos escribir :
Con la sustitución j ≜ n-kL , la tarea se reduce a calcular y k (j) , para M ≤ j ≤ L + M - 1 . Estas etapas se ilustran en las 3 primeras huellas de la figura 1, excepto que la parte deseada de los corresponde salida (tercera traza) a 1 ≤ j ≤ L . [B]
Si periódicamente ampliamos x k [ n ] con período N ≥ L + M - 1, de acuerdo con :
las convoluciones y son equivalentes en la región M ≤ n ≤ L + M - 1. Por lo tanto, es suficiente calcular la convolución circular (o cíclica) de N puntos de con en la región [1, N ]. La subregión [ M , L + M - 1] se agrega al flujo de salida y los demás valores se descartan . 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 :
( Ecuación 2 )
donde :
- DFT N e IDFT N se refieren a la transformada discreta de Fourier y su inversa, evaluada sobre N puntos discretos, y
- L se elige habitualmente de modo que N = L + M-1 sea una potencia entera de 2, y las transformaciones se implementan con el algoritmo FFT , para mayor eficiencia.
- Los efectos del borde anterior y posterior de la convolución circular se superponen y se agregan, [C] y posteriormente se descartan. [D]
Pseudocódigo
( Algoritmo de superposición-guardado para convolución lineal )h = FIR_impulse_responseM = longitud (h)superposición = M - 1N = 8 × superposición (consulte la siguiente sección para una mejor elección)step_size = N - superposiciónH = DFT (h, N)posición = 0mientras que posición + N ≤ longitud (x) yt = IDFT (DFT (x (posición + (1: N))) × H) y (posición + (1: tamaño_paso)) = yt (M: N) (descartar los valores y de M − 1) position = position + step_sizefinal
Consideraciones de eficiencia
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/f/f4/FFT_size_vs_filter_length_for_Overlap-add_convolution.svg/400px-FFT_size_vs_filter_length_for_Overlap-add_convolution.svg.png)
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. [E] 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 :
( Ecuación 3 )
Por ejemplo, cuando M = 201 y N = 1024, la ecuación 3 es igual a 13,67, mientras que la evaluación directa de la ecuación 1 requeriría hasta 201 multiplicaciones complejas por muestra de salida, siendo el peor de los casos cuando tanto x como h tienen valores complejos. Tenga en cuenta también que para cualquier dado M , Eq.3 tiene un mínimo con respecto a N . La figura 2 es una gráfica de los valores de N que minimizan la ecuación 3 para un rango de longitudes de filtro (M).
En lugar de la ecuación 1 , también podemos considerar aplicar la ecuación 2 a una secuencia larga de longitudmuestras. 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-ahorro escala casi como mientras que el costo de una sola circunvolución circular grande es casi .
Superponer-descartar
La superposición-descarte [1] y la superposición-desecho [2] son etiquetas que se utilizan con menos frecuencia para el mismo método descrito aquí. Sin embargo, estas etiquetas son realmente mejores (que superponer-guardar ) para distinguirlas de superponer-agregar , porque ambos métodos "guardan", pero solo uno descarta. "Guardar" simplemente se refiere al hecho de que se necesitan M - 1 muestras de entrada (o salida) del segmento k para procesar el segmento k + 1.
Extender la superposición: guardar
El algoritmo de superposición-guardado se puede ampliar para incluir otras operaciones comunes de un sistema: [F] [3]
- Los canales IFFT adicionales se pueden procesar de forma más económica que el primero mediante la reutilización de la FFT directa.
- Las tasas de muestreo se pueden cambiar mediante el uso de FFT directas e inversas de diferentes tamaños.
- la traducción de frecuencia (mezcla) se puede lograr reorganizando los contenedores de frecuencia
Ver también
Notas
- ↑ Rabiner and Gold , Fig 2.35, cuarto rastro.
- ^ Cambiar los efectos de borde indeseables a las últimas salidas M-1 es una conveniencia potencial de tiempo de ejecución, porque el IDFT se puede calcular en elbúfer, en lugar de ser calculado y copiado. Luego, los efectos de borde se pueden sobrescribir con el siguiente IDFT. Una nota a pie de página posterior explica cómo se realiza el cambio, mediante un cambio en el tiempo de la respuesta al impulso.
- ^ No debe confundirse con el método Overlap-add , que conserva los efectos de borde inicial y final separados.
- ^ Los efectos de borde se pueden mover desde el frente hacia la parte posterior de la salida IDFT reemplazando con lo que significa que el búfer de longitud N se desplaza (gira) circularmente por muestras M-1. Por tanto, el elemento h (M) está en n = 1. El elemento h (M-1) está en n = N. h (M-2) está en n = N-1. Etc.
- ^ Algoritmo Cooley-Tukey FFT para N = 2 k necesita (N / 2) log 2 (N) - ver FFT - Definición y velocidad
- ^ Carlin y col. 1999 , p 31, col 20.
Referencias
- ^ Harris, FJ (1987). DFElliot (ed.). Manual de procesamiento de señales digitales . San Diego: Prensa académica. págs. 633–699. ISBN 0122370759.
- ^ Frerking, Marvin (1994). Procesamiento de señales digitales en sistemas de comunicación . Nueva York: Van Nostrand Reinhold. ISBN 0442016166.
- ^ Borgerding, Mark (2006). "Convertir la superposición: guardar en un banco de filtros de submuestreo y mezcla multibanda" (PDF) . Revista IEEE Signal Processing (marzo de 2006): 158–161.
- 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–67 . ISBN 0-13-914101-4.
- Patente de EE.UU. 6898235 , Carlin, Joe; Terry Collins y Peter Hays et al., "Dispositivo de interceptación y búsqueda de dirección de comunicación de banda ancha mediante hipercanalización", publicado el 10 de diciembre de 1999, publicado el 24 de mayo de 2005, url2 = https://worldwide.espacenet.com/patent/search/family/034590049/publication/US6898235B1?q=pn%3DUS6898235