基4fft原理及matlab实现

基4FFT原理及MATLAB实现 一．时域抽取法基4FFT基本原理： 有限长序列的N点DFT为：   k=0,1,2…,N-1                          设序列长度为N，且满足,M为自然数，可把按下列方法分解为4个长为N/4的子序列：                         r=0,1,…,N/4-1                     r=0,1,…,N/4-1             r=0,1,…,N/4-1                     r=0,1,…,N/4-1 则的DFT为X(k)=+ = = 因为： 所以：原式可 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示为： X(k)= =     k=0,1,…,N/1 其中：分别为的N/4点DFT，即： = = = = 由于均以N/4为周期，且有： ，，， 所以： X(k)=         k=0,1,…,N/4-1 X(k+ N/4)=     k=0,1,…,N/4-1 X(k+ 2N/4)=   k=0,1,…,N/4-1 X(k+ 3N/4)=   k=0,1,…,N/4-1 二．运算规律及编程思想： 1.按照上述分解法，再对进行反复分解，直到每个序列的长度等于4为止，这个4点的DFT的数学表达式为：   2.旋转因子与运算级数的关系（参考《数字信号处理（第三版）》西安电子科技大学出版社第115页）如下： 其中，L表示运算级数（L=1，2，…,M）(M=)(J=0,1,2,…,)     ,(0,1,2…,) 3.序列的倒序： 与基2FFT的倒序相似（参考《数字信号处理（第三版）》西安电子科技大学出版社第116页） 由于，因此顺序数可用M位4进制数（）表示。M次时域抽取如下： 第一次按最低位的0,1,2,3将x(n)分解为4组，第二次又按次低位的0,1,2,3值分别对上面所得的4组分组；以此类推，第M次按位分解，最后得到4进制倒序数。最终可以得到这样的规律：只要将顺序数（）的4进制数倒置，就能得到对应的4进制倒序数（）。 4.运算 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图： 开始 N点采样数据x输入 对采样数据进行4进制逆序排序 For L=1:M For J=0:4L-1-1 For k0=0:N/(4M-L+1)-1 k=k0+JN/4^(M-L); P=J∙4^(M-L) 利用当前级数据X，递推公式计算出次级数据并存入临时数组temp，最后用临时数组中的次级数据覆盖X 得到N点DFT的结果X clc; clear;  a=0:255; x=sin(2*pi/3*a)+sin(2*pi/4*a)+sin(2*pi/5*a)+sin(2*pi/6*a);    %测试信号 subplot(2,1,1),plot(x); axis([0 256 -3 3]),title(' 时域信号波形'); subplot(2,2,3),plot(abs(fft(x))); axis([0 256 0 200]),title('系统FFT 计算出的频谱'); N=256; L=log(N)/log(4);                                              %4点DFT 分解级数 Wn=exp(-2j*pi/N);                                          %旋转因子 temp=zeros(1,N);                                              % 定义中间临时数组 n=0:N-1; screen=ones(1,N); n=bitor(bitand(n,screen*hex2dec('cccc'))/4,bitand(n,screen*hex2dec('3333'))*4); n=bitor(bitand(n,screen*hex2dec('f0f0'))/16,bitand(n,screen*hex2dec('0f0f'))*16); n=bitor(bitand(n,screen*hex2dec('ff00'))/256,bitand(n,screen*hex2dec('00ff'))*256); n=n/4^(8-L)+1; for n1=1:N     temp(n(n1))=x(n1); end x=temp; for l=1:L                                                  % 运算级循环     group_cont_2=4^(L-l);                                  % 第l 级数据分组数     group_cont_1=4^(L-l+1);                                %第l-1 级数据分组数     group_interval_2=4^l;            % 第l 级组间数据间隔个数，也是组内数据个数     group_interval_1=4^(l-1);      %第l-1 级组间数据间隔个数，也是组内数据个数     G=group_cont_2-1;                  %分组上限     K=group_interval_1-1;            % 组内数据上限     for g=0:G              %每一级中包含的组循环，遍历每一组，计算各组中的数据         for k0=0:K          %遍历每一组中的所有数据，计算次级数据             k=k0+g*group_interval_2+1;  % 每组数据中第一个数据序号             m=group_cont_2*k0;             % 每一级所乘旋转因子的指数因子             k1=k; k2=k1+group_interval_1; k3=k2+group_interval_1; k4 =k3+group_interval_1;              X1=x(k1); X2=Wn^m*x(k2); X3=Wn^(2*m)*x(k3); X4=Wn^(3*m)*x(k4);              temp(k1)=X1+X2+X3+X4;             temp(k2)=X1-1j*X2-X3+1j*X4;             temp(k3)=X1-X2+X3-X4;             temp(k4)=X1+1j*X2-X3-1j*X4;         end     end     x=temp;            % 将temp中临时存储的第l 级结果赋值给x，作为次级运算的输入 end subplot(2,2,4),plot(abs(x)); axis([0 256 0 200]),title('自定义基 4FFT计算出的频谱'); 总结：     通过对基4-fft的学习，我发现方法对提高运算速度的重要性，原始的方法可能无法从工程上进行运用，但是提出改进的运算方法后才能在生活中发挥它的应有的作用，所以一方面要理论研究，另一方面要工程运用。要做基4-fft算法，首先的看懂基2-fft的方法，然后看基4-fft就容易些，主要就是因为旋转因子具有周期性和对称性，利用这些性质减少计算量，提高运算速度。