Chap4快速傅立叶变换(FFT).ppt

chap4快速傅立叶变换（fft）,本章主要内容 按时间抽取（dit）的fft算法 按频率抽取（dif）的fft算法 线性调频z变换 实序列fft算法 fft应用,4.1 引言,一、dft的计算工作量,两者的差别仅在指数的符号和因子1/n,4.1 引言（续）,分析计算一个x(k)的值的工作量:如x(1) 考虑一般情况： 都是复数 一个x(k)：n次复数乘法，（n-1）次复数加法 所有x(k)：n2次复数乘法，n（n-1）次复数加法 运算量与n2（序列长度）成正比！ 当n很大时，如n=1024,则要完成1048576次 （一百多万次）运算，这样，难以做到实时处理。,4.1 引言（续）,二、算法改进 1. 的对称性和周期性 对称性： 周期性：,得到：,4.1 引言（续）,利用上述特性，可以将有些项合并，并将dft分解为短序列，从而降低运算次数，提高运算速度。1965年，库利（cooley）和图基（tukey）首先提出fft算法，对于n点dft，仅需 次复数乘法运算。例如 ：,4.1 引言（续）,例如：,将第n项和第n-n项合并，其中实部部分得：,乘法次数减少一半！其它项同样。,4.2按时间抽取的fft算法 库利图基算法,一、算法原理（基-2fft） 1.先将x(n)按n的奇偶分为两组做dft，设 不足时可在序列末尾补零，这样有： n为偶数时： n为奇数时： 因此：,4.2按时间抽取的fft算法（续）,其中：,4.2按时间抽取的fft算法（续）,均为n/2点dft 只能确定出 的前n/2，即： 的后n/2点的确定,4.2按时间抽取的fft算法（续）,的后一半也完全由 的前一半所确定。 结论： 一个n点序列的dft可由两个n/2点的dft来确定。,4.2按时间抽取的fft算法（续）,2.蝶形运算 由 表示 的运算是一种特殊的运算,实现上式运算的流图称作蝶形运算（n/2个蝶形）,1,1,-1,4.2按时间抽取的fft算法（续）,3.计算量分析：按奇偶分组后的计算量 一个n/2点的dft运算量 ： 复乘次数： 复加次数： 两个n/2点的dft运算量： 复乘次数： 复加次数： 一个蝶形运算量： 复乘次数：1 复加次数：2 n/2个蝶形运算量： 复乘次数： n/2 复加次数：n 总运算量： 复乘： 复加：,直接运算量：,运算量减少近一半！,4.2按时间抽取的fft算法（续）,例：n=8 可以分解为两个n/24点的dft,n为偶数时，记,n为奇数时，记,分别计算n/24点的dft，得,（k=0,1,2,3）,4.2按时间抽取的fft算法（续）,得：,蝶形图如下：,4.2按时间抽取的fft算法（续）,同理： 仍为偶数，可进一步把每个n/2点的序 列再按其奇偶部分分解为两个n/4得子序列。,分别进行n/4点的dft，得,4.2按时间抽取的fft算法（续）,这样，,做相同的分解，并分别做傅立叶变换,4.2按时间抽取的fft算法（续）,由 进行蝶形运算，得：,流图如下：,4.2按时间抽取的fft算法（续）,继续分解，直至两个一点为止。 n8完整流图如下：,4.2按时间抽取的fft算法（续）,二、dit dft算法小结： 计算一个 的fft时，需经过 级分解，最终得到n/2个两点dft。 由两点dft逐级合成4点，8点， ，n点。 每级中都有n/2个蝶形。 每次分解都是根据序列序号的奇偶进行的，故称为按时间抽取的算法。 dit dft 属于原位运算。 流图中输入“乱序”，输出“顺序”。,4.2按时间抽取的fft算法（续）,“乱序”原因,0,1,0,1,0,1,0,1,x(000),x(100),x(010),x(110),x(001),x(101),x(011),x(111),0 4 2 6,1 5 3 7,4.2按时间抽取的fft算法（续）,“整序”规律 将输入序号按自然顺序排序后，用相应位数的二 进制码表示，再进行反序，即可实现输入端的整 序。,自然顺序n 二进制 反序二进制 倒位顺序n 0 000 000 0 1 001 100 4 2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7,4.2按时间抽取的fft算法（续）,蝶形图的规律 第 级：蝶形运算有n/2个传输系数，为,共n/2个。,第三级：蝶形运算类型有四个,第二级：蝶形运算类型有二个,第一级：蝶形运算类型有一个,每向前一级，w因子取偶数序号。 参加蝶形运算两点间的距离规律： 最后一级的间距最大，每向前推一级，间距减小一半。,4.2按时间抽取的fft算法（续）,dit dft算法与直接计算的dft运算量的比较,因为在 级运算中，每一级都有n/2个蝶形，每一级 运算中运算有都有n/2次复乘和n次复加（见前面） 因而， 级运算中，共需要 复加次数： 复乘次数：,只考虑乘法计算量时，直接计算与fft方法运算量相比：,n足够大时，fft有明显优势。,4.2按时间抽取的fft算法（续）,直接计算与fft方法，乘法运算比较曲线,4.3按频率抽取（dif）的fft算法 桑德图基算法,一、算法原理 设 不足时，可在末尾补零。 将x(n)按n的自然顺序分为前后两组，即,则：,4.3按频率抽取（dif）的fft算法（续）,4.3按频率抽取（dif）的fft算法（续）,考虑两种情况： 当取偶数时：k2r r=0,1,n/2-1 当取奇数时：k2r1 r=0,1,n/2-1,令：,则：,r=0,1,2,n/2-1,可见，上两式均为n/2点dft,4.3按频率抽取（dif）的fft算法（续）,用蝶形图描述 如下：,1,4.3按频率抽取（dif）的fft算法（续）,上述过程小结如下： 首先形成 计算 分别计算 的n/2点的dft，得到x（k）的偶数点和奇数点的输出。,4.3按频率抽取（dif）的fft算法（续）,以n=8为例，dif fft算法流图如下： 先蝶形运算，后fft：,4.3按频率抽取（dif）的fft算法（续）,仍是偶数,即 可继续分组，使得每一个n/2点的dft由 两个n/4点的dft来得到，以此类推，直至分解到两个 一点序列。,4.3按频率抽取（dif）的fft算法（续）,例如n=8时dif的fft流图如下：,4.3按频率抽取（dif）的fft算法（续）,可见： 一个n=8点的dft经三级（n=23）分解后，变为 计算两点的dft，而这两点的dft实际上只有加 减运算，在每一级运算中，都有n/2个蝶形参加 运算，其运算量同dit fft。 因此，dif fft算法从始至终都是在进行分解，而dit fft算法从始至终都是在进行组合。,4.3按频率抽取（dif）的fft算法（续）,二、dit fft与dif fft 算法的比较 区别： 输入输出顺序相反，每一种dit fft算法都存在一种dif fft算法，二者互为倒置。 两种算法的蝶形运算存在差异，w因子相乘的位置不同。 相同点： 都有 级运算，每级都有n/2个蝶形。 运算量相同，即需要 次复乘， 次复加 都是原位运算。,4.3按频率抽取（dif）的fft算法（续）,三、idft fft算法ifft,两式相比， 相差一个负号，系数相差 ， 故：可用fft流图计算ifft。,方法： 输入输出调换 将fft流图中的 同 代替。 输出的每一个支路乘以,4.3按频率抽取（dif）的fft算法（续）,例：由n=8按频率抽取的fft流图求ifft流图,4.3按频率抽取（dif）的fft算法（续）,可见，一个按频率抽取地fft流图能够实现按 时间抽取地ifft流图，同理一个按时间抽取的 fft流图可以实现按频率抽取地ifft流图。 实际上机实现时，可直接用fft程序计算ifft,dit fft和dif fft都要求 ，故称为基2fft.,4.5 n为复合数的fft算法,对于 情况，可用下述方法提高计算dft速度 将序列补最少的零至 ，这种方法不是最简的。 若要求至计算n点的dft，而n又不能分解成素数的积，则直接计算dftczt. 若n是一个复合数，则有快速算法计算dft。 利用fft的基本思想：将大点数dft的运算尽量分解为小点数的运算，提高运算效率。,4.5 n为复合数的fft算法（续）,一、算法原理 设： 长n=ml m：列 l：行 则：,例：,4.5 n为复合数的fft算法（续）,将n排成矩阵形式如下：,0 1 2 3,0 1 2,0 1 2 3 5 6 7 8 9 10 11,l 行,m列,矩阵中的序号5表示如下：,4.5 n为复合数的fft算法（续）,同理：对于x(k)，k也可以表示成矩阵形式,（与n表示相反）,例：,0 1 2 3,0 1 2,0 1 2 3 5 6 7 8 9 10 11,4.5 n为复合数的fft算法（续）,4.5 n为复合数的fft算法（续）,行dft,4.5 n为复合数的fft算法（续）,说明： 1.,表示将 作为参变量，对,做 与 之间的l,点dft，共有m个（ ）即：对x(n)的每一列（ ）做l点dft，最后得到m点dft.,2.,表示以 作参变量，在 与 之间做的m点dft，共有 l个（ ）即： 将行号为 的行序列 做m点dft，共得n点dft,4.5 n为复合数的fft算法（续）,二、n为复合数的dft算法的运算步骤 1.,即：将x(n)的数据排成矩阵形式。,2.对列作m个l点的dft,3.形成一个n点的新序列,4.对行作l个m点的dft,5.译序,4.5 n为复合数的fft算法（续）,例：,4.5 n为复合数的fft算法（续）,其中，,4.5 n为复合数的fft算法（续）,三、基数 若序列长度为 时，可通过m级r点dft来实现 n点fft的运算，这种运算称为基rfft算法（常用） 如：r=2,4,8分别称为基2，基4，基8算法。 若序列长度为 时，但可分解成一些因子的乘积， 如：n=60=3*4*5,则，可分别进行3,4,5点的dft来实现n点fft，这种算法通常称为混合基算法。 注：这种分解方法不唯一。,4.5 n为复合数的fft算法（续）,四、n为复合数的fft算法的运算量 根据计算步骤：,4.5 n为复合数的fft算法（续）,两种计算方法运算量比较 复数乘法比： 复数加法比： 例：,结论：运算量明显减少！,4.6 线性调频z变换（chirp z transform）,一、算法原理 已知：,则：,现在z平面内对x(z)沿某一路径取样，取样点 ，点数为 m个。,令：,其中：,则：,4.6 线性调频z变换（chirp z transform）,不同的k，对应不同的取样点,：起始取样点 的半径 ：起始取样点 的相角，可正可负 ： 与 之间的角频率差，可正可负 ：,4.6 线性调频z变换(续),若满足下列条件： 1. 2. 3.,则： 就是单位圆上均匀分布的取样点。,此时 就是 的dft,4.6 线性调频z变换(续),将 代入x(z)得：,4.6 线性调频z变换(续),4.6 线性调频z变换(续),频率与时间成线性关系，雷达系统中，通常称 为 线性调频信号（chirp）。 该方法对应的变换称线性调频z变换。,4.6 线性调频z变换(续),czt实现步骤,1.根据a,w，求出 和f(n),2. 利用fft计算 与 l点（ ）圆周卷积 n： 的长度，m: 被截断的长度。,4.6 线性调频z变换(续),3.取出卷积结果的前m个值，并与 相乘，即可。 解释 的选取方法：,4.6 线性调频z变换(续),czt运算量 计算 需要n次复乘 计算 计算 需要l次复乘 计算 需要m次复乘 共计： 复乘。 直接计算需要mn复乘。,当m,n足够大时，czt 运算量将大大减少。,4.6 线性调频z变换(续),czt特点 与标准fft算法相比： 输入与输出的序列长度不必相等。 n与m均可为素数，而这不必是高度复合。 的角间隔 是任意的，因此频率分辨率也是任意的。 取样轨迹不必是圆 起始点位置可任意选定，目的是可从任意频率上开始对输入数据进行窄带的高分辨率的分析。 czt是fft的推广，是一般化的dft，fft是czt的一个特例。,4.7 实序列的fft算法,一、一个n点fft同时计算两个n点实序列的dft 设 长度为n，均为实序列， 现将 组合乘一个复序列，得：,4.7 实序列的fft算法（续）,注意：,4.7 实序列的fft算法（续）,三、一个n点fft计算一个2n点实序列的dft 设： 长度为2n 现将 按序号的奇偶分为两个序列,4.7 实序列的fft算法（续）,现在寻找 与 的关系,4.7 实序列的fft算法（续）,运算量分析 复乘次数： 复加次数： 直接计算2n点dft 复乘次数