按时间抽取的基2FFT算法分析及MATLAB实现

离散时间信号的基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 算法利用了旋转因子的三个性质：周期性、对称性和可约性。

按时间抽取的基2FFT算法分析基2FFT算法是一种快速傅里叶变换算法，它通过将傅里叶变换的计算复杂度从O(n^2)降低到O(nlogn)，大大提高了傅里叶变换的效率。

基2FFT算法的核心思想是将一个长度为n的序列分成长度为n/2的两个子序列，并分别做傅里叶变换。

然后将两个子序列的傅里叶变换结果合并起来，得到原始序列的傅里叶变换结果。

具体来说，基2FFT算法的步骤如下：1.如果输入序列长度为1，则返回输入序列作为傅里叶变换结果。

2.将输入序列按奇偶位置分为两个子序列。

3.对两个子序列分别递归地应用基2FFT算法，得到它们的傅里叶变换结果。

4.根据蝶形算法，将子序列的傅里叶变换结果合并起来，得到原始序列的傅里叶变换结果。

基2FFT算法通过不断将序列分成两半的方式，将傅里叶变换的计算复杂度从O(n^2)降低到O(nlogn)。

在每一层递归中，需要进行O(n)次计算，而递归的层数为logn，因此总的时间复杂度为O(nlogn)。

基2FFT算法的关键之一是蝶形算法。

蝶形算法是一种合并子序列傅里叶变换结果的方法。

在每一层递归中，对于每个位置k，需要计算一个长度为n的序列上的k点DFT。

根据蝶形算法，可以将这个计算分成两个部分：计算序列中偶数位置上的点DFT和计算序列中奇数位置上的点DFT，并通过一些乘法和加法操作合并起来。

这样做可以大大减少计算量，提高计算效率。

基2FFT算法还可以通过多线程或并行处理来进一步提高效率。

由于基2FFT算法具有递归结构，可以将不同的递归层分配给不同的线程或处理器来并行进行计算，从而加快计算速度。

基2FFT算法在数字信号处理、图像处理、通信系统和科学计算等领域有着广泛的应用。

它的高效性和快速运算速度使得它成为处理大规模数据的重要工具。

综上所述，基2FFT算法通过将傅里叶变换的计算复杂度从O(n^2)降低到O(nlogn)，大大提高了傅里叶变换的效率。

它采用递归分治的思想，通过分解和合并操作来实现傅里叶变换的计算。

按时间抽选的基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实现。

数字图像处理与机器视觉——Visual C++与Matlab 实现– 188 – 2,N r N r r r N N N N W W W W ++==- （6-30）式（6-29）是W 矩阵中元素的某些特殊值，而式（6-30）则说明了W 矩阵元素的周期性和对称性。

利用W 的周期性，DFT 运算中的某些项就可以合并；而利用W 的对称性，则可以仅计算半个W 序列。

而根据这两点，我们就可以将一个长度为N 的序列分解成两个长度为N /2的序列并分别计算DFT ，这样就能节省大量的运算量。

我们将在讲述常见的FFT 算法后分析节省的运算量。

这正是快速傅立叶变换（FFT: Fast Fourier Transform ）的基本思路——通过将较长的序列转换成相对短得多的序列来大大减少运算量。

6.3.2 常见的FFT 算法目前流行的大多数成熟的FFT 算法的基本思路大致可以分为两大类，一类是按时间抽取的快速傅立叶算法（Decimation In Time ，DIT-FFT ），另一类是按频率抽取的快速傅立叶算法（Decimation In Freqency ，DIF-FFT ）。

这两种算法思路的基本区别如下。

按时间抽取的FFT 算法是基于将输入序列f (x )分解（抽取）成较短序列，然后从这些序列的DFT 中求得输入序列F (u )的方法。

由于抽取后的较短序列仍然可分，所以最终仅仅需要计算一个很短序列的DFT 。

在这种算法中，我们主要关注的是当序列长度是2的整数次幂时，如何高效地进行抽取和运算的方法。

而按频率抽取的FFT 算法是基于将输出序列F (u )分解（抽取）成较短的序列，并且从f (x )计算这些分解后的序列的DFT 。

同样，这些序列可以继续分解下去，继续得到更短的序列，从而可以更简便地进行运算。

同样这种算法主要针对2的整数次幂长度的序列。

从本章前面对DFT 的介绍和本节开头的分析可知，随着序列长度的减小，FFT 运算的复杂度将以指数规律降低。

电 子 科 技 大 学实 验 报 告学生姓名： 学 号：2010013080 指导教师一、实验室名称：数字信号处理实验室 二、实验项目名称：FFT 的实现 三、实验原理：一．FFT 算法思想：1．DFT 的定义：对于有限长离散数字信号{x[n]}，0 ≤ n ≤ N-1，其离散谱{x[k]}可以由离散付氏变换（DFT ）求得。

DFT 的定义为：21[][]N jnk Nn X k x n eπ--==∑，k=0,1,…N-1通常令2jNN eW π-=，称为旋转因子。

2．直接计算DFT 的问题及FFT 的基本思想：由DFT 的定义可以看出，在x[n]为复数序列的情况下，完全直接运算N 点DFT 需要（N-1）2次复数乘法和N （N-1）次加法。

因此，对于一些相当大的N 值（如1024）来说，直接计算它的DFT 所作的计算量是很大的。

FFT 的基本思想在于，将原有的N 点序列分成两个较短的序列，这些序列的DFT 可以很简单的组合起来得到原序列的DFT 。

例如，若N 为偶数，将原有的N 点序列分成两个（N/2）点序列，那么计算N 点DFT 将只需要约[(N/2)2 ·2]=N 2/2次复数乘法。

即比直接计算少作一半乘法。

因子（N/2）2表示直接计算（N/2）点DFT 所需要的乘法次数，而乘数2代表必须完成两个DFT 。

上述处理方法可以反复使用，即（N/2）点的DFT 计算也可以化成两个（N/4）点的DFT （假定N/2为偶数），从而又少作一半的乘法。

这样一级一级的划分下去一直到最后就划分成两点的FFT 运算的情况。

3．基2按时间抽取（DIT ）的FFT 算法思想：设序列长度为2L N =，L 为整数（如果序列长度不满足此条件，通过在后面补零让其满足）。

将长度为2L N =的序列[](0,1,...,1)x n n N =-，先按n 的奇偶分成两组：12[2][][21][]x r x r x r x r =+=，r=0,1,…,N/2-1DFT 化为：1/21/212(21)0/21/21221200/21/211/22/2[]{[]}[][2][21][][][][]N N N nk rk r kNNNn r r N N rk k rk NNN r r N N rk k rk N NN r r X k DFT x n x n Wx r Wx r W x r W Wx r W x r WWx r W ---+===--==--=====++=+=+∑∑∑∑∑∑∑上式中利用了旋转因子的可约性，即：2/2rkrkNN W W =。

第四章 快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965年，Cooley 和Tukey 提出了计算离散傅里叶变换（DFT ）的快速算法，将DFT 的运算量减少了几个数量级。

从此，对快速傅里叶变换（FFT ）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT 的出现和发展而迅速发展。

根据对序列分解与选取方法的不同而产生了FFT 的多种算法，基本算法是基２DIT 和基２DIF 。

FFT 在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。

快速傅里叶变换（FFT ）是计算离散傅里叶变换（DFT ）的快速算法。

DFT 的定义式为)(k X =)()(10k R W n x N N n knN∑-= 在所有复指数值knN W 的值全部已算好的情况下，要计算一个)(k X 需要N 次复数乘法和N －1次复数加法。

算出全部N 点)(k X 共需2N 次复数乘法和)1(-N N 次复数加法。

即计算量是与2N 成正比的。

FFT 的基本思想：将大点数的DFT 分解为若干个小点数DFT 的组合，从而减少运算量。

N W 因子具有以下两个特性，可使DFT 运算量尽量分解为小点数的DFT运算：（1） 周期性：k N n N kn N nN k N W W W )()(++== （2） 对称性：k N N k NW W -=+)2/(利用这两个性质，可以使DFT 运算中有些项合并，以减少乘法次数。

例子：求当N ＝4时，X(2)的值)()]3()1([)]2()0([)()]3()1([)]2()0([)3()2()1()0()()2(04240464442404324对称性－＝周期性W x x x x W x x W x x W x W x W x W x W n x X n n +++++=+++==∑=通过合并，使乘法次数由4次减少到1次，运算量减少。

第四章 快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT). 1965年，Cooley 和Tukey 提出了计算离散傅里叶变换（DFT ）的快速算法，将DFT 的运算量减少了几个数量级。

从此，对快速傅里叶变换（FFT ）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT 的出现和发展而迅速发展。

根据对序列分解与选取方法的不同而产生了FFT 的多种算法，基本算法是基２DIT 和基２DIF 。

FFT 在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。

快速傅里叶变换（FFT ）是计算离散傅里叶变换（DFT ）的快速算法。

DFT 的定义式为)(k X =)()(10k R W n x N N n knN∑-= 在所有复指数值knN W 的值全部已算好的情况下，要计算一个)(k X 需要N 次复数乘法和N －1次复数加法。

算出全部N 点)(k X 共需2N 次复数乘法和)1(-N N 次复数加法。

即计算量是与2N 成正比的。

FFT 的基本思想：将大点数的DFT 分解为若干个小点数DFT 的组合，从而减少运算量。

N W 因子具有以下两个特性，可使DFT 运算量尽量分解为小点数的DFT运算：（1） 周期性：k N n N kn N nN k N W W W )()(++== （2） 对称性：k N N k NW W -=+)2/(利用这两个性质，可以使DFT 运算中有些项合并，以减少乘法次数。

例子：求当N ＝4时，X(2)的值)()]3()1([)]2()0([)()]3()1([)]2()0([)3()2()1()0()()2(04240464442404324对称性－＝周期性W x x x x W x x W x x W x W x W x W x W n x X n n +++++=+++==∑=通过合并，使乘法次数由4次减少到1次，运算量减少。

基于Matlab的时间抽取基2FFT算法基于Matlab的时间抽取基2FFT算法function y=myditfft(x)%本程序对输入序列实现DIT-FFT基2算法，点数取大于等于长度的2的幂次%------------------------------------% Leo's fft program(改编网上的一个程序)%------------------------------------m=log2(2^nextpow2(length(x))); %求的x 长度对应的2的最低幂次mN=2^m;if length(x)<Nx=[x,zeros(1,N-length(x))]; %若长度不是2的幂，补0到2的整数幂endx;%--------------------------------------------------------------------------%对输入序列进行倒序%如果输入序列的自然顺序号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<NM1if I<JT=x(J+1);x(J+1)=x(I+1);x(I+1)=T;endK=NV2;while K<=JJ=J-K;K=K/2;endJ=J+K;I=I+1;endx;%--------------------------------------------------------------------------%以下程序解释:%第一级从x(0)开始,跨接一阶蝶形,再取每条对称%第二级从x(0)开始,跨接两阶蝶形,再取每条对称%第m级从x(0)开始,跨接2^(m-1)阶蝶形,再取每条对称....%--------------------------------------------------------------------------formm=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)forn=1:Nmr/2 %本次跨越间隔内的各次碟形运算fork=n:Nmr:N %本次碟形运算的跨越间隔为Nmr=2^mmkp=k+Nmr/2;%确定碟形运算的对应单元下标(对称性)t=x(kp)*u;%碟形运算的乘积项x(kp)=x(k)-t;%碟形运算的加法项x(k)=x(k)+t;endu=u*WN;%修改旋转因子，多乘一个基本DFT因子WNend。

按时间抽取的基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算法分析及MATLAB实现按时间抽取的基2FFT算法分析及MATLAB实现一、DIT-FFT算法的基本原理基2FFT算法的基本思想是把原始的N点序列依次分解成一系列短序列，充分利用旋转因子的周期性和对称性，分别求出这些短序列对应的DFT，再进行适当的组合，得到原N点序列的DFT，最终达到减少运算次数，提高运算速度的目的。

按时间抽取的基2FFT算法，先是将N点输入序列x(n)在时域按奇偶次序分解成2个N/2点序列x1(n)和x2(n)，再分别进行DFT运算，求出与之对应的X1(k)和X2(k)，然后利用图1所示的运算流程进行蝶形运算，得到原N点序列的DFT。

只要N是2的整数次幂，这种分解就可一直进行下去，直到其DFT就是本身的1点时域序列。

图1 DIT-FFT蝶形运算流图二、DIT-FFT算法的运算规律及编程思想1.原位计算对N=M2点的FFT共进行M级运算，每级由N/2个蝶形运算组成。

在同一级中，每个蝶的输入数据只对本蝶有用，且输出节点与输入节点在同一水平线上，这就意味着每算完一个蝶后，所得数据可立即存入原输入数据所占用的数组元素(存储单元)，经过M级运算后，原来存放输入序列数据的N个存储单元中可依次存放X(k)的N个值，这种原位(址)计算的方法可节省大量内存。

2.旋转因子的变化规律N点DIT―FFT运算流图中，每个蝶形都要乘以旋转因子p WN，p称为旋转因子的指数。

例如N＝8 ＝32时各级的旋转因子：第一级：L=1，有1个旋转因子：p WN =J/4WN=J2LWJ=0第二级：L=2，有2个旋转因子：p WN =J/2WN=J2LWJ=0,1第三级：L=3，有4个旋转因子：p WN =J WN=J2LWJ=0,1,2,3对于N＝M2的一般情况，第L级共有1-L2个不同的旋转因子：p WN =J2LW J=0,1,2,… ,1-L2－1L2=M2×M-L2= N·M-L2故：按照上面两式可以确定第L级运算的旋转因子3、同一级中，同一旋转因子对应蝶形数目第L级FFT运算中，同一旋转因子用在L-M2个蝶形中；4、同一级中，蝶形运算使用相同旋转因子之间相隔的“距离”第L级中，蝶距：D=L2；5、同一蝶形运算两输入数据的距离在输入倒序，输出原序的FFT变换中，第L 级的每一个蝶形的2个输入数据相距：B=1-L2。

电 子 科 技 大 学实 验 报 告学生姓名： 学 号：2010013080 指导教师一、实验室名称：数字信号处理实验室 二、实验项目名称：FFT 的实现 三、实验原理：一．FFT 算法思想：1．DFT 的定义：对于有限长离散数字信号{x[n]}，0 ≤ n ≤ N-1，其离散谱{x[k]}可以由离散付氏变换（DFT ）求得。

DFT 的定义为：21[][]N jnk Nn X k x n eπ--==∑，k=0,1,…N-1通常令2jNN eW π-=，称为旋转因子。

2．直接计算DFT 的问题及FFT 的基本思想：由DFT 的定义可以看出，在x[n]为复数序列的情况下，完全直接运算N 点DFT 需要（N-1）2次复数乘法和N （N-1）次加法。

因此，对于一些相当大的N 值（如1024）来说，直接计算它的DFT 所作的计算量是很大的。

FFT 的基本思想在于，将原有的N 点序列分成两个较短的序列，这些序列的DFT 可以很简单的组合起来得到原序列的DFT 。

例如，若N 为偶数，将原有的N 点序列分成两个（N/2）点序列，那么计算N 点DFT 将只需要约[(N/2)2 ·2]=N 2/2次复数乘法。

即比直接计算少作一半乘法。

因子（N/2）2表示直接计算（N/2）点DFT 所需要的乘法次数，而乘数2代表必须完成两个DFT 。

上述处理方法可以反复使用，即（N/2）点的DFT 计算也可以化成两个（N/4）点的DFT （假定N/2为偶数），从而又少作一半的乘法。

这样一级一级的划分下去一直到最后就划分成两点的FFT 运算的情况。

3．基2按时间抽取（DIT ）的FFT 算法思想：设序列长度为2L N =，L 为整数（如果序列长度不满足此条件，通过在后面补零让其满足）。

将长度为2L N =的序列[](0,1,...,1)x n n N =-，先按n 的奇偶分成两组：12[2][][21][]x r x r x r x r =+=，r=0,1,…,N/2-1DFT 化为：1/21/212(21)0/21/21221200/21/211/22/2[]{[]}[][2][21][][][][]N N N nk rk r kNNNn r r N N rk k rk NNN r r N N rk k rk N NN r r X k DFT x n x n Wx r Wx r W x r W Wx r W x r WWx r W ---+===--==--=====++=+=+∑∑∑∑∑∑∑上式中利用了旋转因子的可约性，即：2/2rkrkNN W W =。