数字信号处理快速傅里叶变换(FFT)姚

1、第3章 快速(kui s)傅里叶变换(FFT) 共五十一页3.5 引言(ynyn) DFT是信号分析与处理中的一种重要(zhngyo)变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。 共五十一页3.5 基2FFT算法(sun f) 3.5.1 直接计算DFT的特点及减少(jinsho)运算量的基本途径 长度为N的有限长序列x(n)的DFT为 考虑x(n)为复数序列的一般情况，对某一个k值，直

2、接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。 (3.2.1) 共五十一页 如前所述，N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外(ln wi)，旋转因子WmN具有明显的周期性和对称性。其周期性表现为(3.2.2) 其对称性表现(bioxin)为或者 共五十一页 3.5.2 时域抽取(chu q)法基2FFT基本原理 FFT算法基本上分为两大类：时域抽取法FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取法FFT(Decimation In Frequency FFT,简称DIF

3、FFT)。下面先介绍DIFFFT算法。 设序列x(n)的长度为N，且满足为自然数 按n的奇偶把x(n)分解(fnji)为两个N/2点的子序列共五十一页 则x(n)的DFT为由于(yuy)所以(suy) 共五十一页 其中(qzhng)X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即 (3.2.5) (3.2.6) 由于X1(k)和X2(k)均以N/2为周期(zhuq)，且 ，所以X(k)又可表示为(3.2.7) (3.2.8) 共五十一页图4.2.1 蝶形运算(yn sun)符号 共五十一页图4.2.2 N点DFT的一次时域抽取(chu q)分解图(N=8) 共五十一页 与

4、第一次分解相同，将x1(r)按奇偶分解成两个(lin )N/4长的子序列x3(l)和x4(l)，即那么(n me)，X1(k)又可表示为 (3.2.9) 共五十一页式中 同理，由X3(k)和X4(k)的周期性和Wm N/2的对称(duchn)性 Wk+N/4 N/2=-Wk N/2 最后得到： (3.2.10) 共五十一页 用同样(tngyng)的方法可计算出(3.2.11)其中(qzhng) 共五十一页图3.2.3 N点DFT的第二次时域抽取(chu q)分解图(N=8) 共五十一页 图3.2.4 N点DITFFT运算(yn sun)流图(N=8) 同址(原位)计算共五十一页 3.5.3 D

5、ITFFT算法与直接计算DFT运算量的比较1.蝶形运算及运算量的比较 每级由N/2个蝶形组成,每一级运算都需要N/2次复数(fsh)乘和N次复数(fsh)加(每个蝶形需要两次复数(fsh)加法)。所以，M级运算总共需要的复数乘次数为复数(fsh)加次数为 例如，N=210=1024时共五十一页 2. 序列的倒序或变址计算 DITFFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于(yuy)N=2M，所以顺序数可用M位二进制数(nM-1nM-2n1n0)表示。 图4.2.7 形成(xngchng)倒序的树状图(N=23) 共五十一页表4.2.1 顺序(shnx)

6、和倒序二进制数对照表 共五十一页 图4.2.8 倒序(do x)规律 共五十一页 图4.2.9 倒序(do x)程序框图 共五十一页 3.5.4 频域抽取法FFT(DIFFFT) 在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIFFFT。 设序列x(n)长度为N=2M，首先(shuxin)将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：共五十一页偶数(u sh) 奇数(j sh) 将X(k)分解成偶数组与奇数组，当k取偶数(k=2r,r=0,1,N/2-1)时 共五十一页当k取奇数(j sh)(k=2r+1,r=0,1,N/2-1)时(3.2.15) 将x1

7、(n)和x2(n)分别(fnbi)代入(4.2.14)和(4.2.15)式，可得 (3.2.16) 共五十一页图3.2.10 DIFFFT蝶形运算(yn sun)流图符号 共五十一页图3.2.11 DIFFFT一次分解(fnji)运算流图(N=8) 共五十一页图3.2.12 DIFFFT二次分解(fnji)运算流图(N=8) 共五十一页图3.2.13 DIFFFT运算(yn sun)流图(N=8) 共五十一页图3.2.14 DITFFT的一种(y zhn)变形运算流图共五十一页 3.5.6 IDFT的高效算法(sun f) 上述FFT算法流图也可以用于离散傅里叶逆变换(Inverse Disc

8、rete Fourier Transform，简称IDFT)。比较DFT和IDFT的运算公式： 共五十一页图4.2.16 DITIFFT运算(yn sun)流图 共五十一页 如果希望直接调用FFT子程序计算IFFT，则可用下面的方法(fngf)： 由于 对上式两边(lingbin)同时取共轭，得共五十一页 3.5.7 实序列的FFT算法 设x(n)为N点实序列，取x(n)的偶数点和奇数点分别(fnbi)作为新构造序列y(n)的实部和虚部，即对y(n)进行(jnxng)N/2点FFT，输出Y(k)，则 根据DITFFT的思想及式(3.2.7)和(3.2.8)，可得到 共五十一页 3.6 N为合数

9、(hsh)的FFT算法 P90共五十一页3.7 FFT 的应用(yngyng) DFT的快速算法FFT的出现， 使DFT在数字通信、 语言信号处理、 图像处理、 功率谱估计、 仿真、 系统分析、 雷达理论、 光学、 医学、 地震以及数值分析等各个领域都得到广泛应用。3.7.1 四种傅立叶变换1、非周期连续时间(shjin)信号的傅立叶变换（FT）共五十一页 2、周期连续(linx)时间信号的傅立叶级数（FS）3、序列傅立叶变换共五十一页 4、周期序列(xli)的傅立叶级数（DFS）注意周期性、离散性在时域和频域中的对称共五十一页 3.7.2 用FFT对信号进行谱分析 所谓信号的谱分析就是计算信

10、号的傅里叶变换。 连续信号与系统的傅里叶分析显然不便于直接用计算机进行计算， 使其应用受到限制， 而DFT是一种时域和频域均离散化的变换， 适合数值运算， 成为分析离散信号和系统的有力工具。 1. 用DFT对连续信号进行谱分析 工程(gngchng)实际中， 经常遇到的连续信号xa(t)， 其频谱函数Xa(j)也是连续函数。 共五十一页 设连续(linx)信号xa(t)持续时间为tp， 最高频率为fc， xa(t)的傅里叶变换为： 对xa(t)以采样间隔T1/2fc(即fs=1/T2fc)采样得 xa(nT)。 设共采样N点， 并对Xa(jf)作零阶近似(t=nT, dt=T)得共五十一页 显

11、然， Xa(jf)仍是f的连续周期函数(zhu q hn sh), xa(nT)和X (jf)如图3.4.5(b)所示。 对 X(jf)在区间0, fs上等间隔采样N点， 采样间隔为F，F也叫频率分辨率 如图3.4.5(c)所示。 参数fs 、 tp、 N和F满足如下关系式： 由于NT=tp， tp为信号的观测时间(shjin)，所以 N越大,F越小,分辨率越高共五十一页 共五十一页频谱分析(fnx)的步骤1.数据(shj)准备 已知2.用FFT计算频谱共五十一页 计算振幅谱 相位(xingwi)谱 功率谱例P93共五十一页 3.7.3 用DFT计算(j sun)线性卷积 如果0kL-1则由时

12、域循环(xnhun)卷积定理有 Y(k)=DFTy(n)=X1(k)X2(k), 0kL-1共五十一页 由此可见， 循环卷积既可在时域直接计算， 也可以按照图3.4.1所示的计算框图， 在频域计算。 由于DFT有快速(kui s)算法FFT， 当N很大时， 在频域计算的速度快得多， 因而常用DFT(FFT)计算循环卷积。 图 3.4.1 用DFT计算(j sun)循环卷积 共五十一页图 3.4.3 用DFT计算(j sun)线性卷积框图 共五十一页计算(j sun)量的比较N=M81610244096r0.570.9429.2100共五十一页 重叠(chngdi)相加法 当N和M相差很大时,则

13、用FFT计算时,需要在长度较短的序列后面补很多零,这样计算线性卷积效率并不高. 处理方法: 可将长度较长的序列分段处理,从而(cng r)不用补很多0,提高计算效率.共五十一页 设序列h(n)长度(chngd)为N， x(n)为无限长序列。 将x(n)均匀分段， 每段长度(chngd)取M， 则于是(ysh)， h(n)与x(n)的线性卷积可表示为(3.4.4) 共五十一页重叠相加法处理(chl)步骤共五十一页图 3.4.4 重叠(chngdi)相加法卷积示意图 共五十一页 重叠(chngdi)保留法 P97共五十一页内容摘要第3章 快速傅里叶变换(FFT)。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。例如，