一种实序列FFT算法改进及其在DSP上的实现

摘要

Fast Fourier Transform（FFT） is one of most important digital signal processing algorithms. The normal FFT theory of the 2N real-valued is analyzed and a improved algorithms is introduced in this paper. The algorithms computer the odd number and even number sequence separately, the common factor of the twiddle factors is extracted, it reduced the number of addition and multiplication and the reference number of twiddle factors in the computer process enormously. The algorithms is implemented on the actual DSP platform, the data of experiment revealed the algorithms has a sizeable improvability in complexity and operation efficiency.%FFT是数字信号处理最重要的算法之一,论文分析了常规的2N点按时间抽选的实序列FFT运算的基本原理,介绍了一种改进的算法,算法将奇数序列和偶数序列部分开计算,并提取旋转因子的公因子,大大减少了计算过程中的加法和乘法的个数和旋转因子的引用次数,并在实际的DSP平台上进行了实现,实验数据表明,该算法在运算效率和复杂度上都较传统FFT算法有较大的改进。