《信号分析与处理 教学课件 ppt 作者 杨西侠 柯晶 3-4FFT》由会员分享，可在线阅读，更多相关《信号分析与处理 教学课件 ppt 作者 杨西侠 柯晶 3-4FFT（41页珍藏版）》请在金锄头文库上搜索。
1、1,3.6.1 DFT运算的特点 1. DFT计算工作量,将x(n)与WNnK两两相乘再取和即可得到X(k)。每计算一个X(k)值需要进行N次复数相乘，和N1次复数相加。对于N个X(k)点，应重复N次上述运算。因此，要完成全部DFT运算共需 N2次复数乘法和N ( N 1)次复数加法。 例如N = 4，需 N2 = 16次乘法和N ( N 1) = 12次加法。例如N = 10，需N2 = 100次乘法和N ( N 1) = 99次加法。而N = 1024，就需要1048576次乘法运算。,3.6 快速傅里叶变换（FFT）,2,随着N值加大，运算工作量将迅速增长，按照这种规律，如果在N较大的情
2、况下，要求对于信号进行实时处理，所需的运算速度就难以实现。 为了改进算法，减少运算工作量。考虑系数WnK 的周期性与对称性，合理安排重复出现的相乘运算，将使计算工作量显著减少。 2. 改进思路 1）W nk的周期性 WNnk = WN (n +lN)(k+mN) 例 N = 4 W46 = W42 W49 = W41 等等 2）W nk的对称性 WN (nk+N/2) = WN nk WNN/2 = 1,3,例 N = 4 W43 = W41 W42 = W40 等等,-周期性,-对称性,W矩阵与x(n)相乘过程中，存在着不必要的重复计算。,4,3.6.2 基2按时间抽取的FFT算法（时析型）
3、 1. 原理 把N点DFT运算分解为两组N/2点的DFT运算，然后取和。对序列x(n)取N点DFT，假定N是2的整数次方 N = 2M 把x(n)取N点DFT运算按n为偶数和奇数分解为两部分,以符号2r表示偶数n，以符号2r + 1 示奇数n， r = 0, 1, ，N/2 1,5,式中WN2 转换为WN/2，且记 g(r) = x(2r) ， h(r) = x(2r+1)。,一个N点的DFT已被分解为两个N/2点的DFT。注意G(k)和H(k)只有N/2个点，r = 0, 1, , N/2 1，而X(k)需要N个点，k = 0, 1, , N 1，如果以G(k)，H(k)表达全部X(k)，应
4、利用G(k) 与H(k) 的两个重复周期。,6,G(k + N/2) = G(k) H(k + N/2) = H(k) WN(k+N/2) = WNN/2 WNk = WNk 全部关系式 X(k) = G(k) + WNk H(k) k = 0, 1, ，N/2 1 X(k + N/2) = G(k + N/2) WNk H(k + N/2) = G(k) WNk H(k),x(n) n=0,1N 1,x(2r) = g(r) r=0,1N/2 1,x(2r+1) = h(r) r=0,1N/2 1,G(k),H(k),WNk,WNk,X(k),X(k+ N/2),7,基本运算单元呈蝴蝶形,蝶
5、形运算单元,X(k) = G(k) + WNk H(k) X(k + N/2) = G(k) WNk H(k),8,X(1) X(3),以N = 4为例说明 X(0) = G(0) + W40 H(0) k = 0 X(1) = G(1) + W41 H(1) k = N/2 1 = 1 X(2) = G(0) W40 H(0) X(3) = G(1) W41 H(1),X(0) X(2),9,结论：由G(k)、H(k)获得X(k)的过程中，共包含N/2个蝶形结运算，因此，共需N/2次复数乘法和N次复数加减法。当N = 4时，为2次乘、4次加。 为了从x(n)求出G(k)、H(k)，按n的奇偶
6、分别组合两个N/2点的DFT运算，得 G(0) = x(0) + W20 x(2) G(1) = x(0) W20 x(2) H(0) = x(1) + W20 x(3) H(1) = x(1) W20 x(3) 按照同样原理，把这些运算也化成蝶形图。,10,很明显，左半图的流程图，仍然由N/2个蝶形结组成，因此，运算量还是N/2次乘，N次加法。这样为完成全部的运算，共需次乘法2 N/2 = 4 和 2N = 8 次加法；而直接进行N = 4 的DFT全部运算量为 N 2 =16 次乘和 N( N-1 ) =12 次加。经分组简化后构成的快速算法其运算工作量显著减少。,X(1) X(3),x(
7、0) x(2),G(0) G(1),X(0) X(2),x(1) x(3),H(0) H(1),11,对于N = 22 = 4 的情况，只进行了一次奇偶分解。把全部运算过程分为两级蝶形流程图。对于 N = 2M的任意情况，需要把这种奇偶分解逐级进行下去。当 N = 23 = 8 ，分组运算的方框图如图示。,x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7),偶,N/2点 DFT,N/2点 DFT,偶,奇,X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7),12,x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7)
8、,X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7),13,复数乘法：,复数加法： N M = N log2 N 次 而原始的直接DFT方法需要 复数乘法： N 2次 复数加法：N ( N 1)次,2. 运算量比较 当 N = 2M 时，全部DFT运算可分解为M级蝶形流程图 ，其中每级都包含N/2次乘，N次加减，全部运算工作量为：,14,3. 码位顺序与即位运算 FFT的输入：看对输出X(k)的要求 序列的输入：自然顺序 X(k) 自然排序 x(n) 码位倒读 原因：由于按n的奇偶分组进行DFT运算造成的. 所谓倒读是指按二进制表示的数字首尾位置颠倒，重新按二进制读
9、数。,15,N=8 自然顺序 二进制表示 码位倒置 码位倒读顺序,16,能否把输入序列按自然顺序排列进行FFT运算？,输入序列改为自然顺序排列 而输出却变成了码位倒读顺序。,x(0) x(1) x(2) x(3),X(0) X(2),G(0) G(1),H(0) H(1),X(1) X(3),17,输入、输出序列都自然顺序 缺陷：不能实现“即位运算” 什么是“即位运算”？ 但数据输入到存储器中之后，每级运算结果仍然存储在原有的同一组存储器之中，直到最后一级算完，中间无需增设其他存储设备。,x(0) x(1) x(2) x(3),G(0) G(1),H(0) H(1),X(0) X(2),X(1
10、) X(3),18,4. 流程图规律 基2按时间抽取-输入码位倒读顺序，输出自然顺序，N = 2M （1）全部运算分解为M级（也称M次迭代）。 （2）每级都包含 N/2个蝶形单元。自左至右第一级有 N/2个“群” ，第 2级则分为 N/4个“群” 第i 级分为 N/2i个群， 最末一级只有 N/2M个也即一个“群”。 （3）每个蝶形单元的运算，都包括乘WNK ，并与相应的DFT结果加减各一次。 （4） M级蝶形运算，每一级是“即位运算”。,19,（5）同一级中，WNK的分布规律相同，各级WNK的分布规律为 第一级：W20 第二级：W40，W41 第三级：W80，W81，W82，W83 第i 级
11、： W2i 0，W2i 1，W2i 2， W2i 2i/2 1 （6）由于输入x(n) 是按时间先后顺序排列的，是“自然顺序” ，但获得X(k)按自然顺序的输出，对输入进行相应处理，即“码位倒置”处理,20,离散傅立叶变换快速算法同样适用于求逆变换，其差别仅在于取IDFT时，加权系数改为 WNnk (而不是 WNnk) ，运算结果都乘以系数1/N。 【例 3-7 】已知有限长序列 x(n) = 1, 2, 1, 3 按FFT运算流程图求X(k)，再以所得X(k)利用IFFT反求x(n)。 解：1）画出求DFT的流程图，逐级计算得X(k)。,3.7 IDFT的快速算法,x(0)=1 x(1)=2
12、 x(2)=1 x(3)=3,5=X(0) 5= X(2),0 2,5 1,2 +j =X(1) 2 j = X(3),21,2) 画出求IDFT的流程图，逐级计算得x(n),X(0)=5 X(1)= 2 +j X(2)=5 X(3)= 2 j,0 10,4 2j,1 x(0) 1 x(1) 2 x(2) 3 x(3),以上讨论的库利图基FFT算法，按输入序列在时域的奇偶顺序分组，也称为时域抽取的FFT算法。与之对应的另一种算法是在频域按奇偶顺序分组，称为按频率抽取的FFT算法，也称作桑德图基算法。 如果样点数目N不是2的整数幂次，也可以排出FFT算法程序，称为任意因子的FFT运算。,22,F
13、FT的软件实现 1. FFT算法的C语言程序设计 2. MATLAB中用于FFT的函数的用法简介 MATLAB信号分析与处理工具箱中，把FFT算法程序作为它们的一个内部函数，用一条语句直接调用即可完成运算。（8条语句，一维、二维、多维）,3.7 离散傅立叶变换的应用,3.7.1 用FFT计算线卷积 1. 用FFT计算线卷积的基本原理和方法 实际问题中往往处理离散系统响应问题,23,序列x(n)的长度为 N1 序列h(n)的长度为N2 线卷积y(n)也是一个有限长序列，其长度为 N1+N2 1。 每个x(n)的样值都必须与每个h(n)的样值相乘，需N1N2次乘法运算，在 N1 = N2 = N
14、时，需 N2次乘法运算 能否用圆卷积代替线卷积 ? 将进行卷积的两序列长度均加长至N N1 + N2 1，然后再进行圆卷积，则其圆卷积的结果与线卷积的结果相同。 设x(n)、h(n)均分别由N1 和N2 补零加长至N 点，其线卷积y1(n)为,24,-非零长度仍为 N1 + N2 1,= y1p(n),y2(n) = y1p(n) RN(n),25,加长至N的x(n)、h(n)两序列的圆卷积y2(n)与线卷积y1(n)作周期延拓，所得到序列的主值序列相同。 用FFT求解两序列线卷积的原理框图为：,序列补零加长至N,N N1 + N2 1,直接线卷积：N1N2次乘运算， N1 N2 = N 时，
15、需 N 2乘。利用圆卷积：两次FFT，一次IFFT,26,在一般的数字滤波器中，由求是预先设计好的，已置于存储器中，故实际只需二次FFT的运算量。假定 N1 = N2 = N，补零后长度 N1 + N2 1 2N，需要 2 ( N log22N )次乘。此外完成X(k)与H(k)两序列相乘，全部复运算次数为 2 ( N log22N ) + 2N = 2N ( 1 + log22N ) 比如 N = 210 = 1024 N = 26 = 64 直接线卷积：1048576 6464=4096 利用圆卷积： 24576 896 显然，随N，利用圆卷积比N 2显著减小，所以采用圆卷积的方案可以加快完成卷积运算。,27,以上分析是针对两序列长度接近或相等的情况。如果其中一个序列较短，而另一序列很长，圆卷积方案的相对运算量可能减小不多，甚至增多。这时，可采用分段卷积（分段过滤）的方法。 其基本原理是：将较长的一个序列，比如x(n)分成许多小段，每小段长度都与h(n)接近，将x(n)的每个小段分别与h(n)作卷积，最后取和。这时，仍有可能发挥快速卷积的优越性。此方案的具体实现不是唯一的。下面介绍“重叠相加法”。,28,假定x(n)、h(n)均为因果序列。 h(n) - M x(n) - N1 N1 M 现将N1等分为若干小段，每段长N。以xi(n)表示x(
