DFT算法存在的问题 N点DFT的复乘次数与N的平方成比例,显然N较小时 乘法次数大大减少。利用上述旋转因子的特性,可以 将有些项合并,并将DFT分解为短序列,从而降低运 算次数,提高运算速度。 1965年,库利(ooey)和图基( Tukey)首先提出FT算 法。对于N点DFT,仅需(N②2)og2N次复数乘法运算。 例如N=1024=210时,需要(1024/2)og2210 =512*10=5120次。5120/1048576=488%,速度 提高20倍。 ·分为时域抽取(DIT)和频域抽取(DIF)两大类。DFT算法存在的问题 • N点DFT的复乘次数与N的平方成比例，显然N较小时 乘法次数大大减少。利用上述旋转因子的特性，可以 将有些项合并，并将DFT分解为短序列，从而降低运 算次数，提高运算速度。 • 1965年，库利(cooley)和图基(Tukey)首先提出FFT算 法。对于N点DFT，仅需(N/2)log2N 次复数乘法运算。 例 如 N=1024=2 10 时 ， 需 要 (1024/2)log2 2 10 =512*10=5120次。5120/1048576=4.88% ，速度 提高20倍。 • 分为时域抽取（DIT）和频域抽取（DIF）两大类