离散 Fourier 变换
人们刚开始利用无线电技术传输信号时，是将连续信号进行某种调制处理后直接传送的 （图 16.5.1）,本质上传送的还是连续信号 （也叫模拟信号） 。这样的传输方式抗干扰能力差，失真严重，尤其是经过长距离传送或多级传递后,信号可能面目全非,质量自然难尽人意。
传送
调制 解调图 16.5.1
§ 5 快速Fourier 变换以后发展了离散的传输方法，它不是传送连续信号本身，而是每隔一段时间 Δt，从信号中提取一个数值脉冲（称为数值抽样），将连续信号转化成数据序列 x()0,x()1,)2(x,…,xN()?1 （图 16.5.2）,
再经编码后发送。只要抽取的时间间隔足够小，这列数据就能很好地反映原信号，接收方通过逆向处理，
可以复原出所传递的信号（图
16.5.3） 。这种方法称为数字信号传输，具有抗干扰能力强、信号还原质量高、易于加密和解密等优点，
问世后便受到广泛的重视，至今方兴未艾。
1N
t
2
t
1
t
0
t
tΔ
(0)x
(1)x
(2)x
1()Nx?
传送
抽样 编码 调制 解调 解码 还原
图 16.5.3
可以想见的是，为了保证接收的质量,Δt必须取得很小，即 N 非常之大。因此,直接发送这列数据将会长时间地占用传输设备和线路，
这不但需要支付昂贵的费用，在情况紧急时甚至会误事。
所以，在抽样之后需要对数据序列 x()0,x()1,…,xN()?1 进 行简化和压缩，但由于序列中数据的大小是散乱的，因此一方面我们 不能随意舍弃某些数据，另一方面压缩的效果也比较差。
后来经研究发现，若对数据序列 x()0,x()1,…,xN()?1 施以如下的 离散 Fourier 变换
1
2πi
0
() ()e
nj
N
N
n
Xj xn
=
=
∑
（ 1,,2,1,0?= Nj ",i1=? ）
就可以有效地解决上面的问题。
利用正交关系式
1
2πi2πi
,
0
1
ee
nj nk
N
NN
j k
n
N
δ
=
=
∑
≠
=
=
kj
kj
,0
,,1
可以导出 离散 Fourier 逆变换
1
2πi
0
1
() ()e
jk
N
N
j
xk X j
N
=
=
∑
,1,,2,1,0?= Nk ",
这是因为
1
2πi
0
1
()e
jk
N
N
j
Xj
N
=
∑
11
2πi2πi
00
1
()e e
nj jk
NN
NN
jn
xn
N
==
=
∑∑
11
2πi2πi
00
1
() e e
nj jk
NN
NN
nj
xn
N
==
=
∑∑ ∑
=
=
1
0
,
)(
N
n
kn
nx δ = xk()。
也就是说，若发送方将 x()0,x()1,…,xN()?1 作了离散 Fourier 变 换后传输出去，接收方可以对收到的数据进行离散 Fourier 逆变换,再现原始信号。
从表面看来，这么做似乎毫无必要，因为变换后的数据长度仍是
N,并没有缩短，况且还要额外支出两次变换的代价。其实不然。
从变换公式容易看出，变换后的序列中的每个 Xj()，都包含了原序列中所有信号的信息。因此，即使丢失了某些 Xj()，仍可望由其余数据基本正确地还原出原始数据。这当然使得传输过程的抗干扰能力进一步提高，但更重要的是，这可以让我们通过有意剔除某些模较小的数据（通常这类数据数量很大）而使需传输的序列大为缩短。此外，
X()0,X()1,…,XN()?1 的排列将很有规律，模较大的数据往往集中在序列中一两个较窄的范围内，易于作高效的压缩处理。
例16.5.1 对长度为 64 的序列 {( )}xk 做离散 Fourier 变换，其取值如图 16.5.4(a)中的,+”所示，变换后的 Xj()的模用,o”表示。
从图中可以看到,{( )}xk 的变化很大，有高低不同的四个起伏。
但做了 Fourier 变换后,{| ( )|}Xj 只是在序列的起首和终止处附近有两个高的起伏，而处于序列中部的数据，其模的波动范围是不大的。也就是说,{()}Xj 排列确实很有规律，易于作进一步的处理。
此外，我们还发现,{()}Xj 中约有三分之一的点（虚线以下）的模接近于零。现在我们将这些点全部强行置为零后，再对整个序列进行 Fourier 逆变换，这相当在序列中删除了这些数据后再传输出去，
让对方仅用剩下的那部分模较大数据进行逆变换。图 16.5.4(b)显示了所得的结果，这里 {( )}xk 仍用,+”表示，逆变换后得到的相应值用,o”表示，我们发现，除了极个别点误差稍大之外，两者的近似程度是相当令人满意的。
快速 Fourier 变换
尽管早就发现离散 Fourier 变换有如此诱人的好处,但在一个相当长的时期中，人们对它基本上只限于纸上谈兵。这是因为，做一次变换需要进行 N
2
次复数乘法和 NN()?1 次复数加法，实际使用中的 N 总是极为巨大的，相应的高昂代价令人望而却步。
一直到 20 世纪 60 年代中期，Cooley 和 Tukey 发现了计算离 散
Fourier 变换的高效（同时又特别适合于计算机硬件操作）的方法 —
— 快速 Fourier 变换 （简称 FFT— Fast Fourier Transform）之后,它才真正获得了生命力。可以毫不夸张地说，基于 FFT 的离散 Fourier
变换技术，是当今信息传输（图 16.5.5）,频谱分析、图象处理,数据压缩等领域中最重要的数学工具之一。目前，国际上任何一个综 合的数学软件中，必定含有 FFT 的计算程序。
传送
抽样 编码压缩调制 解调解压解码 还原
FFT 逆 FFT
图 16.5.5
下面对 FFT 的思想作一简单介绍。
设 N m= 2,将 j和 n分别改写成
jmj j= +
10
，
=
=
1,0
,1,,1,0
1
0
j
mj "
和
nnn= +2
10
，
=
=
,1,,1,0
,1,0
1
0
mn
n
"
记
2πi
e
N
N
W
=,则
2πi
2
e
m
Nm
WW
==,
πi
e1
m
N
W
= =?,WW
N
m
N
N2
1= =,
2πi
e
nj
N
= ()W
N
nj
=
++
()
()( )
W
N
nn mjj2
10 10
= ()W
N
mn j2
11
()W
N
mn j
01
()W
N
nj2
10
()W
N
nj
00
=?()1
01
nj
()W
m
nj
10
()W
N
nj
00
。
将上式代入离散 Fourier 变换公式，并记 Xj()为 Xjj(,)
10
,
Xj()= Xjj(,)
10
=
1
2πi
0
()e
nj
N
N
n
xn
=
∑
=+
==
∑∑
xn n
nn
m
()2
10
0
1
0
1
01
()?1
01
nj
()W
m
nj
10
()W
N
nj
00
∑∑
=
=
+?=
1
0
1
0
01
0
01
1
0010
)()2()()1(
n
jn
m
m
n
jn
N
jn
WnnxW,
将方括号中的部分记为 zn j(,)
00
，则计算 Xj()（ 1,,2,1,0?= Nj "）可 分解为两个步骤进行,
00 10
1
01
0
1
00 1 0 0 0
0
1
10 00 1 0
0
(,)( ) (2 )( ),0,1; 0,1,,1,
(,) ( 1) (,),0,1; 0,1,,1
m
nj nj
Nm
n
nj
n
zn j W x n n W n j m
Xjj znj j j m
=
=
=+==?
= = =?
∑
∑
"
"。
实际处理数据时,因子 ()W
m
nj
10
和 ()W
N
nj
00
都是事先算好存储在计算机内的。因此，在第一式中，每一个 zn j(,)
00
需要进行 m次复数乘法和
m?1次复数加法，第二式中，每一个 Xjj(,)
10
只需要做 m?1次复数加法而不需要做复数乘法,所以总共需要做 mN 次复数乘法和 21()mN? 次复数加法。
若 N
k
= 2,则 m
k
=
2
1
仍是偶数，因此可对第一式中的
xn n
n
m
()2
10
0
1
1
+
=
∑
()W
m
nj
10
继续进行上述处理，以进一步减少计算量。这样一种反复递减，直到
m = 2为止的过程称为以 2 为底的快速 Fourier 变换。
容易推导出，对 N
k
= 2,执行一个以 2 为底的完整的 FFT，只需要进行
kN
NN
2
1
2
2
= log 次复数乘法和 kN N N= log
2
次复数加法。由于
log
2
0
N
N
→,N →∞,
因此它比原来需要 N
2
次运算的直接算法在数量级上有了重大改进，
节省的工作量相当惊人，比如，对 N = =21024
10
，原算法的复数乘法次数就超过 FFT 的 200 倍！
FFT 还为离散 Fourier 变换开拓出了许多新的用途，计算数列的卷积就是一个典型的例子。
设 {( )}xk
k
N
=
0
1
和 {()}yk
k
N
=
0
1
都是实的或复的数列，定义它们的 卷积 为
1
def
0
()* () ()( ) ()
N
j
x kyk xjykj zk
=
=?=
∑
,1,,1,0?= Nk ",
这与上一节中定义的函数的卷积是很相像的。
显然，若直接按上式计算，要得到 {( )}zk
k
N
=
0
1
总共约需做 2 N
2
次 运算，其中加法和乘法基本上各占一半。这与用直接方法做一次离 散
Fourier 变换的计算量是相同的，并非是一种有效的方法。
考虑到函数的卷积与 Fourier 变换的关系，可以猜想，数列的 卷积可能与离散 Fourier 变换会有类似的关系。 若果真是这样，那么 FFT
就可以在其中找到用武之地。
设 {( )}xk 和 {()}yk 的离散 Fourier 变换分别为 {()}Xj
j
N
=
0
1
和 {()}Yj
j
N
=
0
1
，
即
Xj xnW
N
nj
n
N
() ()( )=
=
∑
0
1
,Yj ynW
N
mj
m
N
() ()( )=
=
∑
0
1
,
则它们对应项的相乘为
XjYj()()=
+
=
=
∑∑
xnym W
N
nmj
m
N
n
N
()( )( )
()
0
1
0
1
,
利用
kj
N
n
kn
N
jn
N
WW
N
,
1
0
)()(
1
δ=
∑
=
,
于是，数列 { ()()}XjYj
j
N
=
0
1
的离散 Fourier 逆变换为
1
2πi
0
1
()()e
jk
N
N
j
XjYj
N
=
∑ ∑∑∑
=
=
+
=
=
1
0
1
0
)(
1
0
)())(()(
1
N
j
jk
N
N
n
jnm
N
m
N
WWmynx
N
∑∑ ∑
=
=
+
=
=
1
0
1
0
)(
1
0
)()(
1
)()(
N
n
N
m
jk
N
jnm
N
j
N
WW
N
mynx
∑∑
=
=
+
=
1
0
1
0
,
)()(
N
n
N
m
knm
mynx δ =?
=
∑
xnyk n
n
N
()( )
0
1
= zk()。
于是，计算 {( )}xk 和 {()}yk 的卷积 {( )}zk 的过程可以分成三步,
⑴ 分别做{( )}xk和{()}yk的离散Fourier变换{()}Xj和{()}Yj ；
⑵ 求XjYj()(),1,,1,0?= Nj "；
⑶ 做{ ()()}XjYj的离散Fourier逆变换，得到{( )}zk 。
上述过程需要两次离散 Fourier 变换和一次离散 Fourier 逆变换，
若用直接计算的方法做变换，总计算量将达到直接求卷积时的三倍，
无疑是大大地划不来。因此尽管这个结果早就为人所知，但在 FFT
问世之前，就实际问题计算而言，从来就是无人问津的。
有了 FFT 之后情况立即改观。因⑴和⑶用 FFT 做，总共只需
45
2
.logNN次运算，其中仅三分之一为乘法，而⑵只需 2N 次运算，所以虽说是绕了一个圈子，计算量反倒大为减少，并且，当 N 很大时，
减少的数目是相当可观的。
由 FFT 方法出发，产生了很大一类基于卷积计算的快速算法。
比如，要计算两个 n次多项式 px ax
nk
k
k
n
()=
=
∑
0
和 qx bx
nk
k
k
n
()=
=
∑
0
的乘积
rx pxqx
nnn2
() () ()= =
=
∑
cx
k
k
k
n
0
2
直接求系数
cab
kjkj
j
n
=
=
∑
0
,nk 2,,1,0 "=,
将是事倍功半的。若观察到 c
k
的形式与卷积非常相象，进而令数列
{()}Ak 和 {()}Bk 分别为
≤<
≤≤
=
,2,0
,0,
)(
nkn
nka
kA
k
≤<
≤≤
=
,2,0
,0,
)(
nkn
nkb
kB
k
则不难验证 {}c
k
正是 {()}Ak 和 {()}Bk 的卷积,于是前面关于卷积的高效的计算方案可以毫不走样地全部照搬 —— 这就是求多项式乘积的快速算法。
人们刚开始利用无线电技术传输信号时，是将连续信号进行某种调制处理后直接传送的 （图 16.5.1）,本质上传送的还是连续信号 （也叫模拟信号） 。这样的传输方式抗干扰能力差，失真严重，尤其是经过长距离传送或多级传递后,信号可能面目全非,质量自然难尽人意。
传送
调制 解调图 16.5.1
§ 5 快速Fourier 变换以后发展了离散的传输方法，它不是传送连续信号本身，而是每隔一段时间 Δt，从信号中提取一个数值脉冲（称为数值抽样），将连续信号转化成数据序列 x()0,x()1,)2(x,…,xN()?1 （图 16.5.2）,
再经编码后发送。只要抽取的时间间隔足够小，这列数据就能很好地反映原信号，接收方通过逆向处理，
可以复原出所传递的信号（图
16.5.3） 。这种方法称为数字信号传输，具有抗干扰能力强、信号还原质量高、易于加密和解密等优点，
问世后便受到广泛的重视，至今方兴未艾。
1N
t
2
t
1
t
0
t
tΔ
(0)x
(1)x
(2)x
1()Nx?
传送
抽样 编码 调制 解调 解码 还原
图 16.5.3
可以想见的是，为了保证接收的质量,Δt必须取得很小，即 N 非常之大。因此,直接发送这列数据将会长时间地占用传输设备和线路，
这不但需要支付昂贵的费用，在情况紧急时甚至会误事。
所以，在抽样之后需要对数据序列 x()0,x()1,…,xN()?1 进 行简化和压缩，但由于序列中数据的大小是散乱的，因此一方面我们 不能随意舍弃某些数据，另一方面压缩的效果也比较差。
后来经研究发现，若对数据序列 x()0,x()1,…,xN()?1 施以如下的 离散 Fourier 变换
1
2πi
0
() ()e
nj
N
N
n
Xj xn
=
=
∑
（ 1,,2,1,0?= Nj ",i1=? ）
就可以有效地解决上面的问题。
利用正交关系式
1
2πi2πi
,
0
1
ee
nj nk
N
NN
j k
n
N
δ
=
=
∑
≠
=
=
kj
kj
,0
,,1
可以导出 离散 Fourier 逆变换
1
2πi
0
1
() ()e
jk
N
N
j
xk X j
N
=
=
∑
,1,,2,1,0?= Nk ",
这是因为
1
2πi
0
1
()e
jk
N
N
j
Xj
N
=
∑
11
2πi2πi
00
1
()e e
nj jk
NN
NN
jn
xn
N
==
=
∑∑
11
2πi2πi
00
1
() e e
nj jk
NN
NN
nj
xn
N
==
=
∑∑ ∑
=
=
1
0
,
)(
N
n
kn
nx δ = xk()。
也就是说，若发送方将 x()0,x()1,…,xN()?1 作了离散 Fourier 变 换后传输出去，接收方可以对收到的数据进行离散 Fourier 逆变换,再现原始信号。
从表面看来，这么做似乎毫无必要，因为变换后的数据长度仍是
N,并没有缩短，况且还要额外支出两次变换的代价。其实不然。
从变换公式容易看出，变换后的序列中的每个 Xj()，都包含了原序列中所有信号的信息。因此，即使丢失了某些 Xj()，仍可望由其余数据基本正确地还原出原始数据。这当然使得传输过程的抗干扰能力进一步提高，但更重要的是，这可以让我们通过有意剔除某些模较小的数据（通常这类数据数量很大）而使需传输的序列大为缩短。此外，
X()0,X()1,…,XN()?1 的排列将很有规律，模较大的数据往往集中在序列中一两个较窄的范围内，易于作高效的压缩处理。
例16.5.1 对长度为 64 的序列 {( )}xk 做离散 Fourier 变换，其取值如图 16.5.4(a)中的,+”所示，变换后的 Xj()的模用,o”表示。
从图中可以看到,{( )}xk 的变化很大，有高低不同的四个起伏。
但做了 Fourier 变换后,{| ( )|}Xj 只是在序列的起首和终止处附近有两个高的起伏，而处于序列中部的数据，其模的波动范围是不大的。也就是说,{()}Xj 排列确实很有规律，易于作进一步的处理。
此外，我们还发现,{()}Xj 中约有三分之一的点（虚线以下）的模接近于零。现在我们将这些点全部强行置为零后，再对整个序列进行 Fourier 逆变换，这相当在序列中删除了这些数据后再传输出去，
让对方仅用剩下的那部分模较大数据进行逆变换。图 16.5.4(b)显示了所得的结果，这里 {( )}xk 仍用,+”表示，逆变换后得到的相应值用,o”表示，我们发现，除了极个别点误差稍大之外，两者的近似程度是相当令人满意的。
快速 Fourier 变换
尽管早就发现离散 Fourier 变换有如此诱人的好处,但在一个相当长的时期中，人们对它基本上只限于纸上谈兵。这是因为，做一次变换需要进行 N
2
次复数乘法和 NN()?1 次复数加法，实际使用中的 N 总是极为巨大的，相应的高昂代价令人望而却步。
一直到 20 世纪 60 年代中期，Cooley 和 Tukey 发现了计算离 散
Fourier 变换的高效（同时又特别适合于计算机硬件操作）的方法 —
— 快速 Fourier 变换 （简称 FFT— Fast Fourier Transform）之后,它才真正获得了生命力。可以毫不夸张地说，基于 FFT 的离散 Fourier
变换技术，是当今信息传输（图 16.5.5）,频谱分析、图象处理,数据压缩等领域中最重要的数学工具之一。目前，国际上任何一个综 合的数学软件中，必定含有 FFT 的计算程序。
传送
抽样 编码压缩调制 解调解压解码 还原
FFT 逆 FFT
图 16.5.5
下面对 FFT 的思想作一简单介绍。
设 N m= 2,将 j和 n分别改写成
jmj j= +
10
，
=
=
1,0
,1,,1,0
1
0
j
mj "
和
nnn= +2
10
，
=
=
,1,,1,0
,1,0
1
0
mn
n
"
记
2πi
e
N
N
W
=,则
2πi
2
e
m
Nm
WW
==,
πi
e1
m
N
W
= =?,WW
N
m
N
N2
1= =,
2πi
e
nj
N
= ()W
N
nj
=
++
()
()( )
W
N
nn mjj2
10 10
= ()W
N
mn j2
11
()W
N
mn j
01
()W
N
nj2
10
()W
N
nj
00
=?()1
01
nj
()W
m
nj
10
()W
N
nj
00
。
将上式代入离散 Fourier 变换公式，并记 Xj()为 Xjj(,)
10
,
Xj()= Xjj(,)
10
=
1
2πi
0
()e
nj
N
N
n
xn
=
∑
=+
==
∑∑
xn n
nn
m
()2
10
0
1
0
1
01
()?1
01
nj
()W
m
nj
10
()W
N
nj
00
∑∑
=
=
+?=
1
0
1
0
01
0
01
1
0010
)()2()()1(
n
jn
m
m
n
jn
N
jn
WnnxW,
将方括号中的部分记为 zn j(,)
00
，则计算 Xj()（ 1,,2,1,0?= Nj "）可 分解为两个步骤进行,
00 10
1
01
0
1
00 1 0 0 0
0
1
10 00 1 0
0
(,)( ) (2 )( ),0,1; 0,1,,1,
(,) ( 1) (,),0,1; 0,1,,1
m
nj nj
Nm
n
nj
n
zn j W x n n W n j m
Xjj znj j j m
=
=
=+==?
= = =?
∑
∑
"
"。
实际处理数据时,因子 ()W
m
nj
10
和 ()W
N
nj
00
都是事先算好存储在计算机内的。因此，在第一式中，每一个 zn j(,)
00
需要进行 m次复数乘法和
m?1次复数加法，第二式中，每一个 Xjj(,)
10
只需要做 m?1次复数加法而不需要做复数乘法,所以总共需要做 mN 次复数乘法和 21()mN? 次复数加法。
若 N
k
= 2,则 m
k
=
2
1
仍是偶数，因此可对第一式中的
xn n
n
m
()2
10
0
1
1
+
=
∑
()W
m
nj
10
继续进行上述处理，以进一步减少计算量。这样一种反复递减，直到
m = 2为止的过程称为以 2 为底的快速 Fourier 变换。
容易推导出，对 N
k
= 2,执行一个以 2 为底的完整的 FFT，只需要进行
kN
NN
2
1
2
2
= log 次复数乘法和 kN N N= log
2
次复数加法。由于
log
2
0
N
N
→,N →∞,
因此它比原来需要 N
2
次运算的直接算法在数量级上有了重大改进，
节省的工作量相当惊人，比如，对 N = =21024
10
，原算法的复数乘法次数就超过 FFT 的 200 倍！
FFT 还为离散 Fourier 变换开拓出了许多新的用途，计算数列的卷积就是一个典型的例子。
设 {( )}xk
k
N
=
0
1
和 {()}yk
k
N
=
0
1
都是实的或复的数列，定义它们的 卷积 为
1
def
0
()* () ()( ) ()
N
j
x kyk xjykj zk
=
=?=
∑
,1,,1,0?= Nk ",
这与上一节中定义的函数的卷积是很相像的。
显然，若直接按上式计算，要得到 {( )}zk
k
N
=
0
1
总共约需做 2 N
2
次 运算，其中加法和乘法基本上各占一半。这与用直接方法做一次离 散
Fourier 变换的计算量是相同的，并非是一种有效的方法。
考虑到函数的卷积与 Fourier 变换的关系，可以猜想，数列的 卷积可能与离散 Fourier 变换会有类似的关系。 若果真是这样，那么 FFT
就可以在其中找到用武之地。
设 {( )}xk 和 {()}yk 的离散 Fourier 变换分别为 {()}Xj
j
N
=
0
1
和 {()}Yj
j
N
=
0
1
，
即
Xj xnW
N
nj
n
N
() ()( )=
=
∑
0
1
,Yj ynW
N
mj
m
N
() ()( )=
=
∑
0
1
,
则它们对应项的相乘为
XjYj()()=
+
=
=
∑∑
xnym W
N
nmj
m
N
n
N
()( )( )
()
0
1
0
1
,
利用
kj
N
n
kn
N
jn
N
WW
N
,
1
0
)()(
1
δ=
∑
=
,
于是，数列 { ()()}XjYj
j
N
=
0
1
的离散 Fourier 逆变换为
1
2πi
0
1
()()e
jk
N
N
j
XjYj
N
=
∑ ∑∑∑
=
=
+
=
=
1
0
1
0
)(
1
0
)())(()(
1
N
j
jk
N
N
n
jnm
N
m
N
WWmynx
N
∑∑ ∑
=
=
+
=
=
1
0
1
0
)(
1
0
)()(
1
)()(
N
n
N
m
jk
N
jnm
N
j
N
WW
N
mynx
∑∑
=
=
+
=
1
0
1
0
,
)()(
N
n
N
m
knm
mynx δ =?
=
∑
xnyk n
n
N
()( )
0
1
= zk()。
于是，计算 {( )}xk 和 {()}yk 的卷积 {( )}zk 的过程可以分成三步,
⑴ 分别做{( )}xk和{()}yk的离散Fourier变换{()}Xj和{()}Yj ；
⑵ 求XjYj()(),1,,1,0?= Nj "；
⑶ 做{ ()()}XjYj的离散Fourier逆变换，得到{( )}zk 。
上述过程需要两次离散 Fourier 变换和一次离散 Fourier 逆变换，
若用直接计算的方法做变换，总计算量将达到直接求卷积时的三倍，
无疑是大大地划不来。因此尽管这个结果早就为人所知，但在 FFT
问世之前，就实际问题计算而言，从来就是无人问津的。
有了 FFT 之后情况立即改观。因⑴和⑶用 FFT 做，总共只需
45
2
.logNN次运算，其中仅三分之一为乘法，而⑵只需 2N 次运算，所以虽说是绕了一个圈子，计算量反倒大为减少，并且，当 N 很大时，
减少的数目是相当可观的。
由 FFT 方法出发，产生了很大一类基于卷积计算的快速算法。
比如，要计算两个 n次多项式 px ax
nk
k
k
n
()=
=
∑
0
和 qx bx
nk
k
k
n
()=
=
∑
0
的乘积
rx pxqx
nnn2
() () ()= =
=
∑
cx
k
k
k
n
0
2
直接求系数
cab
kjkj
j
n
=
=
∑
0
,nk 2,,1,0 "=,
将是事倍功半的。若观察到 c
k
的形式与卷积非常相象，进而令数列
{()}Ak 和 {()}Bk 分别为
≤<
≤≤
=
,2,0
,0,
)(
nkn
nka
kA
k
≤<
≤≤
=
,2,0
,0,
)(
nkn
nkb
kB
k
则不难验证 {}c
k
正是 {()}Ak 和 {()}Bk 的卷积,于是前面关于卷积的高效的计算方案可以毫不走样地全部照搬 —— 这就是求多项式乘积的快速算法。
