DFT算法存在的问题 >N点DFT的直接计算量 1.乘法次数: 对每一个k:N次复数乘法【4N次实乘和2N次实加】 1个复乘等于4四个实乘和2个实加;(+c+1=c-M+b+m 了N个k 次复数乘法 2.加法次数: ·对每一个k:N-1次复加【2(N-1)次实加】 N个k:N(N-1)次复加 即和N成正比 例N=1024,则有1048576次复乘(约400万次实乘),假 定运算器的指令速度为100MIPS,则计算时间大约为4秒。➢N点DFT的直接计算量: DFT算法存在的问题 1. 乘法次数： 对每一个k：N次复数乘法【4N次实乘和2N次实加】 1个复乘 等于 4 四个实乘和 2 个实加； N个k： 次复数乘法 2. 加法次数： • 对每一个k： N－1次复加【2（N－1）次实加】 • N个k： N（N－1）次复加 即和 成正比。 2 N 例N＝1024，则有1048576次复乘（约400万次实乘），假 定运算器的指令速度为100MIPS，则计算时间大约为4秒。 2 N (a + jb)(c + jd) = ac − bd + j(cb + ad)