资源描述：
《基2与基4时分FFT算法浅析及其比较论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、基2与基4时分FFT算法浅析及其比较学生姓名：田秀军指导教师：王川龙摘要：在简要介绍快速傅里叶变换（FFT）相关知识的基础上，研究离散傅里叶变换（DFT）的算法，包括DFT的直接算法、基2时分FFT算法和基4时分FFT算法，并就各算法给出了复杂度分析，并进行了算法间的比较。关键词：FFT；基2时分蝶式运算定理；基2时分FFT；基4时分FFT引言：傅里叶变换作为图像分析的重要工具和数字信号处理的重要内容，在图像处理、语音分析、雷达、声呐、地震、通讯系统、遥感遥测、地质勘探、航空航天、生物医学等众多
2、领域都有着极其广泛的应用。于是傅里叶变换的快速算法就有了至关重要的意义。1、基础知识1.1、离散傅里叶变换（DFT）为了在科学计算和数字信号处理等领域使用计算机进行傅立叶变换，必须将函数定义在离散点而非连续域内，且须满足有限性或周期性条件。这种情况下，使用离散傅立叶变换。定义1：称Keg(k,n)=Wr(n)(1.1.1)为N点典型有限序列，式中，W是周期单位复指数序列W=e(1.1.2)r(n)是单位矩形序列r(n)=(1.1.3)k为归一化数字频率。定义2：对长度为N的复序列x(n),称X(
3、k)=，k=0,1,…,N-1(1.1.4)为序列{A}的离散傅里叶变换（DFT）。1.2、快速离散傅里叶变换（FFT）快速傅里叶变换计算离散傅里叶变换的一种快速算法，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。91.3、基2时分蝶式运算定理内容：设X(k)=DFT[x(n)](0n,kN-1,n,k,为整数，N为偶数)，x(i)=x(2i
4、)，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因此==+9=-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
5、。若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(k)=X(sq+r)====（0kN-1,0sp-1,0rq-1,k,s,r均为整数）（证毕）。2、DFT的直接算法2.1、算法直接按DFT的定义式进行计算：按照DFT的定义式有X(k)==(2.1.1)（k=0,1,…,N-1）通常所遇到的序列都是实序列，因此X(k)=(2.1.2)=U(k)-jV(k)（k=0,1,…,N-1）(
6、2.1.3)式中U(k)=（k=0,1,…,N-1）(2.1.4)9V(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)是实序列，而仅仅是复数，因此上述复数乘法实际上是实数和复数相乘。易知，这样的一次复数乘法相当于两次实数乘法。因此，所需要的实数乘法次数M=2N(2.2.3)由于
7、1次复数加法运算相当于2次实数相加，因此所需要的实数加法次数A=2N(N-1)2N(2.2.4)在x(n)为复序列的一般情况下，由于两个复数相乘需要4次实数相乘和2次实数相加，因此与（2.2.1）是相当的实数乘法次数为M=4N(2.2.5)同时需要的实数加法次数=2N(2.2.6)考虑到（2.2.3）式所需要的实数加法次数，因此，总共所需要的实数加法次数A4N(2.2.7)由此可见，无论是复数运算次数还是实数运算次数都表明，直接计算DFT时的运算量与N成正比。当N较大时，如N=2048，运算量将
8、是巨大的，运算时间长。3、基2时分FFT算法3.1、基本思想与原理基2FFT算法是把长度N=2的序列一分为二，将N点DFT表示为两个N/2点DFT的线性组合。然后再把N/2点DFT一分为二，表示为两个N/4点的D9FT。如此重复下去，直至分解成两点DFT的运算，两点DFT实际上只是加减运算。1.3节中的基2时分蝶式运算定理是基2时分FFT算法的基础。相应的运算称为蝶式运算。相应的运算流图称为运算蝶。基2时分蝶式运算定理表明：若将任何一偶数点序列按n的奇偶性分为两个子列，则原序列的DFT可由两子序
