-第5快速傅里叶变换 实际计算量与这个数字稍有不同,因为W=1,WM2=-1 W2=,这几个系数都不用乘法运算,但是这些情况在直接计 算DFT中也是存在的。此外,当N较大时,这些特例相对而言就 很少。所以,为了统一作比较起见,下面都不考虑这些特例。 由于计算机上乘法运算所需的时间比加法运算所需的时间 多得多,故以乘法为例,直接DFT复数乘法次数是M,FFT复数 乘法次数是(N2)bN。直接计算DFT与FFT算法的计算量之比为 N 2N 1bV16 (3-20) 当№=2048时,这一比值为372.4,即直接计算DFT的运算量是 FFT运算量的372.4倍。当点数N越大时,FFT的优点更为明显
第3章 快速傅里叶变换 实际计算量与这个数字稍有不同，因为W0 N =1，ＷN N/2=-1， ＷN N/2=-j，这几个系数都不用乘法运算，但是这些情况在直接计 算DFT中也是存在的。此外，当N较大时，这些特例相对而言就 很少。所以，为了统一作比较起见，下面都不考虑这些特例。 由于计算机上乘法运算所需的时间比加法运算所需的时间 多得多，故以乘法为例，直接DFT复数乘法次数是N2 ，FFT复数 乘法次数是(N/2) lbN。 直接计算DFT与FFT算法的计算量之比为 bN N bN N N M N N 1 2 1 2 2 2 2 = = 当N=2048时，这一比值为372.4，即直接计算DFT的运算量是 FFT运算量的372.4倍。当点数N越大时，FFT的优点更为明显。 （3-20）
-第5快速傅里叶度换 例3-2用FT算法处理一幅N×N点的二维图像,如用每秒 可做10万次复数乘法的计算机,当N=1024时,问需要多少时间 (不考虑加法运算时间)? 解当λ=1024点时,FFT算法处理一幅二维图像所需复数乘 法约为1bN2≈107次,仅为直接计算DFT所需时间的10万分之 。即原需要3000小时,现在只需要2分钟
第3章 快速傅里叶变换 例3-2 用FFT算法处理一幅N×N点的二维图像，如用每秒 可做10万次复数乘法的计算机，当N=1024时，问需要多少时间 （不考虑加法运算时间）？ 解 当N=1024点时，FFT算法处理一幅二维图像所需复数乘 法约为 次，仅为直接计算DFT所需时间的10万分之 一。 即原需要3000小时，现在只需要2 分钟。 2 7 2 1 10 2 bN N
-第3快速疼里叶变换一 333按时间抽取的FFT算法的特点及 DIT-FFT程序框图 1.原位运算(同址运算) 从图3-5可以看出这种运算是很有规律的,其每级(每列) 计算都是由N2个蝶形运算构成的,每一个蝶形结构完成下述 基本迭代运算: Xm(k)=Xm-(k)+Xm-(WN (3-21a) Xm(=Xm-(k)-XMm(WN (3-21b) 式中,m表示第m列迭代,k,门为数据所在行数。式(3-21)的蝶 形运算如图3-6所示,由一次复乘和两次复加(减)组成
第3章 快速傅里叶变换 3.3.3 按时间抽取的FFT算法的特点及DIT-FFT程序框图 1. 原位运算（同址运算） 从图3-5可以看出这种运算是很有规律的，其每级（每列） 计算都是由N/2 个蝶形运算构成的，每一个蝶形结构完成下述 基本迭代运算： r m m m N r m m m N X j X k X j W X k X k X j W ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 − − − − = − = + （3-21a） （3-21b） 式中，m表示第m列迭代，k, j为数据所在行数。式（3-21）的蝶 形运算如图3-6所示，由一次复乘和两次复加（减）组成
-第5快速傅里叶度换 Xm(k=Xm-(k)+Xm-dD Xn()=Xn-体k)Xm- 图3-6蝶形运算单元
第3章 快速傅里叶变换 图 3-6 蝶形运算单元 － 1 r WN Xm－ 1 (k) Xm－ 1 ( j) Xm (k)＝Xm－ 1 (k)＋Xm－ 1 ( j) Xm ( j)＝Xm－ 1 (k)－Xm－ 1 ( j) r WN r WN
-第3快速疼里叶变换一 由图3-5的流图看出,某一列的任何两个节点k和的节点变量 进行蝶形运算后,得到结果为下一列,两节点的节点变量,而 和其他节点变量无关,因而可以采用原位运算,即某一列的N个 数据送到存储器后,经蝶形运算,其结果为下一列数据,它们以 蝶形为单位仍存储在这同一组存储器中,直到最后输出,中间无 需其他存储器。也就是蝶形的两个输出值仍放回蝶形的两个输入 所在的存储器中。每列的M2个蝶形运算全部完成后,再开始 下一列的蝶形运算。这样存储器数据只需N个存储单元。下 级的运算仍采用这种原位方式,只不过进入蝶形结的组合关系有 所不同。这种原位运算结构可以节省存储单元,降低设备成本
第3章 快速傅里叶变换 由图3-5的流图看出，某一列的任何两个节点k和j的节点变量 进行蝶形运算后，得到结果为下一列k, j两节点的节点变量，而 和其他节点变量无关，因而可以采用原位运算， 即某一列的N个 数据送到存储器后，经蝶形运算，其结果为下一列数据，它们以 蝶形为单位仍存储在这同一组存储器中，直到最后输出，中间无 需其他存储器。也就是蝶形的两个输出值仍放回蝶形的两个输入 所在的存储器中。 每列的N/2 个蝶形运算全部完成后， 再开始 下一列的蝶形运算。 这样存储器数据只需N个存储单元。 下一 级的运算仍采用这种原位方式，只不过进入蝶形结的组合关系有 所不同。 这种原位运算结构可以节省存储单元， 降低设备成本