第二章 离散傅里叶变换及其快速算法07.ppt

第二章 离散傅里叶变换及快速算法 快速傅里叶变换（FFT） 第二章 总复习 离散傅里叶变换(DFT) 循环卷积过程: 基—2 FFT算法 思想：将 x(n) 在时域按序号n的奇偶性分成两个N/2点子序列 N点X(k)，可由两个N/2点DFT求出。 蝶形运算： N点DFT运算流图 (N=8)： N为组合数的FFT算法 Chirp-z变换 FFT应用中的几个问题 一、算法原理： 大点数DFT分解成小点数DFT X1(k),X2(k)分别为偶数号序列和奇数号序列的N/2点DFT,其周期均为N/2. N=8 DIT FFT算法流图 三、算法特点： (1) 原址运算： (2) 输入反序，输出正序(顺序) 000, 100, 010, 110, 001, 101, 011, 111 ---反序 000, 001, 010, 011, 100, 101, 110, 111 ---顺序 (3) 蝶形运算变化规律 其中第m级的蝶型数为 个(椐系数WN 分)。 N=8DIF算法流图： x(0) x(3) x(6) x(9) x(12) x(1) x(4) x(7) x(10) x(13) x(2) x(5) x(8) x(11) x(14) …… …… 则 x(n) 的N点DFT为： 可将x(n) 分解成 p1 组，每组有 q1点组成，且每两点相距p1点。即：每隔 p1 点抽取一个数据。 通式： 采用FFT可以算出全部N点DFT值，即z变换X(z)在z平面单位圆上的等间隔取样值，但要求 N 为复合数。 问题的提出： ①不需要计算整个单位圆上z变换的取样。 ②对其它围线上的z变换取样感兴趣。 ③要求能有效地计算当N是素数时序列的DFT。 又称线性调频z变换 算法的限制 1、用FFT计算IDFT 2、实数序列的FFT 3、线性卷积的FFT算法 4、用FFT计算相关函数 5、用FFT计算二维离散傅里叶变换 快速FFT变换 三、计算卷积和相关函数 1、计算卷积 设x(n)列长为N1 ， h(n)列长为N2 （1）选择N≥ N1+ N2-1且N=2r，将x(n),h(n)补零到N （2）计算X(k),H(k) ，X(k)= FFT[x(n)]，H(k)= FFT[h(n)] （3）求Y(k) =X(k)H(k) （4）求Y*(k) 调用3次，若 N 较大时，则运算效率比较高。 （5）求 x(n) h(n) y(n) 2、计算相关 离散相关 线性相关 相关定理 （1）补零选择N≥ N1+ N2-1且N=2r。 计算过程 （2）计算X1(k), X2(k),X1(k)= FFT[x1(n)], X2(k) = FFT[x2(n)] （3）求X1*(k) （4）求X3(k) = X1*(k) X2(k) （5）求 计算相关函数 2.4.3 线性卷积的FFT算法 线性卷积是求离散系统响应的主要方法之一，许多重要应用都建立在这一理论基础上，如卷积滤波等。 2.4.3 线性卷积的FFT算法 a. 计算X(k)=FFT[x(n)] b. 求H(k)=FFT[h(n)] c. 求Y(k)=H(k)X(k) k = 0～L-1 d. 求y(n)=IFFT[Y(k)] n = 0～L-1 上述结论适用于 x(n)、h(n) 两序列长度比较接近或相等的情况,如果x(n)、h(n) 长度相差较多,例如, h(n) 为某滤波器的单位脉冲响应,长度有限,用来处理一个很长的输入信号 x(n),或者处理一个连续不断的信号，按上述方法, h(n) 要补许多零再进行计算,计算量有很大的浪费，或者根本不能实现。 为了保持快速卷积法的优越性,可将 x(n) 分为许多段,每段的长度与 h(n) 接近 , 处理方法有两种： 2.4.3 线性卷积的FFT算法 (1)?重叠相加法——由分段卷积的各段相加构成总的卷积输出 h(n) x(n) 2.4.3 线性卷积的FFT算法 假定 xi(n) 表示 x(n)序列的第 i段 ： 则输入序列可表为： 于是可分解为： 其中 1）先对 h(n)及 xi(n)补零,补到具有N点长度，N=N1+N2-1。 一般选 N=2M。 2）用基2 FFT计算 yi(n)=xi(n)*h(