Bueno, ayudaría saber qué es la convolución. Una vez que sepas eso, probablemente puedas ver que unir dos señales es lo mismo que multiplicar los números que tienen las muestras como dígitos: simplemente pruébalo, por ejemplo, [1,2,3] * [4,5,6] dará la misma señal que 123 * 456, a saber [5,6,0,8,8] (56088). Entonces, todo lo que necesita hacer es darse cuenta de que la convolución en el dominio del tiempo es la multiplicación en el dominio de la frecuencia, por lo que su convolución de dos números (que equivale a la multiplicación) puede acelerarse tomando la transformación de Fourier de ambos y multiplicando los resultados, luego transformando de nuevo. Por supuesto, querrás tomar el FFT para hacer la transformación de Fourier porque, como su nombre lo indica, es rápido.
En pocas palabras, necesita saber sobre convolución y algunos análisis básicos de Fourier. Aquí hay un libro en línea gratuito que puede ayudarlo a comenzar: http://www.dspguide.com/.
¿Cuáles son los requisitos previos para comprender el algoritmo de transformación rápida de Fourier para la multiplicación?
Related Content
¿Cuál es el algoritmo para resolver el problema BRCKTS de SPOJ?
¿Cómo se les ocurre la fórmula para la multiplicación de matrices de Strassen?
¿Cuál es una explicación de una parte de la derivación del algoritmo de retropropagación?
¿Puedes explicar cómo calcular las complejidades temporales de los algoritmos con un ejemplo?
La parte difícil de la multiplicación de FFT es comprender la propia FFT. Para comprender los detalles de la FFT, necesitamos comprender los números complejos a través de la Fórmula de Euler. Esa es más o menos la parte más avanzada; el resto no es mucho más que álgebra de secundaria. Esbocemos el resto.
A grandes rasgos, el problema es multiplicar dos números muy largos, típicamente como parte de un paquete de computadora bignum. Multiplicar números largos es muy parecido a multiplicar polinomios largos. Cada dígito en la suma es la suma de una gran columna de términos similares. Para números largos, las columnas se llevan entre sí; para polinomios no hay acarreos.
El método FFT es realmente una forma de multiplicar polinomios grandes. Para multiplicar números grandes, tratamos los dígitos como coeficientes. [matemática] 123 \ veces 45 [/ matemática] se convierte en [matemática] (3 + 2 x + 1x ^ 2) (5 + 4x) [/ matemática]. Después de resolver el polinomio del producto, hay un paso en el que tenemos que enchufar la base (aquí [matemática] 10 [/ matemática]) como [matemática] x, [/ matemática] que esencialmente equivale a resolver los acarreos. Entonces, a partir de aquí, hablemos sobre la multiplicación de polinomios.
Hay una manera rápida Si conocemos el valor de dos polinomios en las mismas N entradas, es fácil calcular el valor del producto en las mismas N entradas. Simplemente multiplicamos por pares. No hay una colección tediosa de términos similares.
Pero primero tenemos que evaluar los dos polinomios en cada una de las N entradas para obtener nuestros N valores. Al final, tenemos que convertir los valores del producto a coeficientes para obtener nuestro polinomio de producto. Eso parece al menos tan difícil como multiplicarlos a la larga.
Sería si tuviéramos que evaluar el polinomio una entrada a la vez. La FFT es mágicamente capaz de evaluar todos [matemática] N [/ matemática] a la vez en [matemática] \ log N [/ matemática] pasos, cada paso iterando sobre [matemática] N [/ matemática]. (Por supuesto, la FFT puede elegir qué entradas [matemáticas] N [/ matemáticas] usar.) Por lo tanto, lleva tiempo [matemáticas] O (N \ log N) [/ matemáticas] en lugar de las ingenuas [matemáticas] O (N ^ 2) [/ math] tiempo para evaluar un polinomio de término [math] N [/ math] en [math] N [/ math] diferentes entradas. Eso es muchas veces más rápido cuando [matemática] N [/ matemática] es grande, como la diferencia entre [matemática] 16 [/ matemática] y [matemática] 2 ^ {16}. [/ Matemática] Hace muchos cálculos posibles que realmente No ser susceptible al cálculo directo.
Para poder invertir de manera exclusiva el producto, N debe ser al menos la suma del número de términos en los dos polinomios. Entonces, la FFT inversa, que es esencialmente el cálculo idéntico a la FFT, produce hábilmente el producto, mucho más eficientemente que la multiplicación directa.