Método de superposición y ahorro

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

donde h [ m ] = 0 para m fuera de la región [1, M ] . 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 (véase Convolución#Notación ). ${\textstyle y(t)=x(t)*h(t),}$ ${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$ ${\textstyle t}$

Fig. 1: Una secuencia de cuatro gráficos representa un ciclo del algoritmo de convolución de superposición-guardado. 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, con la parte utilizable coloreada en rojo. El cuarto gráfico muestra el segmento filtrado anexado al flujo de salida. ^[A] El filtro FIR es un filtro de paso bajo de vagón de caja con M=16 muestras, la longitud de los segmentos es L=100 muestras y la superposición es de 15 muestras.

El concepto consiste en calcular segmentos cortos de y [ n ] de una longitud arbitraria L y concatenar los segmentos. Esto requiere segmentos de entrada más largos que se superpongan al siguiente segmento de entrada. Los datos superpuestos se "guardan" y se utilizan una segunda vez. ^[1] Primero describimos ese proceso con solo una convolución convencional para cada segmento de salida. Luego describimos cómo reemplazar esa convolución con un método más eficiente.

Consideremos un segmento que comienza en n = kL  +  M , para cualquier entero k , y definamos :

${\displaystyle x_{k}[n]\ \triangleq {\begin{cases}x[n+kL],&1\leq n\leq L+M-1\\0,&{\textrm {otherwise}}.\end{cases}}}$

${\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-m].}$

Entonces, para , y equivalentemente , podemos escribir: ${\displaystyle kL+M+1\leq n\leq kL+L+M}$ ${\displaystyle M+1\leq n-kL\leq L+M}$

${\displaystyle y[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-kL-m]\ \ \triangleq \ \ y_{k}[n-kL].}$

Con la sustitución , la tarea se reduce a calcular . Estos pasos se ilustran en las primeras 3 trazas de la Figura 1, excepto que la parte deseada de la salida (tercera traza) corresponde a 1  ≤  j  ≤  L . ^[B] ${\displaystyle j=n-kL}$ ${\displaystyle y_{k}[j]}$ ${\displaystyle M+1\leq j\leq L+M}$

Si extendemos periódicamente x _k [ n ] con periodo N  ≥  L  +  M  − 1, según :

${\displaystyle x_{k,N}[n]\ \triangleq \ \sum _{\ell =-\infty }^{\infty }x_{k}[n-\ell N],}$

Las convoluciones     y     son equivalentes en la región . 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  + 1,  L  +  M ] se añade al flujo de salida y los demás valores se descartan . La ventaja es que la convolución circular se puede calcular de forma más eficiente que la convolución lineal, según el teorema de convolución circular : ${\displaystyle (x_{k,N})*h\,}$ ${\displaystyle x_{k}*h\,}$ ${\displaystyle M+1\leq n\leq L+M}$ ${\displaystyle x_{k}[n]\,}$ ${\displaystyle h[n]\,}$

dónde :

• DFT _N e IDFT _N se refieren a la transformada de Fourier discreta y su inversa, evaluadas sobre N puntos discretos, y
• Habitualmente, L se elige de modo que N = L+M-1 sea una potencia entera de 2, y las transformaciones se implementan con el algoritmo FFT para lograr eficiencia.
• Los efectos de borde delantero y trasero de la convolución circular se superponen y se suman, ^[C] y posteriormente se descartan. ^[D]

Pseudocódigo

( Algoritmo de ahorro de superposición para convolución lineal )h = respuesta_impulso_FIRM = longitud(h)superposición = M − 1N = 8 × superposición (ver la siguiente sección para una mejor elección)tamaño_de_paso = 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_de_paso)) = yt(M : N) (descarta M−1 valores y) 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. ^[E] 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-ahorro escala casi igual, mientras que el costo de una única convolución circular grande es casi . ${\displaystyle O\left(N_{x}\log _{2}N\right)}$ ${\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}$

Superposición-descarte

Superposición–descarte ^[2] y Superposición–eliminación ^[3] son ​​etiquetas menos utilizadas para el mismo método descrito aquí. Sin embargo, estas etiquetas son en realidad mejores (que superposición–guardar ) para distinguirlas de superposición–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 superposición–guardar

El algoritmo de superposición-guardado se puede ampliar para incluir otras operaciones comunes de un sistema: ^{[F] [4]}

• Se pueden procesar canales IFFT adicionales de forma más económica que el primero reutilizando la FFT directa
• Las frecuencias de muestreo se pueden cambiar utilizando FFT directas e inversas de diferentes tamaños
• La traducción de frecuencia (mezcla) se puede lograr reorganizando los contenedores de frecuencia

Véase también

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

Notas

1. Rabiner y Gold, Fig. 2.35, cuarto trazo.
2. El desplazamiento de los efectos de borde no deseados a las últimas M-1 salidas es una posible conveniencia en tiempo de ejecución, porque la IDFT se puede calcular en el búfer, en lugar de calcularse y copiarse. Luego, los efectos de borde se pueden sobrescribir con la siguiente IDFT. Una nota al pie posterior explica cómo se realiza el desplazamiento, mediante un desplazamiento temporal de la respuesta al impulso. ${\displaystyle y[n]}$
3. No debe confundirse con el método Overlap-add , que conserva los efectos de borde inicial y final separados.
4. 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 circularmente (se rota) en M-1 muestras. Por lo 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. ${\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])}$ ${\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),}$
5. El algoritmo FFT de Cooley–Tukey para N=2 ^k necesita (N/2) log ₂ (N) – ver FFT – Definición y velocidad
6. Carlín y col. 1999, pág. 31, columna 20.

Referencias

1. "Procesamiento STFT con superposición y adición (OLA) | Procesamiento de señales de audio espectrales". www.dsprelated.com . Consultado el 2 de marzo de 2024 . El nombre de superposición y guardado proviene del hecho de que se guardan L-1 muestras del cuadro anterior [aquí: M-1 muestras del cuadro actual] para calcular el siguiente cuadro.
2. Harris, FJ (1987). DFElliot (ed.). Manual de procesamiento de señales digitales . San Diego: Academic Press. págs. 633–699. ISBN. 0122370759.
3. Frerking, Marvin (1994). Procesamiento de señales digitales en sistemas de comunicación . Nueva York: Van Nostrand Reinhold. ISBN 0442016166.
4. Borgerding, Mark (2006). "Convertir el Overlap–Save en un banco de filtros de submuestreo y mezcla multibanda". Revista IEEE Signal Processing . 23 (marzo de 2006): 158–161. doi :10.1109/MSP.2006.1598092.

4. Rabiner, Lawrence R.; Gold, Bernard (1975). "2.25" . Teoría y aplicación del procesamiento de señales digitales . Englewood Cliffs, NJ: Prentice-Hall. pp. 63–67. ISBN. 0-13-914101-4.
5. Patente estadounidense 6898235, Carlin, Joe; Collins, Terry y Hays, Peter et al., "Dispositivo de intercepción y búsqueda de dirección de comunicaciones de banda ancha mediante hipercanalización", publicada el 10 de diciembre de 1999, expedida el 24 de mayo de 2005  , también disponible en https://patentimages.storage.googleapis.com/4d/39/2a/cec2ae6f33c1e7/US6898235.pdf

Enlaces externos

• Dra. Deepa Kundur, Superposición de adición y superposición de guardado, Universidad de Toronto