一类素因子分解FFT算法的指标映射

结合ＣＦＡ和ＰＦＡ分解数据序列的方式，即所谓指标映射，建立了ＣＦＡ与ＰＦＡ之间的映射关系。它表明ＰＦＡ可按多种方式执行，如同址顺序、非同址顺序、非同址非顺序、同址非顺序。由这种关系建立的新ＰＦＡ算法具有与传统ＰＦＡ完全不同的结构。在新ＰＦＡ算法中，用于计算每一维的小点数ＦＦＴ的数据是按顺序直接从存贮器中提取的，其中地址的确定是按模Ｎ１或模Ｎ２取合，而传统算法中则按模Ｎ１Ｎ２取余。因此新ＰＦＡ算法的地址产生所需的计算量只有传统ＰＦＡ算法的地址产生所需计算量的一半。新算法不需要用余数定理作为指标映射的工具。

Index Mappings of a New Kind of Prime Factor Algorithm of FFT

The common factor algorithm of FFT(CFA)and traditional prime factor algorithm of FFT(PFA) have been combined in this paper such that new index mappings for PFA are obtainable and they can be implemented in any of the following four ways:in place in order,non in place in order, in place non in order, and non in place non in order.Address generation for computing FFT is obtained by evaluating index mapping modulo N1 and modulo N2respectively rather than modulo N1 N2 as is done in traditional PFA. Thus the number of computations is reduced by 50% as compared with that of traditional PFA. New PFA algorithm does not depend upon Chinese Remainder Theorem.