快速傅里叶变换FFT算法及其应用 [当文网提供].doc

快速傅里叶变换 FFT 算法及其应用 摘 要 本文较为系统地阐述了快速傅里叶变换的算法原理及其在数字信号处理等 工程技术中的应用。根据抽取方法的不同，一维基 2 FFT 算法分为两种：频域 抽取的 FFT 算法和时频域抽取的 FFT 算法。第 1 节阐述了这两种 FFT 算法的 原理。第 2 节给出了两种算法的编程思想和步骤。第 3 节阐述了一维非基 2 FFT 的两种算法：Cooley-tukey FFT 算法和素因子算法(Prime Factor Algorithm) 的思想原理，给出了在把一维非基 2 DFT 的多层分解式转化为二层分解的过程 中，如何综合运用这两种算法以达到总运算次数最少的方案；并以 20 点 DFT 为例描述了非基 2 FFT 算法实现的一般步骤。第 4 节介绍了一维 FFT 算法在计 算连续时间信号的傅里叶变换、离散信号的线性卷积、离散信号压缩和滤波等 数字信号处理中的典型应用。第 5 节把一维 FFT 变换推广到二维 FFT 变换，并 在一维 FFT 算法的基础上，给出了二维 FFT 算法的原理和实现过程。最后在附 录中给出了一维 DFT 的基 2 FFT 算法（包括频域抽取的 FFT 和 IFFT 算法、时 域抽取的 FFT 和 IFFT 算法） ，一维任意非基 2 FFT 算法，二维 DFT 的基 2 FFT 算法以及二维 DFT 的任意非基 2 FFT 算法的详细的 Visual C+程序。 本文通过各种流程图和表格，较为深入系统地阐述了 FFT 的算法原理；运 用 Matlab 编程，通过大量生动的实例，图文并茂地列举出了 FFT 算法的各种应 用，并在每个实例中都附上了完整的 Matlab 程序，可供读者参考。由于篇幅所 限，本文未涉及 FFT 变换以及其应用的数学理论背景知识。 关键词：FFT 算法的应用，一维基 2 FFT 算法，频域抽取，时域抽取，非 基 2 FFT 算法，Cooley-Tukey 算法，素因子算法，线形卷积，信号压缩和滤波， 二维 FFT 算法 目 录 摘 要.1 目 录.2 1 一维 DFT 的快速算法FFT .4 1.1 频域抽取的基 2 算法.4 1.1.1 正变换的计算 .4 1.1.2 逆变换的计算 .7 1.2 时域抽取的基 2 算法.8 2 一维基 2 FFT 算法编程.10 3 一维任意非基 2 FFT 算法.14 3.1 COOLEY-TUKEY FFT 算法.14 3.2 素因子算法（PFA）.14 3.3 一维任意非基 2 FFT 算法.16 4 一维 FFT 算法的应用.20 4.1 利用 FFT 计算连续时间信号的傅里叶变换.20 4.2 利用 FFT 计算离散信号的线性卷积.23 4.3 利用 FFT 进行离散信号压缩.25 4.4 利用 FFT 对离散信号进行滤波.28 4.5 利用 FFT 提取离散信号中的最强正弦分量.31 5 二维 DFT 的快速变换算法及应用简介.36 5.1 二维 FFT 变换及其算法介绍.36 5.2 二维 FFT 变换算法的应用.37 参考文献.38 附 录.39 1一维 DFT 的基 2 FFT 算法 VISUAL C+程序.39 （1） 频域抽取的 FFT 和 IFFT 算法.39 （2） 时域抽取的 FFT 和 IFFT 算法.44 2一维任意非基 2 FFT 算法 VISUAL C+程序.49 3二维 DFT 的基 2 FFT 算法 VISUAL C+程序.54 4二维 DFT 的任意非基 2 FFT 算法 VISUAL C+程序.62 1 一维 DFT 的快速算法FFT 当序列的点数不超过时，它的点定义为 f nNNDFT 2 1 0 01 N ikn N n F kf n ekN （1） 反变换定义为IDFT （2） 2 1 0 1 01 N ikn N k f nF k enN N 二者形式相似，快速算法的原理一样，这里先就其正变换进行讨论。令 ，当依次取为时，可表示为如下的方程组： 2/iN N We k0,1,2,1N （3） 0001020(1) 1011121(1) 2021222(1) (1)0(1)1(1)(1) 00121 10121 20121 1011 N NNNN N NNNN N NNNN NNNN NNN FfWfWfWf NW FfWfWfWf NW FfWfWfWf NW F NfWfWf NW 由上式可见，直接按照定义计算点序列的点时，每行含个复NNDFTN 乘和个加，从而直接按定义计算点的总计算量为个复乘和个加。当N 2 N 2 N 较大时，很大，计算量过大不仅耗时长，还会因字长有限而产生较大的N 2 N 误差，甚至造成计算结果不收敛。所谓快速傅里叶变换就是能大大减少计算量 而完成全部点计算的算法。下面介绍两种经典的的快速算法：频域抽取的DFT 算法和时域抽取的算法。FFTFFT 1.1 频域抽取的基 2 算法 1.1.1 正变换的计算 这里仅介绍基 2 算法，即是 2 的整次幂的情况。由定义 1 0 01 N kn N n F kf n WkN （4） 把分成两半，即和，代入（4）式得 f n f n/2f nN(0/2 1)nN /2 1/2 1 (/2) 00 /201 NN knk n N NN nn F kf n Wf nNWkN （5） 由于 (/2)/2 ( 1) k n NknkNkkn NNNN WW WW （5）式两项又可合并为 /2 1 0 ( 1)/201 N kkn N n F kf nf nNWkN （6） 当为偶数时，注意到， （6）2kr( 1)1 k 22 2/knrnirn N NN WWe /2 rn N W 式变为 （7） /2 1 /2 0 /2 1 /2 0 2 ( /2) ( ) ( )0/2 1 N rn N n N rn N n Frf nf nNW g n W G rrN 当为奇数时， ， （6）式变为21kr (21)2 (21) / /2 knrnirn Nnrn NNNN WWeW W （8） /2 1 /2 0 /2 1 /2 0 21( /2) ( )( )0/2 1 N nrn NN n N rn N n Frf nf nNWW p n WP rrN 这样就把一个点序列（）的点（）计算化成了两个N f nNDFT F k 点序列（和）的点（和）计算。由划分/2N g n p n/2NDFT G r P r f n 成 g n 和的计算量为个加，即 p nN 和 /2f nf nN /2, 0/2 1f nf nNnN 和个乘，即/2N ( /2), 0/2 1 n N f nf nNWnN 由于算出的点，是的点（）中为偶数的 g n/2NDFT f nNDFT F kk 那一半，由算出的则是为偶数的那一半，故需要把偶数的抽出来 p nkk F k 放在一起作为的（）输出，同时把奇数的抽出来放在一起 g nDFT( )G rk F k 作为的（）输出。由于是频域变量，故这种算法称为频域抽取 p nDFT( )P rk 的算法。FFT 接着，两个点仍可用上述方法各经个乘个加划分成两/2NDFT/4N/2N 个点（同时还要做相应的频域抽取） ，从而共划分成 4 个点/4NDFT/2N ，总划分计算量仍是个加和个乘。这样的划分可一步步做下去，DFTN/2N 不难看出，每步的总划分计算量都是个加和个乘。N/2N 经过步的划分后就划成了个如下两点的计算问题1M /2NDFT （9） 0 001 22 10110 222 () AaWbWab BaWbWab W 上式所需计算量是 2 个加和 1 个乘，于是完成个两点的总计算量/2NDFT 仍是个加和个乘。从而完成全部点的总计算量N/2NNDFT 个加和个乘，这比直接按定义计算所 2 logMNNN 2 /2(/2)logMNNN 需的个乘和加要少得多。例如，用算法计算 2 N 10 21024N 10M FFT 所需的乘法个数为，而直接按定义计算所需的乘法个数为/2MN5 1024 ，二者相差倍。若直接计算需半小时，而用 2 1024 1024N 1024/5200 计算只需 9s 即可完成，可见其效率之高，而且越大，的效率提高FFTNFFT 越明显。 f0 F0000 F0 F0000 f1 -1 W20 F4100 F2 F1001 gn f2 -1 W40 F2010 F4 F2010 f3 -1 W41 -1 W20 F6110 F6 F3011 f4 -1 W80 F1001 F1 F4100 f5 -1 W81 -1 W20 F5101 F3 F5101 pn f6 -1 W82 -1 W40 F3011 F5 F6110 f7 -1 W83 -1 W41 -1 W20 F7111 F7 F7111 图图 1 频域抽取的频域抽取的 8 点点 FFT 计算流图计算流图 一般情况下，由于做了次分奇偶的抽取，此算法最后的个两点1M /2N 计算出的不是顺序抽取的。次序的变化可用二进码来说明：第一次抽DFT F k 取所分的奇偶是由二进码第 1 位是 1 或 0 来区分的，该位为 0 时为偶数，该位 为 1 时为奇数，第二次抽奇偶是由二进码第 2 位是 1 或 0 来区分的，每次 抽取都是把偶数项放在前（左）边，把奇数项放在后（右）边，从而抽取以后 数的二进码是按照二进制位从左向右依次排列的，和普通二进制数从右向左依 次排列的的规律正好相反，所以称为倒位序。在计算出之后要把倒位序变 F k 成顺序。 1.1.2 逆变换的计算 所谓逆变换是指由求的计算，若直接按定义 F k f n 1 0 1 01 N kn N k f nF k WnN N 做计算，则除了求和号和正变换相同的计算量外，每算一个都还需再多做 f n 一个乘的乘法运算。故按定义完成全部点的总计算量是个加和1/ NNDFT 2 N 个乘。下面从图导出它的快速算法，先讨论第 3 列的 2 点的逆运(1)N N DFT 算如何完成。由式（7）得， 0 2 () abA ab WB 由上式不难解出 0 2 0 2 1 () 2 1 () 2 aABW bABW （10） F0000 F0 F0000 1/8 f0 F1001 F2 F4100 1/8 W2-0 -1 f1 F2010 F4 F2010 1/8 W4-0 -1 f2 F3011 F6 F6110 1/8 W2-0 -1 W4-1 -1 f3 F4100 F1 F1001 1/8 W8-0 -1 f4 F5101 F3 F5101 1/8 W2-0 -1 W8-1 -1 f5 F6110 F5 F3011 1/8 W4-0 -1 W8-2 -1 f6 F7111 F7 F7111 1/8 W2-0 -1 W4-1 -1 W8-3 -1 f7 图图 2 频域抽取的频域抽取的 8 点点 IFFT 计算流图计算流图 此计算过程如图 2 所示，可以看出：左边各列的划分计算也都是由个/2N 碟形运算来完成的，只是各碟形运算所乘的相移因子不同。把每个碟形运算W 都用图的办法变成对应的逆运算，并把它们按输入在左、输出在右重新排列， 就得到了全部点的计算流图。给出了的示例，图中先对顺序输入NIDFT8N 的做次的频域抽取，并把 个乘的运算合成了一个乘的运算 F k1M 31/21/8 放在了最前边，然后就开始做求逆的碟形运算。 1.2 时域抽取的基 2 算法 比较正变换和反变换的定义式DFTIDFT 1 0 01 N kn N n F kf n WkN 1 0 1 01 N kn N k f nF k WnN N 可见，去掉乘的运算，把换成，交换、和、，反1/ N 1 W W F k f nkn 变换定义式就变成了正变换的定义式。对图 2 做这些变换，则得到图 3 的流程 图。对图 1 做这些变换，则得到图 4 的流程图。这就是时域抽取的算法流图。 进行碟形运算之前，先要对顺序的时域输入序列进行次的奇偶抽取，故称1M 为时域抽取的算法。FFT f0000 f0 f0000 F0 f1001 f2 f4100 W20 -1 F1 f2010 f4 f2010 W40 -1 F2 f3011 f6 f6110 W20 -1 W41 -1 F3 f4100 f1 f1001 W80 -1 F4 f5101 f3 f5101 W20 -1 W81 -1 F5 f6110 f5 f3011 W40 -1 W82 -1 F6 f7111 f7 f7111 W20 -1 W41 -1 W83 -1 F7 图图 3 时域抽取的时域抽取的 8 点点 FFT 计算流图计算流图 比较图 2 和图 3 不难看出，两种算法的计算量是完全一样的。这里先算出 个两点的/2NDFT 0 001 22 ( )(/2)( )(/2)Af n Wf nNWf nf nN （11） 1011 22 ( )(/2)( )(/2)Bf n Wf nNWf nf nN f01/8 F0000 F0 F0000 f11/8 -1 W2-0 F4100 F2 F1001 f21/8 -1 W4-0 F2010 F4 F2010 f31/8 -1 W4-1 -1 W2-0 F6110 F6 F3011 f41/8 -1 W8-0 F1001 F1 F4100 f51/8 -1 W8-1 -1 W2-0 F5101 F3 F5101 f61/8 -1 W8-2 -1 W4-0 F3011 F5 F6110 f71/8 -1 W8-3 -1 W4-1 -1 W2-0 F7111 F7 F7111 图图 4 时域抽取的时域抽取的 8 点点 IFFT 计算流图计算流图 然后把个两点的组合成个4点的，再把个4点的/2NDFT/4NDFT/4N 组合成个8点的，经过次的组合之后，就得到了顺序点DFT/8NDFT1M N 计算结果。算法原理参考文献【4】 。DFT 2 一维基 2 FFT 算法编程 以频域抽取的基 2 FFT 正变换为例，对 FFT 的信号流图进行讨论，以找到 FFT 算法的规律。 1）分级 在进行变换的过程中，从点到两点共分了 M 级，如图 1DFTNDFTDFT 所示，从左到右依次为级，级，级。1m 2m mM 2）倒位序 在频域抽取的基 2 FFT 算法中，输出数据不是按照序列的先后顺序排列的， 这是由于变换过程中，输出按奇、偶抽取的缘故。如果将序列中标号用 x nn 二进制值表示，那么在 FFT 信号流图输入端，位于 021 2 () MM nnn x n 处，称为倒序。以 8 点 FFT 为例，顺序和倒序的关系如表 1 所 1202 () MM nnn 示。 表表 1 顺序和倒序对照表顺序和倒序对照表 顺序倒序 十进制数二进制数二进制数十进制数 0 1 2 3 4 5 6 7 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 4 2 6 1 5 3 7 从表 1 可以看出，一个自然顺序二进制数，是在最低位加 1，逢 2 向左移 位；而倒序数的顺序是在最高位加 1，逢 2 向右移位。用 表示顺序数，表示ij 倒序数，表示位权重。对于一个倒序数来说，下一个倒序数可以按下面的kj 方法求：先对最高位加 1，相当于十进制运算。如果，说明二/2jN/2jN 进制最高位为 0，则直接由得到下一个倒序值；如果，说明二/2jN/2jN 进制最高 位为 1，则将的最高位变为 0，通过实现，同时令，接j/2jjN/2kk 着判断次高位是否为 0，直到位为 0 时，令。归结起来算法流程图jjk 如图 5 所示。 j=N/2 i=1 to N-2 t=fi fj=fi fi= fj k=N/2 j=j-k k=k/2 kj j=j+k ij 是 是 否 否 输入 N, 信号 fN M=log2N l=1 to lb r=(l-1)2m-1 n=(l-1): la: N- 2 m=1 to M la=2M+1-m lb=la/2 lc=n+lb t=fn+flc flc=(fn-flc) WNr fn=t 倒位序重排信号 图图 5 倒位序程序流程图倒位序程序流程图 图图 6 频域抽取频域抽取 FFT 程序流程图程序流程图 3）蝶形运算单元和同址计算 频域抽取的信号流图中，基本的运算结构如图 7 所示，该运算结构的形状 输 出 像蝴蝶，故称为“蝶形运算单元” 。 在这一结构中，DFT 和 IDFT 运算关系分别为 （12） 11 11 ( ) mmm r mmmN FpFpFq FpFpFq W 11 11 ( )/2 ( )/2 r mmmN r mmmN fpfpfq W fpfpfq W Fm-1p Fm p Fm-1q -1 WNr Fmq (a) 两点 DFT 的计算 fm-1p 1/2 fmp fm-1q WN-r -1 1/2 fmq (b) 两点 IDFT 的计算 图图 7 频域抽取频域抽取 FFT 算法流图中第算法流图中第 m 级碟形单元级碟形单元 而在时域抽取的信号流图中，基本的运算结构如图 8 所示。在这一结构中， DFT 和 IDFT 运算关系分别为 11 11 r mmmN r mmmN FpFpFq W FpFpFq W 11 11 ( )/2 ( )/2 mmm r mmmN fpfpfq fpfpfq W （13） Fm-1p Fmp Fm-1q WNr -1 Fmq (a) 两点 DFT 的计算 fm-1p 1/2 fm p fm-1q -1 WN-r/2 fmq (b) 两点 IDFT 的计算 图图 8 时域抽取时域抽取 FFT 算法流图中第算法流图中第 m 级碟形单元级碟形单元 其中，、分别表示该蝶形运算单元的上下节点的序号。可以看出参与pq 运算的输入序号，输出序号仍为，并且该运算不涉及到其它的点，因此我pq 们可以将输出的结果仍然放在数组中，称这样的操作为同址计算。也就是说， 共同占有同一个存储单元。 4）寻址和相移因子的计算 r N W 时域抽取基 2 FFT 信号流图中，每一级有个蝶形单元。每一级的个蝶形单 元又可以分为若干组，每一组具有相同的结构和因子的分布。 如图 1 所示，第 1 级分为 1 组，第 2 级分为 2 组，第级分为组。m 1 2m 在第级中，相邻组之间的间距（也即每个分组所含节点数）为，每个m 1 2M m 蝶形单元的上下节点之间的距离（也即每个分组所含碟形单元数）为。每2M m 组的相移因子 ，其中 22 cos()sin() r N Wrir NN m-1 r=(l-1) 2,0,1,l ,21 Mm 综合以上各步骤，得到频域抽取 FFT 程序流程图如图 6 所示。采用类似的 步骤可得到频域抽取 IFFT 流程图、时域抽取 FFT 与 IFFT 流程图（略） 。 频域抽取 FFT 算法、时域抽取 FFT 算法的 Visual C+源程序分别见附录 1.（1） ，1.（2） 。在 Matlab 中，傅里叶变换及其逆变换分别用 dwt()和 idwt()函 数实现。 3 一维任意非基 2 FFT 算法 3.1 Cooley-Tukey FFT 算法 的核心是将一层运算映射为二层运算。作点时，若不是素FFTNFFTN 数，则可分解为，那么由的N 12 NN N f nDFT 1 0 01 N nk N n F kf n WkN （14） 通过映射： 2121122 1121122 01,01 01,01 nN nnnNnN kkN kkNkN （15） 可得到 2 1211 22 1 112 1 22 11 2 2 ()()()N nnkN kN n kN N n kn kN n knk NNN WWW 而，可化简为 12 NN N 1 2 N NN WW 2 1 N NN WW 1 12 12 2 12 n kn kn knk NNNN WWWW （16） 从而式（14）转化为 （17） 21 2 22 11 1 21 21 11 1212 00 ,( ,) NN n kn kn k NNN nn F k kWWf n n W 其中。 1122 01,01kNkN 以点为例，映射方式为：，20FFT 12 20,5,4NNN 12 4nnn ，则计算流图如图 9 所示。 12 5kkk 3.2 素因子算法(Prime Factor Algorithm, PFA) 当 Cooley-Tukey FFT 算法中的、互素的话，相移因子可通过选 1 N 2 N 2 1 n k N W 择前的特殊系数而消去，FFT 的算法进一步的简化。 12 ,n n 12 ,k k 121122 121122 01,01 01,01 nAnBnnNnN kCkDkkNkN （18） 当满足以下条件ABCD、 0 mod 0 mod ADN BCN （19） n1 k2 f0 0 W0 0 F0 f4 1 W0 1 F5 f8 2 W0 2 F10 f12 3 W0 3 F15 f16 4 W0 0 F1 f1 0 W1 1 F6 f5 1 W2 2 F11 f9 2 W3 3 F16 f13 3 f17 4 W0 0 F2 W2 1 F7 f2 0 W4 2 F12 f6 1 W6 3 F17 f10 2 f14 3 W0 0 F3 f18 4 W3 1 F8 W6 2 F13 f3 0 W9 3 F18 f7 1 f11 2 W0 0 F4 f15 3 W4 1 F9 f19 4 W8 2 F14 W12 3 F19 k1=0 n2=0 n2=1 n2=2 n2=3 k1=1 k1=2 k1=3 k1=4 图图 9 Cooley-Tukey 20 点点 FFT 算法算法 2 1 mod mod ACNN BDNN （19） 时，有 1212 1 11 22 12 2 2 1 11 2 2 1 12 2 12 ()() () AnBnCkDknk NN ACn kADn kBCn kBDn k N N n kN n k N n kn k NN WW W W WW （20） 于是式（14）化简为 21 2 21 1 21 21 11 1212 00 ,( ,) NN n kn k NN nn F k kWf n n W （21） 从而消去了相移因子。同样以点为例，修改映射方式为： 2 1 n k N W20FFT 20,N 12 5,4NN 1212 45, 04,03nnnnn （22） 1212 1625,04,03kkkkk （23） 则由式（22）得到的映射关系如表 2，由式（23）得到的映射关系如表 3， 计算流图如图 10 所示。 表表 2 由式由式(22)得到的映射关系得到的映射关系 n1 n20123 0051015 1491419 2813183 3121727 4161611 表表 3 由式由式(23)得到的映射关系得到的映射关系 k1 k20123 0051015 1161611 2121727 3813183 4491419 3.3 一维任意非基 2 FFT 算法 对于非素数点，对做因式分解NDFTN 12l NN NN （24） 令，则。于是式（24）中多层转化为二层。 22ll NNN 12l NN NFFTFFT 如果与互素，那么采用 PFA 算法进行映射，否则采用 Cooley-Tukey FFT 1 N 2l N 算法（此时需乘以相移因子） 。可采用同样的方法分解成个 22ll NNN 2 N n k 点，其中，依此类推，直到长度为。 3l NDFT 33ll NNNDFT l N 可以证明，复乘的总次数不大于 12 () l N NNNl （25） 例如，若，则复乘总次数至多为。而633 3 7N 63 (3 3 73)630 用基 2 的算法计算 64 点，需要的复乘总次数为 192。这说明，将FFTDFT 分解得越细，运算量越少。实际中，常常将输入序列补零，使得成为 2 的NN 幂次数，这样能够减少复乘运算的次数。 n1 k2 f0 0 0 F0 f4 1 1 F5 f8 2 2 F10 f12 3 3 F15 f16 4 0 F16 f5 0 1 F1 f9 1 2 F6 f13 2 3 F11 f17 3 f1 4 0 F12 1 F17 f10 0 2 F2 f14 1 3 F7 f18 2 f2 3 0 F8 f6 4 1 F13 2 F18 f15 0 3 F3 f19 1 f3 2 0 F4 f7 3 1 F9 f11 4 2 F14 3 F19 k1=0 n2=0 n2=1 n2=2 n2=3 k1=1 k1=2 k1=3 k1=4 图图 10 素因子素因子(PFA)20 点点 FFT 算法算法 再以点为例，进行如下三层因式分解20FFT 123 5 2 2NN N N 即，由于 5 与 4 互素，所以第一层采用 PFA 算法，相应 1 5N 23 2 24N 的二层映射为 123123 45, 04,03nnnnn 123123 1625,04,03kkkkk 由于 2 与 2 不互素，所以第二层采用 Cooley-Tukey FFT 算法，相应的二层 映射为 232323 2, 01,01nnnnn 232323 2,01,01kkkkk 总的变换公式如式（26） ，计算流图如图 11 所示。FFT n1 k1 n2 k2 n3 k3 f0 0 0 0 0 W40 0 0 F0 f4 1 1 1 1 W40 1 1 F10 f8 2 2 f12 3 3 0 0 W40 0 0 F5 f16 4 4 1 1 W41 1 1 F15 0 0 W40 0 0 F16 1 1 W40 1 1 F6 f5 0 0 f9 1 1 0 0 W40 0 0 F1 f13 2 2 1 1 W41 1 1 F11 f17 3 3 f1 4 4 0 0 W40 0 0 F12 1 1 1 1 W40 1 1 F2 0 0 W40 0 0 F17 f10 0 0 1 1 W41 1 1 F7 f14 1 1 f18 2 2 0 0 W40 0 0 F8 f2 3 3 1 1 W40 1 1 F18 f6 4 4 0 0 W40 0 0 F13 1 1 W41 1 1 F3 f15 0 0 0 0 W40 0 0 F4 f19 1 1 1 1 W40 1 1 F14 f3 2 2 f7 3 3 0 0 W40 0 - 0 F9 f11 4 4 1 1 W41 1 1 F19 n23=0 n23=1 n23=2 n23=3 n3=0 n3=1 n3=0 n3=1 n3=0 n3=1 n3=0 n3=1 n3=0 n3=1 图图 11 多层分解时多层分解时 20 点点 FFT 算法算法 321 3 33 22 21 1 32321 321 111 123123 000 ,( ,) NNN n kn kn kn k NNNN nnn F k k kWWWf n n n W 3 33 22 21 1 321 114 2421235 000 ( ,) n kn kn kn k nnn WWWf n n n W （26） 比较正变换和反变换的定义式可知，在正变换前加上乘的DFTIDFT1/ N 运算，把换成，并交换、和、，就得到反变换的算法。W 1 W f n F knk 一维任意非基 2 FFT 算法的 Visual C+源程序见附录 2。在 Matlab 中，傅 里叶变换及其逆变换也分别用