和复数加法。但是由{fl}算一个cj要作N个乘法和N－1 个加法，求出全部的 就要做
N2 个乘法和N（N－1）个加法和N个除法。当N 很大时，做起来就很费时间。直到上
世纪60年代提出了目前的快速算法，离散傅立叶变换才得到了广泛应用。所有快速算法的思想都是一个，即尽量减少乘法。比如在算N 个cj 的公式（5）中，表面上有N 个含exp(?ij2?l/N) 的项，而这N2个项中实际上只有N个是不同的，即然后把同exp(?ij2?l/N),j?0,1,?,N?1.把cj中的各项先按exp(?ij2?l/N)归类，
类项中的fl先加起来再和exp(?ij2?l/N)相乘，就可以减少许多操作。特别当N?2 时，乘法次数可以减少到
k21N(log2N) ，比如当N?210，N2?106而21N(log2N)?5*103 计算量少了近200倍，这就节约了计算cj的机器时间。 2
注：① exp(ijx),j?0,1,?,N?1,不构成TN?1 的一组基
② 如果P(x)??cj?0N?1jexp(ijx)中的系数由（5）式确定，则P(x)既是如本节所
述的三角插值多项式，又是如上节所述的离散内积意义下的最佳平方逼近多项式。
2 快速傅立叶变换
kN以下设 N?2，k 是正整数，令??exp(?i2?/N)，则??1 。记
1al?fl
N（5）式就简化为
cj??al?jl,l?0N?1j?0,1,?,N?1, （5’）
或简记成
?c0??a0??c??a?1???1??c2??FN?a2?, ?????????????cN?1???aN?1??jl其中FN 是N×N矩阵，它的第j行，第l列元素为 ?，j,l=0,1,…,N-1.
11
现在分奇数j和偶数j来合并cj中的同类项。 对于偶数j?2j1,
1N?12l?01N?12l?0c2j1??al?l?0N?12j1l??a(?l1N?12l?02j1l)??a1N?l(?)2N)2j1(l?12,
但(?)2j1(1N)2?(?N)j1?1 ，所以上式最后一项是
?a1N?l2(?2)j1l,
于是
1j?0,1,...,N?1. (7) l12l?02.,cN2?和（5）比较，由于??exp(?i2?/1就知道这组偶数编号的cj，即c0,c2,2N), ，
c2j1?1N?12?(a?a1N?l2)(?2)j1l,正好是(a0?a1N),(a1?a1N?1),...,(a1N?1?aN?1) 这
222?c0??c??2??c4??F1N??2?????cN?2??对于奇数j?2j1?1,，
N?1k?01N个数据的离散傅立叶变换： 2?a0?a1?N2??a?a1N?1??12??, a?a1?2N?2?2??????a1N?1?aN?1??2?c2j1?1??ak?2(j1?1)k??ak?k?2j1kl?0N?1?1N?12l?0
ll?(a?ll?0?a1N?l?21N?l2)(?2)j1l?所
以
奇
数
编
号
1N?12?{(a?a的
1N?l2)?l}(?2)j1l,即
?1cj，
Nc1,c3,N?.c.也.正,好是
(a0?a1N),(a1?a1N?1)?,...,(a1N?1?aN?1)?2 这
2221N个数据的离散傅立叶变换： 2 12
?(a0?a1N)?0?2?c1???1?c??(a1?a1N?1)??23?????c5??F1?(a2?a1N?2)?2?.
2N???2???????1???N?1?2?cN?1?(a1N?1?aN?1)????2?1可见为了完成N个数据的离散傅立叶变换，只要完成两个N 个数据的离散傅立叶变
2换即可。当然为了给两个离散傅立叶变换提供数据，还要有些运算量。现在我们来分析一下，设N?2 ，假定通过这种逐次分奇偶的算法需要 Pk个复数乘法和Ak 个复数加法，又从N个数据的离散傅立叶变换转换成两个备数据还要N?2个加法和
kk1N个数据的离散傅立叶变换时，准21N?2k?1 个乘法，所以 2Pk?2Pk?1?2k?1,P0?0Ak?2Ak?1?2,kA0?0
由此推出
Pk?k?2k?1?
1Nlog2N,2Ak?k?2k?Nlog2N.
以 N?2 为例比较一下原来的算法和这种分奇偶的快速算法的运算量见下表： 算法 原算法 分奇偶的快速算法 运算量 加法次数 乘法次数 10N(N?1)?106 N(log2N)?104 N2?106 l11N(log2N)?*104 22另外在作快速傅立叶变换时，要用到?,l?0,1,...,1N?1. 但 2?l?exp(?i2?l/N)?cos(2?l/N)?isin(2?l/N),
简记
?l,sin(2?l/N)?s?l, cos(2?l/N)?c?l和s?l时，不必都用标准子程序。可以只用标准子程序求出 求c?1?cos(2?/N),s?l?sin(2?l/N), c其余则利用三角公式
cos(l?1)x?cosxcos(lx)?sinxsin(lx),sin(l?1)x?cosxsin(lx)?sinxcos(lx),
13
?l?is?l 的公式如下 可以节省机时。总之算??cl?0?1,s?0?0,?c?c??cos(2?/N),s?1?sin(2?/N),??1 （8） ?l?1?c?1c?l?s?1s?l,s?0?c?1s?l?s?1c?l,?c??l?1,2,...,1N?2.??2
14
第1章 Fourier 变换
§1. Fourier变换（FT）
从???,??上的Fourier级数：
a0?f(x)???(akcoskx?bksinkx) （1）
2k?1如果f(x)?C2l?,l??
?a0?kk则f(x)???(akcosx?bksinx) （2）
2k?1ll若l?1形如（2）的FS可以在更大区间上表示任意函数，从另一个角度看
?kkcosx,sin?ll??x?在?上有更丰富的频谱，当l??时，由数学分析知FS?Fourier?积分，类似于复的FS，把Fourier积分放在复数域中就得到了Fourier变换FT。
Fourier变换的定义
设f(x)?L1(?)?L2(?)
FT(f)??????f(t)e?i?tdt
?(?) 称为f(x)的Fourier变换，FT(f)也记作f?)?f(t)?1反演公式：FT(f2??1??????(?)ei?td? f?相当于频率参数，f?(?)认为是频域上的函数，在f(t)中，如果把变量t看成时间参
数，成为时域上的函数。
与FT的系数同样
?(?)——连续频谱 f?(?)——连续振幅谱 f 15