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):
( Ecuación 1 )
donde h [ m ] = 0 para m fuera de la región [1, M ] .
El concepto es dividir el problema en múltiples convoluciones de h [ n ] con segmentos cortos de:
donde L es una longitud de segmento arbitraria. Luego:
y y [ n ] se puede escribir como una suma de convoluciones cortas: [1]
donde la convolución lineal es cero fuera de la región [1, L + M - 1] . Y para cualquier parámetro[A] es equivalente a la convolución circular de N puntosde con en la región [1, 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 :
( 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.
Pseudocódigo
El siguiente es un pseudocódigo del algoritmo:
( Algoritmo de superposición-adición para convolución lineal )h = FIR_impulse_responseM = longitud (h)Nx = longitud (x)N = 8 × 2 ^ techo (log2 (M)) (8 veces la potencia más pequeña de dos más grandes que la longitud del filtro M. Consulte la siguiente sección para obtener una opción ligeramente mejor). Step_size = N - (M-1) (L en el texto arriba)H = DFT (h, N)posición = 0y (1: Nx + M-1) = 0mientras que position + step_size ≤ Nx do y (posición + (1: N)) = y (posición + (1: N)) + IDFT (DFT (x (posición + (1: tamaño_paso)), N) × H) position = position + step_sizefinal
Consideraciones de eficiencia
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. [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 :
( 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-suma escala casi como mientras que el costo de una sola circunvolución circular grande es casi . Los dos métodos también se comparan en la Figura 3, creada por simulación de Matlab. Los contornos son líneas de relación constante de los tiempos que se necesitan para realizar ambos métodos. Cuando el método de superposición-suma es más rápido, la relación supera 1 y se observan relaciones tan altas como 3.
Ver también
Notas
- ^ Esta condición implica que elEl segmento tiene al menos M -1 ceros añadidos, lo que evita la superposición circular de los transitorios de subida y bajada de salida.
- ^ Algoritmo Cooley-Tukey FFT para N = 2 k necesita (N / 2) log 2 (N) - ver FFT - Definición y velocidad
Referencias
- ^ 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.