LTE OFDM、SC-FDMA原理介绍
3.1.3
快速傅里叶变换(FFT)
FFT这宗高效运算方法使DFT的运算效率提高1~2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了良好的条件，大大推动了数字信号处理技术的发展。
2
如前所述，N点DFT复乘次数等于N。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大
m减少。另外，旋转因子WN具有明显的周期性和对称性。其周期性表现为
?j2??m?lN?N?j2?mNW其对称性表现为
m?lNN?e?em ?WNm?mN?mWNN?m??WN或者? WN?WN*WNm?N2m ??WNknFFT算法就是不断地把长序列的DFT分解成几个短序列的DFT，并利用WN的周期性和对称性来减
少DFT的运算次数。
多年来，各种算法层出不穷。本章仅简单介绍时间抽取基2FFT算法。 设序列x(n)的长度为N，且满足
N=2M， M为自然数
按n的奇偶把x(n)分解为两个N/2点的子序列
x1?r??x?2r?x2?r??x?2r?1?则x(n)的DFT为
r=0,1,?,N/2-1
X?k??N?12r?0n?偶数?x?n?WknN?n?奇数?x?n?WknN
2rk?2r?1?k ??x?2r?WN??x?2r?1?WNr?0N?12r?0N?12r?0N?12
2rkk??x1?r?WN?WN?x2?r?WN2rk
由于
W所以
2krN?e?j2?2krN?j?e2?krN2kr?WN
2X?k??N?12r?0?x?r?W1krN2k?WNN?12r?0?x?r?W2krN2k?X1?k??WNX2?k? k = 0,1,?,N-1
普天信息技术研究院有限公司 普院保密二级 第 9 页
LTE OFDM、SC-FDMA原理介绍
其中X1?k?和X2?k?分别为x1?r?和x2?r?的N/2点DFT，即
X1?k??X2?k??N?12r?0?x?r?W12r?0krN2?DFT?x1?r?? ?DFT?x2?r??
N?12?x?r?Wk?N2krN2由于X1?k?和X2?k?均以N/2为周期，且WNk，所以X?k?又可表示为 ??WNkX?k??X1?k??WNX2?k? k = 0,1,?,N/2-1 N??k????X?k???X1k?WNX2k2??这样，就将N点DFT分解为两个N/2点的DFT。上面两式的运算可用图1.2所示的流图符号表示，根据其形状称之为蝶形运算符号。
AA+BCBCA-BC
图 3-2 蝶形运算符号
由图可见，要完成一个蝶形运算，需要一次复数乘和两次复数加法运算。经过一次分解后，计算一个N点DFT共需要计算两个N/2点DFT和N/2个蝶形运算。而计算一个N/2点DFT需要（N/2）2次复数乘和N/2(N/2-1)次复数加法。所以，计算N点DFT总共需要2（N/2）2+N/2=N(N+1)/2?N/2(N>>1时)次复数乘法和N(N/2-1)+2N/2=N2/2次复数加法运算。由此可见，仅仅经过一次分解，就使运算量减少近一半。既然这样分解对减少DFT的运算量是有效的，且N=2M，N/2仍然是偶数，故可以对N/2点DFT再作进一步分解。 3.2
2信号时域、频域概念
时域（时间域）——自变量是时间,即横轴是时间,纵轴是信号的变化。其动态信号x（t）是描述信号在不同时刻取值的函数，如图1。
频域（频率域）——自变量是频率,即横轴是频率,纵轴是该频率信号的幅度,也就是通常说的频谱图。频谱图描述了信号的频率结构及频率与该频率信号幅度的关系，如图2。
普天信息技术研究院有限公司 普院保密二级 第 10 页
LTE OFDM、SC-FDMA原理介绍
1时域信号x(n)0.80.60.40.2x(n) 0-0.2-0.4-0.6-0.8-1 0510152025n3035404550
图 3-3 sinX的时域信号
200信号x(n)的频谱180160140120100806040200 -500-400-300-200-1000100200300400 500
普天信息技术研究院有限公司 普院保密二级 第 11 页
LTE OFDM、SC-FDMA原理介绍
图 3-4 sinX的频域信号
图 3-5 矩形波的时域与频域信号
对信号进行时域分析时，有时一些信号的时域参数相同，但并不能说明信号就完全相同。因为信号不仅随时间变化，还与频率、相位等信息有关，这就需要进一步分析信号的频率结构，并在频率域中对信号进行描述。
同时，当在时域杂乱无章的信号，可能在频域上有很强规律性，反之亦然，如图 3-6，图 3-7, 图 3-6是y（t）=sin（t）+sin（4t）的时域波形，而其在频域的频谱有直观的规律性，如图5，这也是时域与频域转换的一个重要原因。
时域信号10.80.60.40.20-0.2-0.4-0.6-0.8-1 05101520253035404550f1=50Hzf2=200Hz
图 3-6 y（t）=sin（t）+sin（4t）时域波形
普天信息技术研究院有限公司 普院保密二级 第 12 页
