 由于  式两项又可合并为   当为偶数时注意到式 变为          当为奇数时式变为         这样就把个点序列的点计算化成了两个 点序列和的点和计算。由划分成 和的计算量为个加即 和 和个乘即  由于算出的点是的点中为偶数的 那半由算出的则是为偶数的那半故需要把偶数的抽出来放 在起作为的输出同时把奇数的抽出来放在起作 为的输出。由于是频域变量故这种算法称为频域抽取的 算法。快速傅里叶变换算法及其应用 接着两个点仍可用上述方法各经个乘个加划分成两个 点同时还要做相应的频域抽取从而共划分成个点 总划分计算量仍是个加和个乘。这样的划分可步步做下去不难看出 每步的总划分计算量都是个加和个乘。 经过步的划分后就划成了个如下两点的计算问题   上式所需计算量是个加和个乘于是完成个两点的总计算量 仍是个加和个乘。从而完成全部点的总计算量 个加和个乘这比直接按定义计算所需的个乘和加要 少得多。例如用算法计算所需的乘法个数为 而直接按定义计算所需的乘法个数为二 者相差倍。若直接计算需半小时而用计算只需即可完成 可见其效率之高而且越大的效率提高越明显。 图频域抽取的点计算流图 般情况下由于做了次分奇偶的抽取此算法最后的个两点 计算出的不是顺序抽取的。次序的变化可用二进码来说明第次抽 取所分的奇偶是由二进码第位是或来区分的该位为时为偶数该位为 时为奇数第二次抽奇偶是由二进码第位是或来区分的„„每次抽取    图频域抽取的点计算流图 快速傅里叶变换算法及其应用 此计算过程如图所示可以看出左边各列的划分计算也都是由个 碟形运算来完成的只是各碟形运算所乘的相移因子不同。把每个碟形运算 都用图的办法变成对应的逆运算并把它们按输入在左输出在右重新排列就 得到了全部点的计算流图。给出了的示例图中先对顺序输入的 做次的频域抽取并把个乘的运算合成了个乘的运算放在 了最前边然后就开始做求逆的碟形运算。 时域抽取的基算法 比较正变换和反变换的定义式     可见去掉乘的运算把换成交换和反变 换定义式就变成了正变换的定义式。对图做这些变换则得到图的流程图。 对图做这些变换则得到图的流程图。这就是时域抽取的算法流图。进行碟 形运算之前先要对顺序的时域输入序列进行次的奇偶抽取故称为时域 抽取的算法。 图时域抽取的点计算流图 维基算法编程 比较图和图不难看出两种算法的计算量是完全样的。这里先算出 个两点的   图时域抽取的点计算流图 然后把个两点的组合成个点的再把个点的 组合成个点的经过次的组合之后就得到了顺序点 计算结果。算法原理参考文献。 维基算法编程 以频域抽取的基正变换为例对的信号流图进行讨论以找到 算法的规律。 分级 在进行变换的过程中从点到两点共分了级如图 所示从左到右依次为级级„级。 倒位序 快速傅里叶变换算法及其应用 在频域抽取的基算法中输出数据不是按照序列的先后顺序排列的 这是由于变换过程中输出按奇偶抽取的缘故。如果将序列中标号用二 进制值表示那么在信号流图输入端位于 处称为倒序。以点为例顺序和倒序的关系如表所示。 表顺序和倒序对照表 顺序倒序 十进制数二进制数二进制数十进制数 从表可以看出个自然顺序二进制数是在最低位加逢向左移位 而倒序数的顺序是在最高位加逢向右移位。用表示顺序数表示倒序 数表示位权重。对于个倒序数来说下个倒序数可以按下面的方法求 先对最高位加相当于十进制运算。如果说明二进制最高 位为则直接由得到下个倒序值如果说明二进制最高 位为则将的最高位变为通过实现同时令接 着判断次高位是否为直到位为时令。归结起来算法流程图 如图所示。维基算法编程 图倒位序程序流程图图频域抽取程序流程图 蝶形运算单元和同址计算 频域抽取的信号流图中基本的运算结构如图所示该运算结构的形状像 蝴蝶故称为蝶形运算单元。 在这结构中和运算关系分别为        输入信号 倒位序重排信号  是 是 否 否 输 出快速傅里叶变换算法及其应用 摘要 本文较为系统地阐述了快速傅里叶变换的算法原理及其在数字信号处理等 工程技术中的应用。根据抽取方法的不同维基算法分为两种频域抽 取的算法和时频域抽取的算法。第节阐述了这两种算法的原理。 第节给出了两种算法的编程思想和步骤。第节阐述了维非基的两种 算法算法和素因子算法的思想原理 给出了在把维非基的多层分解式转化为二层分解的过程中如何综合 运用这两种算法以达到总运算次数最少的方案并以点为例描述了非基 算法实现的般步骤。第节介绍了维算法在计算连续时间信号的 傅里叶变换离散信号的线性卷积离散信号压缩和滤波等数字信号处理中的典 型应用。第节把维变换推广到二维变换并在维算法的基 础上给出了二维算法的原理和实现过程。最后在附录中给出了维 的基算法包括频域抽取的和算法时域抽取的和 算法维任意非基算法二维的基算法以及二维的 任意非基算法的详细的程序。 本文通过各种流程图和表格较为深入系统地阐述了的算法原理运 用编程通过大量生动的实例图文并茂地列举出了算法的各种应 用并在每个实例中都附上了完整的程序可供读者参考。由于篇幅所 限本文未涉及变换以及其应用的数学理论背景知识。 关键词算法的应用维基算法频域抽取时域抽取非基 算法算法素因子算法线形卷积信号压缩和滤波二 维算法 快速傅里叶变换算法及其应用 摘要 目录 摘要 目录 维的快速算法 频域抽取的基算法 正变换的计算 逆变换的计算 时域抽取的基算法 维基算法编程 维任意非基算法 算法 素因子算法 维任意非基算法 维算法的应用 利用计算连续时间信号的傅里叶变换 利用计算离散信号的线性卷积 利用进行离散信号压缩 利用对离散信号进行滤波 利用提取离散信号中的最强正弦分量 二维的快速变换算法及应用简介 二维变换及其算法介绍 二维变换算法的应用 参考文献