几种特殊的FFT算法

1、7-3 按频率抽取的FFT算法,一、离散傅立叶反变换（IDFT）的快速变换（IFFT） 二、N为组合数的FFT算法 三、实数序列的FFT,2020/7/10,2,一、离散傅立叶反变换（IDFT）的快速变换（IFFT）,2020/7/10,3,2020/7/10,4,直接调用FFT子程序计算IFFT的方法：,2020/7/10,5,二、 N为组合数的FFT算法,N为组合数的FFT（任意基数的FFT算法） 以上讨论的都是以2为基数的FFT算法，即N=2M，这种情况实际上使用得最多，其优点是程序简单，效率很高，使用起来非常方便，实际应用时，有限长序列的长度N很大程度上由人为因素确定，因此多数场合可取

2、N=2M，从而直接使用以2为基数的FFT算法。,2020/7/10,6,如N不能人为确定，N的数值也不是以2为基数的整数次方，处理方法有两种:, 补零，将x(n)补零，使N=2M。,例如N=30，补上x(30)=x(31)=0两点，使N=32=25，这样可直接采用以2为基数M=5的FFT程序。,采用任意数基数的DFT算法,如要求准确的N点DFT值，可采用任意数为基数的DFT算法，计算效率低于以2为基数FFT算法。,2020/7/10,7,设N可以表示为若干因子的乘积,我们定义,则,这样，我们可把输入序列分解成p1个子序列，每个子序列由q1个取样组成。,2020/7/10,8,因而,2020/7

3、/10,9,利用关系式,令,因此,上式说明，当N为组合数时，序列x(n)的离散傅立叶变换X（k）可借助于P1个序列长度为其q1的DFT来表示。,2020/7/10,10,例：讨论一个长N18点序列x（n）的DFT快速计算问题。 解：因为N18332 令p13，q16 首先将原始序列分成p13个子序列，每个子序列长度q1=6个取样 序列1（L=0）;x(0), x(3), x(6), x(9), x(12), x(15) 序列2（L=1）;x(1), x(4), x(7), x(10), x(13), x(16) 序列3（L=p1-1=2）;x(2), x(5), x(8), x(11), x(

4、14), x(17),2020/7/10,11,2020/7/10,12,然后将每一个6点子序列分成三个长度为2的序列。即有,则X（k）可表示为,2020/7/10,13,三、实数序列的FFT,一个N点FFT算法可同时计算两个N点实数序列的DFT,一个N点FFT一次计算一个2N点实数序列的DFT,2020/7/10,14,一个N点FFT算法可同时计算两个N点实数序列的DFT,FFT计算为复数运算，所以输入序列 x(n)在运算时可以为复数数据。如果是实序列一般是把虚部置另。如果利用虚部数据可以提高计算效率。,2020/7/10,15,2020/7/10,16,2020/7/10,2020/7/1

5、0,18,一个N点FFT一次计算一个2N点实数序列的DFT,2020/7/10,19,2020/7/10,20,例 已知 ， 是两个N点实序列 ， 的 值，今需要从 ， 求 ， 的值，为了提高运算效率，试用一个N点 运算一次完成。,2020/7/10,21,构造序列,对 作一次N点IFFT可得序列,又根据DFT的线性性质,而 ， 都是实序列,2020/7/10,22,MATLAB提供了一个称为fft的函数用于计算一个向量X的DFT。调用X=fft(x,N)就计算出N点的DFT。如果向量X的长度小于N，那么就将X补零。如果N略去，那么DFT的长度就是X的长度。如果X是一个矩阵，那么fft(x,N

6、)计算X中每一列的N点的DFT。,2020/7/10,23,这个fft是用机器语言写成的，而不是用MATLAB命令（也就是不是作为一个.m文件来使用的），因此执行起来非常快。并且它是作为一种混合基算法写成的。如果N是2的某个幂，那么就能使用一个高速的基-2FFT算法。如果N不是2的某个幂，那么就将N分解为若干因子并用一个较慢的混合基FFT算法。最后，如果N就是某个质数，那么fft函数就退化为原始的DFT算法。 应用ifft函数计算逆DFT，它与fft具有相同的特性。,2020/7/10,24,例2-1 对连续的单一频率周期信号 按采样频率采样，截取长度N分别选N =20和N =16，观察其DF

7、T结果的幅度谱。 解 此时离散序列，即k=8。用MATLAB计算并作图，函数fft用于计算离散傅里叶变换DFT，程序如下页：,2020/7/10,25, k=8; %所以k=8 n1=0:1:19; %向量n1为0,1,2,19，截取长度N为20 xa1=sin(2*pi*n1/k); %生成正弦周期序列xa1 subplot(2,2,1) %指定画图左上角 plot(n1,xa1) %画图xa1 xlabel(t/T);ylabel(x(n); %标x,y轴说明 xk1=fft(xa1);xk1=abs(xk1); %计算向量xa1的FFT subplot(2,2,2) %指定画图右上角 b

8、ar(n1,xk1) %画xk1的柱状图，要提取幅度用bar(n1,xk1/20*2) 代替 xlabel(k);ylabel(X(k); %标x,y轴说明 n2=0:1:15; %向量n1为0,1,2,15，截取长度N为16 xa2=sin(2*pi*n2/k); %生成正弦周期序列xa1 subplot(2,2,3) %指定画左下角 plot(n2,xa2) %画图xa2 xlabel(t/T);ylabel(x(n); %标x,y轴说明 xk2=fft(xa2);xk2=abs(xk2); %计算向量xk2的FFT subplot(2,2,4) %指定画右下角 bar(n2,xk2) %画xk1的柱状图，要提取幅度用bar(n2,xk2/16*2)代替 xlabel(k);ylabel(X(k); %标x,y轴说明,2020/7/10,26,计算结果示于