fft蝶形运算怎么理解_fft时域抽选蝶形运算_4点dit fft运算流图

5.2.2 减少运算工作量的途径主要原理是利用系数 的以下特性对DFT进行分解：（1）对称性（2）周期性（3）可约性另是：0，1， …，N/2－1 。因此， 只能计算出X(k)的前一半值。后一半X(k) 值， N/2 ， N/2 ＋1， …，N ？利用可得到同理可得考虑到因此可得后半部分X(k)及前半部分X(k)k=0，1， …，N/2－1k=0，1， …，N/2－1蝶形运算蝶形运算式蝶形运算信号流图符号因此，只要求出2个N/2点的DFT，即X1(k)和X2(k)，再经过蝶形运算就可求出全部X(k)的值，运算量大大减少。以8点为例第一次按奇偶分解以N=8为例，分解为2个4点的DFT，然后做8/2=4次蝶形运算即可求出所有8点X(k)的值。蝶形运算量比较复数乘法次数：N2复数加法次数：N(N－1)复数乘法次数：2*(N/2)2+N/2=N2/2+N/2复数加法次数：2*(N/2)(N/2－1)+2*N/2=N2/2N点DFT的运算量分解一次后所需的运算量＝2个N/2的DFT＋N/2蝶形：因此通过一次分解后，运算工作量减少了差不多一半。

进一步按奇偶分解由于N＝2L，因而N/2仍是偶数 ，可以进一步把每个N/2点子序列再按其奇偶部分分解为两个N/4点的子序列。以N/2点序列x1(r)为例则有k=0,1,…,且k=0,1,…,由此可见，一个N/2点DFT可分解成两个N/4点DFT。同理，也可对x2(n)进行同样的分解，求出X2(k)。以8点为例第二次按奇偶分解算法原理对此例N=8，最后剩下的是4个N/4= 2点的DFT，2点DFT也可以由蝶形运算来完成。以X3(k)为例。k=0, 1即这说明，N=2M的DFT可全部由蝶形运算来完成。以8点为例第三次按奇偶分解N=8按时间抽取法FFT信号流图5.3.2 按时间抽取基2-FFT算法与直接计算DFT运算量的比较由按时间抽取法FFT的信号流图可知，当N=2L时，共有 级蝶形运算；每级都由 个蝶形运算组成，而每个蝶形有次复乘、 次复加，因此每级运算都需 次复乘和次复加。LN/2N/212N这样 级运算总共需要：L复数乘法：复数加法：直接DFT算法运算量复数乘法：复数加法：N2N(N－1)直接计算DFT与FFT算法的计算量之比为MFFT算法与直接DFT算法运算量的比较NN2计算量之比MNN2计算量之比M2414.012816 38444836.641644.025665 5361 02464.0864125.4512262 1442 304113.816256328.010241 048 5765 120204.83210288012.820484 194 30411 264372.464404919221.45.3.3 按时间抽取的FFT算法的特点序列的逆序排列同址运算（原位运算）蝶形运算两节点间的距离的确定序列的逆序排列由于 x(n) 被反复地按奇、偶分组，所以流图输入端的排列不再是顺序的，但仍有规律可循：因为 N=2M ，对于任意 n（0≤n ≤N-1)，可以用M个二进制码表示为：n 反复按奇、偶分解时，即按二进制码的“0” “1” 分解。fft蝶形运算怎么理解

序列的逆序排列倒位序的树状图（N=8）码位的倒位序(N=8)自然顺序 n二进制数倒位序二进制数倒位序顺序数0000000010011004201001023011110641000011510110156110011371111117倒位序的变址处理（N=8）同址运算（原位运算）某一列任何两个节点k 和j 的节点变量进行蝶形运算后，得到结果为下一列k、j两节点的节点变量，而和其他节点变量无关。这种原位运算结构可以节省存储单元，降低设备成本。运算前运算后例同址运算（原位运算）观察原位运算规律蝶形运算两节点间的距离以N=8为例：第一级蝶形，距离为：第二级蝶形，距离为：第三级蝶形，距离为：规律：对于共L级的蝶形而言，其m级蝶形运算的节点间的距离为124蝶形运算两节点间的距离的确定以N=8为例：的确定5.4 按频率抽取的基2-FFT算法算法原理再把输出X(k)按k的奇偶分组先把输入按n的顺序分成前后两半设序列长度为N=2L，L为整数前半子序列x(n)5.4.1 算法原理由DFT定义得k=0，1， …，N由于所以则k=0，1， …，N然后按k的奇偶可将X(k)分为两部分则式可转化为令代入可得为2个N/2点的DFT，合起来正好是N点X(k)的值。

蝶形运算将称为蝶形运算与时间抽选基2FFT算法中的蝶形运算符号略有不同。例 按频率抽取(N=8)例 按频率抽取，将N点DFT分解为两个N/2点DFT的组合(N=8)与时间抽取法的推导过程一样，由于 N=2L，N/2仍然是一个偶数，因而可以将每个N/2点DFT的输出再分解为偶数组与奇数组，这就将N/2点DFT进一步分解为两个N/4点DFT。N=85.4.2 频率抽取法与时间抽取法的异同频率抽取法输入是自然顺序，输出是倒位序的；时间抽取好相反。频率抽取法的基本蝶形与时间抽取法的基本蝶形有所不同。频率抽取法运算量与时间抽取法相同。频率抽取法与时间抽取法的基本蝶形是互为转置的。5.5 快速傅里叶逆变换(IFFT)算法IDFT公式DFT公式比较可以看出，IDFT多出M个1/2可分解到M级蝶形运算中。例 频率抽取IFFT流图(N=8)快速傅里叶逆变换另一种算法5.8 Matlab实现用FFT进行谱分析的Matlab实现用CZT进行谱分析的Matlab实现在Matlab中使用的线性调频z变换函数为czt，其调用格式为>>X= czt(x, M, W, A)其中，x是待变换的时域信号x(n)，其长度为N，M是变换的长度，W确定变换的步长，A确定变换的起点。

若M= N，A= 1，则CZT变成DFT。5.8.1 用FFT进行谱分析的Matlab实现例5.1 设模拟信号 ，以 t= 0.01n (n=0: N-1) 进行取样，试用fft函数对其做频谱分析。N分别为：(1) N=45；(2) N=50；(3) N=55；(2) N=60。程序清单如下%计算N=45的FFT并绘出其幅频曲线N=45;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(4*pi*t)+5*cos(8*pi*t);y=fft(x,N);figure(1)subplot(2,2,1)plot(q,abs(y))title('FFT N=45')例5.1程序清单%计算N=50的FFT并绘出其幅频曲线N=50;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(4*pi*t)+5*cos(8*pi*t);y=fft(x,N);figure(1)subplot(2,2,2)plot(q,abs(y))title('FFT N=50')%计算N=55的FFT并绘出其幅频曲线N=55;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(4*pi*t)+5*cos(8*pi*t);y=fft(x,N);figure(1)subplot(2,2,3)plot(q,abs(y))title('FFT N=55')%计算N=60的FFT并绘出其幅频曲线N=60;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(4*pi*t)+5*cos(8*pi*t);y=fft(x,N);figure(1)subplot(2,2,4)plot(q,abs(y))title('FFT N=60')例5.1程序运行结果从图中可以看出，这几种情况下均有较好的精度。fft蝶形运算怎么理解例5.1程序运行结果分析分析：由t=0.01n进行取样可得，采样频率fs=100Hz。而连续信号的最高模拟角频率为Ω＝8 π ，由Ω＝2 πf可得，最高频率为8 π /2 π=4Hz。因此，满足采样定理的要求。采样序列为即为周期序列，周期N=50。将程序中plot改为stem函数，则可以更清楚地看出频谱。例5.1修改程序运行结果

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-44997-1.html