第03章-6 N为合数的FFT算法(6)

数字信号处理

在最一般的情况下，设 N=p1p2···pm,其中p1~pm是m个素因子。首先把N分解为两个因 子，即N=p1q1,其中q1=p2p3···pm,并用以上讨论的方法将DFT分解 为p1个q1点DFT; 然后，将q1分解为q1=p2q2,其中q2=p3p4···pm,即将 每一个q1点DFT分解为p2个q2 点DFT;这样，通过m次分解，最后达 到pm点 DFT。这种算法可以使DFT的运算获得最高效率。