第四章 快速傅里叶变换 数字信号　教学课件.ppt

第四章学习目标 理解按时间抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点 理解按频率抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点 理解IFFT算法 了解混合基、分裂基和基-4FFT算法 了解CZT算法 理解线性卷积的FFT算法及分段卷积方法 第四章 快速傅里叶变换 FFT: Fast Fourier Transform 1965年，Cooley, Tukey 《机器计算傅里叶级数的一种算法》 一、直接计算DFT的问题及改进途径 运算量 利用对称性和周期性,可以将有些项合并,并 将DFT分解为短序列,从而降低运算次数,提 高运算速度. 1965年,库利(cooley)和图基(Tukey)首先提出FFT算法.对于N点DFT,仅需(N/2)log2N 次复数乘法运算.例如N=1024=210 时， 需要(1024/2)log2 210 =512*10=5120次。 5120/1048576=4.88% ,速度提高20倍 FFT算法分类: 时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency 二 、按时间抽选的基-2FFT算法 1、算法原理 设序列点数 N = 2L，L 为整数。 若不满足，则补零 则x(n)的DFT: 再利用周期性求X(k)的后半部分 分解后的运算量： 这样逐级分解，直到2点DFT 当N = 8时，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k = 0, 1 2、运算量 当N = 2L时，共有L级蝶形，每级N / 2个蝶形，每个蝶形有1次复数乘法2次复数加法。 3、算法特点 1）原位计算 2）倒位序 3）蝶形运算 对N = 2L点FFT，输入倒位序，输出自然序， 第m级运算每个蝶形的两节点距离为 2m–1 第m级运算： 蝶形运算两节点的第一个节点为k值，表示成L位二进制数， 4）存储单元 输入序列x(n) : N个存储单元 4、DIT算法的其他形式流图 输入倒位序输出自然序 输入自然序输出倒位序 输入输出均自然序 相同几何形状 输入倒位序输出自然序 输入自然序输出倒位序 三 、按频率抽选的基-2FFT算法 1、算法原理 按k的奇偶将X(k)分成两部分： 令 N /2仍为偶数，进一步分解：N /2 N /4 逐级分解，直到2点DFT 2、算法特点 1）原位计算 2）蝶形运算 对N=2L点FFT，输入自然序，输出倒位序， 两节点距离：2L-m=N / 2m 蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移m-1位，把右边空出的位置补零，结果为r的二进制数。 3、DIT与DIF的异同 基本蝶形不同 四 、IFFT算法 比较： 五、N为复合数的FFT算法 ——混合基算法 八 、线性调频 z变换（CZT)算法 FFT不适用于： 1、算法原理 N点有限长序列，其z变换： 抽样点： 求抽样点处的z变换： 2、CZT的实现步骤及运算量的估算 3）形成L点序列h(n): 总运算量: 4）求乘积 3、CZT算法的优点 N，M可为任意数，可不等 九、线性卷积和线性相关的FFT算法 1、线性卷积的FFT算法 FFT法：以圆周卷积代替线性卷积 比较直接计算和FFT法计算的运算量 1）重叠相加法 2）重叠保留法 2、线性相关的FFT算法 若L点x(n)，M点y(n)，计算线性相关： 思考题： 1）频谱分析 当 ， ， 时，CZT=DFT，解决了N为素数的快速算法问题 z0任意，从任意频率开始，便于窄带高分辨率分析 周线可以是螺线，而不一定是圆弧 任意，易调整频率分辨率 需运算量： 若系统满足线性相位，即： 则需运算量： 若L点x(n)，M点h(n)， 则直接计算其线性卷积y(n) 1) H(k) = FFT [h(n)] N /2*log2N 4) y(n) = IFFT [Y(k)] N /2*log2N 3) Y(k) = H(k)X(k) N 2) X(k) =FFT [x(n)] N /2*log2N N 讨论： 1）当 2）当 M超过64优势明显 N 舍弃yi(n)的前M-1个点，再将yi(n)顺次连接， 即得y(n)。 分段 右移序列 卷积 N 的DFT 算法 (1) 改写 成 做 个 点DFT ，得 为参量，输