面向高数据并行架构的原位 FFT 算法  

An in-place FFT algorithm for high data parallelism architecture

作　　者：王向前[1] 郑启龙[3] 王昊[2] 洪一[1,2] 张磊[1] 

机构地区：[1]合肥工业大学计算机与信息学院,安徽合肥230009 [2]中国电子科技集团公司第三十八研究所,安徽合肥230088 [3]中国科学技术大学计算机科学与技术学院,安徽合肥230027

出　　处：《中国科学技术大学学报》2015年第7期608-613,共6页JUSTC

摘　　要：数字信号处理器的内存较小,而且数字信号处理领域的应用往往是数据密集型,这要求在设计数字信号处理应用算法时既要考虑时间复杂度又要兼顾算法的空间复杂度.为此提出了一种原位的逆序算法;针对数字信号处理器比较高的内存访问并行度,设计了部分逆序的原位高效FFT算法;并在魂芯DSP平台上实现了该算法框架.实验表明,与非原位FFT算法相比,该原位算法的空间复杂度大幅降低而时间效率的损失在可接受范围之内.The on‐chip memory in DSP is small ,and applications for DSP are often data‐intensive ,which requires that space complexity as well as time complexity must be considered when algorithms are designed .So a in‐place bit reverse algorithm was proposed .Then ,to take advantage of memory bandwidth offered by DSP ,an effective in‐place FFT algorithm with part bit reverse was designed and implemented on BWDSP . Experiment result shows that , compared with the out‐of‐place FFT algorithm , its space complexity is significantly reduced ,while the loss of time efficiency for the proposed in‐place FFT algorithm is acceptable .

关 键 词：逆序 原位 FFT 空间复杂度 时间复杂度 

分 类 号：TN957[电子电信—信号与信息处理]