例 例1:当N=1024点时,直接计算DFT需要: N2=1048576次,即一百多万次的复乘运算 这对实时性很强的信号处理(如雷达信号处理)来讲,它对计算速度有 十分苛刻的要求->迫切需要改进DFT的计算方法,以减少总的运 算次数 ●例2:石油勘探,24道记录,每道波形记录长度5秒,若每秒抽样 500点/秒, 每道总抽样点数=500*5=2500点 24道总抽样点数=24*2500=6万点 DFT运算时间=N2=(60000)2=36*108次
例 例1:当N=1024点时，直接计算DFT需要： N2=1048576次，即一百多万次的复乘运算 这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有 十分苛刻的要求-->迫切需要改进DFT的计算方法，以减少总的运 算次数。 例2：石油勘探，24道记录，每道波形记录长度5秒，若每秒抽样 500点/秒， 每道总抽样点数=500*5=2500点 24道总抽样点数=24*2500=6万点 DFT运算时间=N2=(60000)2=36*108次
6.0引言:直接计算DFT的运算量分析 如N=512、1024和8192时,DFT的乘法运算 N2=5122=218=262144(26万次) N2=10242=220=1048576(105万次) N2=81922=226=67108864(6千7百万次) 对于大N,在实际中是不能接受的,无法“实时”应用DFT ⑩一般地,在计算机中,一次加法比一次乘法所需时间要短; ⑩在DSP中,由于乘法用特殊的硬件电路专门完成,因此乘法 和加法所需机器周期相同。 Cooley与 Turkey提出的FFT算法,大大减少了计算次数。如N =512时,FFT的乘法次数约为2000次,提高了约128倍,而 且简化随N的增加而巨增,因而,用数值方法计算频谱得到实际 应用
6.0 引言：直接计算 DFT 的运算量分析 12 如 N=512、1024 和 8192 时，DFT 的乘法运算 N2 = 5122 = 218 = 262144（26万次） N2 = 10242 = 220 = 1048576（105万次） N2 = 81922 = 226 = 67108864（6千7百万次） • 对于大 N，在实际中是不能接受的，无法“实时”应用 DFT。 一般地，在计算机中，一次加法比一次乘法所需时间要短; 在DSP中，由于乘法用特殊的硬件电路专门完成，因此乘法 和加法所需机器周期相同。 • Cooley 与 Turkey 提出的 FFT 算法，大大减少了计算次数。如 N =512 时，FFT 的乘法次数约为 2000 次，提高了约 128 倍，而 且简化随 N 的增加而巨增，因而，用数值方法计算频谱得到实际 应用
2兀 6.0引言:解决问题的思路wn=eN nk 对称性()=WN=W-n6 n(N-k Nk N 周期性WN=W+n)=WNN+) 可约性WN= N w=Wm 2丌 mnk 兀 mM N 2 e 特殊点:W=1WN2=-1W+N2)=-W
6.0 引言：解决问题的思路 13 * ( ) ( ) ( ) nk nk N n k n N k W W W W N N N N 对称性 ( ) ( ) nk N n k n N k W W W N N N 周期性 nk mnk 可约性 W W N mN / / nk nk m W W N N m 0 / 2 ( / 2) 1 1 k N k N N N WN WN W W 特殊点： 2 j nk nk N W e N Nk nk W W N N nN nk W W N N 2 j mnk mN e 2 2 1 N j N j e e
6.0引言:解决问题的思路 ◇虽然存在不同的FFT方法,但其核心思想大致相同,即通过迭代, 反复利用低点数的DFT完成高点数的DFT计算,以此达到降低运算 量的目的。 令迭代:利用W的周期性、特殊点和对称性,合并DFT计算中很 多重复的计算,达到降低运算量的目的。 ◇低点数:将傅氏变换DFT分解成相继小的DFT计算,即N变小,而 计算量与N2成正比。 口基时间抽取( Decimation in time)FT算法 x[2r [k]→ 2r+1 7=0,1…N 口基2频率抽取( Decimation in frequency)FFT算法 X[m]→ ∫X2m X[2m+1 14
6.0 引言：解决问题的思路 14 基2时间抽取(Decimation in time)FFT算法 1 2 0,1, , [2 1] [2 ] [ ] N r x r x r x k 基2频率抽取(Decimation in frequency)FFT算法 [2 1] [2 ] [ ] X m X m X m 虽然存在不同的 FFT 方法，但其核心思想大致相同，即通过迭代， 反复利用低点数的 DFT 完成高点数的 DFT 计算，以此达到降低运算 量的目的。 迭代：利用 WN kn 的周期性、特殊点和对称性，合并 DFT 计算中很 多重复的计算，达到降低运算量的目的。 低点数：将傅氏变换 DFT 分解成相继小的DFT计算，即 N 变小，而 计算量与 N2 成正比
1.合并法:合并DFT运算中的某些项 2.分解法:将长序列DFT利用对称性、周期性和 可约性,分解为短序列DFT。 例:W=W (4+5) =W4=14 25 17 8 8 8 8 DFT的运算量是与N2成正比的,短序列的 DFT比长序列的DT运算量要小。利用以上特 性,得到改进DFT直接算法的方法
1.合并法：合并DFT运算中的某些项。 2.分解法：将长序列DFT利用对称性、周期性和 可约性，分解为短序列DFT。 1 4 5 4 (4 5) 4 9 W4 W W W 1 8 9 8 17 8 25 W8 W W W 例： DFT的运算量是与N 2成正比的，短序列的 DFT比长序列的DFT运算量要小。利用以上特 性,得到改进DFT直接算法的方法