当前位置：文档之家 › 第三章第三节FFT变换mm

第三章第三节FFT变换mm

  • 格式：ppt
  • 大小：2.70 MB
  • 文档页数：72

下载文档原格式

  / 72

合集下载

快速傅里叶变换解析课件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)

傅立叶变换(FFT)离散余弦变换(DCT)

傅立叶变换(FFT)离散余弦变换(DCT)

一个M×N大小的二维函数f(x,y)，其离散傅立叶变换对为
M1N1
f(x,y)F(u,v)expj[2π(ux/Mvy/N)]
u0v0
x0,1,M1,y0,1N1
F(u,v)
1
M1N1
f(x,y)exp[j2π(ux/Mvy/N)]
MNu0v0
u0,1,M1,v0,1,N1
在数字图像处理中，图像一般取样为方形矩阵，即 N×N，则其傅立叶变换及其逆变换为
f (x, y) g(x, y) φ
g(x,y) [f(x,y)]
线性系统
对于一般线性系统，往往是用时间作为参数来描述的，表 示为一维(t)系统。在图像处理中是用空间作为参数来描述 的，通常表示为二维(x,y)系统。输入函数f(x,y)表示原始 图像，输出函数g(x,y)表示经处理后的图像，线性系统可 看作是一种映射φ，它反映了各种线性的图像处理方法， 其输入和输出的关系表示为：
（1）具有有限个间断点 （2）具有有限个极值点 （3）绝对可积
则有下列式成立：
F (u) f ( x)e j 2 π ux dx (1)
f ( x) F (u)e j 2 π ux du (2)
x为时域变量，u 为频域变量
如果令w＝2πu，则有
F (w) f (x)e jwx dx
f
0
0
N
在频域中，原点平移到(u0，v0)时，其对应的f(x,y) 要乘上一个正的指数项 ej2π(u0xv0y)
fx ,y e x j2p u 0x v 0y F u u,v v
N
0
0
也就是说，当空域中f(x,y)产生移动时，在频域中只发 生相移，而傅立叶变换的幅值不变
|F (u ,v )e j2 π (u0 x v0 )y| |F (u ,v )|

fft的算法原理

fft的算法原理

fft的算法原理
傅里叶变换（Fast Fourier Transform，简称FFT）是一种通过离散傅里叶变换（DFT）快速计算信号频谱的算法。

FFT算法的原理基于分治算法，它将一个长度为N的时间序列分解成N个长度为1的时间序列，然后再进行多次合并计算得到最终结果。

具体而言，FFT算法的过程可以分为两个步骤：分解（Decomposition）和合并（Combination）。

在分解步骤中，将长度为N的时间序列分为两个长度为N/2的时间序列，这可以通过以下公式进行表示：
X(k) = X_even(k) + W_N^k * X_odd(k)
其中，X(k)表示频域中的第k个频率点，X_even(k)表示时间序列中偶数索引位置的样本的频谱，X_odd(k)表示时间序列中奇数索引位置的样本的频谱，W_N以及W_N^k是旋转因子。

接着，在合并步骤中，将两个长度为N/2的频谱再次合并为一个长度为N的频谱。

合并过程可以通过以下公式表示：
X(k) = X_even(k mod (N/2)) + W_N^k * X_odd(k mod (N/2))
其中，mod表示取模运算。

通过不断进行分解和合并的过程，最终可以得到整个时间序列的频谱。

FFT算法的关键点是快速计算旋转因子W_N^k。

这可以通过使用旋转因子的周期性特征，以及将其表示为复数的形式，使
用复数乘法和加法来高效计算。

这样，就避免了对每个频率点都重新计算旋转因子，从而提高了计算效率。

总的来说，FFT算法利用分治思想，通过将长序列分解为短序列再合并的方式，实现了高效的频谱计算。

它在信号处理、图像处理、通信等领域具有广泛应用。

第三章第三节FFT变换mm

第三章第三节FFT变换mm

XXXX2222((((0123))))W WWWNNNN2130
-1 X(4) -1 X(5) -1 X(6)
X(7)
(2) N/2(4点)-->N/4(2点
由于)FNF=2TL ,所以 N/2仍为偶数,可以进一
步把每个N/2点的序列再按其奇偶部分分 解为两个N/4的子序列。
X(0) N/4 X3(0) X(4) DFT X3(1)
计算一个X(k)(一个频率成分)值，运算量为 例k=1则
要进行: N次复数乘法 + (N-1)次复数加法 所以，要完成整个DFT运算，其计算量为：
N*N次复数相乘和N*(N-1)次复数加法
数字信号处理
3.一次复数乘法换算成实数运算量
一个复数乘法包括4个实数乘法和2个实数相 法。
(a+jb)(c+jd)=(ac-bd)+j(bc+ad)
第三章第三节FFT变换 mm
2020年4月23日星期四
数字信号处理
2.2 利用DFT进行连续信号的频谱分析
• 1、混叠 • 2、泄漏 • 3、栏栅效应 • 4、DFT的分辨率 • 5、周期信号的谱分析
数字信号处理
数字信号处理
3.3 快速傅里叶变换
• 有限长序列通过离散傅里叶变换 (DFT)将其频 域离散化成有限长序列。但其计算量太大(与N 的平方成正比），很难 实时地处理问题，因 此 引 出 了 快 速傅 里 叶 变 换(FFT) 。
例 8点FFT的算法
首先可以分解为两个N/2=4点的DFT.具体方法如下:
（1）N=8点分解成2个4点的
DFT的信号流图
x(0) x(2)
X1(0)
N/2点 X1(1)

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

《快速傅里叶变换FF》课件
《快速傅里叶变换ff 》ppt课件
contents
目录
• FFT简介 • FFT的基本原理 • FFT的应用 • FFT的实现 • FFT的性能优化 • FFT的局限性
CHAPTER 01
FFT简介
FFT的定义
快速傅里叶变换（FFT）：一种高效计算离散傅里叶变换（DFT）及其逆变换的 算法。它将复杂度为$O(N^2)$的DFT计算降低到$O(Nlog N)$，极大地提高了 计算效率。
通过选择适合特定数据集的基数，混 合基数FFT可以在不同的应用场景下 获得最佳性能。
混合基数FFT结合了基于2的幂次和基 于其他基数的算法，以获得更好的计 算效率和精度。
CHAPTER 06
FFT的局限性
浮点运算的开销
快速傅里叶变换（FFT）是一种高效的算法，用于计算离散傅里叶变换（DFT）和其逆变换。然而， 由于FFT涉及到大量的复数运算，因此其计算开销相对较大，尤其是对于大规模数据。
分段FFT
分段FFT是一种将大规模FFT分 解为多个小规模FFT的方法， 可以显著提高计算速度。
通过将输入数据分成多个段， 每个段可以独立进行FFT计算 ，从而并行处理多个段。
分段FFT适用于大规模数据集 ，可以有效地利用多核处理器 和分布式计算资源，提高计算 效率。
混合基数FFT
混合基数FFT是一种将不同基数算法 结合在一起的FFT方法，可以获得更 好的性能。
快速傅里叶变换（FFT）算法
定义
快速傅里叶变换（FFT）是一种高效的计算离散傅里叶变换（ DFT）和其逆变换的算法。它通过一系列数学运算将DFT的 计算量从N^2降低到了Nlog2N，大大提高了计算效率。
算法原理
FFT算法基于DFT的周期性和对称性，将一个N点的DFT分解 为多个较短序列的DFT，然后利用递归和分治的思想进行计 算，最终得到原始序列的频域表示。

fft算法的基本原理

fft算法的基本原理

fft算法的基本原理FFT算法的基本原理。

快速傅里叶变换（FFT）算法是一种高效的计算傅里叶变换的方法，它在信号处理、图像处理、数值计算等领域有着广泛的应用。

本文将介绍FFT算法的基本原理，以便读者对其有一个清晰的认识。

傅里叶变换是一种信号处理中常用的数学工具，它可以将一个信号从时域转换到频域，从而可以分析信号的频率成分。

传统的傅里叶变换算法需要O(n^2)的时间复杂度，而FFT算法可以将时间复杂度降低到O(nlogn)，这使得FFT算法成为了一种非常高效的计算傅里叶变换的方法。

FFT算法的基本原理是利用了傅里叶变换的对称性和周期性。

假设有一个长度为N的离散信号序列x(n)，其傅里叶变换可以表示为：X(k) = Σ[n=0 to N-1] x(n) exp(-j2πnk/N)。

其中，k为频率索引，n为时间索引，X(k)为频域信号。

FFT算法通过将信号分解为偶数索引和奇数索引的信号，然后利用分治法的思想进行递归计算，最终将信号的傅里叶变换计算量降低到O(nlogn)的时间复杂度。

具体来说，FFT算法可以分为以下几个步骤：1. 首先，将长度为N的信号序列x(n)分为偶数索引和奇数索引的两个子序列x_even(n)和x_odd(n)；2. 然后，分别对x_even(n)和x_odd(n)进行递归计算其傅里叶变换X_even(k)和X_odd(k)；3. 最后，利用X_even(k)和X_odd(k)的结果合并计算出整个信号序列x(n)的傅里叶变换X(k)。

通过以上步骤，FFT算法可以将原始信号的傅里叶变换计算量从O(n^2)降低到O(nlogn)，大大提高了计算效率。

同时，FFT算法还可以利用一些技巧和优化来further improve the computational efficiency, such as Cooley-Tukey算法 and Radix-2算法。

总的来说，FFT算法是一种非常高效的计算傅里叶变换的方法，它利用了傅里叶变换的对称性和周期性，通过分治法的思想将计算复杂度降低到O(nlogn)。

第三章第三节快速傅里叶变换(FFT)


另一种形式的流程图是将节点排列成输入 和输出两者都是 正序排列，但这类流程图不能进行同址计算，因而需要两列 长度为N的复数存储器。
例 8点FFT的算法
首先可以分解为两个N/2=4点的DFT.具体方法如下:
rk k rk X (k ) x(2r )WN /2 WN x(2r 1)WN /2 , r 0 r 0 3 3
x(1) x2 (0)、 x(5) x2 (2) 偶序列 同理：x2 (r ) : x(3) x2 (1)、 x(7) x2 (3) 奇序列
X 1 (k )
N 1 4 l 0
x1 ( r )W4rk
r 0
N 4
N 1 2
在导出FFT算法之前，首先来估计一下直接计算DFT所需的计算量。 DFT的定义
其中
将DFT定义式展开成方程组
将方程组写成矩阵形式
用向量表示
用复数表示：
从矩阵形式表示可以看出，由于计算一个X(k)值需要N次复乘法和 (N-1)次复数加法，因而计算N个X(k)值，共需N2次复乘法和N(N-1)次 复加法。每次复乘法包括4次实数乘法和2次实数加法，每次复加 法包括2次实数加法，因此计算N点的DFT共需要4N2次实数乘法和 (2N2+2N· (N-1))次实数加法。当N很大时，这是一个非常大的计算量。 FFT算法主要利用了WNk的两个性质： (1)对称性，即
第3章第三节 快速傅里叶变换 （FFT)
FFT算法分类：
1.按抽取方法分： 时间抽取法(DIT Decimation-In-Time); 频率抽取法(DIF Decimation-In-Frequency) 2.按“基数”分： 基-2FFT算法； 基-4FFT算法； 混合基FFT算法； 分裂基FFT算法 3.其它方法： 线性调频Z变换(Chrip-z法)

FFT快速傅里叶变换(蝶形算法)详解


X 3(1)x3(0)W 2 1x3(1)x(0)W21x(4)x(0)WN0x(4) 这说明，N=2M的DFT可全部由蝶形运算来完成。
20
以8点为例第三次按奇偶分解
N=8按时间抽取法FFT信号流图
21
5.3.2 按时间抽取基2-FFT算法与直接计算DFT运算量的比较
由按时间抽取法FFT的信号流图可知，当N=2L时，共有 L 级 蝶形运算；每级都由 N/2 个蝶形运算组成，而每个蝶形有
蝶形运算信 号流图符号
因此，只要求出2个N/2点的DFT，即X1(k)和X2(k)，再 经过蝶形运算就可求出全部X(k)的值，运算量大大减少。
14
以8点为例第一次按奇偶分解
以N=8为例，
分解为2个4点
的DFT，然后
做8/2=4次蝶形
运算即可求出
W
0 N
所有8点X(k)的
值。
W
1 N
W
2 N
W
3 N
23
FFT算法与直接DFT算法运算量的比较
N
N2
N
计算量
2 log 2 N 之比M
N
N2
N
计算量
2 log 2 N 之比M
2
4
1
4 16
4
8 64
12
16 256
32
32 1028 80
4.0 128
16 384
448 36.6
4.0 256 65 536 1 024 64.0
5.4 512 262 144 2 304 113.8
7直接计算dft与fft算法的计算量之比为m24fft算法与直接dft算法运算量的比较25533按时间抽取的fft算法的特点序列的逆序排列同址运算原位运算蝶形运算两节点间的距离的确定26序列的逆序排列由于xn被反复地按奇偶分组所以流图输入端的排列不再是顺序的但仍有规律可循

快速傅里叶变换(FFT) 原理 介绍

1点： 512
51点：384
76点：192
按照公式，可以计算出直流分量为：512/N=512/256=2；
50Hz信号的幅度为：384/(N/2)=384/(256/2)=3；75Hz信号的
幅度为192/(N/2)=192/(256/2)=1.5。可见，从频谱分析出来
的幅度是正确的。
2点： -2.6195E-14 - 1.4162E-13i
3点： -2.8586E-14 - 1.1898E-13i
50点：-6.2076E-13 - 2.1713E-12i
51点：332.55 - 192i
52点：-1.6707E-12 - 1.5241E-12i
75点：-2.2199E-13 -1.0076E-12i
做，但是却不知道FFT之后的结果是什意思、如何决定要使用
多少点来做FFT。
现在圈圈就根据实际经验来说说FFT结果的具体物理意义。
一个模拟信号，经过ADC采样之后，就变成了数字信号。采样
定理告诉我们，采样频率要大于信号频率的两倍，这些我就
不在此罗嗦了。
采样得到的数字信号，就可以做FFT变换了。N个采样点，
换算成角度就是180*1.5708/pi=90.0002。可见，相位也是对的。
根据FFT结果以及上面的分析计算，我们就可以写出信号的表达
式了，它就是我们开始提供的信号。
总结：假设采样频率为Fs，采样点数为N，做FFT之后，某
一点n（n从1开始）表示的频率为：Fn=(n-1)*Fs/N；该点的模值
close all; %先关闭所有图片
Adc=2; %直流分量幅度
A1=3; %频率F1信号的幅度

五种傅里叶变换方法

五种傅里叶变换方法标题：探究五种傅里叶变换方法摘要：傅里叶变换在信号处理、图像处理和通信等领域中发挥着重要的作用。

本文将深入探讨五种常见的傅里叶变换方法，包括离散傅里叶变换（DFT）、快速傅里叶变换（FFT）、连续傅里叶变换（CFT）、反射谱傅里叶变换（RFT）和多维傅里叶变换（MDFT）。

通过分析每种方法的原理、特点和应用领域，我们将能够更好地理解傅里叶变换的概念和实际应用。

第一节：离散傅里叶变换（DFT）1.1 原理和定义1.2 算法与实现1.3 应用场景和优缺点第二节：快速傅里叶变换（FFT）2.1 原理和特点2.2 快速傅里叶变换算法2.3 应用领域和性能分析第三节：连续傅里叶变换（CFT）3.1 连续傅里叶变换的数学定义3.2 傅里叶级数和傅里叶变换的关系3.3 应用场景和限制第四节：反射谱傅里叶变换（RFT）4.1 RFT的概念和目的4.2 数学定义和算法4.3 在信号处理中的应用案例第五节：多维傅里叶变换（MDFT）5.1 MDFT的概念和性质5.2 空间和频率域的转换5.3 在图像处理和通信中的应用总结和回顾性内容：本文深入探讨了五种傅里叶变换方法，从离散傅里叶变换（DFT）开始，通过介绍快速傅里叶变换（FFT）、连续傅里叶变换（CFT）、反射谱傅里叶变换（RFT）和多维傅里叶变换（MDFT），我们在深度和广度上对傅里叶变换有了更全面、深入的理解。

每种方法都有自己的原理、特点和应用领域，我们可以根据具体需求选择适合的方法。

傅里叶变换在信号处理、图像处理、通信和其他领域中起着关键作用，通过学习这些方法，我们可以更好地应用傅里叶变换来分析和处理实际问题。

个人观点和理解：傅里叶变换是一种重要的数学工具，能够将一个信号分解为一系列不同频率的正弦和余弦函数。

离散傅里叶变换（DFT）是傅里叶变换在数字信号处理中的离散形式，它通过将信号离散化来实现，适用于离散信号的频域分析。

快速傅里叶变换（FFT）是一种高效计算DFT的算法，它通过利用对称性和重叠子问题来减少计算量，广泛应用于信号处理和频谱分析中。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

数字信号处理
例子

设一序列x(n)的长度为L=9,应加零补长为 N=24=16 应补7个零值。
x(n)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
n
数字信号处理
2.算法步骤
设序列点数 N = 2M，M为整数。若不满足， 则补零
x(n)DFT为：
kn X (k ) x(n)WN n 0 N 1
2
总共运算量: 复乘: 复加:
N2 N N2 2 2 2 2 N N N( 1) N 2 2
*但是,N点DFT的复乘为N2 ;复加N(N-1);与 分解后相比可知,计算工作点差不多减少 一半。
例 8点FFT的算法
首先可以分解为两个N/2=4点的DFT.具体方法如下:
rk k rk X (k ) x(2r )WN / 2 WN x(2r 1)WN / 2 , r 0 r 0 3 3
N 1
kn N
1 kn X (k ) x(n) X (k )WN N k 0
其中x(n)为复数， N kn e W 2 j kn N
也为复数
所以DFT与IDFT二者计算量相同。
数字信号处理
2.以DFT为例复数运算量
计算一个X(k)(一个频率成分)值，运算量为 例k=1则
数字信号处理
直接计算DFT算法存在的问 题及改进途径
•问题提出： 设有限长序列x(n),非零值长度为N, 计算对x(n)进行一次DFT运算，共 需多大的运算工作量?
数字信号处理
1.比较DFT与IDFT的运算量
x(n) X (k ) x(n)W
DFT n 0N 1 IDFT Wk N数字信号处理
4.蝶形运算
k X (k ) X 1 (k ) WN X 2 (k )， 0,1,, N 1) (k 2
X 1 (k ) X 1 (k )
N k X (k ) X 1 (k ) WN X 2 (k )， 0,1, , N 1) (k 2 2 1 1 X (k ) X 1 (k ) WNk X 2 (k )
由于N=2 L ,所以 N/2仍为偶数,可以进一 步把每个N/2点的序列再按其奇偶部分分 解为两个N/4的子序列。
x(0) x1 (0)、 x(4) x1 (2) 偶序列 x1 (r ) : x(2) x1 (1)、 x(6) x1 (3) 奇序列
x(1) x2 (0)、 x(5) x2 (2) 偶序列 同理：x2 (r ) : x(3) x2 (1)、 x(7) x2 (3) 奇序列

2次实数加法

4次实数乘法
所以所有X(k)就要4N2次实数乘法运算,2N2＋2N(N1)＝ N(4N-2)次实数加法运算.当N很大时,运算量 将是惊人的, 这样,难以做到实时处理。
例子 数字信号处理 例1:当N=1024点时，直接计算DFT需要： N2=220=1048576次，即一百多万次的复乘运算 这对实时性很强的信号处理(如雷达信号处理)来 讲，它对计算速度有十分苛刻的要求-->迫切需 要改进DFT的计算方法，以减少总的运算次数。 例2：石油勘探，24道记录，每道波形记录长 度5秒，若每秒抽样500点/秒， 每道总抽样点数=500*5=2500点 24道总抽样点数=24*2500=6万点 DFT运算时间=N2=(60000)2=36*108次
数字信号处理
3.3.1 时域抽取法基2FFT基本原理 Decimation-in-Time(DIT)
1、时域抽取算法原理 设输入序列长度为N=2M(M为正整数， 将该序列按时间顺序的奇偶分解为越来 越短的子序列，称为基2按时间抽取的 FFT算法。也称为Coolkey-Tukey算法。 其中基数2----N=2M，M为整数.若不满 足这个条件，可以人为地加上若干零值 （加零补长）使其达到 N=2M
数字信号处理
2.2 利用DFT进行连续信号的频谱分析
1、混叠 2、泄漏 3、栏栅效应 4、DFT的分辨率 5、周期信号的谱分析
数字信号处理
数字信号处理
3.3 快速傅里叶变换
有限长序列通过离散傅里叶变换 (DFT)将其频 域离散化成有限长序列。但其计算量太大(与N 的平方成正比），很难 实时地处理问题，因 此 引 出 了 快 速傅 里 叶 变 换(FFT) 。 FFT并 不是 一 种 新 的 变 换 形 式，它 只 是 DFT 的一 种 快 速 算 法， 并 且 根 据 对 序列分解与选取方法的不同而产生 了 FFT 的 多 种 算 法 。 FFT 在 离 散 傅 里 叶 反 变 换、线 性 卷 积 和 线 性 相 关 等 方 面 也 有 重 要 应 用。
数字信号处理
(1)N/2点的DFT运算量:复乘次数: N N 复加次数: 2 ( 2 1) (2)两个N/2点的DFT运算量:复乘次数: N 2 N 复加次数: N ( 2 1) (3)N/2个蝶形运算的运算量:复乘次数: N 2 复加次数: 2 N N
2
N 2 N2 ( ) 2 4
数字信号处理
数字信号处理
3.3.1 按时间抽取的DFT
1、WNnk 的特性
nk WN e j 2 nk N nk ( 1)对称性：（WN ） WNnk＝WN N n ) k ＝ nk n 2)周期性：WN ＝W（N n ) k WN ( k N ) N nk mnk nk nk / 3)可约性：WN ＝WmN , WN WN / mm
4)特殊点：W ＝1，W
0 N
N 2 N
1, W
(k N ) 2 N
k WN
数字信号处理
例子
W W
9 4 ( 45) 4
17 8
W W
5 4
9 8 1 8
1 4
W
25 8
W
W W
利用以上特性,得到改进DFT直接算法的方法.
数字信号处理
2、DFT的基本思想
快速傅里叶变换( FFT ) 就是在此特性基础上 发展起来的： （1）利用DFT系数的对称性和周期性,合并DFT 运算中的某些项； （2）将长序列分解为短序列,从而减少其运算 量。 因合并与分解方法的不同产生了多种DFT的快 速算法。
如：X（0） X 1 (0) X 2 (0)W80 X（2） X 1 (2) X 2 (2)W82
X（ ） X 1 (1) X 2 (1)W81 X(4)~X(7) 1 X（3） X 1 (3) X 2 (3)W83 同学们自已写
(2) N/2(4点)-->N/4(2点)FFT
将x(n)按n的奇偶分为两组作DFT， n为偶数时：x(2r ) x1 (r ), r 0,1,, N 1 2 n为奇数时：x(2r 1) x2 (r ), r 0,1,, N 1 2
X (k ) x(n)W
n 0
N 2
N 1
nk N n 偶数
N 2
nk x(n)WN n 0
1
k WN k WN
1 -1
X 2 (k ) X 2 (k )
-1
2 N X ( k ) X 1 (k ) WNk X 2 (k ) 2
1(k ) X (k ) W k X (k ) X 1 N 2 1 1 N X ( k ) X 1 (k ) WNk X 2 (k ) 1
数字信号处理
5、 FFT的计算工作量
FFT算法对于N点DFT,仅需(N/2)log2N 次复数乘法运算和Nlog2N 次复数加法。
数字信号处理
例
如果计算机的速度为平均每次复数乘需要5×10-6 秒 ，每次复加需要1×10-6秒，用来计算 N=1024点DFT, 问1)直接计算需要多少时间？2）用FFT算法计算 需要多少时间？ 1)直接计算所需时间为：
数字信号处理
引言：
离散傅里叶变换不仅具有明确的物理意义，更 便于用计算机处理。但是，直至上个世纪六十 年代，由于数字计算机的处理速度较低以及离 散傅里叶变换的计算量较大，离散傅里叶变换 长期得不到真正的应用，快速离散傅里叶变换 算法的提出，才得以显现出离散傅里叶变换的 强大功能，并被广泛地应用于各种数字信号处 理系统中。近年来，计算机的处理速率有了惊 人的发展，同时在数字信号处理领域出现了许 多新的方法，但在许多应用中始终无法替代离 散傅里叶变换及其快速算法。
N 1
n 奇数
2 ( x(2r )WN rk x(2r 1)WN2 r 1) k r 0
N 2
1
1
r 0
2 k 2 x(2r )WN rk WN x(2r 1)WN rk r 0
N 2
1
N 2
1
r 0 1
k k x(2r )W Nrk WN x(2r 1)W Nrk X 1 (k ) WN X 2 (k ) r 0
6
6. FFT算法分类：
1.按抽取方法分： 时间抽取法(DIT Decimation-In-Time); 频率抽取法(DIF Decimation-In-Frequency) 2.按“基数”分： 基-2FFT算法； 基-4FFT算法； 混合基FFT算法； 分裂基FFT算法 3.其它方法： 线性调频Z变换(Chrip-z法)
T 5 10 6 N 2 10 6 N ( N 1) 5 10 6 1024 2 10 6 1024 1023 6.29 s 2)用FFT计算需要时间为多少？ N N N T 5 10 log 2 10 6 N log 2 35.84 ms 2

1 X (1) x(0)WN0 x(1)WN x(2)WN2 x( N 1)WNN 1