一类素因子分解FFT算法

On Overcoming Scrambling in Existing Prime Factor Algorithm (PFA) of Fast Fourier Transform (FFT)

提出了一类新的素因子分解ＦＦＴＸ法（ＰＦＡ）．该算法可以用非同址的方式实现，也可以用同址的方式实现；既可以输入输出皆为同一顺序而不需要混序，也可以输入输出不为同一顺序而需要混序．同时，还具有新的算法结构，在计算每一维的小数ＤＦＴ时，需要变换数据模块的地址．理论分析与计算机仿真实验证明，与传统ＰＦＡ相比，本文算法可无需混序操作，易于扩展，可同址运算和顺序输入输出，能节省存贮量，提高运算速度。

Prime factor algorithm (PFA) of fast Fourier trasform (FFT) has been improved so that it can be computed in place in order and is widely used in stunal processing, but it suffers from scrambling. We now present a way of overcoming this undesirable scrambling.That existing PFA meets with the troublesome scrambling is due to the index mapping method it uses. My most important contribution in this paper is the proposal of a different Index mapping which is mathematiCally executed with the help of eq. (2c). Eq. (2c) transfers large point one dimensional FFT to small point multldimensional FFT. Each of the latter is computed with small point data rotating in each dimension. Thus frequency index of my PFA is in order with that of take index of input data as shown in Fig. 1 and so scramblingis eliminated.