《实验一. FFT 1． 实验要求 设计一个按照时间抽取的基2快速傅里叶变换 bb》由会员分享，可在线阅读，更多相关《实验一. FFT 1． 实验要求 设计一个按照时间抽取的基2快速傅里叶变换 bb（8页珍藏版）》请在金锄头文库上搜索。
1、实验一. FFT1 实验要求设计一个按照时间抽取的基2快速傅里叶变换基2FFT-DIT。输入倒位序，输出自然顺序。2 实验原理快速傅里叶变换 fast Fourier transform 计算离散傅里叶变换的一种快速算法,简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数N越多,FFT算法计算量的节省就越显著。 当用数字计算机计算信号序列x(n)的离散傅里叶变换时，它的正变换 (1) 反变换(IDFT)是 (2) 式中、x(n)和X(k)可以是实数或复数。由上式可见,要计算一个抽样序
2、列就需要做N次复数乘法运算及N-1次复数加法运算。 计算离散傅里叶变换的快速方法，有按时间抽取的FFT算法和按频率抽取的FFT算法。前者是将时域信号序列按偶奇分排,后者是将频域信号序列按偶奇分排。它们都借助于的两个特点:一是的周期性；另一是的对称性，这里符号*代表其共轭。这样,便可以把离散傅里叶变换的计算分成假设干步进行，计算效率大为提高。 时间抽取取法 令信号序列的长度为N2M,其中M是正整数，可以将时域信号序列x(n)分解成两局部，一是偶数局部x2n，另一是奇数局部x2n+1，其中。于是信号序列x(n)的离散傅里叶变换可以用两个 N/2抽样点的离散傅里叶变换来表示和计算。考虑到和离散傅里叶
3、变换的周期性,式(1)可以写成 (3) 其中 (4a) (4b) 由此可见，式(4)是两个只含有N/2个点的离散傅里叶变换，G(k)仅包括原信号序列中的偶数点序列，H(k)那么仅包括它的奇数点序列。虽然k=0，1，2，N-1，但是G(k)和H(k)的周期都是N/2,它们的数值以N/2周期重复。 因为于是由式(3)和式(4)得到 (5a) (5b) 因此,一个抽样点数为N 的信号序列 x(n)的离散傅里叶变换，可以由两个 N/2抽样点序列的离散傅里叶变换求出。依此类推，这种按时间抽取算法是将输入信号序列分成越来越小的子序列进行离散傅里叶变换计算，最后合成为N点的离散傅里叶变换。 通常用图1中蝶形
4、算法的信号流图来表示式(5)的离散傅里叶变换运算。例如，N823的抽样点的信号序列x(n)的离散傅里叶变换,可用如图2所示的FET算法的信号流图来计算。由图可知 N=2M点的离散傅里叶变换的计算全由蝶形运算组成，需要M级运算,每级包括N/2个蝶形运算，总共有 个蝶形运算。所以，总的计算量为次复数乘法运算和N log2N次复数加法运算。 FFT算法按级迭代进行，计算公式可以写成 (6) N抽样点的输入信号具有N个原始数据x0(n),经第一级运算后，得出新的N个数据x1(n)，再经过第二级迭代运算，又得到另外N个数据x2(n)，依此类推，直至最后的结果x(k)xM(k)X(k)在逐级迭代计算中，每
5、个蝶形运算的输出数据存放在原来存贮输入数据的单元中，实行所谓“即位计算，这样可以节省大量存放中间数据的存放器。 蝶形运算中加权系数随迭代级数成倍增加。由图2可以看出系数的变化规律。对于N=8,M=3情况,需进行三级迭代运算。在第一级迭代中，只用到一种加权系数;蝶形运算的跨度间隔等于1。在第二级迭代中，用到两种加权系数即、；蝶形运算的跨度间隔等于2。在第三级迭代中，用到4种不同的加权系数即、；蝶形运算的跨度间隔等于4。可见,每级迭代的不同加权系数的数目比前一级迭代增加一倍；跨度间隔也增大一倍。 输入数据序列x(n)需重新排列为x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、
6、x(7),这是按照二进制数的码位倒置所得到的反序数，例如N=8中数“1的二进制数为“001，将其码位倒转变为“100，即为十进制数“4。 1倒位序的实现将输入序列的序号用位二进制数表示：，那么倒位序二进制数就是：，这样，原来放的单元现在放。01234567正位序000001010011100101110111倒位序000100010110001101011111由表可知：按正为序自然顺序排列的二进制数，后面一个数总是比前面一个数大1，即按正位加法运算；而按反位序排列的二进制数，后面一个数总是在前面一个数的最高位上加1，并由高位向低位进位而得到。由以上分析可知，所谓的倒位序在本质上就是“反向进位
7、加法。FFT变址流程图如图一所示。设A(I)表示存放原自然顺序输入数据的内存单元，A(J)表示存放倒位序数的内存单元，I,J=0，1，2， ，N-1。当I=J时不用变址；而当IJ，J的最高位为0，只要把该位变为1与K相加，就可得到下一个倒位序数，如果K=J，那么J的最高位为1，只要把该位便为0与K相减。然后判断次高位，这可与K/2相比拟，假设次高位为0，只要把该位变为1J与K/2相加，假设次高位为1，只要把该位变为0J与K/2相减。按上述规律检查下一位，最终获得新的倒位序数J，当I=JA(J)A(J)+A(I);A(I)A(J)-A(I);A(J)A(J)-A(I);K=N/2KJJJ+K;I
8、=I+1;I=N-1J=J-K;K=K/2;NYNY图一输入倒位序LE=1LEI=LE;LEN-1?U=U*W;J=J+1;JLEI-1?M=M+1ML?NNN图二3结果与分析1函数为FFT算法的实现。是一个按照时间抽取的基-2快速傅里叶变换基-2 FFT-DIT。输入倒位序，输出自然顺序。对于函数实现的按时间抽取的基2 FFT运算，在MATLAB命令行输入以下命令： k=linspace(0,4*pi,16); xn=sin(k); N=16; XK=ditfft(xn,N)运行结果如下：XK = 0.0000 -0.8008 - 1.1984i -0.5553 - 0.5553i -0.4
9、885 - 0.3264i -0.4609 - 0.1909i -0.4452 -0.4487 + 0.0893i -0.4885 + 0.3264i -0.5553 + 0.5553i -0.8008 + 1.1984i 2.8658 - 6.9186i由此可得出：对于输入的奇对称序列xn=sin(k)，其输出的频谱序列也是奇对称的。在MATLAB命令行输入以下命令： xn=linspace(1,8,8); N=8; XK=ditfft(xn,N)运行结果如下：XK = 36.0000 -4.0000 - 9.6569i -4.0000 - 4.0000i -4.0000 -4.0000 +
10、 4.0000i由此可得出：对于输入的实数序列xn=linspace(1,8,8)，其输出的频谱序列实部为偶对称，虚部为奇对称的。通过以上例子，我们简要分析了离散数字信号经DFTFFT就是DFT的快速算法后离散谱的一些特点，发现了离散傅里叶变换的一些性质：奇对称序列的频谱序列也是奇对称的；实数序列的频谱序列实部为偶对称，虚部为奇对称的。当然经过详细分析我们还会得出一些其他奇，偶，虚，实关系，以及线性性质，序列的圆周移位，对偶性，圆周共轭对称性,在此就不一一列举了。2实现用两个N点FFT计算一个长度为2N的实数序列的2N点离散傅里叶变换。在MATLAB命令行输入以下命令： xn=1:8; N=8; XK=exam1_2(xn,N)运行结果如下：XK = 36.0000 -4.0000 - 1.6569i -4.0000 -4.0000 + 1.6569i -4.0000 + 4.0000i在输入MATLAB自带函数fft验证上述结果 xk=fft(xn,N)xk = 36.0000 -4.0000 - 4.0000i -4.0000 - 1.6569i -4.0000 -4.0000 + 1.6569i -4.0000 + 4.0000i二者结果相同，因此exam1_2.m实现了用两个N点FFT计算一个长度为
