王 丹，许 虎

（重庆邮电大学 通信与信息工程学院，重庆400065）

在数字信号处理中，离散傅里叶变换(DFT)是常用的变换方法，它在各种数字信号处理系统中扮演着重要的角色。快速傅里叶变换(FFT)[1-2]是离散傅里叶变换的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅里叶变换的算法进行改进获得的，两者都是为了将信号变换到频域并进行相应的频谱分析。对于实时性要求很强的信号处理来说，运算速度对整个处理的影响是显而易见的。因为FFT拥有很高的运算能力，使其在无线通信和数字通信、高速图像处理、匹配滤波等领域得到极为广泛的应用。

LTE作为准4 G技术，以正交频分复用OFDM和多输入多输出MIMO技术为基础，下行采用正交频分多址（OFDM）技术，上行采用单载波频分多址（SC-FDMA）技术，在20 MHz频谱带宽下能够提供下行100 Mb/s和上行 50 Mb/s的峰值速率[3]。

频域分析比时域分析更优越，不仅简单，且易于分析复杂信号[4]。在LTE系统中，FFT算法主要应用于基带信号生成、信号的接收和检测等，将时域信号转移到频域进行处理。

1 FFT算法分析

设x(n)为N点的有限长度序列，其DFT正变换为：

假设输入序列x(n)长度为N=2M，M是正整数。如果不满足这个条件，在序列尾部人为地加上若干零值点，使其达到这一要求。将序列x(n)按n的奇偶分解为两个N/2点的子序列：

按以上步骤继续分为奇偶组，直到分解两个点的DFT为止。图1是使用FFT算法和直接DFT算法总运算量与抽样点数N的关系图。

序列x(n)逆变换（IDFT）连续取两次共轭有：

这样逆变换也可以直接调用FFT子程序。……