一种在多核嵌入式平台上实现FFT的快速并行算法

Fast parallel algorithm for FFT based on multi-core embedded platform

快速傅里叶变换(fast Fourier transform,FFT)算法是对实时数字信号进行快速分析处理的一种基本方法。针对多核嵌入式实时环境下并行FFT算法进行了研究,以有效提高实时信号处理的速度。提出了一种新的静态多项式FFT算法,充分利用静态多项式奇偶项的不同特点直接代入数据计算,免去了层层迭代的计算过程,减少了运算过程中的通信,提高了并行性能。对算法的理论进行了严密论证,通过嵌入式实时平台上运行测试和仿真实验,证实了在数据分段较短的约束条件下,提出算法较经典的FFT并行算法在时间复杂度上有一定优势。多项式静态FFT算法能够有效提高并行FFT运行速度。

Fast Fourier transform algorithm is a basic method for fast analysis and processing of real time digital signals. In order to improve the speed of real-time signal processing, this paper studied the parallel FFT algorithm based on multi-core embedded real-time environment and put forward a new static FFT algorithm. The algorithm made full use of the different charac- teristics of the odd and even items of the static polynomial, to avoid the iterative calculation process of layers, reduce the communication operation in the process of improving the performance of parallel. This paper proved the algorithm in theory, and tested the operating efficiency of the algorithm on the embedded real-time platform. It is confirmed that the polynomial static algorithm has certain time complexity advantages for processing short data segment, compared to classical FFT algorithm. It concludes that polynomial static FFr algorithm can effectively improve the running speed of parallel FFT algorithm.