第四章快速傅里叶变换 §4-2直接计算DFT的起源和改善DF运算效率的途径 一、直接计算DFT的问题 X(k)=∑x(n)0≤k≤N-1 x(n)=1∑X(k)W0≤n≤N-1 设N=10248092 *: N =10 65.5×10 +:N(N-1) 106 65.5×106一、直接计算DFT的问题 ( ) ( ) 0 1 1 0 =    − − = X k x n W k N N n kn N ( ) 0 1 1 ( ) 1 0 =    − − − X k W n N N x n N kn N 第四章 快速傅里叶变换 §4-2 直接计算DFT的起源和改善DFT运算效率的途径 2 ：N +：N(N −1) 6 6 =10 65.510 6 6 =10 65.510 设 N =1024 8092