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