N点DFT，用FFT快速算法实现。.ppt

N点DFT，用FFT快速算法实现。

* 第 5章 快速傅立叶变换 * 第 5章 快速傅立叶变换 第5章 快速傅立叶变换 5.1 快速计算DFT的改进途径 5.2 按时间抽选的基—2FFT算法 5.3 按频率抽取的基-2FFT算法 5.4 离散傅里叶逆变换的快速算法 5.5 数字信号处理的FFT实现 5.6 线性调频z变换（Chirp-z变换）算法 5.1 快速计算DFT的改进途径 1.直接计算DFT的计算量 设x(n)为N点的有限长序列，其离散傅立叶变换为 直接计算X(k)的实数乘法运算量： 直接计算X(k)的实数加法运算量： 2.快速计算DFT的改进途径： 仔细观察DFT的运算就可以发现，变换式中的系数 具有以下性质： (1) 的共轭对称性： (2) 的周期性： 5.2 按时间抽选的基—2FFT算法 5.2.1 DIT—FFT算法的基本原理 设有限长序列 的长度为N=2L，L为整数。如果不满足 这个条件，可以在序列末尾补零点值，使之达到这个要 求。这个序列长度N为2的整数幂的FFT也称为基—2FFT。 由于N为偶整数，所以可对 先按奇偶分成如下两组： 这样，序列的DFT可改写为： N为偶数 N为奇数 利用系数的可约性： X(k)可改写为： 式中 和 分别是 和 的 点DFT 式中 和 分别是 点DFT，得到的只是 的 前一半项数的结果。 由DFT性质可知， 、 都是周期为 的周期函数 这样，就可将 表示为前后两部分。 实现上式运算的流图称作蝶形运算 （N/2个蝶形) (前一半) (后一半) -1 例如讨论N=8的蝶形流图表示方法 x1(0)=x(0) x1(1)=x(2) N/2点 x1(2)=x(4) DFT x1(3)=x(6) x2(0)=x(1) x2(1)=x(3) N/2点 x2(2)=x(5) DFT x2(3)=x(7) X1(0) X1(2) X1(3) X2(0) X2(1) X2(2) X2(3) W N 2 W N 1 W N 0 W N 3 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) X1(1) 按时间抽取，将一个8点DFT分解为两个4点的DFT 由于N=2L ,所以 N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。例如，n为偶数时的 N/2点分解为: 则有： N=8时，将一个N/2点DFT分解成两个N/4点DFT组合成一 个N/2点DFT的流程图。 N/4点 DFT N/4点 DFT -1 -1 由两个N/4点DFT组合成一个N/2点DFT 也可以进行同样的分解： 其中 将系数统一为： 则N=8点DFT就可以分解为四 个N/4=2点DFT，就可以得到如下流程图 按时间抽选，将一个N点DFT分解为四个N/2点DFT 对于N=8时DFT,N/4点即为两点DFT,因此 即 因此，8点按时间抽取的完整的FFT流程图如下图所示 N=8按时间抽选法FFT运算流程图 5.2.2 DIF-FFT算法的特点 (1)蝶形结构运算 序列的长度为N=2L，一共需要分解成L级运算，每级包含 N/2个蝶形运算，总共蝶形运算个数为 个。 (2)运算量小 复乘次数： 复加次数： (3)采用原位运算 (4)输入序列顺序的倒位序 为了得到倒位序的排列，可通过变址运算来完成，其实现 方法是：将输入序列的序号n用二进制表示(n2n1n0)，然后 将该二进制倒位，形成倒位序二进制(n0n1n2)，然后将该 二进制(n0n1n2)转化成十进制数 5.3 按频率抽取的基-2FFT算法 5.3.1 DIF-FFT算法的基本原理 设序列点数为N=2L，L为整数。 首先对时间分先后，将x(n)按n的顺序分为前后两部分，并 按照定义得： 因为 所以上式改写为： 按照k的奇偶将X(k)分成奇偶两部分： 若令： 则有： 则用蝶形图表示为： -1

相关知识

【机器学习】KNN算法实现鸢尾花分类
原生python实现knn分类算法(鸢尾花数据集)
Python原生代码实现KNN算法（鸢尾花数据集）
机器学习算法
KNN算法实现鸢尾花数据集分类
Knn算法实现鸢尾花分类
堪称最好最全的A*算法详解（译文）
基于花授粉算法优化实现SVM数据分类
不同浇水频率对鼠尾草生长的影响
机器学习（三）：感知器算法实现鸢尾花分类项目实战

网址: N点DFT，用FFT快速算法实现。.ppt https://www.huajiangbk.com/newsview548685.html