摘要
基于一维 DFT变换为多维 DFT的公因子算法 CFA,提出一种有效的修剪算法 .该算法首先利用 CFA算法将 DFT分解为内外两层若干组一维小点数 DFT,然后针对其特点对内外两层分别进行修枝 ,最大限度地减少了冗余计算 ,同时可实现任意点数截取或抽选输出
A efficient pruning algorithm based on the common factor algorithm which decomposes one dimension DFT to several dimension is proposed here. After decomposing the DFT to outside part and inside part that each composed a certain number of small size DFT, the algorithm can prune the outside layer and inside layer separately. The new algorithm can reduce the redundant computation to a minimum and realize the DFT when only fewer than N outputs are needed to compute or only a few inputs are nonzero.
