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−1x[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−1X[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+a1x+...+an−1xn−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+b1x+...+bn−1xn−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+a1x+a2x2+a3x3+...+an−1xn−1=(a0+a2x2+a4x4+...+an−2xn−2)+(a1x+a3x3+...+an−1xn−1)=(a0+a2x2+a4x4+...+an−2xn−2)+x(a1+a3x2+...+an−1xn−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+a2x+...+an−2xn/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+a3x+...+an−1xn/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
