当前位置：文档之家 › dsp第4章快速傅里叶变换(FFT)

dsp第4章快速傅里叶变换(FFT)

  • 格式：ppt
  • 大小：1.36 MB
  • 文档页数：89

下载文档原格式

  / 89

合集下载

快速傅里叶变换FFT

快速傅里叶变换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算法
数字信号处理课件第4章快速傅里叶变换FF

数字信号处理课件第4章快速傅里叶变换FF

雷达信号压缩
通过FFT对雷达信号进行频谱分析，实现雷 达数据的压缩，减小存储空间和传输带宽。
谢谢聆听
05 FFT的局限性与挑战
浮点运算的开销问题
浮点运算开销
快速傅里叶变换（FFT）算法在实 现过程中需要进行大量的浮点运 算，这可能导致计算成本较高， 尤其是在处理大规模数据时。
硬件资源需求
由于FFT的浮点运算密集特性，对 计算设备的硬件资源（如CPU、 GPU等）要求较高，需要具备高 性能的计算能力。
FFT的软件实现
C/C实现
01
使用C或C等通用编程语言实现FFT算法，具有较好的通用性和
可移植性。
优化编译器
02
利用现代编译器的优化功能，如向量化、内联等，可以提高软
件实现的计算速度。
并行计算框架
03
利用OpenMP、CUDA等并行计算框架，可以实现多核或多
GPU上的并行计算。
FFT的优化方法
算法改进
FFT的历史与发展
历史
FFT的诞生可以追溯到1960年代，其发展经历了多个阶段，包括库利-图基算法、威尔金森算法、桑德斯算法等 。
发展
随着计算机技术的不断进步，FFT算法在实现方式、精度、并行化等方面不断得到优化和改进，以满足不同应用 场景的需求。
02 FFT的基本算法
递归算法
递归算法是一种基于数学归纳法的算法，通过将问题分解为更小的子问题来解决 问题。在FFT中，递归算法将一个长度为N的DFT问题分解为两个长度为N/2的 DFT问题，直到最后分解为基本的DFT问题。
特别是在信号处理领域，FFT的应用非常广泛。
FFT与Z变换的关系
定义
Z变换是离散时间信号 到复平面上的扩展，而 FFT是频域的一种快速 计算方法。
DSP第4章快速付里叶变换FFT.

DSP第4章快速付里叶变换FFT.

第四章快速付里叶变换(FFT) Fast Fourier Transforming第一节引言、快速付里叶变换FFT •有限反序列通过离散傅里叶变换(DFT)将其频域离散化成有限K序列•但其计算量太大(与N 的平方成正比)，很难实时地处理问题，因此引出了快速傅里叶变换(FFT)・•FFT并不是一种新的变换形式，它只是DFT的一种快速算法•并且根据对序列分解与选取方法的不同而产生了FFT的多种算法.•FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重耍应用・。

二、FFT产生故事当时加文(Garwin)在自已的研究中极需要一个计算付里叶变换的快速方法。

他注意到图基(J.W.Turkey)iE 在写有关付里叶变换的文章，因此详细询问了图基关于计算付里叶变换的技术知识。

图基概括地対加文介绍了一种方法，它实质上就是后来的著名的库利(Cooley J.W)图基算法。

在加文的迫切要求下，库利很快设计出一个计算机程序o 1965年库利-图基在v计算数学〉、Mathematic of Computation 杂志上发表了著乞的“机器计算付里级数的一种算法”文章，提出一种快速计算DFT的方法和计算机程序-揭开了FFT发展史上的第一页，促使FFT算法产牛原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件，使DFT的运算大简化了。

、本章主要内容•1 •立接计算DFT算法存在的问题及改进途径。

•2•多种DFT算法（时间抽取算法DIT算法，频率抽取算法DIF算法，线性调频Z变换即CZT 法）• 3.FFT的应用直接计算DFT算法存在的问题及改进逐径\直接计算DFT计算量•问题提出：设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT 运算，共需多大的运算工作量？1 •比较DFT与IDFT之间的运算量N—1x(n) DFT > X 伙)=工上=0,1,…N -1n=0N-\X伙)u)n > x(n) = Y X伙)A2 = 0,1,・・・ N -1 k=0其中x(n)为复数，W严之G"也为复数所以DFT与IDFT二者计算量相同。

数字信号处理DSP第4章

数字信号处理DSP第4章

G[3] 1
k 0,1, , N 1
2
13
4.2 按时间抽取（DIT）的基2–FFT算法
将系数统一为 WNk 2 WN2k ,则可得
x[0]
N 4点
x[4]
DFT
G[0]
X [0]
G[1]
X [1]
x[2]
N 4点
WN0
x[6]
DFT
WN2
G[2]
1 G[3]
1
X [2] X [3]
x[1]
N 4点
X m1[i] WNr X m1[ j] , X m1[i] WNr X m1[ j]
m 1, 2 ,
每一个蝶形需要一次复数乘法和两次复数加法。
17
4.2 按时间抽取（DIT）的基2–FFT算法
N点的DIT-FFT计算量为
复数乘法：
1
N 2
log2
N
N 2
复数加法：
2
N 2
log2
N
N
例： 如果每次复数乘法需要100us，每次复数加法需要20us，来 计算N=1024点DFT，则需要
12
4.2 按时间抽取（DIT）的基2–FFT算法
同理
( N 4)1
( N 4)1
G[k] DFT[g[r]]
g[2l]WN2lk2
g[2l 1]WN(22l1)k
l 0
l 0
( N 4)1
( N 4)1
g[2l]WNlk 4 WNk 2
g[2l 1]WNlk 4 ,
l 0
l 0
k 0,1,
(3) WN0 WN4 WN8 WN12 WN16 WN20 WN24 WN28
或 WN4i i 0,1, 2, 3, 4, 5, 6, 7 (dm 1)
数字信号处理第4章快速傅里叶变换FFT

数字信号处理第4章快速傅里叶变换FFT


X 6(k)
x6 (l)WNkl/ 4 DFT [x6(l)]
i0
x5 (l ) x6 (l )

x2 x2
(2l (2l
)
1)

,
l

0,1, N
/
4
1
(4.2.11)
课件
12
第4章 快速傅里叶变换(FFT)
x(0 )
N/4点 X3(0 )
x(4 )
DFT X3(1 )
e N
j 2 m
e N
WNm
(4.2.2)
其对称性表现为
WNm WNN m 或者 [WNN m ] WNm
m N
WN 2
WNm
课件
4
第4章 快速傅里叶变换(FFT)
4.2.2 时域抽取法基2FFT基本原理 FFT 算 法 基 本 上 分 为 两 大 类 ： 时 域 抽 取 法
课件
21
第4章 快速傅里叶变换(FFT)
x(0 )
N/4点
X(0 )
x(1 )
DFT
X(4 )
x(2 )
W
0 N
N/4点
X(2 )
x(3 )
W
2 N
DFT
X(6 )
x(4 )
W
0 N
N/4点
X(1 )
x(5 )
W
1 N
DFT
X(5 )
x(6 )
W
2 N
W
0 N
N/4点
X(3 )
x(7 )
W
3 N
W
X
(k

N 2
)
《快速傅里叶变换》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滤波器的乘法运算量
快速傅立叶变换(FFT)的实现(DSP实验报告)

快速傅立叶变换(FFT)的实现(DSP实验报告)

快速傅立叶变换（FFT ）的实现一、实验目的在数字信号处理系统中，FFT 作为一个非常重要的工具经常使用，甚至成为DSP 运算能力的一个考核因素。

FFT 是一种高效实现离散付氏变换的算法。

离散付氏变换的目的是把信号由时域变换到频域，从而可以在频域分析处理信息，得到的结果再由付氏逆变换到时域。

本实验的目的在于学习FFT 算法，及其在TMS320C54X 上的实现，并通过编程掌握C54X 的存储器管理、辅助寄存器的使用、位倒序寻址方式等技巧，同时练习使用CCS 的探针和图形工具。

另外在BIOS 子目录下是一个使用DSP/BIOS 工具实现FFT 的程序。

通过该程序，你可以使用DSP/BIOS 提供的分析工具评估FFT 代码执行情况。

二、实验原理1）基 2 按时间抽取FFT 算法对于有限长离散数字信号{x[n]} ，0 ≤n ≤-1 N，其离散谱{x[k]} 可以由离散付氏变换（DFT）求得。

DFT 的定义为：X(k) x[n]e N k 0,1,...,N 1 n0可以方便的把它改写为如下形式：N1nkX(k) x[n]W n N k k 0,1,..., N 1n0不难看出，WN 是周期性的，且周期为N，即( n mN )(k lN ) nkm,l 0, 1, 2...W N W NWN 的周期性是DFT 的关键性质之一。

为了强调起见，常用表达式WN 取代W 以便明确其周期是N。

2) 实数FFT 运算对于离散傅立叶变换( DFT)的数字计算，FFT 是一种有效的方法。

一般假定输入序列是复数。

当实际输入是实数时，利用对称性质可以使计算DFT 非常有效。

一个优化的实数FFT 算法是一个组合以后的算法。

原始的2N 个点的实输入序列组合成一个N 点的复序列，之后对复序列进行N 点的FFT 运算，最后再由N 点的复数输出拆散成2N 点的复数序列，这2N点的复数序列与原始的2N点的实数输入序列的DFT 输出一致。

《快速傅里叶变换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，然后利用递归和分治的思想进行计 算，最终得到原始序列的频域表示。
数字信号处理课后答案-第4章高西全

数字信号处理课后答案-第4章高西全


解: 当N=1024=210时， 直接计算DFT的复数乘法运算 次数为
N2=1024×1024=1 048 576次 复数加法运算次数为
N（N－1）=1024×1023=1 047 552次 直接计算所用计算时间TD为
TD=4×10－6×10242+1 047 552×10－6=5.241 856 s 用FFT计算1024点DFT所需计算时间TF为
第３章 离散傅里叶变换(DFT)及其快速算法
(FFT)
作品欣赏 谢谢观看！
Re[
y(n)]
1 2
[
y(n)
y* (n)]
DFT[Yep
(k )]
x1(n)
j Im[
y(n)]
1 [ y(n) 2
y* (n)]
DFT[Yop (k)]
jx2 (n)
③ 由x1(n)和x2(n)合成x(n):
x(n)
x1
n 2
x2
n
2
1
n 偶数 n 奇数
，0≤n≤2N－1
TF
10 109
N 2
l
bN
10 109
N
l
bN
108 1024 10 108 1024 10 2
0.1536 ms
快速卷积计算时间Tc约为
Tc 2TF 1024 次复数乘计算时间 2 0.1536103 10109 1024
0.317 44 ms
可实时处理的信号最高频率fmax为
fmax ≤
由DFT的共轭对称性可知
Re［f(n)］=IDFT［Fep(k)］=IDFT［X(k)］=x(n)
j Im［f(n)］=IDFT［Fop(k)］=IDFT［jY(k)］=jy(n)
DSP--FFT-深入浅出-详细讲解快速傅里叶变换

DSP--FFT-深入浅出-详细讲解快速傅里叶变换

第四章 迅速付里叶变换 (FFT) Fast Fourier Transforming
第一节 引言
一、迅速付里叶变换FFT
• 有限长序列经过离散傅里叶变换 (DFT)将其频 域离散化成有限长序列.但其计算量太大(与N 旳平方成正比）, 极难 实时地处理问题 , 因 此 引 出 了 快 速 傅 里 叶 变 换(FFT) .
• 一种复数乘法涉及4个实数乘法和2个实数相 法。
(a+jb)(c+jd)=(ac-bd)+j(bc+ad)
2次实数加法
4次实数乘法
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 ])}
4
4
X (k) N X (k) N
(
N
)
4 2
4
+
(
N 4
4
)2
=
N 4
2
这么一直分下去，剩余两点旳变换。
2、将长序列DFT利用对称性和 周期性分解为短序列DFT--结论
• 迅速付里时变换(FFT)就是在此特征基础上 发展起来旳，并产生了多种FFT算法，其基 本上可提成两大类：
• 按抽取措施分： 时间抽取法(DIT);频率抽取法(DIF)
r 0
r 0
W 2
j 2 2
e N
j 2
e N/2
W
3.求出子序列旳DFT
上式得：
N / 21
N / 21
X（k)
x1(r)WNrk/ 2
x2 (r)WNrk/ 2WNk
数字信号处理[第四章 快速傅里叶变换(FFT)]

数字信号处理[第四章 快速傅里叶变换(FFT)]


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)

基于DSP的C程序实验报告------快速傅立叶变换(FFT)算法

第二次间隔为二，如第一个和第三个，第二个和第四个等 （2）基本运算单元以下面的蝶形运算为主：
计算公式如下：
X m1 ( p)

Xm

W
r N
X m (q)
X m1 ( p) X m WNr X m (q)
（3）在FFT运算中，旋转因子WmN=cos(2πm/N)-jsin(2πm/N)，求正弦和余弦函数值的
二．FFT 的基本结构： FFT信号流图如下：
x(0)
X3(0) N/4点
X1(0)
X(0)
x(4)
DFT X3(1)
X1(1)
X(1)
x(2)
N/4点
X4(0)
W
0 N
2
X1(2)
X(2)
x(6)
DFT
X4(1)
W
1 N
2
X1(3)
X(3)
x(1)
N/4点
X2(0)
W
0 N
X(4)
x(5)
DFT
X2(1)
/************** following code FFT *******************/ /*说明： 基2fft算法，蝶形运算为核心 */ for ( L=1;L<=7;L++ ) { /* for(1) */
b=1; i=L-1; while ( i>0 ) {
b=b*2; i--; } /* b= 2^(L-1) */
图1
图2
图3 3．清除显示：在以上打开的窗口中单击鼠标右键，选择弹出式菜单中“Clear Display”功 能。 4．设置断点：在程序FFT.c 中有注释“break point”的语句上设置软件断点。

(完整word版)快速傅里叶变换(FFT)的DSP实现

目录一、前言二、设计题目三、设计要求3。

1 设计目的3.2 设计要求四、设计内容五、设计原理5.2 离散傅里叶变换DFT5。

3 快速傅里叶变换FFT六、总体方案设计6。

1 设计有关程序流程图6.2 在CCS环境下加载、调试源程序七、主要参数八、实验结果分析九、设计总结一、前言随着数字电子技术的发展，数字信号处理的理论和技术广泛的应用于通讯、语音处理、计算机和多媒体等领域。

快速傅里叶变换（FFT）使离散傅里叶变换的时间缩短了几个数量级.在数字信号处理领域被广泛的应用。

FFT已经成为现代化信号处理的重要手段之一。

本次课程设计主要运用CCS这一工具.CCS(Code Composer Studio）是一种针对TM320系列DSP的集成开发环境,在Windows操作系统下，采用图形接口界面，提供环境配置、源文件编辑、程序调试、跟踪和分析等工具，可以帮助用户在一个软件环境下完成编辑、编译、链接、调试和数据分析等工作。

CCS有两种工作模式,即软件仿真器和硬件在线编程。

软件仿真器工作模式可以脱离DSP芯片，在PC上模拟DSP的指令集和工作机制，主要用于前期算法实现和调试。

硬件在线编程可以实时运行在DSP芯片上，与硬件开发板相结合进行在线编程和调试应用程序。

二、设计题目快速傅里叶变换(FFT）的DSP实现三、设计要求3。

1设计目的⑴加深对DFT算法原理和基本性质的理解;⑵熟悉FFT的算法原理和FFT子程序的算法流程和应用;⑶学习用FFT对连续信号和时域信号进行频谱分析的方法；⑷学习DSP中FFT的设计和编程思想;⑸学习使用CCS的波形观察器观察波形和频谱情况；3.2 基本要求⑴研究FFT原理以及利用DSP实现的方法;⑵编写FFT程序；⑶调试程序，观察结果。

四、 设计内容⑴用DSP 汇编语言及C 语言进行编程; ⑵实现FFT 运算、对输入信号进行频谱分析。

五、 设计原理快速傅里叶变换FFT快速傅里叶变换(FFT)是一种高效实现离散傅里叶变换（DFT ）的快速算法，是数字信号处理中最为重要的工具之一，它在声学，语音，电信和信号处理等领域有着广泛的应用。

第四章 快速傅里叶变换(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

4-快速傅里叶变换解析


k 0,1,, N 1 2
X

k

N 2


X1 (k )
WNk
X 2 (k)
k 0,1,
, N 1 2
x1(0 )＝x(0 ) x1(1 )＝x(2 )
X1(0 )
X1(1 ) N点
X(0 ) X(1 )

x(2r x(2r
) x1(r) 1) x2
从上面的统计可以看到，直接计算DFT，乘法次数和加法 次数都是和N2成正比的，当N很大时，运算量是很可观的，有 时是无法忍受的。
6
第4章 快速傅里叶变换(FFT)
例3-1 根据式（3-1），对一幅N×N点的二维图像进行DFT 变换，如用每秒可做10万次复数乘法的计算机，当N=1024时， 问需要多少时间（不考虑加法运算时间）？
X1(k) WNk X 2 (k) ,
k 0,1,, N 1 2
13
第4章 快速傅里叶变换(FFT)
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
22
(2)两个N/2点的DFT运算量:复乘次数: N 2
2
复加次数: N ( N 1)
2
(3)N/2个蝶形运算的运算量:复乘次数: N
复加次数:
2 2
N
N
2
总共运算量:
复乘: 复加:
N2 N

N ( N 1)/ 2 N 2

dsp 数字信号处理课件 第4章 快速付里叶变换FFT


(4)如果在某一支路上 如果在某一支路上 信号需要进行相乘运 算，则在该支路上标 以箭头， 以箭头，将相乘的系 数标在箭头旁。 数标在箭头旁。
2011年5月2日星期一
(5)当支路上没有箭头及系数 当支路上没有箭头及系数 则该支路的传输比为1。 时，则该支路的传输比为 。
25
第4章 快速付里叶变换FFT
第4章 快速付里叶变换FFT
FFT产生
加文(Garwin)：研究，极需计算FT的快速方法。 图基(J.W.Turkey)：正写有关FT换的文章。 在加文的迫切要求下，库利很快设计出一个计算机程序。
2011年5月2日星期一
1
An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19:297-301, 1965.
N / 2 −1 r =0
∑ x (r )W
= DFT [ x 2( r )]
19
k=0,1,…,N/2-1
第4章 快速付里叶变换FFT
因此，可写出两个N/2点的方程:
X ( k ) = X 1( k ) + W X 2( k )
k N
N k = 0 ,1,..., −1 2
N N X ( k + ) = X 1( k + ) + WN 2 2
码位 倒置 混序或反 序
x0 x1 x2 x3
x0 x2 x1 x2 X3
x0 x2 x1 x3
2011年5月2日星期一
27
第4章 快速付里叶变换FFT
butterfly（蝶形运算） the butterfly（蝶形运算）

DSP第4章快速付里叶变换FFT

• 快速付里时变换(FFT)就是在此特性基础上 发展起来的，并产生了多种FFT算法，其基 本上可分成两大类：
• 按抽取方法分： 时间抽取法(DIT);频率抽取法(DIF)
• 按“基数”分：基-2FFT算法；基-4FFT算 法；混合基FFT算法；分裂基FFT算法
• 其它方法：线性调频Z变换(CZT法)
(1) 合并法：步骤3合并有些项
根据： 有：
Re WNk (N n) Re WNkn ImWNk (N n) ImWNkn
Re x(n) ReWNnk Re x(N n) ReWNk(Nn) [Re x(n) Re x(N n)]ReWNnk
Im x(n) ImWNnk Im x(N n) ImWNk(Nn) [Im x(n) Im x(N n)]ImWNnk
每道总抽样点数=500*5=2500点 24道总抽样点数=24*2500=6万点 DFT运算时间=N2=(60000)2=36*108次
作业
二、改善DFT运算效率的基本途径
利用DFT运算的系数 WNkn 的固有对称性和
周期性，改善DFT的运算效率。 1.合并法：合并DFT运算中的某些项。 3. 分解法：将长序列DFT利用对称性和周
kn
也为复数
所以DFT与IDFT二者计算量相同。
2.以DFT为例，计算DFT复数运算量
• 计算一个X(k)(一个频率成分)值，运算量为
N 1
例k=1则
X (1) x(n)WNn
n0
要进行N次复数乘法+(N-1)次复数加法
所以，要完成整个DFT运算，其计算量为：
N*N次复数相乘和N*(N-1)次复数加法
3.一次复数乘法换算成实数运算量
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2
X
4
(k
)
,
k
0,1, ,
N
/
4
1
(4.2.10)
第4章 快速傅里叶变换(FFT)
用同样的方法可计算出
X X
2 2
(k (k
) X5(k N / 4)
) WNk X5k
/2
X 6 (k Wk
N /2
) X
6
(k
)
,
k
0,1, N
/
4
1
其中
N / 41
X5(k)
x5(l)WNkl/ 4 DFT [x5(l)]
x2 (r)WNkr/ 2 DFT [x2 (r)]
r0
(4.2.6)
由于X1(k)和X2(k)均以N/2为周期，且
kN
WN 2
WNk
，所以X(k)又可表示为
X (k) X1(k) WNk X 2(k)
k 0,1, N 1 2
X (k
N 2
)
X1(k)
WNk
X 2 (k )
k 0,1, N 1 2
A(7 )
x(7 )
W
0 N
A(0 )
A(1 )
A(2 )
W
0 N
A(3 )
W
2 N
A(4 )
A(5 )
A(6 )
W
0 N
A(7 )
W
2 N
A(0 )
A(1 )
A(2 )
A(3 )
A(4 )
W
0 N
A(5 )
W
1 N
A(6 )
W
2 N
A(7 )
W
3 N
图4.2.4 N点DIT―FFT运算流图(N=8)
WNm WNN m 或者 [WNN m ] WNm
m N
WN 2
WNm
第4章 快速傅里叶变换(FFT)
4.2.2 时域抽取法基2FFT基本原理 FFT 算 法 基 本 上 分 为 两 大 类 ： 时 域 抽 取 法
FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取 法FFT(Decimation In Frequency FFT,简称DIF―FFT)。 下面先介绍DIF―FFT算法。
第4章 快速傅里叶变换(FFT)
4.2 基2FFT算法
4.2.1 直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列x(n)的DFT为
N 1
X (k) x(n)WNkn, k 0,1,, N 1
n0
(4.2.1)
考虑x(n)为复数序列的一般情况，对某一个k值，
直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次
XL(J ) XR(J ) j(J )
则
X R (J ) X R (J ) TR
X I (J ) X I(J ) TI
X R (J B) X R (J ) TR
X I (J B) X I(J ) TI
4. 编程思想及程序框图
图4.2.6 DIT―FFT运算和程序框图
第4章 快速傅里叶变换(FFT)
第4章 快速傅里叶变换(FFT)
观察图4.2.4不难发现，第L级共有2 L-1个不同的旋 转因子。N=23=8时的各级旋转因子表示如下：
L=1时，WpN=WJ N/4=WJ2L， J=0 L=2时， WpN =WJ N/2=WJ2L， J=0，1 L=3时， WpN =WJN=WJ2L， J=0，1，2，3 对N=2M的一般情况，第L级的旋转因子为
W
2 N
X2(3 )
W
3 N
X(6 ) X(7 )
图4.2.3 N点DFT的第二次时域抽取分解图(N=8)
第4章 快速傅里叶变换(FFT)
A(0 ) x(0 )
A(1 )
x(4 )
A(2 )
W
0 N
x(2 )
A(3 )
x(6 )
A(4 )
W
0 N
x(1 )
A(5 )
x(5 )
A(6 )
W
0 N
x(3 )
n
n
N / 21
N / 21
x(2r)WN2kr
x(2r 1)WNk (2r1)
r0
r0
N / 21
N / 21
x1(r) WNk
x2 (r)WN2kr
由于
r0
r0
W 2kr N
j 2 2kr
eN
j
2 N
kr
e 2
W 2kr N /2
所以
N / 21
N / 21
X (k)
x1(r)WNkr/ 2 WNk
WNp W2J L, J 0,1, 2, , 2L1 1 2L 2M 2LM N 2LM
WNP
WJ N g2LM
WNJ g2M L , J
0,1, 2, , 2L1 1
(4.2.12)
p J g2M L
(4.2.13)
第4章 快速傅里叶变换(FFT)
3. 蝶形运算规律 设序列x(n)经时域抽选(倒序)后，存入数组X中。 如果蝶形运算的两个输入数据相距B个点，应用原位计 算，则蝶形运算可表示成如下形式：
长的子序列x3(l)和x4(l)，即
x3 (l ) x4 (l )
x2 x1
(2l (2l
)
1)
,
l
0,1, ,
N 4
1
那么，X1(k)又可表示为
N / 41
N / 41
X1(k)
x1(2l
)WN2
kl /2
x1(2l
1)WNk
(2l 1) /2
i0
i0
N / 41
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 /
CM (2)
N 2
M
N 2
log2
N
复数加次数为
CA(2) N M N log2 N 例如，N=210=1024时
N2
1048576 204.8
(N / 2) log2 N 5120
第4章 快速傅里叶变换(FFT) 图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线
第4章 快速傅里叶变换(FFT)
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
(4.2.9)
第4章 快速傅里叶变换(FFT)
式中
N / 41
x3(k)
x3(l)WNkl/ 4 DFT [x3(l)]
i0
N / 41
设序列x(n)的长度为N，且满足
N 2M , M 为自然数
按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
第4章 快速傅里叶变换(FFT)
则x(n)的DFT为
X (k ) x(n)WNkn x(n)WNkn
4.2.4 DIT―FFT的运算规律及编程思想 1.原位计算 由图4.2.4可以看出，DIT―FFT的运算过程很有规
律。N=2M点的FFT共进行M级运算，每级由N/2个蝶 形运算组成。
2.旋转因子的变化规律 如上所述，N点DIT―FFT运算流图中，每级都有 N/2个蝶形。每个蝶形都要乘以因子WpN，称其为旋转 因子，p称为旋转因子的指数。
i0
N / 41
X 6(k)
x6 (l)WNkl/ 4 DFT [x6(l)]
i0
x5 (l ) x6 (l )
x2 (2l ) x2(2l
1)
,
l
0,1, N
/
4
1
(4.2.11)
第4章 快速傅里叶变换(FFT)
x(0 )
N/4点 X3(0 )
X1(0 )
X(0 )
x(4 )
DFT X3(1 )
X1(1 )
X(1 )
x(2 )
N/4点
X4(0 )
W
0 N
2
X1(2 )
X(2 )
x(6 )
DFT
X4(1 )
W
1 N
2
X1(3 )
X(3 )
x(1 )
N/点
X2(0 )
W
0 N
X(4 )
x(5 )
DFT
X2(1 )
W
1 N
X(5 )
x(3 )
N/4点
x(7 )
DFT
W
0 N
2
W
1 N
2
X2(2 )
001 1 101 5 011 3 111 7
图4.2.7 形成倒序的树状图(N=23)
第4章 快速傅里叶变换(FFT) 表4.2.1 顺序和倒序二进制数对照表
第4章 快速傅里叶变换(FFT)
x(0 ) x(1 ) x(2 ) x(3 ) x(4 ) x(5 ) x(6 ) x(7 ) A(0 ) A(1 ) A(2 ) A(3 ) A(4 ) A(5 ) A(6 ) A(7 )