-第3快速疼里叶变换一 (3)W的可约性 nk W=w nmk k nk/m 另外 N/m (N-n)k W,WN2=-1W(+N2)=-W 这样,利用这些特性,使DFT运算中有些项可以合并,并能 使DFT分解为更少点数的DFT运算。而前面已经说到,DFT的运 算量是与M成正比的,所以N小越有利,因而小点数序列的 DFT比大点数序列的DFT的运算量要小。 快速傅里叶变换算法正是基于这样的基本思想而发展起来的 它的算法形式有很多种,但基本上可以分成两大类,即按时间抽 取( D ecimation in Time,缩写为DIT)法和按频率抽取 ( Decimation-in F requency,缩写为法s第3章 快速傅里叶变换 （3） WN nk的可约性 n k m N m n k N nmk mN n k WN W W W / / = , = 另外 k N k N N N N n k N N n k N n N k WN = W = W W = − W = −W ( − ) ( − ) − / 2 ( + / 2) , 1, 这样，利用这些特性，使DFT运算中有些项可以合并，并能 使DFT分解为更少点数的DFT运算。而前面已经说到，DFT的运 算量是与N2成正比的，所以N越小越有利，因而小点数序列的 DFT比大点数序列的DFT的运算量要小。 快速傅里叶变换算法正是基于这样的基本思想而发展起来的。 它的算法形式有很多种，但基本上可以分成两大类，即按时间抽 ( Ｄecimation in Time，缩写为DIT）法和按频率抽取 （Decimation in Ｆrequency， 缩写为DIF）法