FFT快速傅里叶变换推导

DFT的定义

DFT，即离散傅里叶变换，假设我们有长为N的序列x[0],x[1],…,x[N-1]，那么DFT计算过程如下 X [ k ] = ∑ n = 0 N − 1 x [ n ] W N n k , ( W N = e − j 2 π N ) X[k]=\sum_{n=0}^{N-1}x[n]W_N^{nk},(W_N^{}=e^{-j\frac{2\pi}{N}}) X[k]=∑n=0N−1​x[n]WNnk​,(WN​=e−jN2π​) 而IDFT(离散傅里叶逆变换)计算过程为 x [ k ] = ∑ n = 0 N − 1 X [ n ] W N − n k x[k]=\sum_{n=0}^{N-1}X[n]W_{N}^{-nk} x[k]=∑n=0N−1​X[n]WN−nk​

多项式的两种表示方法

知道了DFT和IDFT的数学表达式，下面考虑一个多项式乘法的例子 A ( x ) = a 0 + a 1 x + . . . + a n − 1 x n − 1 A(x)=a_0+a_1x+...+a_{n-1}x^{n-1} A(x)=a0​+a1​x+...+an−1​xn−1 B ( x ) = b 0 + b 1 x + . . . + b n − 1 x n − 1 B(x)=b_0+b_1x+...+b_{n-1}x^{n-1} B(x)=b0​+b1​x+...+bn−1​xn−1 我们知道，我们可以用序列 ( a 0 , a 1 , . . . , a n − 1 ) 和 序 列 ( b 0 , b 1 , . . . , b n − 1 ) 来 表 示 A ( x ) 和 B ( x ) (a_0,a_1,...,a_{n-1})和序列(b_0,b_1,...,b_{n-1})来表示A(x)和B(x) (a0​,a1​,...,an−1​)和序列(b0​,b1​,...,bn−1​)来表示A(x)和B(x)两个多项式，这也是最容易让人想到的表示方法，那么是否还有其他的表示多项式的方法呢？ 答案是肯定的，首先，让我们来看一个代数学中的基本定理: 平 面 上 n 个 不 同 的 点 唯 一 确 定 一 个 n − 1 次 多 项 式 平面上n个不同的点唯一确定一个n-1次多项式 平面上n个不同的点唯一确定一个n−1次多项式 该定理的证明在此处略去（事实上就是一个矩阵方程求解的问题） 有了该定理的支撑，我们就可以用n个点，来表示A(x)和B(x)了，我们取序列 t 0 , t 1 , . . . , t n − 1 t_0,t_1,...,t_{n-1} t0​,t1​,...,tn−1​,并计算 A ( t 0 ) , A ( t 1 ) , . . . , A ( t n − 1 ) A(t_0),A(t_1),...,A(t_{n-1}) A(t0​),A(t1​),...,A(tn−1​)和 B ( t 0 ) , B ( t 1 ) , . . . , B ( t n − 1 ) B(t_0),B(t_1),...,B(t_{n-1}) B(t0​),B(t1​),...,B(tn−1​) 那么点列 ( ( t 0 , A ( t 0 ) ) , . . . , ( t n − 1 , A ( t n − 1 ) ) ) ((t_0,A(t_0)),...,(t_{n-1},A(t_{n-1}))) ((t0​,A(t0​)),...,(tn−1​,A(tn−1​)))可以唯一的表示多项式 A ( x ) A(x) A(x),点列 ( ( t 0 , B ( t 0 ) ) , . . . , ( t n − 1 , B ( t n − 1 ) ) ) ((t_0,B(t_0)),...,(t_{n-1},B(t_{n-1}))) ((t0​,B(t0​)),...,(tn−1​,B(tn−1​)))可以唯一的表示多项式 B ( x ) B(x) B(x)

FFT

准备知识 n次单位根： ω n k \omega_n^k ωnk​ 考虑方程 x n = 1 x^n=1 xn=1在复数域的解，由代数学基本定理可知，该方程在复数域上共有n个复数根，进一步的，这n个根为: e j 2 k π n , k = 0 , 1 , 2 , . . , n − 1 e^{j\frac{2k\pi}{n}}, k=0,1,2,..,n-1 ejn2kπ​,k=0,1,2,..,n−1 我们记 ω n k = e j 2 k π n \omega_n^k=e^{j\frac{2k\pi}{n}} ωnk​=ejn2kπ​,下面来看看它的性质 1. ω 2 n 2 k = ω n k \omega_{2n}^{2k}=\omega_n^k ω2n2k​=ωnk​ 2. ω n k = ω n k + n \omega_n^k=\omega_n^{k+n} ωnk​=ωnk+n​ 3. ω n k + n / 2 = − ω n k \omega_n^{k+n/2}=-\omega_n^k ωnk+n/2​=−ωnk​ 这些性质都是容易证明的，这里不再赘述。 再来看 A ( x ) A(x) A(x) A ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 + . . . + a n − 1 x n − 1 = ( a 0 + a 2 x 2 + a 4 x 4 + . . . + a n − 2 x n − 2 ) + ( a 1 x + a 3 x 3 + . . . + a n − 1 x n − 1 ) = ( a 0 + a 2 x 2 + a 4 x 4 + . . . + a n − 2 x n − 2 ) + x ( a 1 + a 3 x 2 + . . . + a n − 1 x n − 2 ) A(x)=a_0+a_1x+a_2x^2+a_3x^3+...+a_{n-1}x^{n-1}\\=(a_0+a_2x^2+a_4x^4+...+a_{n-2}x^{n-2})+(a_1x+a_3x^3+...+a_{n-1}x^{n-1})\\=(a_0+a_2x^2+a_4x^4+...+a_{n-2}x^{n-2})+x(a_1+a_3x^2+...+a_{n-1}x^{n-2}) A(x)=a0​+a1​x+a2​x2+a3​x3+...+an−1​xn−1=(a0​+a2​x2+a4​x4+...+an−2​xn−2)+(a1​x+a3​x3+...+an−1​xn−1)=(a0​+a2​x2+a4​x4+...+an−2​xn−2)+x(a1​+a3​x2+...+an−1​xn−2) 我们令 A 1 ( x ) = a 0 + a 2 x + . . . + a n − 2 x n / 2 − 1 A_1(x)=a_0+a_2x+...+a_{n-2}x^{n/2-1} A1​(x)=a0​+a2​x+...+an−2​xn/2−1 A 2 ( x ) = a 1 + a 3 x + . . . + a n − 1 x n / 2 − 1 A_2(x)=a_1+a_3x+...+a_{n-1}x^{n/2-1} A2​(x)=a1​+a3​x+...+an−1​xn/2−1 则上式可以化简为 A ( x ) = A 1 ( x 2 ) + x A 2 ( x 2 ) A(x)=A_1(x^2)+xA_2(x^2) A(x)=A1​(x2)+xA2​(x2) 设 k < n / 2 k