当前位置：文档之家 › 9快速付里叶变换FFT-DIT(4)PPT课件

9快速付里叶变换FFT-DIT(4)PPT课件

  • 格式：pptx
  • 大小：1.34 MB
  • 文档页数：51

下载文档原格式

  / 51

合集下载

《快速傅里叶变换》课件

《快速傅里叶变换》课件
FFT算法的出现极大地推动了数字信号 处理技术的发展和应用。
FFT的历史背景
01
1960年代，Cooley和Tukey提 出了基于“分治”思想的FFT 算法，为快速傅里叶变换的实 用化奠定了基础。
02
随后，出现了多种FFT算法的 变种和优化，如Radix-2、 Radix-4等。
03
随着计算机技术的发展，FFT 算法在硬件实现上也得到了广 泛应用，如FPGA、GPU等。
《快速傅里叶变换》ppt课件
contents
目录
• FFT简介 • FFT基本原理 • FFT实现 • FFT的应用 • FFT的优化与改进 • FFT的挑战与未来发展
01 FFT简介
FFT的定义
快速傅里叶变换（FFT）：一种高效计算离散傅里叶变换（DFT）及其逆变换的 算法。它将复杂度为$O(N^2)$的DFT计算降低到$O(Nlog N)$，大大提高了计 算效率。
详细描述
混合基数FFT算法结合了基数-2和基数-4算法的特点，利用两者在计算过程中的 互补性，减少了计算量，提高了计算效率。同时，该算法在处理大规模数据时 ，能够保持较高的精度。
分段FFT算法
总结词
分段FFT算法将输入数据分成若干段，对每一段进行快速傅里叶变换，以降低计算复杂度和提高计算效率。
详细描述
02 FFT基本原理
离散傅里叶变换（DFT）
定义
应用
DFT是时间域信号到频域的变换，通 过计算信号中各个频率成分的幅度和 相位，可以分析信号的频谱特性。
DFT在信号处理、图像处理、频谱分 析等领域有广泛应用。
计算量
DFT的计算量随着信号长度N的增加 而呈平方关系增长，因此对于长信号 ，计算量巨大。

《快速傅里叶变换》PPT课件

《快速傅里叶变换》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滤波器的乘法运算量

快速傅里叶变换解析课件PPT学习

快速傅里叶变换解析课件PPT学习

(2)两个N/2点的DFT运算量:复乘次数: N 2
2
复加次数: N ( N 1)
2
(3)N/2个蝶形运算的运算量:复乘次数: N
复加次数:
2 2
N
2
N
总共运算量:
复乘: 复加:
N2 N
N(N
1)/ 2 N 2
22
2
N(N
1) N
N2
2
2
*N点DFT的复乘为N2 ;复加N(N-1);与分解后相比可知,
X (k) X1(k) WNk X 2 (k) , k 0,1,
, N 1 2
（4-11）
X
k
N 2
X1
k
N 2
W
k
N 2
N
X 2
k
N 2
X1(k) WNk X 2 (k), k 0,1,, N 1 （4-12） 2
13
第13页/共57页
这样，就可将X(k)表达为前后两部分：
n0
n0
N 1
{Re[x(n)]Re[WNnk ] Im[x(n)]Im[WNnk ]
n0
j(Re[x(n)]Im[WNnk ] Im[x(n)]Re[WNnk ])}
（4-3）
由此可见，一次复数乘法需用四次实数乘法和二次实数加法； 一次复数加法需二次实数加法。 因而每运算一个X(k)需4N次实 数乘法和2N+2(N-1)=2(2N-1)次实数加法。 所以，整个DFT运算 总共需要4N2次实数乘法和2N(2N-1)次实数加法。
2
第2页/共57页
N 1
正变换： X (k ) x(n)WNnk
n0
反变换：
x(n)

数字信号处理快速傅立叶变换PPT课件

数字信号处理快速傅立叶变换PPT课件
第4章 快速傅立叶变换（FFT）
4.1 引
DFT是数字信号分析与处理中的一种重要变换。
但直接计算DFT的计算量与变换区间长度N的平方成正
比，当N较大时，计算量太大，所以在快速傅里叶变
换FFT(Fast Fourier Transform)出现以前，直接用
DFT算法进行谱分析和信号的实时处理是不切实际的。
i0
(4.2.11)
X X
2 2
(k) X5(k) WNk/2 X6 (k)
(k
N
/
4)
X5
(k)
Wk N/2
X
6
, (k )
k
0,1,N
/
4
1
第18页/共79页
第4章 快速傅立叶变换（FFT）
x1(0) x(0) x1(1) x(2) x1(2) x(4) x1(3) x(6)
X1(0)
1 N
N 1
X
(k
)W
nk N
,
k0
n 0,1,, N 1
两者的差别仅在指数的符号和因子1/N.
第2页/共79页
第4章 快速傅立叶变换（FFT）
一个X(k)的值的工作量,如X(1)
X(1) x(0)WN0 x(1)WN1 x(2)WN2 x(N 1)WNN1
计算一个X(k)的值： N次复数乘法运算 N-1 次复数加法运算.
N 2
X 1 (1)
点DFT X1(2)
X1(3)
x2(0) x(1) x2(1) x(3) x2(2) x(5) x2(3) x(7)
X 2 (0) WN0
N 2
X 2 (1)
W
1 N
点DFT X 2(2)

快速傅里叶变换PPT课件

快速傅里叶变换PPT课件

WNk
-
6
4.3 按时间抽取的基2-FFT算法
算法原理
DIT-FFT(Decimation-In-Time)
按时间抽取基-2FFT算法与直接计算 DFT运算量的比较
按时间抽取的FFT算法的特点
按时间抽取FFT算法的其它形式流程图
-
7
4.3.1 算法原理
设N＝2M，将x(n)按 n 的奇偶分为两组：
直接按DFT变换进行计算，当序列长度N很大时，计算
量非常大，所需时间会很长,实时处理难以实现。 1965年，图基和库利发表了《机器计算快速傅立叶级
数的一种算法》论文后，很快形成了快速计算DFT的计 算机算法FFT。（Fast Fourier Transform) FFT并不是一种与DFT不同的变换，而是DFT的一种快速 计算的算法。
2
28
观察原位运算规律
-
29
序列的逆序排列
序列的逆序排列
由于 x(n) 被反复地按奇、偶分组，所以流图输入端的 排列不再是顺序的，但仍有规律可循：
因为 N=2M ，对于任意 n（0≤n ≤N-1)，可以用M个 二进制码表示为：
n (D)E C (n M 1 n M 2 n 2 n 1 n 0)(B)IN 0
nM1,nM2,,n2,n1,n0 1
n 反复按奇、偶分解时，即按二进制码的“0” “1” 分解。
-
30
倒位序的树状图（N=8）
-
31
码位的倒位序(N=8)
自然顺序 n 二进制数 倒位序二进制数 倒位序顺序nˆ 数
0
000
000
0
1
001
100
4
2
010
010

精编制作FFT快速傅里叶变换(蝶形算法)详解PPT课件

精编制作FFT快速傅里叶变换(蝶形算法)详解PPT课件

因此可得后半部分X(k)
X (k
k=0，1， …，N/2－1
N N N kN 2 ) X 1 (k ) WN X 2 (k ) 2 2 2
k X1 (k ) WN X 2 (k )
k=0，1， …，N/2－1
13
蝶形运算
X (k ) X 1 (k ) WNk X 2 (k )
由按时间抽取法FFT的信号流图可知，当N=2L时，共有 L 级 蝶形运算；每级都由 N/2 个蝶形运算组成，而每个蝶形有 1 次复乘、 2 次复加，因此每级运算都需 N/2 次复乘和 N 次复加。
22
这样 L 级运算总共需要： 复数乘法：
N N L log 2 N 2 2
复数加法：N L N log2 N 直接DFT算法运算量 复数乘法： N2 复数加法： N(N－1) 直接计算DFT与FFT算法的计算量之比为M N2 2N M N log2 N log2 N 2
N 1
nk nk {[Re x(n) ReWN Im x(n) ImWN ]
nk nk j[Re x(n) ImWN Im x(n) ReWN ]}
5
一次复数乘法： 4次实数乘法 一个X(k) ：
＋ 2次实数加法
4N次实数乘法 ＋ 2N+2(N-1)= 2(2N-1)次实数加法
33
5.4 按频率抽取的基2-FFT算法

算法原理
先把输入按n的顺序分成前后两半 再把输出X(k)按k的奇偶分组 设序列长度为N=2L，L为整数 前半子序列x(n) 后半子序列 x(n
nk x ( n ) W N
N 1
rk k rk x ( r ) W W x ( r ) W 1 N N 2 N r 0 2 2

《数字信号处理教学课件》第四章 快速傅立叶变换


k
)
k 0,1,...... N 4 1
注意：通常我们会把
WNk
/
写成
2
W
2k N
。
N点DFT的第二次时域抽取分解图(N=8)
x(0)
x(4) x(2) x(6) x(1) x(5) x(3) x(7)
x(0) xD2(F2点)T
X3(0) X3(1)
4点
x2(4点) xD(F6)T
x2(1点) xD(F3)T
分解后的运算量：
一个N 点DFT 一个N / 2点DFT 两个N / 2点DFT
一个蝶形 N / 2个蝶形
总计
复数乘法 N2
(N / 2)2 N2/ 2
1 N/2 N2/2 + N/2 ≈ N2/2
运算量减少了近一半
复数加法 N (N–1) N / 2 (N / 2 –1) N (N / 2 –1)
x(1),x(3),x(5),x(7)为奇子序列 频域上：X(0)~X(3)，由X(k)给出
X(4)~X(7)，由X(k+N/2)给出
N=8点的直接DFT的计算量为： 复乘：N2次 = 64次 复加：N(N-1)次 = 8×7=56次
X (k )

X
1
(k
)

W
k N
X2(k)
k 0,, N / 2 1
N点 DFT
复乘：
N2
N/2点 DFT
N/2点 DFT
N/4点 DFT N/4点 DFT N/4点 DFT N/4点 DFT
…….

N
2


N
2
2 2
N2 2

快速傅里叶变换PPT课件


W
0 N
运算即可求出
所有8点X(k)的
W
1 N
值。
W
2 N
W
3 N
分解一次后所需的运算量＝2个N/2的DFT＋N/2蝶形
-
14
运算量比较
N点DFT的运算量
每次蝶形含一次复数
复数乘法次数： N2
乘和两次复数加
复数加法次数： N(N－1)
分解一次后所需的运算量＝2个N/2的DFT＋ N/2蝶形：
复数乘法次数： 2*(N/2)2+N/2=N2/2+N/2
-
3
4.2 直接计算DFT的问题及改进的途径
DFT的运算量 设复序列x(n) 长度为N点，其DFT为
N1
X(k) x(n)WNnk n0
k=0，，…，N-1
（1）计算一个X(k) 值的运算量
复数乘法次数： N
复数加法次数： N－1
（2）计算全部N个X(k) 值的运算量
复数乘法次数： N2
复数加法次数： N(N－1)
-
5
4.2.2 减少运算工作量的途径
主要原理是利用系数
W
nk N
的以下特性对DFT进行分解：
（1）周期性 W N (nN)kW N n(kN)W N nk
（2）对称性
(WNnk )
W nk N
W k(N n) N
（3）可约性
Wmnk mN
WNnk
WNnk WNnk/m/m
另外，
WNN/2 1
W(kN/2) N
复数加法次数： 2*(N/2)(N/2－1)+2*N/2=N2/2
通过一次分解后，运算工作量减少了差不多一半。

数字信号处理教学课件-第四章 快速傅立叶变换

此外，还有4个蝶形结，每个蝶形结需要1次复乘，2次复加。 一共是：复乘4次，复加8次。
用分解的方法得到X (k)需要： 复乘：32+4 = 36次 复加：24+8 = 32次
2020/4/17
N点DFT的一次时域抽取分解图(N=8)
x(0)
X1(0)
x(2)
4点 X1(1)
x(4)
DFT X1(2)
2020/4/17
第二节 改善DFT运算效率的基本途径
1、利用DFT运算的系数
W
kn N
的固有对称性和周期
性，改善DFT的运算效率。
1）对称性
2）周期性
3）可约性
2020/4/17
WNnk的特性
WNnk
j2nk
e N
对 称 性 ( W N n k ) * W N n k W N ( N n ) k W N n ( N k )
2020/4/17
以DFT为例：
N 1
X (k ) D[x F (n ) T ] x (n )W N nk0 k N 1
n 0
计算机运算时（编程实现）：
k 0 X ( 0 ) x ( 0 ) W N 0 0 x ( 1 ) W N 1 0 x ( N 1 ) W N ( N 1 ) 0
X(4)~X(7)，由X(k+N/2)给出
N=8点的直接DFT的计算量为： 复乘：N2次 = 64次 复加：N(N-1)次 = 8×7=56次
X(k)X1(k)W N kX2(k)
k0,,N/21
X(kN/2)X1(k)W N kX2(k)
得到X1(k)和X2(k)需要： 复乘：(N/2)2+ (N/2)2次 = 32次 复加：N/2(N/2-1)+N/2(N/2-1) =12+12 =24次

快速傅里叶变换

n 0 N 1
r 0,1,
, N 2 1

N / 2 1

r 0
x(2r )WN
2 rk

N / 2 1

r 0
x(2r 1)WN
(2 r 1) k

N / 2 1

r 0
rk k x(2r )WN W /2 N
N / 2 1

r 0
rk x(2r 1)WN /2
N 2 N N ( N 1） N 2 所以8点FFT求X (k )共需 36次复数乘法, 2 2 2 2 N N2 N ( 1) N 32次复数加法, 共计为68次。看出仅做一次 2 2 分解就可以节省约一半计算量。
(2)N/2(4点)-->N/4(2点)FFT
N/2点 DFT
X1(1)
X1(2)
X1(3) X2(0)
WN
0
X(0) X(1) X(2) X(3)
1 2
x2(r) x2(0)=x(1)
奇 数 序 列
x2(1)=x(3) x2(2)=x(5) x2(3)=x(7)
N/2点 DFT
X2(1)
X2(2)
WN
WN
X2(3)
3 WN
X(4) -1 X(5) -1 X(6) -1 X(7)
-1 X(4)~X(7)
如：X（0） X 1 (0) X 2 (0)W80 X（2） X 1 (2) X 2 (2)W82
X（ 1） X 1 (1) X 2 (1)W81
X（3） X 1 (3) X 2 (3)W83
同学们自已写
比较直接计算N=8点DFT 与分解2个4点DFT的
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

X (k) N
4
+ ( N )2 4
一直分下去，剩下两点的变换。
X (k) N
+
4
( N )2 4
=
N2 4
结论
• 按抽取方法分：时间抽取法(DIT);频率抽取法 (DIF)
• 按“基数”分：基-2FFT算法；基-4FFT算法； 混合基FFT算法；分裂基FFT算法
• 其它方法：线性调频Z变换(CZT法)
N 1
[Re x(n) j Im x(n)][ReWNnk j ImWNnk ] n0
展开：
N 1
X (k) {[Re x(n) ReWNnk Im x(n) ImWNnk ]} n0
N 1
{ j[Re x(n) ImWNnk Im x(n) ReWNnk ]} n0
步骤3：合并有些项
• 直接计算DFT算法存在的问题及改进途 径。
• 多种FFT算法(时间抽取算法DIT算法，频 率抽取算法DIF算法，线性调频Z变换即 CZT法)
• FFT的应用
1 直接计算DFT存在的问题及改 进途径
1.1 直接计算DFT计算量
1.2 改善DFT运算效率的基本途径
1.1 直接计算DFT计算量
问题提出： 设有限长序列x(n),非零值 长度为N，计算对x(n)进行一次DFT运 算，共需多大的运算工作量?
DFT的复杂度与点数N有关！
1.2 改善DFT运算效率的基本途径
两个途径：
1.合并法：合并DFT运算中的某些项。 2. 分解法：将长序列DFT利用对称性和周
期性，分解为短序列DFT。
WNkn 的对称性和周期性
对称性：
(WNkn )*
W nk N
周期性：
WNkn
W (n N
N
)k
WNn(N k )
计算一个X(k)值的运算量：
例k=1则
N 1
X (1) x(n)WNn n0
要进行N次复数乘法和(N-1)次复数加法
要完成整个DFT运次复数加法
复数乘法换算成实数运算量
• 一个复数乘法包括4个实数乘法和2个实数加 法。
(a+jb)(c+jd)=(ac-bd)+j(bc+ad)
2 基--2按时间抽取的FFT算法 Decimation-in-Time(DIT) (Coolkey-Tukey)
2.1 算法原理 2.2 算法步骤 2.3 蝶形运算 2.4 FFT算法中的一些概念 2.5 DIT FFT算法与直接计算DFT运算量
的比较 2.6 DIT FFT算法的特点
2.1 算法原理
• DFT计算量太大, 很难实时地处理问题, 因此引 出了快速傅里叶变换(FFT) .
• 特别说明：FFT并不是一种新的变换形式,它 只是DFT的一种快速算法.并且根据对序列分 解与选取方法的不同而产生了FFT的多种算法 .
• FFT在离散傅里叶反变换、线性卷积和线性相 关等方面也有重要应用。
0.2 主要内容
快速傅立叶变换 (FFT) Fast Fourier Transforming
快速傅立叶变换FFT
0 引言 1 直接计算DFT存在的问题及改进途径 2 基--2按时间抽取的FFT算法 3 基--2按频率抽取的FFT算法 4 离散反傅立叶变换的快速计算方法 5 线性卷积的FFT算法
0 引言
0.1 快速付里叶变换FFT
W n(Nk) N
WN(N n)k
W nk N
kN
WN 2
WNk
合并法
步骤1：分解成虚实部
• 合并DFT运算中的有些项
W k(N n) N
(WNkn )*
• 对虚实部而言
ReWNk ( N n) ReWNkn ImWNk ( N n) ImWNkn
步骤2：代入DFT中
N 1
X (k) x(n)WNnk n0
2次实数加法
4次实数乘法
计算DFT需要的实数运算量
N 1
X (k) {(Re[x(n)]Re[WNkn ] Im[x(n)]Im[WNkn ]) n0
j(Re[x(n) Im[WNkn ] Im[x(n)]Re[WNkn ])}
• 每运算一个X(k)的值，需要进行 4N次实数相乘和 2N+2(N-1)=2(2N-1)次实数相加. • 整个DFT运算量为：4N2次实数相乘和2N(2N-1)次实数
• 如果大点数N的DFT能分解为若干小点数 DFT的组合，则可减少运算工作量。
方法 把N点数据分成二半：
X (k) N
运算量：
分二半： 运算量：
X (k) N
X (k) N
2
2
( N )2 2
+ ( N )2 2
N2
N2 =2
再分二半：X (k) N
4
运算量： ( N )2 4
X (k) N
4
+ ( N )2 4
根据： 有：
ReWNk ( N n) ReWNkn ImWNk ( N n) ImWNkn
Re x(n) ReWNnk Re x(N n) ReWNk(N n) [Re x(n) Re x(N n)]ReWNnk
Im
x(n)
ImW
nk N
Im x(N
n) ImWNk(N n)
[Im x(n) Im x(N n)]ImWNnk
步骤4：结论
由此找出其它各项的类似归并方法：乘法次数 可以减少一半。 例：
Re x(1) ReW51 Re x(5 1)W5(51) [Re x(1) Re x(4)]ReW54 [Re x(1) Re x(4)]ReW51
将长序列DFT利用对称性和周期性分解 为短序列DFT
思路
• DFT的运算量与N2成正比
• 按时间抽取----将该序列按时间顺序的奇偶分解 为越来越短的子序列。
比较DFT与IDFT之间的运算量
N 1
x(n) DFT X (k) x(n)WNkn n0
k 0,1, N 1
X (k)
IDFT x(n)
1 N
N 1
X (k)WNkn
k 0
n 0,1, N 1
其中 WNkn ,WNkn 均为复数
所以DFT与IDFT二者计算量相同。
计算DFT复数运算量
相加.
直接计算DFT时，乘法次数与加法次数都和N2成比例。
1.2 改善DFT运算效率的基本途径
算法基础：W的两个性质。
1. W具有周期性 2. W具有对称性
经过周期性与对称性简化之后, 容易发现DFT运算中存在着不 必要的重复计算,避免这种重复, 是简化运算的关键.
N点DFT运算可以分解为两组N/2 点DFT运算，然后再取和。