下载文档原格式
基2FFT算法一、什么是基2FFT算法基2FFT算法（Fast Fourier Transform）是一种用于将一个离散信号变换成其频域表示的算法。
它通过将离散信号分解为多个较小的离散信号，并对这些信号进行递归处理，最后合并得到频域表示。
基2FFT算法是最常用的FFT算法之一，其时间复杂度为O(nlogn)。
二、基2FFT算法的原理基2FFT算法的核心思想是分治法。
根据离散信号的长度，将信号分解为两个较小的子信号，然后对这两个子信号分别进行FFT变换。
再将得到的两个子信号的频域表示合并，得到整个信号的频域表示。
具体过程如下：1.判断信号长度是否为1，如果是，则直接返回该信号作为其频域表示。
2.将信号分为偶数索引和奇数索引两个子信号。
3.对这两个子信号分别进行FFT变换，并得到它们的频域表示。
4.合并两个子信号的频域表示，得到整个信号的频域表示。
基于分治法，基2FFT算法可以将信号的长度减半，并通过递归的方式处理子信号，直到信号长度为1，再进行合并得到整个频域表示。
三、基2FFT算法的实现下面是基于伪代码的基2FFT算法的实现：function FFT(signal):n = length(signal)if n == 1:return signalelse:even = FFT(signal[0::2])odd = FFT(signal[1::2])for k = 0 to n/2-1:t = odd[k] * exp(-2*pi*i*k/n)signal[k] = even[k] + tsignal[k + n/2] = even[k] - treturn signal四、基2FFT算法的应用基2FFT算法在信号处理、图像处理、数字滤波器等领域具有广泛的应用。
以下是一些基于基2FFT算法的应用示例：1.频谱分析：将时间域信号转换为频域信号，可以分析信号的频率分量及其强弱关系，从而实现信号的频谱分析。
离散时间信号的基2快速傅里叶变换FFT （时间抽取）蝶形算法实现一、一维连续信号的傅里叶变换连续函数f(x)满足Dirichlet （狄利克雷）条件下，存在积分变换：正变换：2()()()()j ux F u f x e dx R u jI u π+∞--∞==+⎰ 反变换：2()()j ux f x F u e du π+∞-∞=⎰其中()()cos(2)R u f t ut dt π+∞-∞=⎰，()()sin(2)I u f t ut dt π+∞-∞=-⎰定义幅值、相位和能量如下：幅度：1222()()()F u R u I u ⎡⎤⎡⎤=+⎣⎦⎣⎦ 相位：()arctan(()/())u I u R u ϕ= 能量：22()()(E u R u I u =+）二、一维离散信号的傅里叶变换将连续信号对自变量进行抽样得到离散信号（理想冲击抽样脉冲），利用连续信号的傅里叶变换公式得到离散时间傅里叶变换DTFT ；再利用周期性进行频域抽样，得离散傅里叶变换DFT （详情参考任何一本《数字信号处理》教材）。
DFT 变换如下：正变换：12/0()(),0,1,2,1N j ux Nx F u f x eu N π--===-∑。
反变换：12/01()(),0,1,2,1N j ux Nu f x F u ex N Nπ-===-∑。
DFT 是信号分析与处理中的一种重要变换，因为计算机等数字设备只能存储和处理离散数据（时域、频域）。
因直接计算DFT 的计算量大（与变换区间长度N 的平方成正比，当N 较大时，计算量太大），所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT 算法进行谱分析和信号的实时处理是不切实际的。
直到1965年发现了DFT 的一种快速算法（快速傅里叶变换，即FFT ）以后，情况才发生了根本的变化。
FFT 有时间抽取和频率抽取两种，下面介绍时间抽取FFT 。
三、时间抽取的基2快速傅里叶变换FFT令2j NN W eπ-=，则2jkm km NNWeπ-=称为旋转因子，把DFT 正变换改写为：1[][],0,1,1N km N k F m f k W m N -===-∑将函数记作x ，变换后为X ，则为：10[][],0,1,1N kmN k X m x k W m N -===-∑时间抽取的FFT 算法利用了旋转因子的三个性质：周期性、对称性和可约性。
华北电力大学实验报告||实验名称FFT的软件实现实验（Matlab）IIR数字滤波器的设计课程名称信号分析与处理||专业班级：电气化1308 学生姓名：袁拉麻加学号： 2 成绩：指导教师：杨光实验日期： 2015-12-17快速傅里叶变换实验一、实验目的及要求通过编写程序，深入理解快速傅里叶变换算法（FFT）的含义，完成FFT和IFFT算法的软件实现。
二、实验内容利用时间抽取算法，编写基2点的快速傅立叶变换（FFT）程序；并在FFT程序基础上编写快速傅里叶反变换（IFFT）的程序。
三：实验要求1、FFT和IFFT子程序相对独立、具有一般性，并加详细注释；2、验证例6-4，并能得到正确结果。
3、理解应用离散傅里叶变换（DFT）分析连续时间信号频谱的数学物理基础。
四、实验原理：a.算法原理1、程序输入序列的元素数目必须为2的整数次幂，即N=2M,整个运算需要M 级蝶形运算；2、输入序列应该按二进制的码位倒置排列，输出序列按自然序列排列；3、每个蝶形运算的输出数据军官占用其他输入数据的存储单元，实现“即位运算”；4、每一级包括N/2个基本蝶形运算，共有M*N/2个基本蝶形运算；5、第L级中有N/2L个群，群与群的间隔为2L。
6、处于同一级的各个群的系数W分布相同，第L级的群中有2L-1个系数；7、处于第L级的群的系数是(p=1,2,3，…….,2L-1)而对于第L级的蝶形运算，两个输入数据的间隔为2L-1。
b.码位倒置程序流程图开始检测A序列长度nk=0j=1x1(j)=bitget(k,j);j=j+1Yj<m?Nx1=num2str(x1);y(k+1)=bin2dec(x1);clear x1k=k+1c.蝶形运算程序流程图五、程序代码与实验结果a.FFT程序：%%clear all;close all;clc;%输入数据%A=input('输入x(n)序列','s');A=str2num(A);% A=[1,2,-1,4]; %测试数据%%%%校验序列,%n=length(A);m=log2(n);if (fix(m)~=m)disp('输入序列长度错误，请重新输入!');A=input('输入x(n)序列','s');A=str2num(A);elsedisp('输入正确，请运行下一步')end%%%码位倒置%for k=0:n-1for j=1:m %取M位的二进制数%x1(j)=bitget(k,j); %倒取出二进制数%endx1=num2str(x1); %将数字序列转化为字符串%y(k+1)=bin2dec(x1); %二进制序列转化为十进制数%clear x1endfor k=1:nB(k)=A(y(k)+1); %时间抽取序列%endclear A%%%计算%for L=1:m %分解为M级进行运算%LE=2^L; %第L级群间隔为2^L%LE1=2^(L-1); %第L级中共有2^(L-1)个Wn乘数，进行运算蝶运算的两数序号相隔LE1%W=1;W1=exp(-1i*pi/LE1);for R=1:LE1 %针对第R个Wn系数进行一轮蝶运算，共进行LE1次%for P=R:LE:n %每个蝶的大小为LE% Q=P+LE1;T=B(Q)*W;B(Q)=B(P)-T;B(P)=B(P)+T;endW=W*W1;endendB %输出X(k)%%%验证结果：例6-4b.IFFT程序：%%clear all;close all;clc;%输入数据%A=input('输入X(k)序列','s');A=str2num(A);% A=[6,2+2i,-6,2-2i]; %测试数据%%%%校验序列,%n=length(A);m=log2(n);if (fix(m)~=m)disp('输入序列长度错误，请重新输入!');A=input('输入x(n)序列','s');A=str2num(A);elsedisp('输入正确，请运行下一步')end%%%码位倒置%for k=0:n-1for j=1:m %取M位的二进制数%x1(j)=bitget(k,j); %倒取出二进制数%endx1=num2str(x1); %将数字序列转化为字符串%y(k+1)=bin2dec(x1); %二进制序列转化为十进制数%clear x1endfor k=1:nB(k)=A(y(k)+1); %时间抽取序列%endclear A%%%计算%for L=1:m %分解为M级进行运算%LE=2^L; %第L级群间隔为2^L%LE1=2^(L-1); %第L级中共有2^(L-1)个Wn乘数，进行运算蝶运算的两数序号相隔LE1%W=1;W1=exp(-1i*pi/LE1);for R=1:LE1 %针对第R个Wn系数进行一轮蝶运算，共进行LE1次%for P=R:LE:n %每个蝶的大小为LE%Q=P+LE1;T=B(Q)*W;B(Q)=B(P)-T;B(P)=B(P)+T;endW=W*W1;endendB=conj(B); %取共轭%B=B/n %输出x(n)%验证结果：六、实验心得与结论本次实验借助于Matlab软件，我避开了用C平台进行复杂的复数运算，在一定程度上简化了程序，并添加了简单的检错代码，码位倒置我通过查阅资料，使用了一些函数，涉及到十-二进制转换，数字-文本转换，二-文本转换，相对较复杂，蝶运算我参考了书上了流程图，做些许改动就能直接实现。
一、概述Fast Fourier Transform（快速傅里叶变换，FFT）是一种非常重要的数学算法，它在信号处理、图像处理、通信等领域有着广泛的应用。
其中，radix-2 FFT算法是FFT算法中最为简单、高效的一种算法。
本文将对radix-2 FFT算法的原理进行介绍，并通过具体的例子来演示其工作原理。
二、FFT算法简介FFT算法是一种离散傅里叶变换的快速计算方法，它能够将时域的信号转换为频域的信号，从而方便地进行频域分析和处理。
在数字信号处理中，FFT算法广泛应用于滤波、频谱分析、信号合成等方面。
FFT 算法的应用十分广泛，因此对其进行深入的学习和理解具有重要意义。
三、radix-2 FFT算法原理1. 蝶形运算：radix-2 FFT算法采用了蝶形运算（butterfly operation）的思想。
蝶形运算是一种迭代的运算方式，它将输入信号分为偶数点和奇数点，然后通过相位的旋转实现频域变换。
具体而言，蝶形运算可以表示为：\[ X(k) = X_e(k) + W_N^kX_o(k), \quad 其中，W_N^k为旋转因子，k为频率索引，X_e(k)和X_o(k)分别为偶数点和奇数点的频谱。
蝶形运算是FFT算法中的核心操作，它通过不断的迭代运算，将时域信号转换为频域信号。
2. 蝶形运算的分解：在radix-2 FFT算法中，蝶形运算会被分解为多个小规模的蝶形运算，这样可以大大简化运算的复杂度。
具体而言，对于长度为N的信号，radix-2 FFT算法将其分解为长度为2的小块，然后通过不断的迭代运算，完成整个频域变换过程。
这种分解的方式大大降低了计算的时间复杂度，使得FFT算法能够高效地完成频域变换。
3. 基-2的选择：radix-2 FFT算法之所以被称为radix-2算法，是因为它将信号的长度N限定为2的幂次。
这样一来，在进行频域变换时，可以将信号不断拆分为长度为2的小块，然后通过不断的迭代运算完成整个频域变换。
按时间抽选的基2FFT算法基2FFT算法（Fast Fourier Transform，快速傅里叶变换）是一种高效的算法，用于在计算机上计算离散傅里叶变换（Discrete Fourier Transform，DFT）。
它的核心思想是利用分治策略和递归操作，在O(nlogn)的时间复杂度下完成离散傅里叶变换。
基2FFT算法的关键步骤如下：1. 将输入的序列划分为两个子序列：偶数位置和奇数位置上的元素分别组成两个子序列。
2. 对这两个子序列分别进行离散傅里叶变换，得到两个新的子序列。
3. 将两个新子序列的元素按照原始顺序交替排列，得到最终的结果。
基于以上步骤，可以利用递归操作来实现基2FFT算法。
具体的实现过程如下：1. 如果输入序列的长度为1，则不需要进行任何操作，直接返回该序列作为结果。
2. 如果输入序列的长度大于1，则按照上述步骤进行分割和计算。
3. 首先将输入序列分为偶数位置和奇数位置上的元素组成的两个子序列。
4. 对这两个子序列分别递归调用基2FFT算法，得到两个新的子序列。
5. 将两个新子序列的元素按照原始顺序交替排列，得到最终的结果。
基2FFT算法的时间复杂度分析如下：假设输入序列的长度为n，则每一层递归的时间复杂度为O(n)，总共有logn层递归。
因此，基2FFT算法的总时间复杂度为O(nlogn)。
基2FFT算法在信号处理、图像处理等领域具有广泛的应用。
它可以高效地计算离散傅里叶变换，将时域信号转换为频域信号，从而实现信号分析、频谱分析和频域滤波等操作。
同时，基于基2FFT算法的快速傅里叶变换还能够应用于多项式乘法、高效计算卷积等问题的求解。
总之，基2FFT算法是一种高效的离散傅里叶变换算法，通过利用分治策略和递归操作，能够在O(nlogn)的时间复杂度下完成计算。
它在信号处理和图像处理等领域有着重要的应用价值。
基2FFT算法（Fast Fourier Transform，快速傅里叶变换）是离散傅里叶变换（Discrete Fourier Transform，DFT）的一种高效计算方法。
按时间抽取的基2FFT算法分析及MATLAB实现基2FFT算法是一种快速傅里叶变换（Fast Fourier Transform，FFT）的算法，在信号处理、图像处理等领域有着广泛的应用。
该算法通过将N个输入值分解成两个长度为N/2的DFT（离散傅里叶变换）来实现快速的计算。
本文将对基2FFT算法进行分析，并给出MATLAB实现。
基2FFT算法的主要思路是将输入序列分解成奇偶两个子序列，然后分别对这两个子序列进行计算。
具体步骤如下：1.将输入序列拆分成奇数位和偶数位两个子序列。
比如序列x[0],x[1],x[2],x[3]可以拆分成x[0],x[2]和x[1],x[3]两个子序列。
2. 对两个子序列分别进行DFT计算。
DFT的定义为：X[k] = Σ(x[n] * exp(-i * 2π * k * n / N))，其中k为频率的索引，N为序列长度。
3.对得到的两个DFT结果分别进行合并。
将奇数位子序列的DFT结果和偶数位子序列的DFT结果合并成一个长度为N的DFT结果。
4.重复以上步骤，直到计算结束。
基2FFT算法的时间复杂度为O(NlogN)，远远小于直接计算DFT的时间复杂度O(N^2)。
这是因为基2FFT算法将问题的规模逐步减半，从而实现了快速的计算。
下面是MATLAB中基2FFT算法的简单实现：```matlabfunction X = myFFT(x)N = length(x);if N == 1X=x;%递归结束条件return;endeven = myFFT(x(1:2:N)); % 偶数位子序列的FFT计算odd = myFFT(x(2:2:N)); % 奇数位子序列的FFT计算W = exp(-1i * 2 * pi / N * (0:N/2-1)); % 蝶形因子temp = W .* odd; % 奇数位子序列的DFT结果乘以蝶形因子X = [even + temp, even - temp]; % 合并得到一个长度为N的DFT结果end```上述代码中，函数myFFT为基2FFT算法的MATLAB实现。
FFT算法研究及基2-FFT算法的C语⾔实现毕业设计 [论⽂]题⽬：FFT算法研究及基2-FFT算法的C语⾔实现学院：电⽓与信息⼯程学院专业：电⽓⼯程及其⾃动化姓名：XXX学号：XXXXXX指导⽼师：XXX完成时间：2015年06⽉01⽇摘要离散傅⽴叶变换（DFT）常常⽤于计算信号处理。
DFT算法可以得到信号的频域特性，因为该算法在计算上是密集的，长时间的使⽤时，计算机不能实时进⾏信号处理。
所以DFT被发现之后的相当长时间内是没被应⽤到实际的项⽬。
到了⼆⼗世纪六⼗年代中期⼀种新的计算⽅法被研究者发现出来，它就是FFT。
FFT 并不是⼀种新的获取频域特征的⽅式，⽽是离散傅⾥叶变换的⼀种快速实现算法。
数字信号处理在当今科技发展中发展很迅速，不但是在传统的通信领域，其他⽅⾯也经常⽤到。
利⽤快速傅⾥叶变换，实现了信号频域的变换处理。
对于信号的处理，往往会和数学中的算法联系到⼀起。
如果处理得当，将会对⽓象，地理信息等的发展，起到举⾜轻重的作⽤，同时对世界其他领域的发展有很⼤的促进作⽤。
关键词: FFT算法，C语⾔，编译实现AbstractDiscrete Fourier Transform (DFT) is often used to calculate the signal processing to obtain frequency domain signals. DFT algorithm can get the frequency domain characteristics of the signal, because the algorithm is computationally intensive, long-time use, the computer is not conducive to real-time signal processing. So DFT since it was discovered in a relatively long period of time is not to be applied to the actual projects until a new fast discrete Fourier calculation method --FFT is found in discrete Fourier transform was able to actually project has been widely used. FFT is not a new way to get the frequency domain, but the discrete Fourier transform of a fast algorithm.Fast Fourier Transform (FFT) is a digital signal processing important tool that the time domain signal into a frequency-domain signal processing. matched filtering has important applications. FFT is a discrete Fourier transform (DFT) is a fast algorithm, it can be a signal from the time domain to the frequency domain. Some signals in the time domain is not easy to observe the characteristics of what is, but then if you change the signal from the time domain to the frequency domain, it is easy to see out of. This design is required to be familiar with the basic principles of FFT algorithm, based on the preparation of C language program to achieve FFT algorithm real number sequence. Keywords: FFT algorithm, C language compiler to achieve⽬录摘要 ................................................................................................................................. I Abstract ............................................................................................................................. I I ⽬录............................................................................................................................. I II 1 引⾔ . (4)1.1 课题背景 (4)1.2 FFT算法的现状 (4)1.3 研究内容 (2)1.4 论⽂的研究成果 (2)2 数字信号处理综述 (3)2.1 数字信号理论 (3)2.2 数字信号处理的实现 (4)2.3 数字信号处理的应⽤及特点 (4)3 基本理论 (6)3.1 FFT算法的基本概念 (6)3.1.1离散傅⾥叶变换（DFT） (6)3.1.2 快速傅⾥叶变换（FFT） (7)3.2 FFT算法的分类 (8)3.2.1按时间抽取（DIT）的FTT (8)3.2.2 按频率抽取（DIF）的FTT (12)3.2.3 快速傅⾥叶分裂基FFT算法 (15)3.2.4 N为组合数的FFT——混合基算法 (18)3.3 傅⾥叶变换的应⽤ (20)4 基-2FFT算法的C语⾔实现及仿真 ........................................ 错误！未定义书签。
2维FFT算法实现——基于GPU的基2快速⼆维傅⾥叶变换上篇讲述了⼀维FFT的GPU实现（），后来我⼜由于需要做了⼀下⼆维FFT，⼤概思路如下。
⾸先看的肯定是公式：如上⾯公式所描述的，2维FFT只需要拆分成⾏FFT，和列FFT就⾏了，其中我在下⾯的实现是假设原点在F(0,0)，由于我的代码需要原点在中⼼，所以在最后我将原点移动到了中⼼。
下⾯是原点F(0,0)的2维FFT的伪代码：//C2DFFT//被执⾏2DFFT的是⼀个N*N的矩阵，在source_2d中按⾏顺序储存//⽔平⽅向FFTfor (int i=0;i<N;i++){fft1(&source_2d[i*N],&source_2d_1[i*N],N);}//转置列成⾏for (int i=0;i<N*N;i++){int x = i%N;int y = i/N;int index = x*N+y;source_2d[index] = source_2d_1[i];}//垂直FFTfor(int i=0;i<N;i++){fft1(&source_2d[i*N],&source_2d_1[i*N],N);}//转置回来for (int i=0;i<N*N;i++){int x = i%N;int y = i/N;int index = x*N+y;source_2d[index] = source_2d_1[i];}GPU实现⽆⾮把这些东西转换到GPU上。
我基于OpenGL的fragment shader来计算fft；数据都存放在纹理或者FBO⾥⾯。
和1维fft不同的是，NXN的数据⾥⾯，只是对当前列或者当前排做⼀维FFT，所以bit反转表只需要⼀个1*N的buffer就可以了。
对应的蝴蝶图数据也只需要1*N即可。
所以我们有如下的分配：static ofFbo _fbo_bitrev_table;static ofFbo _origin_butterfly_2d;_fbo_bitrev_table.allocate(N,1,GL_RGBA32F);_origin_butterfly_2d.allocate(N,1,GL_RGBA32F);⾸先要做的是把长度为N的bit反转表求出来，这个只需要求⼀次，所以在最开始的时候就⽤CPU求出来：for(int i=0;i<N;i++){_bitrev_index_2d.setColor(i,0,ofFloatColor(bit_rev(i,N-1),0,0,0));}_bitrev_index_2d.update();//翻转后的索引_fbo_bitrev_table.begin();_bitrev_index_2d.draw(0,0,N,1);_fbo_bitrev_table.end();然后初始化最初的蝴蝶图，这个和1维FFT是⼀样的，只是长度不同⽽已：for(int i=0;i<N;i++){//初始化⼆维蝴蝶图if(i%2==0){_data_2d.setColor(i,0,ofFloatColor(0.f,2.f,0,i+1));}else{_data_2d.setColor(i,0,ofFloatColor(1.f,2.f,0,i-1));}}_data_2d.update();/////////////////2D初始化///////////////////初始化2D蝴蝶图_weight_index_2d[0].begin();_data_2d.draw(0,0,N,1);_weight_index_2d[0].end();//备份2D初始蝴蝶图,⽤于下⼀次新的计算_origin_butterfly_2d.begin();_data_2d.draw(0,0,N,1);_origin_butterfly_2d.end();辅助函数：static unsigned int bit_rev(unsigned int v, unsigned int maxv){unsigned int t = log(maxv + 1)/log(2);unsigned int ret = 0;unsigned int s = 0x80000000>>(31);for (unsigned int i = 0; i < t; ++i){unsigned int r = v&(s << i);ret |= (r << (t-i-1)) >> (i);}return ret;}static void bit_reverse_copy(RBVector2 src[], RBVector2 des[], int len){for (int i = 0; i < len;i++){des[bit_rev(i, len-1)] = src[i];}}下⾯定义计算2维IFFT的函数：void GPUFFT::ifft_2d(ofFbo& in,ofFbo& out,int size);其中in是输⼊，out是输出，size就是N，由初始化的时候传⼊了⼀次，在这⾥写是为了⽅便调试的时候临时改变尺⼨。
C编写的时域基2抽取的FFT算法程序以下是一种用C语言编写的时域基2抽取的FFT算法程序：```c#include <stdio.h>#include <math.h>//交换两个复数*a=*b;*b = temp;//计算基2抽取位倒序unsigned int bitReverse(unsigned int num, unsigned int bits) unsigned int reversedNum = 0;int i;for (i = 0; i < bits; i++)reversedNum <<= 1;reversedNum ，= (num & 1);num >>= 1;}return reversedNum;//进行基2抽取FFT运算unsigned int bits = log2(length);unsigned int i, j, k;for (i = 0; i < length; i++)j = bitReverse(i, bits);output[j] = input[i];}unsigned int step, half;for (step = 1, half = 1; step < length; step <<= 1, half <<= 1)theta = -2 * PI / step;w=1.0+0.0*I;for (j = 0; j < half; j++)for (k = j; k < length; k += step)temp = w * output[k + half];output[k + half] = output[k] - temp;output[k] += temp;}}}//打印复数序列unsigned int i;for (i = 0; i < length; i++)printf("(%f) + (%f)i\n", creal(sequence[i]), cimag(sequence[i]));}int maiunsigned int length, i;printf("请输入序列长度：");scanf("%u", &length);printf("请输入序列元素：");for (i = 0; i < length; i++)double real, imag;printf("请输入第%d个元素的实部和虚部：", i+1);scanf("%lf %lf", &real, &imag);input[i] = real + imag * I;}fft(input, output, length);printf("正变换结果为：\n");return 0;```该算法首先对输入序列进行基2抽取位倒序处理，然后使用蝶形算法进行FFT计算。
按时间抽取基2的FFT算法的实现
杜义君
【期刊名称】《塔里木大学学报》
【年(卷),期】2007(19)2
【摘要】详细介绍按时间抽取的傅立叶快速变换算法的基本原理,深入分析其特点,介绍了其程序实现的思想和具体内容.
【总页数】3页(P85-87)
【作者】杜义君
【作者单位】塔里木大学信息工程学院,新疆,阿拉尔,843300
【正文语种】中文
【中图分类】TP314
【相关文献】
1.按频率抽取的基-2FFT算法的矩阵形式 [J], 左大海;常安定;马良
2.基于FPGA的混合基FFT算法设计与实现 [J], 侯晓晨;孟骁;陈昊
3.基于FPGA的混合基FFT算法设计与实现 [J], 侯晓晨;孟骁;陈昊
4.按频率抽取的基4FFT算法在FPGA中实现 [J], 刘学梅;孙志坚
5.一种按时间抽取的混合基实序列高效FFT算法 [J], 张卉;刘永刚;阎跃鹏
因版权原因，仅展示原文概要，查看原文内容请购买。
基2 fft 算法（时域、频域）的基本原理下载提示：该文档是本店铺精心编制而成的，希望大家下载后，能够帮助大家解决实际问题。
文档下载后可定制修改，请根据实际需要进行调整和使用，谢谢!本店铺为大家提供各种类型的实用资料，如教育随笔、日记赏析、句子摘抄、古诗大全、经典美文、话题作文、工作总结、词语解析、文案摘录、其他资料等等，想了解不同资料格式和写法，敬请关注!Download tips: This document is carefully compiled by this editor. I hope that after you download it, it can help you solve practical problems. The document can be customized and modified after downloading, please adjust and use it according to actual needs, thank you! In addition, this shop provides you with various types of practical materials, such as educational essays, diary appreciation, sentence excerpts, ancient poems, classic articles, topic composition, work summary, word parsing, copy excerpts, other materials and so on, want to know different data formats and writing methods, please pay attention!一、绪论1. 引言离散傅里叶变换(DFT)是一种重要的信号处理工具,它可以将时域信号转换为频域信号,为后续的频谱分析和信号处理提供基础。
实验一基2-FFT算法实现
实验目的
1、掌握基2-FFT的原理及具体实现方法。
2、编程实现基2-FFT算法。
3、加深理解FFT算法的特点。
实验设备与环境
计算机、MATLAB软件环境
实验原理
FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform）。
FFT算法可分为按时间抽取算法和按频率抽取算法，先简要介绍FFT的基本原理。
从DFT运算开始，说明FFT的基本原理。
FFT算法基本上可以分为两大类，即按时间抽取法和按频率抽取法。
实验内容
1.编程实现序列长度N=8的按时间抽取的基2-FFT算法。
给定一个8点序列，采用编写的
程序计算其DFT，并与MATLAB中的fft函数计算的结果相比较，以验证结果的正确性。
结果如下：
验证如下：
2.编程实现序列长度为N=8的按频率抽取的基2-FFT算法。
给定一个8点序列，采用编写
的程序计算其DFT，并与MATLAB中fft函数计算的结果相比较，以验证结果的正确性。
心得与体会
通过本次实验，我加深了对课堂上所学的FFT运算的理解，掌握了如何用matlab实现基2-FFT 算法。
过程中在编程上有一些不熟练，经过老师同学的帮助，最终得以完成。
数字信号处理补充快速傅里叶变换授课教师：胡双红QQ：79274544长沙理工大学计算机与通信工程学院DFT 设x(n)改进途径 W nk的对称性利用这些特性，我们可以1 合并DFT运算的某些项2 使长序列的DFT分解为短序列的DFT 由此得到两类快速傅里叶变换（FFT) 1按时间抽取（DIT-FFT）2按频率抽取（DIF-FFT）DIT-FFT()()()2121212221N N r krk x r Wx r W−−+=++∑∑但是，要用考虑系数N 将X(k)N N W W=−按时间抽取，将一个x1(0)=x(0)X1(0)X(0)运算量分析分解后，共需要N/2次蝶形运算和两个N/2点DFT 每个蝶形运算需要一次复数乘法和两次复数加法每个N/2点DFT 需要(N/2)2次复数乘法，N/2(N/2-1)次复数加法分解后，共需要(N/2)2×2＋N/2 N 2/2次复数乘法和N(N/2-1)+N=N 2/2次复数加法分解后，运算量约减小一半，因此我们可进一步把序列进行分解≈将每个同理：X2(k)也可进行同样的分解：x 3(0)=x 1(0)=x(0)N/4 点X 3(0)X(0)X 1(0)奇偶分解过程中序列标号的变化以N=8点的DFT 为例：输入序列x(n)按偶数点与奇数点第一次分解为两个N/2点序列偶序列x(2r)=x 1(r), 奇序列x(2r+1)=x 2(r) ,其中r=0,1,2…,N/2-16420n=2r 3210r7531n=2r+13210r第二次分解把每个N/2点的子序列按其奇偶分解为两个N/4点子序列偶序列中的偶数序列偶序列中的奇数序列x1(2l)=x3(l) x1(2l+1)=x4(l)奇序列中的偶数序列奇序列中的奇数序列x2(2l)=x5(l) x2(2l+1)=x6(l)4n=2r20r=2l 10l 62n=2r31r=2l+110l 51n=2r+120r=2l10l 73n=2r+131r=2l+11l最后剩下的是4个2点DFT X 3(k), X 4(k), X 5(k), X 6(k), k=0,1()()()/4133/4013/4,0,1N lk N l lk N l X k x l Wx l Wk −=====∑∑()()()()()()()()()()3323133230010410104X x W x x x X x W x x x =+=+=+=−这种方法的每一步分解都是按输入序列在时间上的次序是属于偶数还是奇数来进行的，故称为“按时间抽取法”由DFT 计算公式得：即：x 3(0)=x 1(0)=x(0)X 3(0)X(0)X 1(0)二、运算量DFT 与FFT 算法运算量比较表113.82304262144512204.85120104857610246410246553625636.64481638412821.419240966412.8801024328.03225616 5.412648441644142N 2/(log 2N ×N/2)log 2N ×N/2N 2N1、原位运算（同址运算）由图可见，第m-1列的两个节点k和j进行蝶形运算后，得到结果为第m列的k,j节点，与其他节点变量无关因而可采用原位运算：第m-1列的N个数据送到存储器后，经蝶形运算，其结果为第m列数据，以蝶形为单位仍存储在同组存储器中，准备下一列蝶形运算优点：可节省存储单元，降低设备成本2、倒位序规律按原位计算时，输出3、倒位序的实现通过变址运算得到：在原来自然顺序时存放x(n)的单元(n=n 2n 1n 0)，现在存放， ()x n 012n n n n =7111111730111106510110151001100461100113201001024100001100000000倒位序顺序倒位序数二进制数自然顺序x(7)x(3)x(5)x(1)x(6)x(2)x(4)x(0)倒位序变址x(7)x(6)x(5)x(4)x(3)x(2)x(1)x(0)自然顺序输入A(7)A(6)A(5)A(4)A(3)A(2)A(1)A(0)存储单元倒位序的变址处理为保证只调换一次，避免已调换再次调换回到原状，我们在调换之前必须规定约束条件012210,n n n n n n n n >>即4、蝶形运算两节点的距离第一级两个蝶形的两节点间的距离为1第二级两个蝶形的两节点间的距离为2第三级两个蝶形的两节点间的距离为4依此类推第m级两个蝶形的两节点间的距离为2m-15、W Nr 的确定对第m 级运算，一个DIT 蝶形运算的两节点“距离”为2m-1，蝶形输出()()()()()()1111111222m r m m m N m m r m m m NX k X k X k WX k X k X k W−−−−−−−=+++=−+r 的确定：把蝶形运算的第一个节点k 表示为L 位二进制数把此二进制数乘上2L-m ，即为r6、存储单元由于是原位运算，只需有输入序列x(n) (n=0,1,…,N-1)的N个存储单元，加上系数W N r(r=0,1,…,N/2-1)的N/2个存储单元算法的其它形式流图对于任何流图，只要保持各节点所连的支路及其传输系数不变，不论节点怎么排列所得流图等效DIT-FFTX 1(0)X(0)x(0)X 3(0)输入自然顺序、输出自然顺序的X(0)X 1(0)x(0)X 3(0)几何形状的X1(0)X(0) x(0)X(0)几何形状的x(0)X3(0)X1(0)X(0)一、算法原理因为∑i ()()()2 =++X r x n x n N W 2/2n r⎡⎤令则21N−⎫N/2x(0)进一步分解x(0)x(0)N/4点x3(0)N=8x(0)x1(0)x3(0)X(0)每级计算都由三、蝶形运算两节点间的距离第一级两个蝶形的两节点间的距离为4 第二级两个蝶形的两节点间的距离为2 第三级两个蝶形的两节点间的距离为1依此类推第m级两个蝶形的两节点间的距离为2L-m=N/2m四、对第m级运算，一个DIT蝶形运算的两节点“距五、DIT-FFT与DIF-FFT的异同不同点：基本蝶形不同DIT的基本蝶形先复乘后减法DIF的基本蝶形先减法后复乘相同点：运算量相同都可进行原位运算联系：把DIT的基本蝶形加以转置，就得到DIF的基本蝶形转置：将流图的所有支路方向都反向，并交换输入输出，但节点权值不变DITIDFT 上述由1/2作业：画出N=16的基2DIT-FFT和DIF-FFT流图。
function y=MyFFT_FB(x,n)%MYFFT_TB:My Fast Fourier Transform Frequency Based%按频率抽取基2-fft算法%input:% x -- 输入的一维样本% n -- 变换长度，缺省时 n=length(x) 当n小于x数据长度时，x数据被截断到第n个数据% 当n大于时，x数据在尾部补0直到 x 含n个数据%output:% y -- 1*n的向量，快速傅里叶变换结果%variable define:% N -- 一维数据x的长度% xtem -- 临时储存x数据用% m,M -- 对N进行分解 N=2^m*M,M为不能被2整除的整数% two_m -- 2^m% adr -- 变址，1*N的向量% l -- 当前蝶形运算的级数% W -- 长为 N/2的向量，记录 W(0,N),W(1,N),...W(N/2-1,N)% d -- 蝶形运算两点间距离% t -- 第l级蝶形运算含有的奇偶数组的个数% mul -- 标量，乘数% ind1,ind2 -- 标量，下标% tem -- 标量，用于临时储存%参考文献：% 81c 输入参数个数检查msg=nargchk(1,2,nargin);error(msg);%% 输入数据截断或加0N=length(x);if nargin==2if N<n % 加0xtem=x;x=zeros(1,n);x(1:N)=xtem;N=n;else % 截断xtem=x;x=xtem(1:n);N=n;endend%% 对N进行分解 N=2^m*M[m,M]=factorize(N);two_m=N/M;%% 变换if m~=0%% 如果N可以被2整除adr=address(m,M,two_m);y=x; % 蝶形运算级数 l=m 时%% 计算W向量W=exp(-2*pi*i* ( 0:N/2-1 ) /N);%% 蝶形运算d=N/2;t=1;for l=1:m% 加for ii=0:t-1ind1=ii*2*d+1;ind2=ind1+d;for r=0:d-1tem=y(ind1)+y(ind2);y(ind2)=y(ind1)-y(ind2);y(ind1)=tem;ind1=ind1+1;ind2=ind2+1;endend% 乘for r=0:d-1mul=W(r*t+1);for ii=0:t-1y(ii*2*d+d+1+r) = y(ii*2*d+d+1+r)*mul;endendd=d/2;t=t*2;end%% 直接傅里叶变换if M~=1 % N 分解含有非2因数M时，对y中每M个数据做直接傅里叶变换 for ii=1:two_my((ii-1)*M+1 : ii*M ) = DDFT( y((ii-1)*M+1 : ii*M ) );end%% 变址输出y=y(adr+1);else%% 如果N 不能被2整除y=DDFT(x);endend%% 内嵌函数 ====================================================== function y=DDFT(x)%% 直接离散傅里叶变换%input:% x -- 样本数据，N维向量%output:% y -- N维向量%参考文献：% 结构动力学，克拉夫，P82% variable define% s -- sum，用于求和N=length(x);y=zeros(size(x));for n=1:Ns=0;for m=1:Ns=s+x(m)*exp( -i*2*pi*(m-1)*(n-1)/N );endy(n)=s;endendfunction [m,M]=factorize(N)%% 对N分解m=0;while trueif mod(N,2)==0m=m+1;N=N/2;elsebreak;endendendfunction adr=address(m,M,two_m)%% 变址% b -- 2^m * m 的矩阵，用来存储二进制数据% ds -- 数，公差adr=zeros(two_m,M);b=de2bi(0:two_m-1,m);%转换为2进制注：matlab中二进制[0 1 1]=6 b=b(:,end:-1:1);% 逆序adr(:,1)=bi2de(b);%2进制转换为10进制if M~=1ds=two_m;adr=adr(:,1)*ones(1,M);adr=adr+ds*ones(size(adr,1),1)*(0:M-1);adr=reshape(adr',1,[]);endend。
按时间抽取的基2FFT算法分析与MATLAB实现基2FFT算法（Fast Fourier Transform）是一种高效的离散傅里叶变换（DFT）算法，其时间复杂度为O(NlogN)，其中N为输入数据的大小。
该算法利用了DFT的对称性质以及分治的思想，通过将一个大规模的DFT问题分解为若干个规模较小的DFT问题来加快计算速度。
基2FFT算法的实现步骤如下：1.输入N个复数序列x(n)，其中n取值范围为0到N-12.如果N为1，直接返回x(n)。
3. 将x(n)分为两个子序列，分别为x_odd(n)和x_even(n)，其中x_odd(n)包含所有奇数索引的元素，x_even(n)包含所有偶数索引的元素。
4. 对x_odd(n)和x_even(n)分别进行基2FFT变换，递归地计算它们的DFT结果。
5. 根据DFT的对称性，计算出x(k)的前半部分和后半部分的值，其中k为频率索引，取值范围为0到N/2-1、具体计算方法是将x_odd(k)和x_even(k)与旋转因子W_N^k相乘，可通过以下公式计算：x(k) = x_even(k) + W_N^k * x_odd(k)x(k+N/2) = x_even(k) - W_N^k * x_odd(k)其中W_N^k = e^(-j*2*pi*k/N)为旋转因子。
6.返回x(k)作为输出结果。
基2FFT算法的MATLAB实现如下：```matlabfunction X = myfft(x)N = length(x);if N == 1X=x;%如果序列长度为1，直接返回原始序列returnendx_even = myfft(x(1:2:end)); % 奇数索引的元素序列x_odd = myfft(x(2:2:end)); % 偶数索引的元素序列W_N = exp(-2i * pi / N); % 计算旋转因子X = zeros(1, N); % 保存DFT结果for k = 0:N/2-1X(k+1) = x_even(k+1) + W_N^k * x_odd(k+1);X(k+1+N/2) = x_even(k+1) - W_N^k * x_odd(k+1); endend```该实现使用了递归的方式计算DFT，首先对输入序列进行分解，然后递归地计算子序列的DFT结果，并根据对称性将结果合并到一起。
实验二 基-2FFT 算法的软件实现一、实验目的1、 加深对DFT 算法原理和基本性质的理解；2、 熟悉FFT 算法的流程；3、 了解FFT 算法的应用。
二、基本原理1、 DFT 算法原理 （见教材第三章）2、按时间抽取（DIT ）的-2FFT 算法（1）算法原理序列x (n )的N (N =2-M )点DFT 为kn N N n N Wn x n x DFT k X ∑-===1)()]([)(点，k =0, 1, …, N -1 （2.1）将式（2.1）按n 的奇偶性分解为)12(12/212/)12()2()()()(+-=-===∑∑∑∑++=+=l k NN n l k NN n kn Nn kn Nn Wl x Wl x Wn x Wn x k X 奇数偶数奇数偶数（2.2）令)2()(1l x l x =, )12()(2+=l x l x ，因为klN lk NW W 2/2=, 所以式（2.2）可写成)12(2/122/12/012)()()(+--=-=∑∑+=l k N M n k NklN N l Wl x WWl x k X 奇数（2.3）式（2.3）说明，按n 的奇偶性将x (n )分解为两个N /2长的序列x 1(l )和x 2(l )，则N 点DFT 可分解为两个N /2点DFT 来计算。
用X 1(k )和X 2(k )分别表示12,...,1,0 )()]([)(12/02/12/11-===∑-=Nk Wl x l x DFT k X N l kl N N 点 （2.4） 12,...,1,0 )()]([)(12/02/22/22-===∑-=Nk W l x l x DFT k X N l kl N N 点 （2.5）将(2.4)式和(2.5)式代入(2.31)式，并利用kN Nk N W W -=+2和X 1(k )、 X 2(k )的隐含周期性可得到：12,...1,0)()()2()()()(2121-=⎪⎭⎪⎬⎫-=++=N k k X W k X N k X k X W k X k X kN kN （2.6） 这样，将N 点DFT 的计算分解为计算两个N/2点离散傅立叶变换X 1(k )和X 2(k )，再计算(2.6)式。
为了将如上分解过程用运算流图表示，以便估计其运算量，观察运算规律，总结编程方法，先介绍一种表示(2.6)式的蝶形图。
图2.1蝶形运算图图2.2 8点DFT 一次时域抽取分解运算流图根据图2.2可以求得第一次分解后的运算量。
图2.2包括两个N/2点DFT 和N/2个蝶形，每个N/2点DFT 需要2)2/(N 次复数乘法和2/)12/(N N -次复数加法运算，每个蝶形只有一次复数乘法运算和两次复数加法运算。
所以，总的复数乘法次数为总的复数加法次数为2|)1(222)2(212N N N N N N ≈+=+⨯>> （2.7）22222)12(2N N N N =⨯+⨯⨯- （2.8） N=8点DIT-FFT 的运算流图如图2.3(a)所示。
根据W k N/m =W km N ，将图2.3(a)转换成如图2.3(b)所示的标准形式的运算流图图2.3 N=8点DIT-FFT 的运算流图（2）算法效率由图2.3可见，N =2M 时，DIT-FFT 运算流图由M 级蝶形构成，每级有N/2个蝶形。
因此，每级需要N/2次复数乘法运算和N 次复数加法运算，M 级形共需复数乘法次数C M (2)和复数加法次数C A (2)分别为lbN NM N C M 22)2(=⋅=（2.9） C A (2) =N ·M =N lb N （2.10）式中，lb N=log 2 N 。
直接计算N 点DFT 的复数乘法次数为N 2,复数加法次数为(N -1)N 。
当N 1时, N 2/C M(2)>>1，所以N 越大，DIT-FFT 运算效率越高。
DIT-FFT 算法与DFT 所需乘法次数与N 的关系曲线如图2.4所示。
例如，N =210=1024时，DIT-FFT 的运算效率为8.20410210241024)2(22=⨯==-M C N FFT DIT DFT 的乘法次数的乘法次数 （2.11）而当N=211=2048时，37.372112048222)2(22≈⨯==⨯=M N M N N C N M （2.12）图2.4 DIT-FFT 与DFT 所需乘法次数比较曲线（3）运算规律r N W 的确定第m 级运算，一个DIT 蝶型运算的的两接点“距离”为12-m ，所以r Nm m m m m rNm m m m Wk X k X k X W k X k X k X )2()()2()2()()(1111111-------+-=+++= （2.13）r 的求解：（1）将式（2.13）中第一个节点的标号k 表示成L （LN 2=）位二进制数；（2）把此二进制数乘上m L -2，即将L 位二进制数左移m L -位（注意m 是第m 级运算），把右边空出的位置补0，此数即为所求r 的二进制数。
序列的倒序DIT-FFT 算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。
由于LN 2=，因此顺序数可用L 位二进制数(0121n n n n L L --)表示。
M 次偶奇时域抽选过程如图2.5所示。
第一次按最低位0n 的0和1将x(n)分解为偶奇两组，第二次又按次低位1n 的0、 1值分别对偶奇组分解； 依次类推，第L 次按1-L n 位分解，最后所得二进制倒序数如图2.5所示。
图2.5 形成例序的树状图(N =23)形成倒序J 后，将原存储器中存放的输入序列重新按倒序排列。
设原输入序列x (n )先按自然顺序存入数组A 中。
例如，对N =8, A (0)，A (1)，A (2)，…，A (7)中依次存放着x (0),x (1), …, x (7)。
对x(n)的重新排序(倒序)规律如图2.6所示。
图2.6倒序规律三、实验仪器计算机四、实验要求及内容用所学过的编程语言，自行设计出一个按时间抽取的、输入倒位序、输出顺序的基-2 FFT 算法程序。
五、实验报告（1）简述实验目的及原理；（2）画出程序流程框图；（3）主要给出实验内容的程序（要求程序模块化并加注释）。
程序流程框图实验的程序#include<iostream.h> #include<math.h>#include<string.h>#define PI 3.1415926 class Plural//复数类{float real;//实部float img;//虚部public:Plural(float r,float i){real=r;img=i;}Plural(float r)//通过构造函数重载使用数与复数乘法{real=r;img=0;}Plural(){real=0;img=0;}friend Plural* fft(float X[],int n); //fft（）；friend Plural operator *(Plural p1,Plural p2);//重载乘法运算符friend Plural operator -(Plural p1,Plural p2);//重载减法运算符friend Plural operator +(Plural p1,Plural p2);//重载加法运算符friend Plural* daoxu(Plural* x[],int n); //倒序Plural operator =(Plural p) ; //重载赋值符号friend Plural W(int N,int i) ; //生成旋转因子void show() ; //输出real+imgi};Plural operator *(Plural p1,Plural p2)//复数乘法{return Plural(p1.real *p2.real -p1.img *p2.img ,p1.real *p2.img +p1.img *p2.real ); }Plural operator +(Plural p1,Plural p2)//复数加法{return Plural(p1.real+p2.real,p1.img +p2.img );}Plural operator -(Plural p1,Plural p2)//复数加法{return Plural(p1.real-p2.real,p1.img -p2.img );}Plural Plural::operator =(Plural p) //重载赋值符号{real=p.real ;img=p.img ;return *this;}//********************生成旋转因子***************************Plural W(int N,int i){float r;float im;r=(float)cos(2*PI*float(i)/float(N));im=(float)sin((-1)*2*PI*float(i)/float(N));return Plural(r,im);}//*********************输出函数show（）************************* void Plural::show() //输出real+imgi{if(real==0){if(img==0)cout<<0<<" ";elsecout<<img<<"i ";}else{if(img<0)cout<<real<<img<<"i ";elseif(img==0)cout<<real<<" ";elsecout<<real<<"+"<<img<<"i ";}}/************2的n次方*******************/int mi2(int n){int m=1;for(int i=0;i<n;i++){m*=2;//m=2^n}return m;}/*************由二进制数转化为十进制数******************/int twoten(int xu[],int i){int m=0;for(int j=0;j<i;j++){m+=xu[j]*mi2(i-j-1);//m=xu[0]*1+xu[1]*2+xu[2]*4+xu[3]*8+xu[4]*16+...}return m;}/*************对二进制数倒序加一*****************/void add(int xu[],int i){xu[0]++;for(int j=0;j<i;j++){if(xu[j]==2){xu[j]=0;xu[j+1]++;//例如xu[]=0000,1000,0100,1100，0010......}}}/*************倒序**********************************/void daoxu(Plural x[],int n){float m=float (n);int i=0;for(i=0;m>1;i++)//得到n是2的多少次方{m/=2;//m=log(n)/log(2)}int M=mi2(i);int* xu=new int[i];//定义一个长度为i的数组，当做2进制数for(int j=0;j<i;j++){xu[j]=0;}Plural* jia=new Plural[M];//定义一个长度为M的数组jia，以保存倒序for(j=0;j<M;j++){int mm;mm=twoten(xu,i);//得到数组xu[]所对应的十进制数jia[j]=x[mm];add(xu,i);//二进制数组最左端加1}for(j=0;j<n;j++)//撤销动态生成的数组{x[j]=jia[j];}if(jia)delete[] jia;}//***************快速傅里叶变换FFT()************************* Plural* fft(Plural X[],int m){int n=1;for(;m>mi2(n);n++);//得到m等于n次方Plural* A=new Plural[m];for(int i=0;i<n;i++)//共有n级{for(int j=0;j<mi2(n-1-i);j++)//第i级有2^(n-i)族{for(int k=0;k<mi2(i);k++)//每族有2^(m-1)个蝶形运算{int m,n;m=k+j*mi2(i+1);n=k+mi2(i)+j*mi2(i+1);Plural a1,a2;if(i==0){a1=X[m]+W(mi2(i+1),k)*X[n]; //蝶形运算a2=X[m]-W(mi2(i+1),k)*X[n];//蝶形运算A[m]=a1;A[n]=a2;}else{a1=A[m]+W(mi2(i+1),k)*A[n]; //蝶形运算a2=A[m]-W(mi2(i+1),k)*A[n];//蝶形运算A[m]=a1;A[n]=a2;}}}}for(i=0;i<m;i++)//撤销动态生成的数组{X[i]=A[i];}delete[] A;return X;}/****************************主函数*******************/ void main(){int N=0;cout<<"输入变换的点数N："<<endl;cin>>N;Plural *x=new Plural[N] ;cout<<"数据实部：虚部（少于N点时以#结束）:"<<endl;for(int i=0;i<N;i++){char s;float x1,x2;cin>>x1;s=(char)x1;if(s=='#'){ break;}else{cin>>x2;x[i]=Plural(x1,x2);}x1=0;x2=0;}cout<< "您输入的数组："<<endl;for( i=0;i<N;i++){x[i].show();if((i+1)%4==0)cout<<endl;}cout<<endl;daoxu(x,N);//调用倒序daoxu()函数cout<< "倒序后的数组："<<endl;for( i=0;i<N;i++){x[i].show();if((i+1)%4==0)cout<<endl;}cout<<endl;x=fft(x,N);//调用fft()函数cout<< "FFT变换后数组"<<endl;for( i=0;i<N;i++){x[i].show();if((i+1)%4==0)cout<<endl;}if(x)delete[] x;}通过本次实验：1、加深了对DFT算法原理和基本性质的理解；2、熟悉了FFT算法的流程；3、了解FFT算法的应用。
