Método de superposición y guardado

En procesamiento de señales , 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 pensarse en su totalidad, en lugar de en instantes específicos (ver 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 y guardado. 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, con la porción utilizable coloreada en rojo. El cuarto gráfico muestra el segmento filtrado agregado al flujo de salida. ^[A] El filtro FIR es un paso bajo de furgón con M = 16 muestras, la longitud de los segmentos es L = 100 muestras y la superposición es de 15 muestras.

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

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

${\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 de manera equivalente , 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 los primeros 3 trazos de la Figura 1, excepto que la porción deseada de la salida (tercer trazo) 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 circunvoluciones     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 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, según el teorema de la 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 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 de borde inicial y posterior de la convolución circular se superponen y agregan, ^[C] y posteriormente se descartan. ^[D]

Pseudocódigo

( Algoritmo de superposición y guardado para convolución lineal )h = FIR_impulso_respuestaM = longitud(h)superposición = M − 1N = 8 × superposición (consulte la siguiente sección para una mejor elección)tamaño_paso = N - superposiciónH = EPS(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 M−1 valores y) 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. ^[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 :

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 ecuación dada, 3 tiene un mínimo con respecto a la Figura 2. Es una gráfica de los valores de esa ecuación 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 ahorro aumenta casi 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)}$

Superponer-descartar

Superponer-descartar ^[2] y Superponer-desechar ^[3] son ​​etiquetas que se utilizan con menos frecuencia para el mismo método que se describe aquí. Sin embargo, estas etiquetas son en realidad mejores (que solapar–guardar ) para distinguirlas de solapar–añadir , 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.

Ampliar superposición: guardar

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

• Los canales IFFT adicionales se pueden procesar de forma más económica que el primero reutilizando 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

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

Notas

1. Rabiner y Gold, figura 2.35, cuarto trazo.
2. Cambiar los efectos de borde indeseables a las últimas salidas M-1 es una posible conveniencia en tiempo de ejecución, porque el IDFT se puede calcular en el búfer, en lugar de calcularlo y copiarlo. 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 desplazamiento temporal de la respuesta al impulso. ${\displaystyle y[n]}$
3. No debe confundirse con el método Overlap-add , que conserva efectos de borde inicial y posterior separados.
4. Los efectos de borde se pueden mover desde el frente hacia la parte posterior de la salida IDFT reemplazándolos con el significado de que el búfer de longitud N se desplaza (gira) circularmente mediante 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. ${\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. Algoritmo Cooley-Tukey FFT 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 de superposición y adición (OLA) | Procesamiento de señales de audio espectral". www.dsprelacionado.com . Consultado el 2 de marzo de 2024 . El nombre de superposición-guardado proviene del hecho de que L-1 muestras del fotograma anterior [aquí: M-1 muestras del fotograma actual] se guardan para calcular el siguiente fotograma.
2. Harris, FJ (1987). DFElliot (ed.). Manual de procesamiento de señales digitales . San Diego: Prensa académica. págs. 633–699. ISBN 0122370759.
3. Frerking, Marvin (1994). Procesamiento Digital de Señales en Sistemas de Comunicación . Nueva York: Van Nostrand Reinhold. ISBN 0442016166.
4. Borgerding, Mark (2006). "Convertir superposición: guardar en un banco de filtros de reducción de resolución y mezcla multibanda". Revista de procesamiento de señales IEEE . 23 (marzo de 2006): 158-161. doi :10.1109/MSP.2006.1598092.

4. 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.
5. patente estadounidense 6898235, Carlin, Joe; Collins, Terry & Hays, Peter et al., "Dispositivo de búsqueda de dirección y interceptación de comunicaciones de banda ancha mediante hipercanalización", publicado el 10 de diciembre de 1999, publicado 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, Superponer agregar y superponer guardar, Universidad de Toronto