可以用基2FFT算法

Ⅰ 基-2fft算法的软件实现 matlab代码

% 基于Matlab的时间抽取基2FFT算法
function y=myditfft(x)
%本程序对输入序列实现DIT-FFT基2算法，点数取大于等于长度的2的幂次
%------------------------------------
% Leo's fft program(改编网上的一个程序)
%------------------------------------
m=log2(2^nextpow2(length(x))); %求的x长度对应的2的最低幂次m
N=2^m;
if length(x)<N
x=[x,zeros(1,N-length(x))]; %若长度不是2的幂，补0到2的整数幂
end
x;
%--------------------------------------------------------------------------
%对输入序列进行倒序
%如果输入序列的自然顺序号I用二进制数（例如n2n1n0）表示
%则其倒位序J对应的二进制数就是（n0n1n2），这样，在原来自然顺序时应该放x(I)的
%单元，现在倒位序后应放x(J)。
%--------------------------------------------------------------------------
%以下程序相当于以下程序:
%nxd=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1; %求1：2^m数列的倒序
%y=x(nxd); %将倒序排列作为初始值
%--------------------------------------------------------------------------
NV2=N/2;
NM1=N-1;
I=0;
J=0;
while I<NM1
if I<J
T=x(J+1);
x(J+1)=x(I+1);
x(I+1)=T;
end
K=NV2;

while K<=J
J=J-K;
K=K/2;
end
J=J+K;
I=I+1;
end
x;
%--------------------------------------------------------------------------
%以下程序解释:
%第一级从x(0)开始,跨接一阶蝶形,再取每条对称
%第二级从x(0)开始,跨接两阶蝶形,再取每条对称
%第m级从x(0)开始,跨接2^(m-1)阶蝶形,再取每条对称....
%--------------------------------------------------------------------------
for mm=1:m %将DFT做m次基2分解，从左到右，对每次分解作DFT运算
Nmr=2^mm;
u=1; %旋转因子u初始化
WN=exp(-j*2*pi/Nmr); %本次分解的基本DFT因子WN＝exp(-i*2*pi/Nmr)
for n=1:Nmr/2 %本次跨越间隔内的各次碟形运算
for k=n:Nmr:N %本次碟形运算的跨越间隔为Nmr=2^mm
kp=k+Nmr/2; %确定碟形运算的对应单元下标(对称性)
t=x(kp)*u; %碟形运算的乘积项
x(kp)=x(k)-t; %碟形运算的加法项
x(k)=x(k)+t;
end
u=u*WN; %修改旋转因子，多乘一个基本DFT因子WN
end
end
y=x; %输出

Ⅱ 以2为基的FFT算法的基本运算单元是什么

T/FFT的发展历史
离散傅里叶变换（Discrete Fourier Transform，DFT）是数字信号处理最重要的基石之一，也是对信号进行分析和处理时最常用的工具之一。在200多年前法国数学家、物理学家傅里叶提出后来以他名字命名的傅里叶级数之后，用DFT这个工具来分析信号就已经为人们所知。历史上最伟大的数学家之一。
欧拉是第一个使用“函数”一词来描述包含各种参数的表达式的人，例如：y = f(x)。他是把微积分应用于物理学的先驱者之一。 给出了一个用实变量函数表示傅立叶级数系数的方程； 用三角级数来描述离散声音在弹性媒介中传播，发现某些函数可以通过余弦函数之和来表达。 但在很长时间内，这种分析方法并没有引起更多的重视，最主要的原因在于这种方法运算量比较大。直到1965年，Cooley和Tukey在《计算机科学 》发表着名的《机器计算傅立叶级数的一种算法》论文，FFT才开始大规模应用。
那个年代，有个肯尼迪总统科学咨询委员会。其中有项研究主题是，对苏联核测试进行检测，Tukey就是其中一员。美国/苏联核测试提案的批准，主要取决于不实地访问核测试设施而做出检测的方法的发展。其中一个想法是，分析离海岸的地震计情况，这种计算需要快速算法来计算DFT。其它应用是国家安全，如用声学探测远距离的核潜艇。所以在军事上，迫切需要一种快速的傅立叶变换算法，这也促进了FFT的正式提出。
FFT的这种方法充分利用了DFT运算中的对称性和周期性，从而将DFT运算量从N2减少到N*log2N。当N比较小时，FFT优势并不明显。但当N大于32开始，点数越大，FFT对运算量的改善越明显。比如当N为1024时，FFT的运算效率比DFT提高了100倍。在库利和图基提出的FFT算法中，其基本原理是先将一个N点时域序列的DFT分解为N个1点序列的DFT，然后将这样计算出来的N个1点序列DFT的结果进行组合，得到最初的N点时域序列的DFT值。实际上，这种基本的思想很早就由德国伟大的数学家高斯提出过，在某种情况下，天文学计算（也是现在FFT应用的领域之一）与等距观察的有限集中的行星轨道的内插值有关。由于当时计算都是靠手工，所以产生一种快速算法的迫切需要。 而且，更少的计算量同时也代表着错误的机会更少，正确性更高。高斯发现，一个富氏级数有宽度N=N1*N2，可以分成几个部分。计算N2子样本DFT的N1长度和N1子样本DFT的N2长度。只是由于当时尚欠东风——计算机还没发明。在20世纪60年代，伴随着计算机的发展和成熟，库利和图基的成果掀起了数字信号处理的革命，因而FFT发明者的桂冠才落在他们头上。
之后，桑德（G.Sand）-图基等快速算法相继出现，几经改进，很快形成了一套高效运算方法，这就是现在的快速傅立叶变换（FFT）。这种算法使DFT的运算效率提高1到2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了良好的条件，大大推进了数学信号处理技术。1984年，法国的杜哈梅（P.Dohamel）和霍尔曼（H.Hollamann）提出的分裂基块快速算法，使运算效率进一步提高。
库利和图基的FFT算法的最基本运算为蝶形运算，每个蝶形运算包括两个输入点，因而也称为基-2算法。在这之后，又有一些新的算法，进一步提高了FFT的运算效率，比如基-4算法，分裂基算法等。这些新算法对FFT运算效率的提高一般在50%以内，远远不如FFT对DFT运算的提高幅度。从这个意义上说，FFT算法是里程碑式的。可以说，正是计算机技术的发展和FFT的出现，才使得数字信号处理迎来了一个崭新的时代。除了......

Ⅲ 求教在基2-FFT算法中补零后输出幅值减小的问题

1.补零可以使FFT后的结果更平滑，可以反映出原信号的频谱。因为FFT前后的点数一样， 实际上补零的作用是增加了频域的显示分辨率。如果有MATLAB可以看到 补零前的数据和补零后的数据 图形是基本一致的，但是多了补的0的个数个采样点来平滑。\r\n\r\n2.补零不会增加你数据中携带的信息。所以不能提高信号的频率分辨率，就是说如果你的采样率不够表现信号特性，你补零后，貌似采样率够了，但是实际上并不能显示出信号的正确信息。\r\n\r\n3.利用插值(就是根据信号波形补充可能的图形位置)也可以补偿数据到2的整数次方，插值会携带数据信息，根据你的插值方法可以增加采样率。

Ⅳ 基数为2的FFT算法

从上节所述，FFT算法快速的关键在于将原来傅氏矩阵分解为每一行仅含有两个非零项l与Wⁱ的矩阵的乘积。下面用基数为2，即N=2ⁿ的情形讨论矩阵的分解过程.并主要按时间分解的情况讨论。

按时间分解的FFT算法

设N=2ⁿ，n为正整数。考虑输入序列x₀(l)的DFT

物探数字信号分析与处理技术

将l与m用二进制表示

物探数字信号分析与处理技术

将(7-2-2)代入(7-2-1)中，得到

物探数字信号分析与处理技术

为了说明问题，我们取N=8，于是从(7-2-2)得到

物探数字信号分析与处理技术

从(7-2-4)和(7-2-3)得到

物探数字信号分析与处理技术

将(7-2-5)中的W的指数按时间l进行分解，有

物探数字信号分析与处理技术

因为

物探数字信号分析与处理技术

故从(7-2-6)得到

物探数字信号分析与处理技术

将上式代入(7-2-5)中得到

物探数字信号分析与处理技术

物探数字信号分析与处理技术

我们在公式(7-2-7)中由里往外求和，并置

物探数字信号分析与处理技术

于是得到

物探数字信号分析与处理技术

首先写出(7-2-8)的所有式子

物探数字信号分析与处理技术

将方程组(7-2-12)写成矩阵形式，得到

物探数字信号分析与处理技术

我们看到(7-2-13)中的方阵，正好是(7-1-13)中的方阵，也就是(7-1-12)中被分解出来的第3个矩阵，只不过这里的x₁(l)与x₀(l)中的l是用二进制数表示而已。

再写出(7-2-9)的所有式子，得到

物探数字信号分析与处理技术

将方程组写成矩阵形式，则有

物探数字信号分析与处理技术

显然(7-2-15)中的矩阵，正好是(7-1-14)中的方阵，也就是(7-1-12)中被分解出来的第二个矩阵，只不过这里的x₂(l)与x₁(l)是用二进制数表示而已，最后将(7-2-10)中的全部式子写出，得到

物探数字信号分析与处理技术

将方程组(7-2-16)写成矩阵形式，则有

物探数字信号分析与处理技术

显然，(7-2-17)中的方阵正是(7-1-15)中的方阵，也就是(7-1-12)中被分解出来的第1个矩阵，只不过这里的x₃(l)与x₂(l)中的l是用二进制数表示。

由此可见，(7-2-7)中由里往外的三个求和式(7-2-8)、(7-2-9)及(7-2-10)，完全确定了(7-1-12)中三个被分解的矩阵因子。求和得到的最终结果x₃(m₀，m₁，m₂)，与我们所要求的X(m₂，m₁，m₀)正好是逆序的。

到此为止，我们就看到(7-1-11)中的方阵是怎样被分解成三个方阵因子的。对于N=8，方程(7-2-8)～(7-2-11)就是计算DFT的FFT算法。为了对FFT算法有一个直观的了解并便于编制程序，我们以N=8为例，画出其流程图(图7-2-1)。

根据(7-2-13)，将其中的W⁴用-W⁰代替，画出从x₀(r)到x₁(r)的流程图。这一迭代过程用符号#1表示;再根据(7-2-15)，将其中的与W⁴、W⁶分别换成-W⁰与-W²，画出从x₁(r)到x₂(r)的流程图，这一迭代过程记为#2;最后，根据(7-2-17)，将其中的W⁴、W⁶、W⁵、W⁷分别换成-W⁰、-W²、-W¹、-W³，画出流程图7-2-3合并图7-2-1～7-2-3，就得到从x₀(r)到x₃(r)的完整流程图7-2-4。

图7-2-1 第一次递推

图7-2-2 第二次递推

在图7-2-5中，画出N=16=2⁴的FFT算法流程图:

根据从x₀到谱X的FFT算法流程图7-2-4与图7-2-5，我们总结出如下几点:

(1)从x₀到终值x_r的最大迭代次数r，由r=log₂N确定。

例如，N=8，最大迭代次数r=3;N=16，最大迭代次数r=4。

(2)在第r次迭代中，要乘的W因子为

图7-2-3 第三次递推

例如，N=8，在第一次迭代中，要乘因子W⁰;在第二次迭代中要乘因子W⁰，W¹，W²，W³。

(3)在第r次迭代中，包含2^r-1个组，每个组

包含 。例如N=8，第一次迭代r=1，有

一个组，每组包含8个x(s);在第二次迭代中包含2个组，每组包含4个x(s);第三次迭代中包含4个组，每组2个x(s)。

图7-2-4 x₀(r)到x₃(r)的完整流程图

(4)在第r次迭代中，各组包含的W因子各不相同，且每一组仅包含一种类型的因子 ，此因子在组中一半数为正，另一半数为负。例如N=8，第二次迭代中，第一组包含因子W⁰，且在该组中一半数为正，另一半数为负;第二组包含因子W²，在该组中也是一半数为正，另一半数为负。

(5)在第r次迭代中，各组包含的W因子除正负号外类型均相同。所以只须确定每组中第一个因子，之后按半数反号，即得到所求W因子。具体做法是，在每组第一个因子W^SN2r对应的x_r(k)中，将k表示成n位的二进制数，n=log₂N，并把这个二进制数右移n-r位，左边空出的地方添零补足n位，之后再将此n位二进制数逆位，即得到所求W因子的指数。例如，N=8，迭代#2包含两组，每组包含4个x₂(k)，第二组第一个因子W对应于x₂(4)。将4表示成3位的二进制数为100，把它右移1位成10，右边添零补成3位为010，逆位仍为010，故所求因子为W²，第2组全部W因子为W²，W²，-W²，-W²。又如，N=16，迭代#3中包含4个组，每组包含4个x₃(k)，第4组第1个因子W对应于x₃(12)。将12表示成4位的二进制数为1100。右移1位变成110，将左边空处添零补成4位为0110，逆位仍为0110，故所求因子为W⁶，从而第4组全部W因子为W⁶，W⁶，-W⁶与-W⁶。

图7-2-5 N=16=2⁴的FFT算法流程图

(6)如果已知N=2的FFT算法，容易从它求得n=2的FFT算法。具体作法是，在n=2^n-1的FFT算法中，将所有x_r(l)的个数加倍，所有W的个数及其乘幂加倍，就得N=2ⁿ中前n-1次迭代的全部结果。之后，将新得到的第n-1次迭代中乘幂相同的W个数减半，就是第n次迭代中前2ⁿ/2个W，将这些W的乘幂依次加1，就得到后2ⁿ/2个W。例如N=16的前3次迭代，都是N=8的三次迭代中所有x_r(l)的个数加倍，W的个数及其乘幂加倍的结果。再将N=16的第三次迭代中乘幂相同的W个数减半，就是第4次迭代中前8个W。

(7)在第r-1次迭代中的x_r-1(i)与x_r-1(j)仅用于计算r次迭代中的x_r(i)与x_r(j)，而不会用于计算任何其它的x_r(k)与x_r(l)。例如N=16的第二次迭代中的x₂(0)与x₂(2)，只用于计算第三次迭代中的x₃(0)与x₃(2);第三次迭代中的x₃(8)与x₃(9)也只用于计算第四次迭代中的x₄(8)与x₄(9)。因此，我们可以把第r次迭代中的x_r(i)与x_r(j)，存放到r-1次迭代x_r-1(i)与x_r-1(j)所占用的原存储单元中去，这样，所需要的计算机存储容量就只限于原数据序列占据的单元数。如果是复序列的话，存储单元要加倍。

(8)上述FFT算法也可用于计算逆离散傅氏变换(IDFT)(图7-2-6)，只不过在计算时要将上述FFT算法中的W因子用其共轭W^*代替，并将最后迭代计算的结果统统乘以1/N.

图7-2-6 N=8的逆离散富氏变换流程图

Ⅳ 采用基2的FFT算法共需要多少 复数乘法运算

二分之（N）*log2（N）

Ⅵ 如何实现128点的基2-FFT算法,并与MATLAB的fft算法作对比分析.

我只能给你一个fft算法，流程图说起来有点复杂，可以matlab里面的函数tic（开启时钟）t=toc（关闭时钟）t就是运算过程的时间
当然tic放程序开始，toc放结尾，来分析之即可
function d=lxfft(x)
n=length(x);
if n>2
for i=0:n/2-1
x1(i+1)=x(2*i+1);
x2(i+1)=x(2*i+2);
end
X1=lxfft(x1);
X2=lxfft(x2);
for i=0:n/2-1
X2(i+1)= X2(i+1)*exp(-j*2*pi/n*i);//旋转因子
d(i+1)=X1(i+1)+X2(i+1);
d(i+n/2+1)=X1(i+1)-X2(i+1);
end
else
d(1)=x(1)+x(2);
d(2)=x(1)-x(2);
end
end

Ⅶ 基2—fft算法的软件实现(MATLAB代码)

参考网络： clc; clear all; close all; x=ones(1,128); %输入的信号，自己可以改变 %整体运用原位计算 m=nextpow2(x);N=2^m; % 求x的长度对应的2的最低幂次m if length(x)<N x=[x,zeros(1,N-length(x))]; % 若x的长度不是2的幂，补零到2的整数幂 end nxd=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1; % 求1:2^m数列序号的倒序 y=x(nxd); % 将x倒序排列作为y的初始值 for mm=1:m % 将DFT作m次基2分解,从左到右，对每次分解作DFT运算,共做m级蝶形运算，每一级都有2^(mm-1)个蝶形结 Nz=2^mm;u=1; % 旋转因子u初始化为WN^0=1 WN=exp(-i*2*pi/Nz); % 本次分解的基本DFT因子WN=exp(-i*2*pi/Nz) for j=1:Nz/2 % 本次跨越间隔内的各次蝶形运算,在进行第mm级运算时需要2^(mm-1)个 蝶形 for k=j:Nz:N % 本次蝶形运算的跨越间隔为Nz=2^mm kp=k+Nz/2; % 蝶形运算的两个因子对应单元下标的关系 t=y(kp)*u; % 蝶形运算的乘积项 y(kp)=y(k)-t; % 蝶形运算 y(k)=y(k)+t; % 蝶形运算 end u=u*WN; % 修改旋转因子,多乘一个基本DFT因子WN end end y y1=fft(x) %自己编的FFT跟直接调用的函数运算以后的结果进行对比

Ⅷ 试画出信号按时间抽取的基-2FFT算法信号流图，并写出对应过程奇偶分流的公式。

基2算法，序列的长度是为2的幂，序列的DFT为。序列可以由奇序列和偶序列组成，DFT分别为和。 从最后一级往前分解对应的蝶形结构，这些蝶形结构最左边的输入都是序列的DFT值，而分解直到最左边的蝶形结构是两点序列的DFT，此时最左边的值是序列x[k]。

f1=50; %10Hz

f2=100; %100Hz

%抽样频率

Fs=1000; %100Hz

%抽样点数N

L=10;

N=2^L;

%抽样脉冲序列

n = 0:N-1;

t = n./Fs;

% f2 一个周期的采样数

M = floor(Fs/f2);

%被采样信号

x = cos(2*pi*f1.*t)+sin(2*pi*f2.*t);

%采样序列

subplot(311);

stem(t(1:2*M),x(1:2*M));

hold off;

%傅里叶变换

%根据有限长序列的离散傅里叶变换公式计算DFT

n = 0:N-1;

k = 0:N-1;

F = x * exp(-j*2*pi/N).^(n'*k);

subplot(312);

plot(n,abs(F));

subplot(313);

plot(k,angle(F));

(8)可以用基2FFT算法扩展阅读：

库利－图基快速傅里叶变换算法是将序列长为N的DFT分区为两个长为N/2的子序列的DFT，因此这一应用只适用于序列长度为2的幂的DFT计算，即基2-FFT。实际上，如同高斯和库利与图基都指出的那样，库利－图基算法也可以用于序列长度N为任意因数分解形式的DFT，即混合基FFT，而且还可以应用于其他诸如分裂基FFT等变种。

尽管库利－图基算法的基本思路是采用递归的方法进行计算，大多数传统的算法实现都将显示的递归算法改写为非递归的形式。另外，因为库利－图基算法是将DFT分解为较小长度的多个DFT，因此它可以同任一种其他的DFT算法联合使用。