《快速傅里叶变换(FFT)-第四章》
- 格式：pdf
- 大小：655.54 KB
- 文档页数：37
下载文档原格式
合集下载
快速傅里叶变换FFT
第4章 迅速傅里叶变换(FFT)
本章主要内容
▪ 引言 ▪ 基2FFT算法 ▪ 进一步降低运算量旳措施
4.1 引言
▪ DFT是信号分析与处理中旳一种主要变换。但直接计算DFT旳 计算量与变换区间长度N旳平方成正比，当N较大时，计算量 太大，直接用DFT算法进行谱分析和信号旳实时处理是不切 实际旳。
▪ 1965年发觉了DFT旳一种迅速算法，使DFT旳运算效率提升1－2 个数量级，为数字信号处理技术应用于多种信号旳实时处理 发明了条件，推动了数字处理技术旳发展。
r 0
x2 ( r )WN2 kr
X (k) x(n)WNkn x(n)WNkn
n
n
X(k) x(n)WNkn x(n)WNkn
n
n
X (k )
x(n)WNkn
x(n)WNkn
N / 21
N / 21
N / 21
N / 21
n
n
x(2r)WN2kr
x(2r 1)WNk(2r1) x(2r)WN2kr x(2r1)WNk(2r1)
4.2 基2FFT算法
2.旋转因子旳变化规律
N点DIT―FFT运算流图中，每个蝶形都要乘以旋转因子WpN，p 称为旋转因子旳指数。N＝8 ＝23 时各级旳旋转因子
第一级：L=1， 有1个旋转因子：WNp =WN/4J =W2LJ J=0 第二级：L=2，有2个旋转因子：WNp =WN/2J =W2LJ J=0,1 第三级：L=3，有4个旋转因子：WNp =WNJ =W2LJ J=0,1,2,3 对于N＝2M 旳一般情况，第L级共有2L-1个不同旳旋转因子：
▪ 1984年，提出了分裂基迅速算法，使运算效率进一步提升；
4.2 基2FFT算法
本章主要内容
▪ 引言 ▪ 基2FFT算法 ▪ 进一步降低运算量旳措施
4.1 引言
▪ DFT是信号分析与处理中旳一种主要变换。但直接计算DFT旳 计算量与变换区间长度N旳平方成正比，当N较大时，计算量 太大，直接用DFT算法进行谱分析和信号旳实时处理是不切 实际旳。
▪ 1965年发觉了DFT旳一种迅速算法，使DFT旳运算效率提升1－2 个数量级，为数字信号处理技术应用于多种信号旳实时处理 发明了条件，推动了数字处理技术旳发展。
r 0
x2 ( r )WN2 kr
X (k) x(n)WNkn x(n)WNkn
n
n
X(k) x(n)WNkn x(n)WNkn
n
n
X (k )
x(n)WNkn
x(n)WNkn
N / 21
N / 21
N / 21
N / 21
n
n
x(2r)WN2kr
x(2r 1)WNk(2r1) x(2r)WN2kr x(2r1)WNk(2r1)
4.2 基2FFT算法
2.旋转因子旳变化规律
N点DIT―FFT运算流图中，每个蝶形都要乘以旋转因子WpN，p 称为旋转因子旳指数。N＝8 ＝23 时各级旳旋转因子
第一级：L=1， 有1个旋转因子：WNp =WN/4J =W2LJ J=0 第二级：L=2，有2个旋转因子：WNp =WN/2J =W2LJ J=0,1 第三级：L=3，有4个旋转因子：WNp =WNJ =W2LJ J=0,1,2,3 对于N＝2M 旳一般情况，第L级共有2L-1个不同旳旋转因子：
▪ 1984年，提出了分裂基迅速算法，使运算效率进一步提升；
4.2 基2FFT算法
第4章 快速傅里叶变换(FFT)1资料
设序列x(n)的N长度2M为, NM，为自且然满数 足
按n的奇偶把x(n)分解为两个N/2点的子序列
x1(r) x(2r),
r 0,1, N 1 2
x2(r) x(2r 1),
r 0,1, N 1 2
则x(n)的DFT为
X (k ) x(n)WNkn x(n)WNkn
n
n
N / 21
DFT的FFT运算量
N=8点的直接DFT的计算量为：N2次(64次）复数 相乘,N(N-1)次(8＊(8-1)=56次)复数相加.共计120 次。
（b)求 一个蝶形结需要的运算量
要运算一个蝶形结，需要一次乘 法 WNk X 2 (k) ， 两次加法。
X (k) X1(k) WNk X 2 (k) X (k N / 2) X1(k) WNk X 2 (k)
运算。
X
2
(k)及2
N 2
次(8次）加法
所以8点FFT求X (k)共需 N 2 N N (N 1） N 2 36次复数乘法,
22
2
2
N ( N 1) N N 2 32次复数加法,共计为68次。看出仅做一次
2
2
分解就可以节省约一半计算量。
(e)将N=8点分解成2个4点的DFT
的信号流图
x1(r)
i0
N / 41
x4(k)
x4 (l)WNkl/ 4 DFT [x4 (l)]
i0
同理，由X3(k)和X4(k)的周期性和Wm N/2的对称
性 Wk+N/4 N/2=-Wk N/2 最后得到：
X X
1 1
(k (k
) X3(k N / 4)
) WNk / 2 X 4 (k ) X 3(k ) WNk /
按n的奇偶把x(n)分解为两个N/2点的子序列
x1(r) x(2r),
r 0,1, N 1 2
x2(r) x(2r 1),
r 0,1, N 1 2
则x(n)的DFT为
X (k ) x(n)WNkn x(n)WNkn
n
n
N / 21
DFT的FFT运算量
N=8点的直接DFT的计算量为：N2次(64次）复数 相乘,N(N-1)次(8＊(8-1)=56次)复数相加.共计120 次。
（b)求 一个蝶形结需要的运算量
要运算一个蝶形结，需要一次乘 法 WNk X 2 (k) ， 两次加法。
X (k) X1(k) WNk X 2 (k) X (k N / 2) X1(k) WNk X 2 (k)
运算。
X
2
(k)及2
N 2
次(8次）加法
所以8点FFT求X (k)共需 N 2 N N (N 1） N 2 36次复数乘法,
22
2
2
N ( N 1) N N 2 32次复数加法,共计为68次。看出仅做一次
2
2
分解就可以节省约一半计算量。
(e)将N=8点分解成2个4点的DFT
的信号流图
x1(r)
i0
N / 41
x4(k)
x4 (l)WNkl/ 4 DFT [x4 (l)]
i0
同理，由X3(k)和X4(k)的周期性和Wm N/2的对称
性 Wk+N/4 N/2=-Wk N/2 最后得到：
X X
1 1
(k (k
) X3(k N / 4)
) WNk / 2 X 4 (k ) X 3(k ) WNk /
《快速傅里叶变换》PPT课件
然后计算圆周卷积
此时y(n)能代表线性卷积结果。
用FFT计算y(n)步骤如下： （1）求
，N点
（2）求
，N点
（3）计算
；
（4）求
，N点
工作量分析 FFT计算工作量
（4.105）
用线性相位滤波器来比较直接计算线性卷积和FFT法 计算线性卷积时比值
（4.106）
运算量分析：
（1）x(n)与h(n)点数差不多，设M＝L，
2
X1 k
x1
r
W rk N2
x
2r
W rk N2
r0
r0
（4.6）
N 1
N 1
2
2
X2 k
x2
r
W rk N2
x
2r
1
W rk N2
（4.7）
r 0
r0
应用系数的周期性
可得
N 1
X1
N 2
k
2 r 0
x1
r
W x r
N 2
k
N2
N 1 2
1
r0
比较可知，只要把DFT运算中的每一个系数
变成
，最后再乘常数1/N，则以上所有
按时间抽选或按频率抽选的FFT都可以拿来运算
IDFT。
不改FFT的程序计算IFFT方法： 对4.29式取共轭
因而
4.6 N为复合数的FFT算法 －－混合基算法
当N不满足
时，可有以下几种办法
（1）将x(n)补一些零值点的办法
y(n)也是有限长序列，其点数为L＋M－1。 2. 线性卷积运算量 乘法次数
线性相位滤波器满足条件
运算结构如图5.26,5.27所示 线性相位FIR滤波器的乘法运算量
此时y(n)能代表线性卷积结果。
用FFT计算y(n)步骤如下： （1）求
，N点
（2）求
，N点
（3）计算
；
（4）求
，N点
工作量分析 FFT计算工作量
（4.105）
用线性相位滤波器来比较直接计算线性卷积和FFT法 计算线性卷积时比值
（4.106）
运算量分析：
（1）x(n)与h(n)点数差不多，设M＝L，
2
X1 k
x1
r
W rk N2
x
2r
W rk N2
r0
r0
（4.6）
N 1
N 1
2
2
X2 k
x2
r
W rk N2
x
2r
1
W rk N2
（4.7）
r 0
r0
应用系数的周期性
可得
N 1
X1
N 2
k
2 r 0
x1
r
W x r
N 2
k
N2
N 1 2
1
r0
比较可知，只要把DFT运算中的每一个系数
变成
，最后再乘常数1/N，则以上所有
按时间抽选或按频率抽选的FFT都可以拿来运算
IDFT。
不改FFT的程序计算IFFT方法： 对4.29式取共轭
因而
4.6 N为复合数的FFT算法 －－混合基算法
当N不满足
时，可有以下几种办法
（1）将x(n)补一些零值点的办法
y(n)也是有限长序列，其点数为L＋M－1。 2. 线性卷积运算量 乘法次数
线性相位滤波器满足条件
运算结构如图5.26,5.27所示 线性相位FIR滤波器的乘法运算量
数字信号处理 第4章 快速傅里叶变换(FFT)-资料
x[0]
x[2]
W20
x[1]
x[3] W20
X1[0]
2点DFT X1[1] 1 X2[0]
2点DFT X2[1] 1
W40
1
W41
1
X [0] X [1] X [2] X [3]
4点基2时间抽取FFT算法流图
x[0]
x[2]
W40
x[1]
x[3]
W40
X1[0]
X1[1] 1
X2[0]
W40 1
W80 W80
2点DFT XX111[11[]1]
1 X4X1点21[20[]D0W] FW80T40
2点DFT XX121[21[]1W] W82411
1
1
xx[[11]]
XX212[10[]0]
xx[[35]] xx[[53]] xx[[77]]
W80 W80
2点DFT XX212[11[]1]
X2[1]
W41
1
1
X[0] X[1] X[2] X[3]
X[8mX点[m4基]]2X时X11[[间mm]]抽WW取88mmFXXF22[[Tmm算]],, 法mm流 00图,,11,,22,,33
x[0]
X1[0]
X [0]
x[2]
X1[1]
X [1]
x[4]
4点DFT
X1[2]
X [2]
x[6]
N=2
x[k]={x[0], x[1]}
X[0] x[0] W20 x[1] X [1] x[0] W21x[1] x[0] W20 x[1]
x[0]
X [0]
x[1] W20
-1
X [1]
课后习题及答案第4章快速傅里叶变换习题答案.pdf
和共轭反对称分量， 即
F(k)=X(k)+jY(k)=Fep(k)+Fop(k) 计算一次 N 点 IFFT 得到
f(n)=IFFT［F(k)］=Re［f(n)］+j Im［f(n)］ 由 DFT 的共轭对称性可知
Re［f(n)］=IDFT［Fep(k)］=IDFT［X(k)］=x(n) j Im［f(n)］=IDFT［Fop(k)］=IDFT［jY(k)］=jy(n)
X (k + N ) = X1(k) −W2kN X 2 (k)
k = 0,1,L, N −1
由上式可解出
X1(k)
=
1 2
[
X
(k)
+
X
(k
+
N )]
X
2
(k)
=
1 2
[X
(k)
+
X
(k
+
N
)]W2−Nk
k = 0,1, 2,L, N −1
由以上分析可得出运算过程如下：
（1）由 X(k)计算出 X1(k)和 X2(k):
Xk=conj(Xk)；
%对 Xk 取复共轭
xn=conj(fft(Xk， N))/N； %按照所给算法公式计算 IFFT
分别对单位脉冲序列、 长度为 8 的矩形序列和三角序列进行 FFT， 并调
用函数 ifft46 计算 IFFT 变换， 验证函数 ifft46 的程序 ex406.m 如下：
%程序 ex406.m
Tc = 2TF +1024 次复数乘计算时间 = 2 × 0.1536×10−3 +10×10−9 ×1024
= 0.317 44 ms 可实时处理的信号最高频率 fmax 为
第4章：快速傅里叶变换
2次复数乘，1组
令：X 0 (0) x(0) X 0 (1) x(2) X 0 (2) x(1) X 0 (3) x (3)
X 0 (0) DFT {x(0)} x(0); X 0 (1) DFT {x(2)} x(2); X 0 (2) DFT {x(1)} x(1); X 0 (3) DFT {x(3)} x(3);
X 1 (0) X 1 (1) X 1 (2) X 1 (3)
W40
W41
W40
W41
-1
-1
X 2 (0) X 1 (0) W40 X 1 (2) X 2 (1) X 1 (1) W41 X 1 (3) X 2 (2) X 1 (0) W40 X 1 (2) X 2 (3) X 1 (1) W41 X 1 (3)
X 1 (0) X 0 (0) W20 X 0 (1) x(0) x(2) X 1 (1) X 0 (0) W20 X 0 (1) x(0) x(2) X 1 (2) X 0 (2) W20 X 0 (3) x(1) x(3) X 1 (3) X 0 (2) W20 X 0 (3) x(1) x(3)
输入端输出端仅取少数点的Pruning算法 频谱细化的ZoomFFT技术——CZT算法 简单细化要付出巨大代价。快速算法
时间抽取（DIT）基2 FFT算法
1 X (0) 1 1 X (1) 1 1 W 1 4 X (2) 1 1 1 X (3) 1 1 W41 1 x(0) [ x(0) x(2)] [ x(1) x(3)] W41 x(2) [ x(0) x(2)] [ x(1) x(3)]W41 1 x(1) [ x(0) x(2)] [ x(1) x(3)] 1 1 W4 x(3) [ x(0) x(2)] [ x(1) x(3)]W4
第四章 快速傅里叶变换(FFT)_肖太龙
分解为两个N/2点的子序列
X (k )
n 奇数 N /2 1
kn x(n)WN
n 偶数 N /2 1
kn x(n)WN
r 0
2 kr x(2r )WN
r 0
k (2 r 1) x(2r 1)WN
N /2 1
r 0
k x1 (r ) WN
N /2 1
• 首先我们根据奈奎斯特定律得到：Fs 2 fc
fc
，
为连续信号的截至（最高）频率（因为它可能有很多频率
成分）。现在问题就是取样点N的选取？现在我们从序列的
FT说起！
• FT完成的任务就是对时域连续信号抽样之后通过序列的傅
里叶变换得到的频谱关系，我们知道这个谱是连续的。此
时的谱是一个周期谱，那么周期是多少呢？是不是与时域 采样频率有关系呢？答案是肯定的，此时的周期就是 Fs
WN
WN
3
2
W
2 N
8点DIT-FFT运算流图
从上面的蝶形算法，当 N 2M
时，其运算应该有
M级蝶形，每一级都由N/2个蝶形运算构成。因此每一级运算 都需要N/2次复数乘法和N次复数加法，所以M级蝶形运算的乘 法次数为： 加法次数：
N N N CM = M log 2 2 2
CA N M N log
N 2 N N ( N 1) N2 2( ) 2 2 2 2 N 1
复数加法次数为
N N N2 N ( 1) 2 2 2 2
类似地，我们将 x1 (r )
x 序列 3 (l )和x4 (l )
按奇偶分解成两个N/4点子
x3 ( l ) x1 (2l ) N ，其表达式分别如下： , l 0,1, , 1 x4 (l ) x1 (2l 1) 4
第4章 快速傅里叶变换(FFT)
r 0 N / 2 1
由于 所以
2 k r W e N
2 j 2 k r N
e
2 j k r N 2
r 0 N / 2 1 k N 2 r 0
k r W N /2
k r k X ( k ) x ( r ) W Wx ( r ) W X ( k ) W X ( k ) N 1 / 2 1 N 2 r 0 k r N / 2
则x(n)的DFT为
k n k n X ( k ) xn () W xn ( ) W N N n 偶 数 n 奇 数
2 k r kr ( 2 1 ) x ( 2 r ) W x ( 21 r ) W N N
N / 2 1
N / 2 1
2 k r 2 k r x ( r ) WW x ( r ) W N 1 N r 0
二.旋转因子W
m N
的周期性和对称性
1.周期性表现为
m l N W e N 2 j ( m l N ) N
e
2 j m N
m W N
(4.2.2)
2.对称性表现为
m N m N m m W W [ W ] W 或者 N N N N N m 2 N
4.FFT应用（见第三章）
习题
1. 3.
画8点基2 DIT-FFT和8点基2 DIF-FFT 算法运算流图
4.2 基2FFT算法
4.2.1 直接计算DFT的特点
及减少运算量的基本途径
一.DFT的运算次数
N 点 有 限 长 序 列 x () n
n k D F TX : ( k ) D F T [ xn () ] xn ( ) W N n 0 N 1
第4章快速傅里叶变换FFT
2kr N
N/2 1 r0
x (r)W
1
2kr N
W
k N
N/2 1 r 0
2 k r x ( r ) W 2 N
4.2.2 时域抽取法基2FFT基本原理
2 k r 2 k r 2 k r X () k x ( r ) WW x ( r ) W W e 1 N N N r 0
将N点DFT分解为两个N/2点DFT上式运算可用蝶形运算符号表示
A B C A＋BC A－BC
X1(k) X2(k)
WNk
X1(k)+ WNkX2(k)
X1(k)WNkX2(k)
图：蝶形运算符号 完成一个蝶形运算需要一次复数乘和两次复数加法运算
4.2.2 时域抽取法基2FFT基本原理
4.2 基2FFT算法
4.2.1 直接计算DFT的特点及减少运算量的基本途径
N 1 n 0
kn 有限长序列x(n)的N点DFT X ( k ) x ( n ) W 0 ， 1 ， ， N 1 N k
计算量
a jb c jd ac bd j ad cb
基2FFT算法
长度N满足N=2M（M为整数），若不满足将序列补零延长， 使其满足长度要求
本节主要介绍 1、FFT的基本思想
2、时域与频域抽取的基－2FFT算法
3、FFT程序实现
4.2.2 时域抽取法基2FFT基本原理
1、基2 DIT－FFT算法基本原理 设序列x(n)的长度为N，且满足N=2M，M为自然数。 按n的奇偶把x(n)分解为两个N/2点的子序列
4.2.2 时域抽取法基2FFT基本原理 FFT算法分类
按抽取方式 时域抽取法FFT(Decimation In Time FFT，简称DIT－FFT ) 频域抽取法FFT (Decimation In Frequency FFT，简称DIF－FFT) 按基数分
第4章 快速傅里叶变换(FFT)
第4章 快速傅里叶 变换(FFT)
本章主要内容
直接计算DFT的问题及改进的途径 按时间抽取的基2-FFT算法 按频率抽取的基2-FFT算法 快速傅里叶逆变换(IFFT)算法
2
4.1 引言
DFT在实际应用中很重要: 可以计算信号 的频谱、功率谱和线性卷积等。
直接按DFT变换进行计算，当序列长度N很
5.4 512 262 144 2 304 113.8
8.0 1024 1 048 576 5 120 204.8
12.8 2048 4 194 304 11 264 372.4
64 4049 192
21.4
24
4.2.5 按频率抽取的基2-FFT算法
算法原理
先把输入按n的顺序分成前后两半
再把输出X(k)按k的奇偶分组
所以 整个N点DFT运算共需要： 实数乘法次数： 4 N2
实数加法次数： N×2(2N-1)= 2N(2N-1)
6
DFT运算量的结论
N点DFT的复数乘法次数举例
N
N2
N
N2
2
4
64
4049
4
16
128
16384
8
64
256
65 536
16
256
512
262 144
32
1028
1024
1 048 576
N / 21
x(n)WNnk
n0
N / 21
x(n
n0
N 2
(n N )k
)WN 2
N / 21 x(n)
n0
x(n
N 2
本章主要内容
直接计算DFT的问题及改进的途径 按时间抽取的基2-FFT算法 按频率抽取的基2-FFT算法 快速傅里叶逆变换(IFFT)算法
2
4.1 引言
DFT在实际应用中很重要: 可以计算信号 的频谱、功率谱和线性卷积等。
直接按DFT变换进行计算，当序列长度N很
5.4 512 262 144 2 304 113.8
8.0 1024 1 048 576 5 120 204.8
12.8 2048 4 194 304 11 264 372.4
64 4049 192
21.4
24
4.2.5 按频率抽取的基2-FFT算法
算法原理
先把输入按n的顺序分成前后两半
再把输出X(k)按k的奇偶分组
所以 整个N点DFT运算共需要： 实数乘法次数： 4 N2
实数加法次数： N×2(2N-1)= 2N(2N-1)
6
DFT运算量的结论
N点DFT的复数乘法次数举例
N
N2
N
N2
2
4
64
4049
4
16
128
16384
8
64
256
65 536
16
256
512
262 144
32
1028
1024
1 048 576
N / 21
x(n)WNnk
n0
N / 21
x(n
n0
N 2
(n N )k
)WN 2
N / 21 x(n)
n0
x(n
N 2
数字信号处理第4章快速傅里叶变换FFT
x(n)WNkn
n0
x(n
N 2
)W k (nN / 2) N
N / 21
n0
[x(n)
W kN / 2 N课件
x
(n
N 2
)]WNkn
17
第4章 快速傅里叶变换(FFT)
W kN / 2 N
(1)k
1, 1
k 偶数 k 奇数
X(k)分解成偶数组与奇数组，当k取偶数
X1(k)
x1
(2l
)WN2
kl /2
x1(2l
1)WNk
(2l 1) /2
i0
i0
N / 41
N / 41
x3(l )WNkl/ 4 WNk / 2
x4 (l )WNkl/ 4
i0
i0
x3(k ) WNk /2 X 4 (k ), k 0,1, N / 2 1
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
)]WN2
rn /2
(4.2.14)
课件
18
第4章 快速傅里叶变换(FFT)
当k取奇数(k=2r+1,r=0,1,…,N/2-1)时
第4章 快速傅里叶变换(FFT)
第4章 快速傅里叶变换(FFT)
4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.4 分裂基FFT算法 4.5 离散哈特莱变换(DHT)
n0
x(n
N 2
)W k (nN / 2) N
N / 21
n0
[x(n)
W kN / 2 N课件
x
(n
N 2
)]WNkn
17
第4章 快速傅里叶变换(FFT)
W kN / 2 N
(1)k
1, 1
k 偶数 k 奇数
X(k)分解成偶数组与奇数组，当k取偶数
X1(k)
x1
(2l
)WN2
kl /2
x1(2l
1)WNk
(2l 1) /2
i0
i0
N / 41
N / 41
x3(l )WNkl/ 4 WNk / 2
x4 (l )WNkl/ 4
i0
i0
x3(k ) WNk /2 X 4 (k ), k 0,1, N / 2 1
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
)]WN2
rn /2
(4.2.14)
课件
18
第4章 快速傅里叶变换(FFT)
当k取奇数(k=2r+1,r=0,1,…,N/2-1)时
第4章 快速傅里叶变换(FFT)
第4章 快速傅里叶变换(FFT)
4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.4 分裂基FFT算法 4.5 离散哈特莱变换(DHT)
数字信号处理[第四章 快速傅里叶变换(FFT)]
![数字信号处理[第四章 快速傅里叶变换(FFT)]](https://img.taocdn.com/s1/m/abb6b7114431b90d6c85c7a9.png)
A(2)
-1 -1
W
0 N
A(2)
-1
A(3)
0 N
WN2
A(3)
-1
A(4) A(5)
W
0 N
A(4) A(5) A(6)
-1
-1
1 WN
A(4) = X (4) A(5) = X (5) A(6) = X (6)
A(7) = X (7)
A(6)
-1 -1
-1
2 WN
W
0 N
A(7)
0 WN
WN2
1
16
快速傅里叶变换(FFT) 快速傅里叶变换(FFT)
三,蝶形运算规律
p XL (J ) = XL1(J ) + XL1(J + B) WN p XL (J + B) = XL1(J ) X运算级数,=1,2, M
X L ( J )表示第L级运算后数组元素X ( J )的值 p = J 2M L;J = 0,1, , 2 L 1 1
J L12
J N 2 L M
M L
L = 1,WNp = WNJ/4 = W2JL,J = 0
L = 2,WNp = WNJ/2 = W2JL,J = 0,1
L
=W 2 N 1 L = 3,WNp = WNJ = W2J ,J = 0,1, 2,3 L级,W = W ,J = 0,1, 2, 2
p N J 2L L 1
x(0) = A(0)
x(4) = A(1)
A(0) A(1)
W W
0 N
A(0) A(1)
A(0) = X (0) A(1) = X (1) A(2) = X (2) A(3) = X (3)
第四章 快速傅里叶变换(FFT)
比较DFT mF(DFT) N2 2N mF(FFT) N 2log2N log2N
(8)、DIT-FFT算法的其他形式流图
输入倒位序输出自然序 输入自然序输出倒位序 输入输出均自然序 相同几何形状
输入倒位序输出自然序 输入自然序输出倒位序
时间抽取、 输入自然顺序、 输出倒位序的FFT流图
第四章 快速傅里叶变换
（FFT）
主要内容
DIT-FFT算法 DIF-FFT算法 IFFT算法 Chirp-FFT算法 线性卷积的FFT算法
学习目标 理解按时间抽选的基-2FFT算法的算法原理、计算
量和运算流图的特点
理解按频率抽选的基-2FFT算法的算法原理、计算 量和运算流图的特点
按时间抽取（Decimation In Time，DIT）
（1）算法原理
设序列x(n)点数为 N = 2L，L 为正整数。
N为2的整数幂的FFT算法称基-2FFT算法。
将序列x(n)按n的奇偶分成两组：
x x 1 2 ((r r)) x x ( (2 2 r r) 1 )， r 0 ， 1 ， 2 ， .N ./.2 1
k 0,1,..., N1 4
其中：
X 5 ( k ) D F T [ x 5 ( l ) ] D F T [ x 2 ( 2 l ) ]l 0 ,1 ,...,N /4 1 X 6 ( k ) D F T [ x 6 ( l ) ] D F T [ x 2 ( 2 l 1 ) ]
统 一 系 数 ： W N k /2 W N 2 k
k 0 ,1 ,...,N 1
按k的奇偶将X(k)分成两部分：
下面讨论 k2r,2r1的 X(k)：
X(2r)N /21x(n)x(nN 2)W N2rn
(8)、DIT-FFT算法的其他形式流图
输入倒位序输出自然序 输入自然序输出倒位序 输入输出均自然序 相同几何形状
输入倒位序输出自然序 输入自然序输出倒位序
时间抽取、 输入自然顺序、 输出倒位序的FFT流图
第四章 快速傅里叶变换
（FFT）
主要内容
DIT-FFT算法 DIF-FFT算法 IFFT算法 Chirp-FFT算法 线性卷积的FFT算法
学习目标 理解按时间抽选的基-2FFT算法的算法原理、计算
量和运算流图的特点
理解按频率抽选的基-2FFT算法的算法原理、计算 量和运算流图的特点
按时间抽取（Decimation In Time，DIT）
（1）算法原理
设序列x(n)点数为 N = 2L，L 为正整数。
N为2的整数幂的FFT算法称基-2FFT算法。
将序列x(n)按n的奇偶分成两组：
x x 1 2 ((r r)) x x ( (2 2 r r) 1 )， r 0 ， 1 ， 2 ， .N ./.2 1
k 0,1,..., N1 4
其中：
X 5 ( k ) D F T [ x 5 ( l ) ] D F T [ x 2 ( 2 l ) ]l 0 ,1 ,...,N /4 1 X 6 ( k ) D F T [ x 6 ( l ) ] D F T [ x 2 ( 2 l 1 ) ]
统 一 系 数 ： W N k /2 W N 2 k
k 0 ,1 ,...,N 1
按k的奇偶将X(k)分成两部分：
下面讨论 k2r,2r1的 X(k)：
X(2r)N /21x(n)x(nN 2)W N2rn
fx第4章 FFT
T
2.蝶形运算
N x(n)和x(n + )进行如下碟形运算： 2 N x(n)
x(n) + x(n + 2
)
N x(n + ) 2
n = 0,1 L, N −1 , 2
-1
W
n N
N n x(n) − x(n + 2 )WN
四、DIF法与DIT法的异同 DIF法与DIT法的异同 法与DIT
(k = 0,1,L, N − 1) 2 (k = N ,L, N − 1) 2
return
FFT的运算量为 3. N点的FFT FFT 复乘:
（N/2） log2 N N/ ）
复加:
L=N log2 N
三、DIF的FFT算法 DIF的FFT算法 1.算法原理(基2FFT) 1.算法原理( 算法原理
1.相同点 1. (1)进行原位运算； (1) (2)运算量相同,均为（N/2) Log2N次 (2) , 复乘,N Log2N次复加。 , 2.不同点 2. (1)DIT输入为倒位序,输出为自然顺 (1)DIT 序； DIF正好与此相反。但DIT DIT也有输入 DIF DIT 为自然顺序,输出为倒位序的情况。 （2）蝶形运算不同
按时间抽取(DIT) FFT算法 (DIT)的 二、按时间抽取(DIT)的FFT算法 1.算法原理( 1.算法原理(基2FFT) 算法原理
将
x(n)
按n的奇偶分为两组作DFT, N=2L ,不足时,可补些零。 DFT,设N=2 DFT,
2.蝶形运算 2.蝶形运算
k X (k) = X1(k) +WN X2 (k) 前一半 k X (k) = X1(k) −WN X2 (k) 后一半
2.蝶形运算
N x(n)和x(n + )进行如下碟形运算： 2 N x(n)
x(n) + x(n + 2
)
N x(n + ) 2
n = 0,1 L, N −1 , 2
-1
W
n N
N n x(n) − x(n + 2 )WN
四、DIF法与DIT法的异同 DIF法与DIT法的异同 法与DIT
(k = 0,1,L, N − 1) 2 (k = N ,L, N − 1) 2
return
FFT的运算量为 3. N点的FFT FFT 复乘:
（N/2） log2 N N/ ）
复加:
L=N log2 N
三、DIF的FFT算法 DIF的FFT算法 1.算法原理(基2FFT) 1.算法原理( 算法原理
1.相同点 1. (1)进行原位运算； (1) (2)运算量相同,均为（N/2) Log2N次 (2) , 复乘,N Log2N次复加。 , 2.不同点 2. (1)DIT输入为倒位序,输出为自然顺 (1)DIT 序； DIF正好与此相反。但DIT DIT也有输入 DIF DIT 为自然顺序,输出为倒位序的情况。 （2）蝶形运算不同
按时间抽取(DIT) FFT算法 (DIT)的 二、按时间抽取(DIT)的FFT算法 1.算法原理( 1.算法原理(基2FFT) 算法原理
将
x(n)
按n的奇偶分为两组作DFT, N=2L ,不足时,可补些零。 DFT,设N=2 DFT,
2.蝶形运算 2.蝶形运算
k X (k) = X1(k) +WN X2 (k) 前一半 k X (k) = X1(k) −WN X2 (k) 后一半
第四章快速傅里叶变换(FFT)
N2 法约为 log2 N 2 107 次，仅为直接计算DFT所需时间的10万 2 分之一。 即原需要3000小时，现在只需要2 分钟。
§4.4 按频率抽取（DIF）的FFT算法
（Decimation In Frequency) 一、算法原理
• 与DIT-FFT算法类似分解，但是抽取的是X(k)。 即分解X(k)成奇数与偶数序号的两个序列。 • 设： N = 2L，L 为整数。将X(k)按k的奇偶分组 前，先将输入x(n)按n的顺序分成前后两半：
FFT算法分类:
时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency
§4.3 按时间抽取（DIT）的FFT算法
（Decimation In Time）
1、算法原理
设序列点数 N = 2L，L 为整数。 若不满足，则补零 N为2的整数幂的FFT算法称基-2FFT算法。
1、 DFT与IDFT
N 点有限长序列x(n)
X (k ) x(n)W
n 0 N 1 kn N
1 x ( n) N
X (k )W
k 0
பைடு நூலகம்
N 1
kn N
2、DFT与IDFT运算特点
x(n)W
n 0
N 1
nk N
a jb c jd ac bd j ad cb
§4.1 引言
• DFT的快速算法——快速傅里叶变换（FFT）
• 1965年，Cooley-Turky 发表文章《机器计算傅 里叶级数的一种算法》，提出FFT算法，解决 了DFT运算量太大，在实际使用中受限制的问 题。
• FFT的应用。频谱分析、滤波器实现、实时信 号处理等。 • DSP芯片实现。TI公司的TMS 320c30，10MHz 时钟，基2-FFT1024点FFT时间15ms。
第4章 快速傅里叶变换(FFT)
DIF-FFT）。
第4章 快速傅里叶变换(FFT)
4.2.2 时域抽取法基2FFT基本原理
先设序列点数为N=2M，M为整数。如果不满足这个条 件，可以人为地加上若干零值点，使之达到这一要求。 这种N为2的整数幂的FFT称基-2 FFT。
(一)N/2点DFT
按n的奇偶把x(n)分解为两个N/2点的子序列
第4章 快速傅里叶变换(FFT)
(3)对X1(k)和X 2 (k)进行蝶形运算,前半部为
X(0)~X(3),后半部分为 X(4) ~ X(7) 整个过程如图4.2.2 所示:
x(0 )
X1(0 )
X(0 )
x(2 )
N/2点 X1(1 )
X(1 )
x(4 )
X1(2 )
X(2 )
DFT
x(6 )
X1(3 )
WNk
X2(k)
X(N 2
k)
X1(k) WNk
X 2 (k )
(后一半)
计算X(k)包含N/2个蝶形运算和两个N/2点DFT运算
计算工作量分析
第4章 快速傅里叶变换(FFT)
(1)1个N/2点的DFT运算量:
复乘次数: ( N )2 N 2 复加次数: N ( N 1)
24
22
(2)两个N/2点的DFT运算量:
例如,N=8时的DFT可分解为四个N/4的DFT, 具体步骤如下:
(1) 将原序列x(n)的“偶中偶”部分:
x3(l) x1(r) x(n) x3(0) x1(0) x(0) x3(1) x1(2) x(4)
第4章 快速傅里叶变换(FFT)
第4章 快速傅里叶变换(FFT)
4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施
第4章 快速傅里叶变换(FFT)
4.2.2 时域抽取法基2FFT基本原理
先设序列点数为N=2M，M为整数。如果不满足这个条 件，可以人为地加上若干零值点，使之达到这一要求。 这种N为2的整数幂的FFT称基-2 FFT。
(一)N/2点DFT
按n的奇偶把x(n)分解为两个N/2点的子序列
第4章 快速傅里叶变换(FFT)
(3)对X1(k)和X 2 (k)进行蝶形运算,前半部为
X(0)~X(3),后半部分为 X(4) ~ X(7) 整个过程如图4.2.2 所示:
x(0 )
X1(0 )
X(0 )
x(2 )
N/2点 X1(1 )
X(1 )
x(4 )
X1(2 )
X(2 )
DFT
x(6 )
X1(3 )
WNk
X2(k)
X(N 2
k)
X1(k) WNk
X 2 (k )
(后一半)
计算X(k)包含N/2个蝶形运算和两个N/2点DFT运算
计算工作量分析
第4章 快速傅里叶变换(FFT)
(1)1个N/2点的DFT运算量:
复乘次数: ( N )2 N 2 复加次数: N ( N 1)
24
22
(2)两个N/2点的DFT运算量:
例如,N=8时的DFT可分解为四个N/4的DFT, 具体步骤如下:
(1) 将原序列x(n)的“偶中偶”部分:
x3(l) x1(r) x(n) x3(0) x1(0) x(0) x3(1) x1(2) x(4)
第4章 快速傅里叶变换(FFT)
第4章 快速傅里叶变换(FFT)
4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1、直接DFT运算N点运算： 复数乘次数：N×N 复数加次数：N×(N-1) 2、 用DIT-FFT作N点运算： 复数乘次数：M×N/2=N/2×log2N； 复加次数： 2 ×N/2×M= N×log2N。 整个运算流图中 有 M 级蝶形，每 一级运算流图中 有 N/2 个 蝶 形 ， 每个蝶形需一次 复乘和两次复数 加运算。
第4章 快速傅里叶变换(FFT)
本章主要内容
引言
基2FFT算法 进一步减少运算量的措施
4.1 引言
DFT是信号分析与处理中的一种重要变换。但直接计算DFT的
计算量与变换区间长度N的平方成正比，当N较大时，计算量 太大，直接用 DFT 算法进行谱分析和信号的实时处理是不切 实际的。
1965年发现了DFT的一种快速算法，使DFT的运算效率提高1－2
WN/20
WN/21
X1(2) X1(3)
X (2) X (3)
WN
X5(0) N/4 点 X5(1) DFT
X6(0) N/4 点 X (1) 6 DFT WN/2 WN/21
0
X2(0) X2(1) X2(2) X2(3)
W N1
W N2 W N3
0
X (4) X (5) X (6) X (7)
0
X (1)
X (2) X (3) WN
0
W N2
x(1)
x(5)
X (4)
X (5)
WN
0
W N1 WN
0
x(3) x(7)
WN0
W N2
W N3
X (6)
WN2
L=1级
L=2 N=8点DIT-FFT运算流图
L=3
X (7)
4.2 基2FFT算法
4.2.3 DIT―FFT算法与直接计算DFT运算量的比较
x (2r )W x (2r 1)W x (2 r ) W x (2 r 1) W x (2 r ) W x (2 r 1) W X (k ) x ( n ) W x ( n ) W )W x (2 r 1)W x(2r
x ( r ) W x ( r )W x ( r ) W x ( r ) W W x ( r ) W x ( r ) x (2 r ) W x (2 1)W e W W x (r re ) W x ( r ) W
x ( r ) W x ( r )W X (k ) x ( r )W W x (r )W
k Nk 2 N 2
N=8点的DIT-2FFT(时域抽取图)一次分解图
4.2 基2FFT算法
(3)第二次分解： 将x1(r)按r取奇、偶可分解成2个长度为N/4的子序列 x3(l)= x1(2l)、 l=0,1,…，N/4-1； x4(l) = x1(2l+1)， 根据上面推导可得：X1 (k)= X3(k)+ WN/2kX4(k)， k=0,1,…,N/2-1 X1 (k)=X3(k)+WN/2kX4(k)， k=0,1,…,N/4-1； X1 (k+N/4)=X3(k)WN/2kX4(k)， k=0,1,…,N/4-1； 将x2(r)按r取奇、偶可分解成2个长N/4的子序列 x5(l)= x2(2l) ， l=0,1,…，N/4 x6(l) = x2(2l+1) ； 同理得 X2(k) = X5(k)+ WN/2kX6(k)， k=0,1,…,N/4-1 ；
W e
2 j 2 kr 2 kr N N /2
X (k ) W X 2 (k )
注意：这里的k的取值范围为0，1，…，N-1
4.2 基2FFT算法
由于X1(k)和X2(k)均以N/2为周期，且 W
k k N 2 N 2 k N 2 k k 1 N 2 1 N 2 k 1 N 2
k N N 2 k, X(k)又可表示为: WN
N / 2 1 N / 2 1 n n n n1 2 kr k (2 r 1) N / 2 1 N / 2 N / 2 1 N / 2 1 N / 2 1 N / 2 1 N N 2 kr k (2 r 1) 2 kr k (2 r 1) k (2 r 1) kn kn r 0 r 0 2 kr N N N N N N N N r1 0 Nr/ 20 1 N /2 n r 0 r 0 2 r 0 r 0 2 kr kn j kr N / 2 1 N / 2 1 N /2 1 /2 N /N 2 11 N1 N N 2 N k N / 2 2 kr j 2 2 kr / 2 1 N /1 2 1 2 kr 2 kr 2 kr k r 0 k 2 2N kr Nkr k ( 2 r 1) 2 r 0 2 1 N N 1 N N 1 N N r 0 N 2 N 2 N r 0 r 0 r 0 r 0 r 0 r 0 r 0 N / 2 1 N / 2 1 k 2 kr N / 2 1 N / 2 1 kr N k k 1 2 Nkr 1 N /2 2 N /2 1 N r 0 rN 0 r 0 r 0
x(1) x(3) x(5) x(7)
X1(0)
N/2 点DFT
X1(1) X1(2) X1(3) X2(0) X2(1) X2(2) X2(3)
X (0) X (1)
X (2) X (3)
W N0 W N1
N/2 点DFT
X (4) X (5)
X (6) X (7)
W N2 W N3
｛
N N 1 X ( k ) X ( k ) W X ( k ) k 0,1, 1 X (k ) X 1 (k ) W X (k ) k 0,1, 2 1 2 N NN k N X kk kk )) W X ) ) kk 0,1, 11 1 (( Nk 2 (k X(( 2 )) X X W X ( k 0,1, 1 N 2 22 2
N=8点DFT的二次时域抽取分解图
X1 (k)=X3(k)+WN/2kX4(k) X1 (k+N/4)=X3(k)WN/2kX4(k) X2(k) = X5(k)+ WN/2kX6(k) X2(k+N/4) = X5(k) WN/2kX6(k)
k=0,1,…,N/4-1 ；
4.2 基2FFT算法
1
｛
N 2 1 x1 ( r ) x(2r ), r 0,1, N x1 ( r ) x(2r ), r 0,1, 2N 1 x2 ( r ) x(2r 1), r 0,1, 2 1 N 2 1 x2 ( r ) x(2r 1), r 0,1, N x2 ( r ) x(2r 1), r 0,1, 2 1
考虑x(n)为复数序列 的一般情况，对某一
个k值，直接按上式
计算X(k)值需要N次 复数乘法、(N-1)次复
2、减少运算量的思路和方法
数加法。
思路： N 点 DFT 的复乘次数等于 N2 。把 N 点 DFT 分解为几个
较短的 DFT ，可使乘法次数大大减少。另外，旋转因子 WmN
具有周期性和对称性。
X5(1)
X6(0) X6(1) WN/4
0
X2(1)
WN/2
0
W N1 W N2 W N3
X (5)
X (6) X (7)
X2(2) X2(3)
WN/21
L=1级
L=2 N=8点DIT-FFT运算流图
L=3
4.2 基2FFT算法
x(0) X (0)
x(4)
x(2) x(6)
W N0
W N0 WN
再次分解，对N=8点，可分解三次。
x(0)
x(4) WN/40 X3(0) X3(1) X1(0)
X (0)
X (1)
X1(1)
WN/20
x(2) x(6)
x(1) WN/4
0
X4(0)
X4(1) X5(0)
X1(2) X1(3)
X2(0) WN
0
X (2)
X (3) X (4)
WN/2
1
x(5)
x(3) x(7) WN/40
频域抽取法FFT(简称DIF―FFT)。 1、时域抽取法FFT的算法思想：
将序列 x(n) 按 n 为奇、偶数分为 x1(n) 、 x2(n) 两组序列；用 2 个N/2点DFT来完成一个N点DFT的计算。 设序列x(n)的长度为N，且满足： N 2 M ,
M 为自然数
N (1) 按n的奇偶把 x(n) 分解为两个 N/2点的子序列 x ( r ) x(2r ), r 0,1, 1
个数量级，为数字信号处理技术应用于各种信号的实时处理 创造了条件，推动了数字处理技术的发展。 1984年，提出了分裂基快速算法，使运算效率进一步提高；
4.2 基2FFT算法
4.2.1 直接计算DFT的特点及减少运算量的基本途径 1.直接计算DFT 长度为N的有限长序列x(n)的DFT为：
kn X (k ) x(n )WN , k 0,1, , N 1 n 0 N 1
mm NN
WN
m
N 2
m WN
不断地把长序列的DFT分解成几个短序列的DFT，并利用旋转
因子的周期性和对称性来减少DFT的运算次数。
mm 22 W W W W NN NN
4.2 基2FFT算法
4.2.2 时域抽取法基2FFT基本原理 FFT算法基本上分为两大类：时域抽取法 FFT( 简称 DIT-FFT) 和
4.2 基2FFT算法
(2)用N/2点X1(k)和X2(k)表示序列x(n)的N点DFT X(k)
第4章 快速傅里叶变换(FFT)
本章主要内容
引言
基2FFT算法 进一步减少运算量的措施
4.1 引言
DFT是信号分析与处理中的一种重要变换。但直接计算DFT的
计算量与变换区间长度N的平方成正比，当N较大时，计算量 太大，直接用 DFT 算法进行谱分析和信号的实时处理是不切 实际的。
1965年发现了DFT的一种快速算法，使DFT的运算效率提高1－2
WN/20
WN/21
X1(2) X1(3)
X (2) X (3)
WN
X5(0) N/4 点 X5(1) DFT
X6(0) N/4 点 X (1) 6 DFT WN/2 WN/21
0
X2(0) X2(1) X2(2) X2(3)
W N1
W N2 W N3
0
X (4) X (5) X (6) X (7)
0
X (1)
X (2) X (3) WN
0
W N2
x(1)
x(5)
X (4)
X (5)
WN
0
W N1 WN
0
x(3) x(7)
WN0
W N2
W N3
X (6)
WN2
L=1级
L=2 N=8点DIT-FFT运算流图
L=3
X (7)
4.2 基2FFT算法
4.2.3 DIT―FFT算法与直接计算DFT运算量的比较
x (2r )W x (2r 1)W x (2 r ) W x (2 r 1) W x (2 r ) W x (2 r 1) W X (k ) x ( n ) W x ( n ) W )W x (2 r 1)W x(2r
x ( r ) W x ( r )W x ( r ) W x ( r ) W W x ( r ) W x ( r ) x (2 r ) W x (2 1)W e W W x (r re ) W x ( r ) W
x ( r ) W x ( r )W X (k ) x ( r )W W x (r )W
k Nk 2 N 2
N=8点的DIT-2FFT(时域抽取图)一次分解图
4.2 基2FFT算法
(3)第二次分解： 将x1(r)按r取奇、偶可分解成2个长度为N/4的子序列 x3(l)= x1(2l)、 l=0,1,…，N/4-1； x4(l) = x1(2l+1)， 根据上面推导可得：X1 (k)= X3(k)+ WN/2kX4(k)， k=0,1,…,N/2-1 X1 (k)=X3(k)+WN/2kX4(k)， k=0,1,…,N/4-1； X1 (k+N/4)=X3(k)WN/2kX4(k)， k=0,1,…,N/4-1； 将x2(r)按r取奇、偶可分解成2个长N/4的子序列 x5(l)= x2(2l) ， l=0,1,…，N/4 x6(l) = x2(2l+1) ； 同理得 X2(k) = X5(k)+ WN/2kX6(k)， k=0,1,…,N/4-1 ；
W e
2 j 2 kr 2 kr N N /2
X (k ) W X 2 (k )
注意：这里的k的取值范围为0，1，…，N-1
4.2 基2FFT算法
由于X1(k)和X2(k)均以N/2为周期，且 W
k k N 2 N 2 k N 2 k k 1 N 2 1 N 2 k 1 N 2
k N N 2 k, X(k)又可表示为: WN
N / 2 1 N / 2 1 n n n n1 2 kr k (2 r 1) N / 2 1 N / 2 N / 2 1 N / 2 1 N / 2 1 N / 2 1 N N 2 kr k (2 r 1) 2 kr k (2 r 1) k (2 r 1) kn kn r 0 r 0 2 kr N N N N N N N N r1 0 Nr/ 20 1 N /2 n r 0 r 0 2 r 0 r 0 2 kr kn j kr N / 2 1 N / 2 1 N /2 1 /2 N /N 2 11 N1 N N 2 N k N / 2 2 kr j 2 2 kr / 2 1 N /1 2 1 2 kr 2 kr 2 kr k r 0 k 2 2N kr Nkr k ( 2 r 1) 2 r 0 2 1 N N 1 N N 1 N N r 0 N 2 N 2 N r 0 r 0 r 0 r 0 r 0 r 0 r 0 N / 2 1 N / 2 1 k 2 kr N / 2 1 N / 2 1 kr N k k 1 2 Nkr 1 N /2 2 N /2 1 N r 0 rN 0 r 0 r 0
x(1) x(3) x(5) x(7)
X1(0)
N/2 点DFT
X1(1) X1(2) X1(3) X2(0) X2(1) X2(2) X2(3)
X (0) X (1)
X (2) X (3)
W N0 W N1
N/2 点DFT
X (4) X (5)
X (6) X (7)
W N2 W N3
｛
N N 1 X ( k ) X ( k ) W X ( k ) k 0,1, 1 X (k ) X 1 (k ) W X (k ) k 0,1, 2 1 2 N NN k N X kk kk )) W X ) ) kk 0,1, 11 1 (( Nk 2 (k X(( 2 )) X X W X ( k 0,1, 1 N 2 22 2
N=8点DFT的二次时域抽取分解图
X1 (k)=X3(k)+WN/2kX4(k) X1 (k+N/4)=X3(k)WN/2kX4(k) X2(k) = X5(k)+ WN/2kX6(k) X2(k+N/4) = X5(k) WN/2kX6(k)
k=0,1,…,N/4-1 ；
4.2 基2FFT算法
1
｛
N 2 1 x1 ( r ) x(2r ), r 0,1, N x1 ( r ) x(2r ), r 0,1, 2N 1 x2 ( r ) x(2r 1), r 0,1, 2 1 N 2 1 x2 ( r ) x(2r 1), r 0,1, N x2 ( r ) x(2r 1), r 0,1, 2 1
考虑x(n)为复数序列 的一般情况，对某一
个k值，直接按上式
计算X(k)值需要N次 复数乘法、(N-1)次复
2、减少运算量的思路和方法
数加法。
思路： N 点 DFT 的复乘次数等于 N2 。把 N 点 DFT 分解为几个
较短的 DFT ，可使乘法次数大大减少。另外，旋转因子 WmN
具有周期性和对称性。
X5(1)
X6(0) X6(1) WN/4
0
X2(1)
WN/2
0
W N1 W N2 W N3
X (5)
X (6) X (7)
X2(2) X2(3)
WN/21
L=1级
L=2 N=8点DIT-FFT运算流图
L=3
4.2 基2FFT算法
x(0) X (0)
x(4)
x(2) x(6)
W N0
W N0 WN
再次分解，对N=8点，可分解三次。
x(0)
x(4) WN/40 X3(0) X3(1) X1(0)
X (0)
X (1)
X1(1)
WN/20
x(2) x(6)
x(1) WN/4
0
X4(0)
X4(1) X5(0)
X1(2) X1(3)
X2(0) WN
0
X (2)
X (3) X (4)
WN/2
1
x(5)
x(3) x(7) WN/40
频域抽取法FFT(简称DIF―FFT)。 1、时域抽取法FFT的算法思想：
将序列 x(n) 按 n 为奇、偶数分为 x1(n) 、 x2(n) 两组序列；用 2 个N/2点DFT来完成一个N点DFT的计算。 设序列x(n)的长度为N，且满足： N 2 M ,
M 为自然数
N (1) 按n的奇偶把 x(n) 分解为两个 N/2点的子序列 x ( r ) x(2r ), r 0,1, 1
个数量级，为数字信号处理技术应用于各种信号的实时处理 创造了条件，推动了数字处理技术的发展。 1984年，提出了分裂基快速算法，使运算效率进一步提高；
4.2 基2FFT算法
4.2.1 直接计算DFT的特点及减少运算量的基本途径 1.直接计算DFT 长度为N的有限长序列x(n)的DFT为：
kn X (k ) x(n )WN , k 0,1, , N 1 n 0 N 1
mm NN
WN
m
N 2
m WN
不断地把长序列的DFT分解成几个短序列的DFT，并利用旋转
因子的周期性和对称性来减少DFT的运算次数。
mm 22 W W W W NN NN
4.2 基2FFT算法
4.2.2 时域抽取法基2FFT基本原理 FFT算法基本上分为两大类：时域抽取法 FFT( 简称 DIT-FFT) 和
4.2 基2FFT算法
(2)用N/2点X1(k)和X2(k)表示序列x(n)的N点DFT X(k)