首页|嵌入式系统|显示技术|模拟IC/电源|元件与制造|其他IC/制程|消费类电子|无线/通信|汽车电子|工业控制|医疗电子|测试测量
首页 > 分享下载 > 嵌入式系统 > 【转】数字信号处理 教案 ---- 4、快速傅立叶变换(FFT)

【转】数字信号处理 教案 ---- 4、快速傅立叶变换(FFT)

资料介绍
【转】数字信号处理 教案 ---- 4、快速傅立叶变换(FFT)

【转】 数字信号处理 教案 ---- 4、快速傅立叶变换(FFT)
第四章 快速傅立叶变换(FFT)
4.1引言
快速傅立叶变换(FFT)并不是一种新的变换,而是离散傅立叶变换(DFT)的一种快速
算法。
DFT的计算在数字信号处理中非常有用。例如在FIR滤波器设计中会遇到从h(n)求H(k)或
由H(k)计算h(n),这就要计算DFT;信号的谱分析对通信、图像传输、雷达等都是很重要
的,也要计算DFT。因直接计算DFT的计算量与变换区间长度N的平方成正比,当N较大时
,计算量太大。
自从1965年图基(J. W. Tukey)和库利(T. W. Coody)在《计算数学》(Math.
Computation , Vol. 19,
1965)杂志上发表了著名的《机器计算傅立叶级数的一种算法》论文后,桑德(G. Sand)-
图基等快速算法相继出现,又经人们进行改进,很快形成一套高效运算方法,这就是快
速傅立叶变换简称FFT(Fast Fourier
Transform)。这种算法使DFT的运算效率提高1~2个数量级。
4.2 基2 FFT算法
一、直接计算DFT的问题及改进的途径
设x(n)为N点有限长序列,其DFT正变换为
[pic]= [pic], k=0,1,…,N-1
其反变换(IDFT)
x(n)= [pic],n=0,1,…,N-1
二者的差别只在于[pic]的指数符号不同,以及差一个常数乘因子1/N,因而下面我们只
讨论DFT正变换的运算量,反变换的运算量是完全相同的。
考虑x(n)为复数序列的一般情况,每计算一个X(k),需要N次复数乘法以及(N-
1)次复数加法。因此,对所有N个k值,共需N2次复数乘法及
N(N-
1)次复数加法运算。所以直接计算DFT,乘法次数和加法次数都是和N……
【转】数字信号处理 教案 ---- 4、快速傅立叶变换(FFT)
本地下载

评论