[理学]chap4 快速付里叶变换FFT

《[理学]chap4 快速付里叶变换FFT》由会员分享，可在线阅读，更多相关《[理学]chap4 快速付里叶变换FFT（83页珍藏版）》请在金锄头文库上搜索。

1、第四章 快速付里叶变换(FFT) Fast Fouriet Transformer第一节 引 言一、快速付里叶变换FFTn有 限 长 序 列 通 过 离 散 傅 里 叶 变 换 (D F T) 将 其 频 域 离 散 化 成 有 限 长 序 列 . 但 其 计算 量 太 大, 很 难 实 时 地 处 理 问 题 , 因 此 引 出 了 快 速 傅 里 叶 变 换(FFT) .n FFT 并 不 是 一 种 新 的 变 换 形 式 ,它 只 是 DFT 的 一 种 快 速 算 法 . 并 且 根 据 对 序 列 分 解 与 选 取 方 法 的 不 同 而 产 生 了 FFT 的 多 种 算 法

2、.n FFT 在 离 散 傅 里 叶 反 变 换 、 线 性 卷 积 和 线 性 相 关 等 方 面 也 有 重 要 应 用。二、FFT的产生1965年库利-图基在计算数学（Mathematic of Computation ）杂志上发表了著名的“机器计算付里级数 的一种算法”文章，提出一种快速计算DFT的方法和计 算机程序-揭开了FFT发展史上的第一页。促使FFT算 法产生原因还有1967年至1968年间FFT的数字硬件制成 ，电子数字计算机的条件， 使DFT的运算大简化了。FFT出现后使DFT的运算大大简化，运算时间一般可缩短一二个数量级之多，从而使DFT的运算在实际中真正得到了广泛的应用

3、。 三、本章主要内容n1.直接计算DFT算法存在的问题及改进途径 。n2.多种DFT算法(时间抽取算法DIT算法，频 率抽取算法DIF算法，线性调频Z变换即CZT 法)n3.FFT的应用第二节 直接计算DFT算法存在的 问题及改进途径一、直接计算DFT计算量n问题提出： 设有限长序列x(n),非零值 长度为N,计算对x(n)进行一次DFT运算 ，共需多大的运算工作量?1.比较DFT与IDFT之间的运算量其中x(n)为复数， 也为复数所以DFT与IDFT二者计算量相同。2.以DFT为例，计算DFT复数运算量n计算一个X(k)(一个频率成分)值，运算量为例k=1则 要进行N次复数乘法+(N-1)次

4、复数加法 所以，要完成整个DFT运算，其计算量为：nN*N次复数相乘+N*(N-1)次复数加法3.一次复数乘法换算成实数运算量n复数运算要比加法运算复杂，需要的运算时 间长。n一个复数乘法包括4个实数乘法和2个实数相 法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)n 4次实数乘法2次实数加法4.计算DFT需要的实数运算量n每运算一个X(k)的值，需要进行 4N次实数相乘和 2N+2(N-1)=2(2N-1)次实数相加. 整个DFT运算量为：4N2次实数相乘和2N(2N-1)次 实数相加. 由此看出：直接计算DFT时，乘法次数与加法次 数都是和N2成比例的。当N很大时，所需工作量

5、非 常可观。例子n例1:当N=1024点时，直接计算DFT需要： N2=1048576次，即一百多万次的复乘运算 这对实时性很强的信号处理(如雷达信号处理)来 讲，它对计算速度有十分苛刻的要求迫切需 要改进DFT的计算方法，以减少总的运算次数 。n例2：石油勘探，24道记录，每道波形记录长 度5秒，若每秒抽样500点/秒， 每道总抽样点数=500*5=2500点 24道总抽样点数=24*2500=6万点 DFT运算时间=N2=(60000)2=36*108次二、改善DFT运算效率的基本途径能否减少运算量，从而缩短计算时间呢？仔细观察DFT 的运算就可看出， 利用系数Wnk的以下固有特性，就可减

6、少运算量： （1） WNnk的对称性 （2） WNnk的周期性 （3） WNnk的可约性 将长序列DFT利用对称性和周期性 分解为短序列DFTn因为DFT的运算量与N2成正比的n如果一个大点数N的DFT能分解为若干小点 数DFT的组合，则显然可以达到减少运算工 作量的效果。把N点数据分成二半：其运算量为 ： 再分二半 ：+=+=这样一直分下去，剩下两点的变换。n快速付里时变换(FFT)就是在此特性基础上 发展起来的，并产生了多种FFT算法，其基 本上可分成两大类：n按抽取方法分：时间抽取法(DIT);频率抽取法(DIF)n按“基数”分：基-2FFT算法；基-4FFT算法 ；混合基FFT算法；分

7、裂基FFT算法n其它方法：线性调频Z变换(CZT法)第三节 基-2按时间抽取的FFT算 法Decimation-in- Time(DIT) (Coolkey-Tukey)一、算法原理n设输入序列长度为N=2M(M为正整数，将该序 列按时间顺序的奇偶分解为越来越短的子序列， 称为基2按时间抽取的FFT算法。也称为Coolkey- Tukey算法。n其中基数2-N=2M，M为整数.若不满足这个条 件，可以人为地加上若干零值（加零补长）使其 达到 N=2Mn设一序列x(n)的长度为L=9,应加零补长为nN=24=16 应补7个零值。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

8、 15 nx(n)二、算法步骤 1.分组，变量置换DFT变换：先将x(n)按n的奇偶分为两 组，作变量置换:当n=偶数时，令n=2r;当n=奇数时，令n=2r+1;得到：x(2r)=x1(r); x(2r+1)=x2(r); r=0N/2-1; 则其DFT可化为两部分：x(0),x(2)x(2r) 偶数点x(1),x(3)x(2r+1) 奇数点2.代入DFT中代入DFT变换式：3.求出子序列的DFT 上式得：n一个N点的DFT被分解为两个N/2点DFT 。X1(k),X2(k)这两个N/2点的DFT按照：n再应用W系数的周期性，求出用X1(k),X2(k)表 达的后半部的X(k+N/2)的值。

9、频域中的N个点频率成分为：通过这样分解后运算工作量差不多节省了一半。 结论：只要求出（0N/2-1）区间内的各个整 数k值所对应的X1(k),X2(k)值，既可以求出(0N -1)整个区间内全部X(k)值，这就是FFT能大量 节省计算的关键。时间抽取法蝶形运算流图符号 求 N=8点FFT变换按N/2=4，做4点的DFT：将N=8DFT分解成2个4点DFT：可知：时域上：x(0),x(2),x(4),x(6)为偶子序列x(1),x(3),x(5),x(7)为奇子序列频域上：X(0)X(3)，由X(k)给出X(4)X(7),由X(k+N/2)给出按时间抽取将一个N点DFT分解为两个N/2点DFT（

10、N=8） 偶 数 序 列x1(r)奇 数 序 列x2(r)X(4)X(7)同学们自已写既然这样分解是有效的，由于N=2M，因而N/2仍是偶数，可以进一步把每个N/2点子序列再按其奇偶部分分解为两个N/4点的子序列。按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算。且 式中： 下图给出N=8时，将一个N/2点DFT分解成两个N/4点DFT， 由这两个N/4点DFT组合成一个N/2点DFT的流图。 N/2点DFT分解为两个N/4点DFT 一个一个2 2点的点的DFTDFT蝶形流图蝶形流图X2(k)也可进行同样的分解： 式中： 一个N=8点DFT分解为四个2点DFT

11、根据上面同样的分析知道，利用四个N/4点的DFT及两级蝶形组合运算来计算N点DFT，比只用一次分解蝶形组合方式的计算量又减少了大约一半。 最后，剩下的是2点DFT，对于此例N=8，就是四个N/4=2 点DFT，其输出为X3(k)，X4(k)，X5(k)，X6(k)，k=0, 1。故上式不需要乘法。 类似地, 可求出X4(k)，X5(k)，X6(k)。 这种方法的每一步分解，都是按输入序列在时间上的次序是属于偶数还是属于奇数来分解为两个更短的子序列，所以称 为“按时间抽取法”。 N=8 按时间抽取的FFT运算流图三 、FFT算法中一些概念 （1）“级”概念n将N 点DFT先分成两个N/2点DFT

12、，再是四个 N/4点DFT直至N/2个两点DFT.每分一次称为 “一”级运算。n因为N=2m ，所以N点DFT可分成m级（2）“组”概念每一级都有N/2个蝶形单元，例如：N=8,则每级 都有4个蝶形单元。每一级的N/2个蝶形单元可以分 成若干组，每一组具有相同的结构，相同 的因子 分布，第m级的组数为：例：N=8=23，分3级。m=1级,分成四组,每组系数为m=2级,分成二组,每组系数为m=3级,分成一组,每组系数为(3) 因子的分布四、按时间抽取FFT算法的特点根据DIT基2-FFT算法原理，能得出任何N=2m点的FFT信号流图。总结按时间抽取法解过程的规律。1. 原位运算（同址运算）从蝶形

13、图可以看出这种运算是很有规律的，其每级（每列）计算都是由N/2 个蝶形运算构成的，每一个蝶形结构完成下述基本迭代运算： 式中，m表示第m列迭代，k, j为数据所在行数。该式表示的蝶形运算下图所示，由一次复乘和两次复加（减）组成。 蝶形运算单元 X1(0 )X2(0 )X1(2 )X2(2 )由N8按时间抽取法FFT运算流图看出，某一列的任何两个节点k和j的节点变量进行蝶形运算后，得到结果为下一列k, j两节点的节点变量，而和其他节点变量无关，因而可以采用原位运算，即某一列的N个数据送到存储器后，经蝶形运算，其结果为下一列数据，它们仍存储在这同一组存储器中，直到最后输出，中间无需其他存储器。也就

14、是蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中。 这样只需N个存储单元。 下一级的运算仍采用这种原位方式，只不过进入蝶形结的组合关系有所不同。这种原位运算结构可以节省存储单元， 降低设备成本。 2. 倒位序规律观察N8按时间抽取法FFT运算流图，发现当运算完成后，FFT的输出X(k)按正常顺序排列在存储单元中，即按X(0)，X(1)，X(7)的顺序排列，但是这时输入x(n)却不是按自然顺序存储的，而是按x(0)，x(4)， ， x(7)的顺序存入存储单元，看起来好像是“混乱无序”的，实际上是有规律的，我们称之为倒位序。 造成倒位序的原因是输入x(n)按标号n的偶奇的不断分组。 如果n用二

15、进制数表示为(n2n1n0)2（当N=8=23时，二进制为三位）， 第一次分组，n为偶数（相当于n的二进制数的最低位n0=0）在上半部分，n为奇数（相当于n的二进制数的最低位 n0=1）在下半部分。 下一次则根据次最低位n1为“0”或是“1”来分偶奇（而不管原来的子序列是偶序列还是奇序列）， 如此继续分下去，直到最后N个长度为1的子序列。下面的树状图描述了这种分成偶数子序列和奇数子序列的过程。 倒位序的形成 表 N=8时的自然顺序二进制数和相应的倒位序二进制数 自然顺序（I） 二进制数 倒位序二进制数 倒位序（J） 0 1 2 3 4 5 6 7000 001 010 011 100 101

16、110 111000 100 010 110 001 101 011 1110 4 2 6 1 5 3 7看出：码位倒读后的顺序刚好是数据送入计算机内的顺序。N=8 倒位序的变址处理 3. 蝶形运算两节点的“距离”以8点FFT为例，其输入是倒位序的，输出是自然顺序的。 其第一级（第一列）每个蝶形的两节点间“距离”为1， 第二级每个蝶形的两节点“距离”为2， 第三级每个蝶形的两节点“距离”为4。 由此类推得，对N=2m点FFT，当输入为倒位序， 输出为正常顺序时，其第m级运算，每个蝶形的两节点“距离”为2m-1。 N=8 按时间抽取的FFT运算流图X1(k )X4(k )X2(k )X3(k )X5(k )X6(k )五、按时间抽取的FFT算法与直 接计算DFT运算量的比较n由前面介绍的按时间抽取的FFT运算流图可见：n复乘次