【VIP专享】快速傅里叶变换FFT算法8

形运算构成。由于一个N点DFT运算量为N2次乘法和N(N-1)
次加法；而一个蝶形运算包括1次乘法和2次加法，所以
一次 分解后 的运算量
乘法
N
2
2
N2
2个
N 2
点DFT 2
加法
N 2
N 2
2
1 2＝ N 2
2
N
N 2
个蝶形运算加 乘法 法12 N2N2
＝N
乘法次数N2/2+N/2,
当k取奇数(k=2r+1,r=0,1,…,N/2-1)时
N / 21
X (2r 1)
n0
[x(n)
x(n
N 2
)]WNn ( 2 r 1)
N / 21
n0
[x(n)
x(n
N 2
)]WNn
W nr N /2
(4-129)
令
x1
n
xn
x n
N 2
x
2
n
xn
x n
N 2
W
n N
(4-130)
W kN / 2 N
(1)k
1, 1
k 偶数 k 奇数
将X(k)分解成偶数组与奇数组，当k取偶数
(k=2r,r=0,1,…,N/2-1)时
N / 21
X (2r)
n0
[x(n)
x(n
N 2
)]WN2rn
N / 21
n0
[x(n)
x(n
N 2
)]WN2r/n2
(4-128)
快速傅里叶变换(FFT)
W
2 N
x2(2 ) DFT
X(5 )X2(2),r=2

快速傅里叶算法快速傅里叶算法（Fast Fourier Transform，FFT）是一种十分高效的离散傅里叶变换（Discrete Fourier Transform，DFT）算法。

它的效率在各种场合中被证明为远好于传统的DFT算法，占用的计算时间也更少。

这种算法在数字信号处理、音频压缩、图像处理、数据压缩、地震勘探、分子建模、遥感等领域中都可以发挥重要的作用。

因此，了解和掌握FFT算法对于科学计算和数据分析是非常有意义的。

傅里叶分析的基本概念傅里叶分析是一种将一个周期或非周期信号分解为若干个基本频率的信号的方法。

在这个过程中，一个连续的时间信号被分成一系列所谓的正弦波或余弦波。

这种方法适用于信号的处理，让人们能够理解事物如何被组成，以便更好地观察和控制这些信号。

在数字信号处理中，一个离散时间信号的傅里叶变换（DFT）是周期为N的复数序列，其中每一个元素都是一个基本频率的振幅，这里的基本频率是可以在一定周期内重复的赫兹频率。

然而，传统的DFT算法的计算量却是N^2（二次方级别），这对于大型数字信号的处理过程会带来巨大的计算负担。

FFT的发明在1965年，Caltech的物理学家J. W. Cooley和John Tukey发明了一个绝妙的数字信号算法——快速傅里叶变换算法。

这种算法利用对称性和重复性来减小计算量，使得N个点进行DFT只需要O(NlogN)的计算量。

由于它的速度比传统DFT快了许多，这种算法被称为“快速傅里叶变换”，简称FFT。

FFT算法原理FFT算法基于一个经典的数学定理，即“将一个长度为N的序列进行N次简单DFT变换，可以得到一个长度为N 的DFT变换”。

这个定理告诉我们，DFT可以通过分别对长度为N的较短序列进行DFT来实现。

由此可以看出，FFT算法的基本原理就是把一个大的DFT变换分解成许多个小的DFT变换，再利用其对称性和重复性来减少计算量。

FFT算法流程和优化FFT算法的基本流程分为两个阶段：分解和合并。

N / 21
N 1

x(n)WNnk
x(n)WNnk
n0
nN /2

N / 21
x(n)WNnk
n0

N / 21
x(n
n0
N 2
(n
)WN
因为 N=2M ，对于任意 n（0≤n ≤N-1)，可以用M个 二进制码表示为：
n(DEC) (nM 1nM 2 n2 n1n0 ) (BIN)
nM 1, nM 2 ,, n2 , n1, n0

0 1
n 反复按奇、偶分解时，即按二进制码的“0” “1” 分解。
ppt课件
26
倒位序的树状图（N=8）
DFT运算量的比较 按时间抽取的FFT算法的特点 按时间抽取FFT算法的其它形式流程图
ppt课件

5.3.1 算法原理
设N＝2L，将x(n)按 n 的奇偶分为两组：
x(2r) x1(r) x(2r 1) x2 (r)
r =0，1，…，N 1
2
则
N 1
X (k) DFT[x(n)] x(n)WNnk
r 0
r 0
N
N
1
1
2
2

x1
(r
)W
rk N
WNk
x2
(r
)W
rk N
r 0
2
r 0
2
X 1 (k ) WNk X 2 (k )
式中，X1(k)和X2(k)分别是x1(n)和x2(n)的N/2的DFT。 另外，式中k的取值范围是：0，1， …，N/2－1 。
ppt课件
64 4049 192

则有
N 21
N 41
N 41
X1(k ) x1(r)WNrk2 x1(2l)WN2lk2 x1(2l 1)WN(22l1)k
r0
l 0
l0
N 41
N 41
x3(l)WNlk 4 WNk 2 x4 (l)WNlk 4
l0
l0
X 3(k ) WNk / 2 X 4 (k )
k=0,1,…,
N 1 4
16
第16页/共53页
且
X1
N 4
k
X 3 (k )
WNk/ 2 X 4 (k )
k=0,1,…,
由此可见，一个N/2点DFT可分解成两个N/4点DFT。
N 1 4
同理，也可对x2(n)进行同样的分解，求出X2(k)。
17
第17页/共53页
以8点为例第二次按奇偶分解
18
第18页/共53页
算法原理
对此例N=8，最后剩下的是4个N/4= 2点的DFT，2点DFT也可以由蝶形运 算来完成。以X3(k)为例。
N / 41
1
X3(k)
x3 (l)WNlk/ 4 x3 (l)WNlk/ 4 k=0, 1
l0
l0
即
X 3 (0) x3 (0) W20 x3 (1) x(0) W20 x(4) x(0) WN0 x(4)
L
由按时间抽取法FFT的信号流图可知，当N=2L时，共有 级
蝶形运算；每级都由
个N蝶/2形运算组成，而每个蝶形有
1 次复乘、 次2复加，因此每级运算都需 次复乘和 N/2
N 次复加。
21
第21页/共53页
这样 L级运算总共需要：
复数乘法：