基2与基4时分FFT算法浅析及其比较_精品.doc

基2与基4时分FFT算法浅析及其比较 学生姓名：田秀军 指导教师：王川龙 摘要：在简要介绍快速傅里叶变换（FFT）相关知识的基础上，研究离散傅里叶变换（DFT）的算法，包括DFT的直接算法、基2时分FFT算法和基4时分FFT算法，并就各算法给出了复杂度分析，并进行了算法间的比较。 关键词：FFT；基2时分蝶式运算定理；基2时分FFT；基4时分FFT 引言：傅里叶变换作为图像分析的重要工具和数字信号处理的重要内容，在图像处理、语音分析、雷达、声呐、地震、通讯系统、遥感遥测、地质勘探、航空航天、生物医学等众多领域都有着极其广泛的应用。于是傅里叶变换的快速算法就有了至关重要的意义。 1、基础知识 1.1、离散傅里叶变换（DFT） 为了在科学计算和数字信号处理等领域使用计算机进行傅立叶变换，必须将函数定义在离散点而非连续域内，且须满足有限性或周期性条件。这种情况下，使用离散傅立叶变换r(n) (1.1.1) 为N点典型有限序列， 式中，W是周期单位复指数序列 W=e (1.1.2) r(n)是单位矩形序列 r(n)= (1.1.3) k为归一化数字频率。 定义2：对长度为N的复序列x(n),称 X(k)=，k=0,1,…,N-1 (1.1.4) 为序列{A}的离散傅里叶变换（DFT）。 1.2、快速离散傅里叶变换（FFT） 快速傅里叶变换计算离散傅里叶变换的一种快速算法，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。 1.3、基2时分蝶式运算定理 内容：设X(k)=DFT[x(n)](0n,kN-1,n,k,为整数，N为偶数)，x(i)=x(2i)，x(i)=x(2i+1)(0i-1，i为整数)。若X(k)=DFT[x(i)]，X(k)=DFT[x(i)]，0k-1，则 (1.3.1) 证明：若0k-1，则 X(k)==+ =+W 由于 W=e= e= W 因此，由（1.3.2）式可得 X(k)= +W = 由于 == 而 W=e=e=-1 因此 = =+ = -W = (证毕)。 1.4、多基时分蝶式运算定理 内容：设X(k)=DFT[x(n)],0n,kN-1,n,k为整数，N=pq，p和q为大于1的正整数。x(i)=x(ip+m),i=0,1,…，q-1；m=0,1,…,p-1。若XI=DFT[x(i)],r=0,1,…,q-1,则 X(k)=X(sq+r)= (1.4.1) （0kN-1,0sp-1,0rq-1,k,s,r均为整数）=X(sq+r)= = == （0kN-1,0sp-1,0rq-1,k,s,r均为整数）= (2.1.1) （k=0,1,…,N-1） 通常所遇到的序列都是实序列，因此 X(k)= (2.1.2) =U(k)-jV(k) （k=0,1,…,N-1） (2.1.3) 式中 U(k) = （k=0,1,…,N-1） (2.1.4) V(k)= （k=0,1,…,N-1） (2.1.5) 2.2、复杂度分析 在整个计算过程中，若不考虑正弦函数和余弦函数的计算量，则直接计算N点DFT所需要的复数乘法次数M和复数加法次数A，由（1.1.1）式容易求得 M=N (2.2.1) A=N(N-1)N (2.2.2) 由于x(n)是实序列，而仅仅是复数，因此上述复数乘法实际上是实数和复数相乘。易知，这样的一次复数乘法相当于两次实数乘法。因此，所需要的实数乘法次数