资源描述
第 4章 快速傅里叶变换 (FFT) 课件 1 第 4章 快速傅里叶变换 (FFT) 4.1 引言 4.2 基 2FFT算法 4.3 进一步减少运算量的措施 4.4 分裂基 FFT算法 4.5 离散哈特莱变换 (DHT) 第 4章 快速傅里叶变换 (FFT) 课件 2 4.1 引言 DFT是信号分析与处理中的一种重要变换 。 因直 接计算 DFT的计算量与变换区间长度 N的平方成正比 ， 当 N较大时 ， 计算量太大 ， 所以在快速傅里叶变换 (简 称 FFT)出现以前 ， 直接用 DFT算法进行谱分析和信号 的实时处理是不切实际的 。 直到 1965年发现了 DFT的 一种快速算法以后 ， 情况才发生了根本的变化 。 第 4章 快速傅里叶变换 (FFT) 课件 3 4.2 基 2FFT算法 4.2.1 直接计算 DFT的特点及减少运算量的基本途径 长度为 N的有限长序列 x(n)的 DFT为 考虑 x(n)为复数序列的一般情况 ， 对某一个 k值 ， 直接按 (4.2.1)式计算 X(k)值需要 N次复数乘法 、 (N-1)次 复数加法 。 1 0 ( ) ( ) , 0 , 1 , , 1 N kn N n X k x n W k N (4.2.1) 第 4章 快速傅里叶变换 (FFT) 课件 4 如前所述 ， N点 DFT的复乘次数等于 N2。 显然 ， 把 N点 DFT分解为几个较短的 DFT， 可使乘法次数大大 减少 。 另外 ， 旋转因子 WmN具有明显的周期性和对称 性 。 其周期性表现为 22()j m l N j m m l N mNN NNW e e W (4.2.2) 其对称性表现为 2 m N m N m mN N N N Nm m NN W W W W WW 或者 第 4章 快速傅里叶变换 (FFT) 课件 5 4.2.2 时域抽取法基 2FFT基本原理 FFT 算法基本上分为两大类：时域抽取法 FFT(Decimation In Time FFT,简称 DIT-FFT)和频域抽取 法 FFT(Decimation In Frequency FFT,简称 DIFFFT) 。 下面先介绍 DIFFFT 算法 。 设序列 x(n)的长度为 N， 且满足 2,MNM 为自然数 按 n的奇偶把 x(n)分解为两个 N/2点的子序列 1 2 ( ) ( 2 ), 0 , 1 , 1 2 ( ) ( 2 1 ), 0 , 1 , 1 2 N x r x r r N x r x r r 第 4章 快速傅里叶变换 (FFT) 课件 6 则 x(n)的 DFT为 / 2 1 / 2 1 2 ( 2 1 ) 00 / 2 1 / 2 1 2 12 00 ( ) ( ) ( ) ( 2 ) ( 2 1 ) ( ) ( ) k n k n NN nn NN k r k r NN rr NN k k r NN rr X k x n W x n W x r W x r W x r W x r W 由于 2 2 2 22 2 /2 j krN j krkr krN NNW e e W 所以 / 2 1 / 2 1 1 / 2 2 / 2 1 2 00 ( ) ( ) ( ) ( ) ( ) NN k r k k r k N N N N rr X k x r W W x r W X k W X k 第 4章 快速傅里叶变换 (FFT) 课件 7 其中 X1(k)和 X2(k)分别为 x1(r)和 x2(r)的 N/2点 DFT， 即 / 2 1 1 1 / 2 1 0 / 2 1 2 2 / 2 2 0 ( ) ( ) ( ) ( ) ( ) ( ) N kr N r N kr N r X k x r W D FT x r X k x r W D FT x r (4.2.5) (4.2.6) 由于 X1(k)和 X2(k)均以 N/2为周期 ， 且 ， 所以 X(k)又可表示为 2 Nk k NNWW 12 12 ( ) ( ) ( ) 0 , 1 , 1 2 ( ) ( ) ( ) 0 , 1 , 1 22 k N k N N X k X k W X k k NN X k X k W X k k (4.2.7) (4.2.8) 第 4章 快速傅里叶变换 (FFT) 课件 8 图 4.2.1 蝶形运算符号 C A B A BC A BC 第 4章 快速傅里叶变换 (FFT) 课件 9 图 4.2.2 N点 DFT的一次时域抽取分解图 (N=8) N /2 点 D F T W N 0 N /2 点 D F T W N 1 W N 2 W N 3 x ( 0 ) X 1 ( 0 ) x ( 2 ) x ( 4 ) x ( 6 ) x ( 1 ) x ( 3 ) x ( 5 ) x ( 7 ) X 1 ( 1 ) X 1 ( 2 ) X 1 ( 3 ) X 2 ( 0 ) X 2 ( 1 ) X 2 ( 2 ) X 2 ( 3 ) X ( 0 ) X ( 1 ) X ( 2 ) X ( 3 ) X ( 4 ) X ( 5 ) X ( 6 ) X ( 7 ) 第 4章 快速傅里叶变换 (FFT) 课件 10 与第一次分解相同 ， 将 x1(r)按奇偶分解成两个 N/4 长的子序列 x3(l)和 x4(l)， 即 32 41 ( ) ( 2 ) , 0 , 1 , , 1 ( ) ( 2 1 ) 4 x l x l Nl x l x l 那么， X1(k)又可表示为 / 4 1 / 4 1 2 ( 2 1 ) 1 1 / 2 1 / 2 00 / 4 1 / 4 1 3 / 4 / 2 4 / 4 00 3 / 2 4 ( ) ( 2 ) ( 2 1 ) ( ) ( ) ( ) ( ), 0 , 1 , / 2 1 NN kl k l NN ii NN kl k kl N N N ii k N X k x l W x l W x l W W x l W x k W X k k N (4.2.9) 第 4章 快速傅里叶变换 (FFT) 课件 11 式中 / 4 1 3 3 / 4 3 0 / 4 1 4 4 / 4 4 0 ( ) ( ) ( ) ( ) ( ) ( ) N kl N i N kl N i x k x l W D FT x l x k x l W D FT x l 同理 ， 由 X3(k)和 X4(k)的周期性和 Wm N/2的对称 性 Wk+N/4 N/2=-Wk N/2 最后得到： 1 3 / 2 4 1 3 / 2 4 ( ) ( ) ( ) , 0 , 1 , , / 4 1 ( / 4 ) ( ) ( ) k N k N X k X k W X k kN X k N X k W X k (4.2.10) 第 4章 快速傅里叶变换 (FFT) 课件 12 用同样的方法可计算出 2 5 / 2 6 2 5 / 2 6 ( ) ( ) ( ) , 0 , 1 , / 4 1 ( / 4 ) ( ) k N k N X k X k W X k kN X k N X k W X k (4.2.11) 其中 / 4 1 5 5 / 4 5 0 / 4 1 6 6 / 4 6 0 52 62 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( 2 ) , 0 , 1 , / 4 1 ( ) ( 2 1 ) N kl N i N kl N i X k x l W DFT x l X k x l W DFT x l x l x l lN x l x l 第 4章 快速傅里叶变换 (FFT) 课件 13 图 4.2.3 N点 DFT的第二次时域抽取分解图 (N=8) N /4 点 D F T W N 1 2 W N 1 2 W N 0 W N 1 W N 2 W N 3 X 1 ( 0 ) X 1 ( 1 ) X 1 ( 2 ) X 1 ( 3 ) X 2 ( 0 ) X 2 ( 1 ) X 2 ( 2 ) X 2 ( 3 ) X ( 0 ) X ( 1 ) X ( 2 ) X ( 3 ) X ( 4 ) X ( 5 ) X ( 6 ) X ( 7 ) x ( 0 ) X 3 ( 0 ) X 3 ( 1 ) X 4 ( 0 ) X 4 ( 1 ) x ( 4 ) x ( 2 ) x ( 6 ) x ( 1 ) x ( 5 ) x ( 3 ) x ( 7 ) N /4 点 D F T N /4 点 D F T N /4 点 D F T W N 0 2 W N 0 2 第 4章 快速傅里叶变换 (FFT) 课件 14 图 4.2.4 N点 DITFFT 运算流图 (N=8) W N 0 W N 1 W N 2 W N 3 W N 0 W N 2 W N 0 W N 2 W N 0 W N 0 W N 0 W N 0 x ( 0 ) x ( 4 ) x ( 2 ) x ( 6 ) x ( 1 ) x ( 5 ) x ( 3 ) x ( 7 ) A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 ) A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 ) A ( 0 ) A ( 7 ) X ( 0 ) X ( 1 ) X ( 2 ) X ( 3 ) X ( 4 ) X ( 5 ) X ( 6 ) X ( 7 ) A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 ) 第 4章 快速傅里叶变换 (FFT) 课件 15 4.2.3 DITFFT 算法与直接计算 DFT运算量的比较 每一级运算都需要 N/2次复数乘和 N次复数加 (每个 蝶形需要两次复数加法 )。 所以 ， M级运算总共需要的 复数乘次数为 2 2 ( 2 ) l o g 22 ( 2 ) l o g M A NN C M N C N M N N 复数加次数为 例如 ， N=210=1024时 2 2 1048576 2 0 4 . 8 ( / 2 ) l o g 5 1 2 0 N NN 第 4章 快速傅里叶变换 (FFT) 课件 16 图 4.2.5 FFT算法与直接计算 DFT所需乘法次数的比较曲线 第 4章 快速傅里叶变换 (FFT) 课件 17 4.2.4 DITFFT 的运算规律及编程思想 1.原位计算 由图 4.2.4可以看出 ， DITFFT 的运算过程很有规 律 。 N=2M点的 FFT共进行 M级运算 ， 每级由 N/2个蝶 形运算组成 。 2.旋转因子的变化规律 如上所述 ， N点 DITFFT 运算流图中 ， 每级都有 N/2个蝶形 。 每个蝶形都要乘以因子 WpN， 称其为旋转 因子 ， p称为旋转因子的指数 。 第 4章 快速傅里叶变换 (FFT) 课件 18 观察图 4.2.4不难发现 ， 第 L级共有 2 L-1个不同的旋 转因子 。 N=23=8时的各级旋转因子表示如下： L=1时 ， WpN=WJ N/4=WJ2L， J=0 L=2时 ， WpN =WJ N/2=WJ2L， J=0， 1 L=3时 ， WpN =WJN=WJ2L， J=0， 1， 2， 3 对 N=2M的一般情况 ， 第 L级的旋转因子为 1 2 21 2 , 0 , 1 , 2 , , 2 1 2 2 2 2 , 0 , 1 , 2 , , 2 1 2 ML LM p J L N L M L M L M P J J L NN N ML W W L J N W W W J pJ (4.2.12) (4.2.13) 第 4章 快速傅里叶变换 (FFT) 课件 19 3. 蝶形运算规律 设序列 x(n)经时域抽选 (倒序 )后 ， 存入数组 X中 。 如果蝶形运算的两个输入数据相距 B个点 ， 应用原位计 算 ， 则蝶形运算可表示成如下形式： X (J) XL-1(J)+X L-1(J+B)WpN XL(J+B) XL-1(J)-X L-1(J+B)WpN 式中 p=J2 M-L； J=0,1,， 2 L-1-1； L=1,2,， M 第 4章 快速傅里叶变换 (FFT) 课件 20 下标 L表示第 L级运算 ， XL(J)则表示第 L级运算后 数组元素 X(J)的值 。 如果要用实数运算完成上述蝶形 运算 ， 可按下面的算法进行 。 设 T=X L-1(J+B)WpN=TR+jTI X L-1(J)=XR(J)+jXI(J) 式中下标 R表示取实部 ， I表示取虚部 ， 22 ( ) c o s ( ) si n 22 ( ) c o s ( ) si n R R R I I I R I T X J B p X J B p NN T X J B p X J B p NN 第 4章 快速傅里叶变换 (FFT) 课件 21 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) LR R R R I I I R R R I I I X J X J j J X J X J T X J X J T X J B X J T X J B X J T 则 第 4章 快速傅里叶变换 (FFT) 课件 22 4. 编程思想及程序框图 图 4.2.6 DITFFT 运算和程序框图 开 始 送入 x ( n ) ， M N 2 M 倒 序 L 1 , M 0 , B 1 P 2 M L J k J , N 1 , 2 L p N p N WBkXkXBkX WBkXkXkX )()()( )()()( 输 出 结 束 B 2 L 1 第 4章 快速傅里叶变换 (FFT) 课件 23 5. 序列的倒序 DITFFT 算法的输入序列的排序看起来似乎很乱 ， 但仔细分析就会发现这种倒序是很有规律的 。 由于 N=2M， 所以顺序数可用 M位二进制数 (nM-1nM-2n1n0) 表示 。 图 4.2.7 形成倒序的树状图 (N=23) 0 1 0 1 0 1 0 1 0 1 0 1 0 1 ( n 2 n 1 n 0 ) 2 0 0 0 0 4 2 6 1 5 3 7 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 第 4章 快速傅里叶变换 (FFT) 课件 24 表 4.2.1 顺序和倒序二进制数对照表 第 4章 快速傅里叶变换 (FFT) 课件 25 图 4.2.8 倒序规律 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 ) A ( 0 ) A ( 1 ) A ( 2 ) A ( 3 ) A ( 4 ) A ( 5 ) A ( 6 ) A ( 7 ) x ( 0 ) x ( 4 ) x ( 2 ) x ( 6 ) x ( 1 ) x ( 5 ) x ( 3 ) x ( 7 ) 第 4章 快速傅里叶变换 (FFT) 课件 26 图 4.2.9 倒序程序框图 2 2 1 NN LHJ NLH I 1 , N 1 I J TJA JXIA IXT )( )()( )( J K LHK KJJ 2KK KJJ N N Y 第 4章 快速傅里叶变换 (FFT) 课件 27 4.2.5 频域抽取法 FFT(DIFFFT) 在基 2快速算法中 ， 频域抽取法 FFT也是一种常用 的快速算法 ， 简称 DIFFFT 。 设序列 x(n)长度为 N=2M， 首先将 x(n)前后对半分 开 ， 得到两个子序列 ， 其 DFT可表示为如下形式： 1 0 / 2 1 1 0 / 2 / 2 1 / 2 1 ( / 2 ) 00 / 2 1 /2 0 ( ) ( ) ( ) ( ) ( ) ( ) ( ) 2 ( ) ( ) 2 N k N n NN k n k n NN n n N NN k n k n N NN nn N k N k n NN n X k DFT x n x n W x n W x n W N x n W x n W N x n W x n W 第 4章 快速傅里叶变换 (FFT) 课件 28 /2 1,( 1 ) 1 kN k N k W k 偶数 奇数 将 X(k)分解成偶数组与奇数组，当 k取偶数 (k=2r,r=0,1,N/2 -1)时 / 2 1 2 0 / 2 1 2 /2 0 ( 2 ) ( ) ( ) 2 ( ) ( ) 2 N rn N n N rn N n N X r x n x n W N x n x n W (4.2.14) 第 4章 快速傅里叶变换 (FFT) 课件 29 当 k取奇数 (k=2r+1,r=0,1,N/2-1)时 / 2 1 ( 2 1 ) 0 / 2 1 /2 0 ( 2 1 ) ( ) ( ) 2 ( ) ( ) 2 N nr N n N n n r NN n N X r x n x n W N x n x n W W (4.2.15) 将 x1(n)和 x2(n)分别代入 (4.2.14)和 (4.2.15)式 ， 可得 / 2 1 1 / 2 0 / 2 1 2 / 2 0 ( 2 ) ( ) ( 2 1 ) ( ) N rn N n N rn N n X r x n W X r x n W (4.2.16) 第 4章 快速傅里叶变换 (FFT) 课件 30 图 4.2.10 DIFFFT 蝶形运算流图符号 第 4章 快速傅里叶变换 (FFT) 课件 31 图 4.2.11 DIFFFT 一次分解运算流图 (N=8) N /2 点 D F T W N 0 N /2 点 D F T W N 1 W N 2 W N 3 X ( 0 ) x 1 ( 0 ) X ( 2 ) X ( 4 ) X ( 6 ) X ( 1 ) X ( 3 ) X ( 5 ) X ( 7 ) x 1 ( 1 ) x 1 ( 2 ) x 1 ( 3 ) x 2 ( 0 ) x 2 ( 1 ) x 2 ( 2 ) x 2 ( 3 ) x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) 第 4章 快速傅里叶变换 (FFT) 课件 32 图 4.2.12 DIFFFT 二次分解运算流图 (N=8) N /4 点 D F T W N 0 W N 1 W N 2 W N 3 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) X ( 0 ) X ( 4 ) X ( 2 ) X ( 6 ) X ( 1 ) X ( 5 ) X ( 3 ) X ( 7 ) W N 0 W N 2 W N 0 W N 2 N /4 点 D F T N /4 点 D F T N /4 点 D F T 第 4章 快速傅里叶变换 (FFT) 课件 33 图 4.2.13 DIFFFT 运算流图 (N=8) W N 0 W N 1 W N 2 W N 3 W N 0 W N 2 W N 0 W N 2 W N 0 W N 0 W N 0 W N 0 X ( 0 ) X ( 4 ) X ( 2 ) X ( 6 ) X ( 1 ) X ( 5 ) X ( 3 ) X ( 7 ) x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) 第 4章 快速傅里叶变换 (FFT) 课件 34 图 4.2.14 DITFFT 的一种变形运算流图 W N 0 W N 0 W N 2 W N 0 X ( 0 ) X ( 4 ) X ( 2 ) X ( 6 ) X ( 1 ) X ( 5 ) X ( 3 ) X ( 7 ) x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) W N 0 W N 2 W N 1 W N 3W N 2 W N 0 W N 0 W N 0 第 4章 快速傅里叶变换 (FFT) 课件 35 图 4.2.15 DITFFT 的一种变形运算流图 W N 0 W N 0 W N 2 W N 0 X ( 0 ) X ( 1 ) X ( 2 ) X ( 3 ) X ( 4 ) X ( 5 ) X ( 6 ) X ( 7 ) x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) W N 0 W N 2 W N 1 W N 3 W N 2 W N 0 W N 0 W N 0 第 4章 快速傅里叶变换 (FFT) 课件 36 4.2.6 IDFT的高效算法 上述 FFT算法流图也可以用于离散傅里叶逆变换 (Inverse Discrete Fourier Transform， 简称 IDFT)。 比较 DFT和 IDFT的运算公式： 1 0 1 0 ( ) ( ) ( ) 1 ( ) ( ) ( ) N k N n N kn N k X k D F T x n x n W x n I D F T x n X k W N 第 4章 快速傅里叶变换 (FFT) 课件 37 图 4.2.16 DITIFFT 运算流图 W N 0 W N 1 W N 2 W N 3 W N 0 W N 0 N1 x ( 0 ) x ( 4 ) x ( 2 ) x ( 6 ) x ( 4 ) x ( 5 ) x ( 3 ) x ( 7 ) X ( 0 ) X ( 1 ) X ( 2 ) X ( 3 ) X ( 4 ) X ( 5 ) X ( 6 ) X ( 7 ) W N 2 W N 2 N1 N1 N1 N1 N1 N1 N1 第 4章 快速傅里叶变换 (FFT) 课件 38 图 4.2.17 DITIFFT 运算流图 (防止溢出 ) W N 0 2 1 21 x ( 0 ) x ( 4 ) x ( 2 ) x ( 6 ) x ( 1 ) x ( 5 ) x ( 3 ) x ( 7 ) X ( 0 ) X ( 1 ) X ( 2 ) X ( 3 ) X ( 4 ) X ( 5 ) X ( 6 ) X ( 7 ) 21 21 21 W N 1 2 1 W N 2 2 1 W N 3 2 1 21 21 W N 0 2 1 W N 2 2 1 21 21 W N 0 2 1 W N 2 2 1 21 W N 0 2 1 21 W N 0 2 1 21 21 W N 0 2 1 W N 0 2 1 第 4章 快速傅里叶变换 (FFT) 课件 39 如果希望直接调用 FFT子程序计算 IFFT， 则可用下 面的方法： 由于 1 0 1 0 1 ( ) ( ) 1 ( ) ( ) N kn N k N kn N k x n X k W N x n X k W N 对上式两边同时取共轭 ， 得 1 0 11( ) ( ) ( ) N kn N k x n X k W DF T X kNN 第 4章 快速傅里叶变换 (FFT) 课件 40 4.3 进一步减少运算量的措施 4.3.1 多类蝶形单元运算 由 DITFFT 运算流图已得出结论 ， N=2M点 FFT共 需要 MN/2次复数乘法 。 由 (4.2.12)式 ， 当 L=1时 ， 只有一种旋转因子 W0N=1， 所以 ， 第一级不需要乘法运算 。 第 4章 快速傅里叶变换 (FFT) 课件 41 综上所述 ， 先除去第一 、 二两级后 ， 所需复数乘法 次数应是 从 L=3至 L=M共减少复数乘法次数为 ( 2 ) ( 2 )2M NCM (4.3.1) 1 33 12 ( ) 2 2 2 2 MM L L LL NNN (4.3.2) 因此， DITFFT 的复乘次数降至 ( 2 ) ( 2 ) ( 2 ) ( 3 ) 22 2 2M N N NC M M (4.3.3) 第 4章 快速傅里叶变换 (FFT) 课件 42 22 ( 1 ) ( ) ( ) 22 2 ( ) ( ) 2 2 () 2 22 ( ) ( ) 22 de f j x jy x jy jx y x y j x y R jI R x y I x y y x 第 4章 快速傅里叶变换 (FFT) 课件 43 从实数运算考虑 ， 计算 N=2M点 DITFFT 所需实数 乘法次数为 ( 2 ) 4 ( 3 ) 2 ( 2 ) 22 13 ( 2 ) 1 0 2 M NN RM NM (4.3.4) 第 4章 快速傅里叶变换 (FFT) 课件 44 4.3.2 旋转因子的生成 在 FFT运算中，旋转因子 WmN=cos(2m/N)- jsin(2m/N)，求正弦和余弦函数值的计算量是很大的。 第 4章 快速傅里叶变换 (FFT) 课件 45 4.3.3 实序列的 FFT算法 设 x(n)为 N点实序列 ， 取 x(n)的偶数点和奇数点分 别作为新构造序列 y(n)的实部和虚部 ， 即 12 12 ( ) ( 2 ), ( ) ( 2 1 ), 0 , 1 , , 1 2 ( ) ( ) ( ), 0 , 1 , , 1 2 N x n x n x n x n n N y n x n j x n n 对 y(n)进行 N/2点 FFT， 输出 Y(k)， 则 11 22 ( ) ( ) ( ) , 0 , 1 , , 1( ) ( ) ( ) 2ep op X k DFT x n Y k N kX k DFT x n jY k 根据 DITFFT 的思想及式 (4.2.7)和 (4.2.8)，可得到 12( ) ( ) ( ) , 0 , 1 , 2 k N NX k X k W X k k 第 4章 快速傅里叶变换 (FFT) 课件 46 由于 x(n)为实序列，所以 X(k)具有共轭对称性， X(k)的另外 N/2点的值为 ( ) ( ) , 1 , 2 , , 12NX N k X k k 第 4章 快速傅里叶变换 (FFT) 课件 47 4.4 分裂基 FFT算法 4.4.1 分裂基 FFT算法原理 当 n=pq， 且 p=N/4， q=4时 ， n可表示为 1 0 1 0 1 0, 0 3 , 0 144 NNn pn n n n n n 并有 10 1 1 0 / 4 1 3 () 4 10 00 ( ) ( ) () 4 N kn N n NN k n n N nn X k x n W N x n n W 第 4章 快速傅里叶变换 (FFT) 课件 48 0 1 01 0 0 / 4 1 3 1 0 4 / 4 1 02 4 0 4 0 4 0 33 04 ( ) 4 ( ) ( ) ( ) 42 3 ( ) 4 N kn kn N nn N kk n knkk NN N W x n n W NN x n W x n W x n W N x n W W W 再将上式中的 k表示为 1 0 1 04 , 0 1 , 0 34 Nk k k k k 第 4章 快速傅里叶变换 (FFT) 课件 49 可得 10 0 1 0 1 0 1 0 0 00 0 0 1 0 0 10 / 4 1 ( 4 ) 0 0 4 0 8 2 3 ( 4 ) ( 4 ) 0 4 0 4 / 4 1 2 0 0 4 0 4 0 3 ( 4 ) 04 ( ) ( 4 ) ( ) ( ) 4 3 ( ) ( ) 24 ( ) ( ( ) ( ) 42 3 ( ) 4 N kk n k k k k k n N N kk n k k k n N X k X k k N x n x n W NN x n W x n W W NN x n x n W x n W N x n W W 对 k0=0， 1,2,3,并用 k表示 k1， 用 n表示 n0， 可以 写出 第 4章 快速傅里叶变换 (FFT) 课件 50 / 4 1 4 0 / 4 1 4 0 / 4 1 42 0 3 ( 4 ) ( ) ( ) ( ) ( ) 4 2 4 3 ( 4 1 ) ( ) ( ) ( ) ( ) 4 2 4 3 ( 4 2 ) ( ) ( ) ( ) ( ) 4 2 4 ( 4 3 ) ( ) ( ) ( ) ( 42 N kn N n N k n n N n N k n n N n N N N X k x n x n x n x n W N N N X k x n jx n x n jx n W N N N X k x n x n x n x n W NN X k x n jx n x n jx n / 4 1 43 0 3 ) 4 01 4 N k n n N n N W N k (4.4.1) 第 4章 快速傅里叶变换 (FFT) 课件 51 / 2 1 2 0 / 4 1 4 0 / 4 1 34 0 ( 2 ) ( ) ( ) , 0 1 22 3 ( 4 1 ) ( ) ( ) ( ) ( ) 4 2 4 01 4 3 ( 4 3 ) ( ) ( ) ( ) ( ) 4 2 4 01 4 N kn N n N n k n NN n N n k n NN n NN X k x n x n W k N N N X k x n j x n x n j x n W W N k N N N X k x n j x n x n j x n W W N k (4.4.2) 第 4章 快速傅里叶变换 (FFT) 课件 52 2 1 4 23 4 ( ) ( ) ( ) , 0 1 22 3 ( ) ( ) ( ) ( ) ( ) 4 2 4 3 ( ) ( ) ( ) ( ) ( ) 4 2 4 01 4 n N n N NN x n x n x n n N N N x n x n j x n x n j x n W N N N x n x n j x n x n j x n W N n (4.4.3) 令 第 4章 快速傅里叶变换 (FFT) 课件 53 则 (4.4.2)式可写成如下更简明的形式： / 2 1 2 22 0 / 4 1 1 4 1 44 0 / 4 1 2 4 2 44 0 ( 2 ) ( ) ( ) , 0 1 2 ( 4 1 ) ( ) ( ) , 0 1 4 ( 4 3 ) ( ) ( ) , 0 1 4 N kn N n N kn N n N kn N n N X k x n W DFT x n k N X k x n W DFT x n k N X k x n W DFT x n k (4.4.4) 第 4章 快速傅里叶变换 (FFT) 课件 54 图 4.4.1 分裂基第一次分解 L形流图 点 D F T 点 D F T 点 D F T x 2 ( 1 ) x 2 (1 N / 4 ) 2 N 4 N 4 N )1( 1 4 x )1( 2 4 x 1 N W 3 N W x ( 1 ) 4 1 N x 2 1 N x 4 3 1 N x 1 1 1 j 第 4章 快速傅里叶变换 (FFT) 课件 55 例如 ， N=16， 第一次抽选分解时 ， 由式 (4.4.3)得 x2(n)=x(n)+x(n+8), 0n7 x14(n)= x(n)-x(n+8) -j x(n+4)-x(n+12) Wn16, 0n3 x24(n)= x(n)-x(n+8) +j x(n+4)-x(n+12) W3n16, 0n3 把上式代入式 (4.4.4)， 可得 X(2k)=DFT x2(n) , 0k7 X(4k+1)=DFT x14(n) , 0k3 X(4k+3)=DFT x24(n) , 0k3 第 4章 快速傅里叶变换 (FFT) 课件 56 图 4.4.2 分裂基 FFT算法 L形排列示意图与结构示意图 (a)分裂基 FFT算法 L形排列示意图； (b)分裂基 FFT算法运算流图结构示意图 ( a ) ( b ) 第 4章 快速傅里叶变换 (FFT) 课件 57 图 4.4.3 16点分裂基第一次分解 L形流图 (图中省去箭头 ) ( 8 ) 点 D F T x 2 ( 0 ) x 2 ( 1 ) x 2 ( 2 ) x 2 ( 3 ) x 2 ( 4 ) x 2 ( 5 ) x 2 ( 6 ) x 2 ( 7 ) 点 D F T 点 D F T )0( 1 4 x )1( 1 4 x )2( 1 4 x )3( 1 4 x )0( 2 4 x )1( 2 4 x )2( 2 4 x )3( 2 4 x 4 4 N 4 4 N 2 N x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) x ( 8 ) x ( 9 ) x ( 1 0 ) x ( 1 1 ) x ( 1 2 ) x ( 1 3 ) x ( 1 4 ) x ( 1 5 ) 0 N W 1 N W 3 N W 2 N W 0 N W 3 N W 6 N W j j j X ( 0 ) X ( 1 ) X ( 2 ) X ( 3 ) X ( 4 ) X ( 5 ) X ( 6 ) X ( 7 ) X ( 8 ) X ( 9 ) X ( 1 0 ) X ( 1 1 ) X ( 1 2 ) X ( 1 3 ) X ( 1 4 ) X ( 1 5 ) X (2 k ) X (4 k 1) X (4 k 3) 1 1 1 1 1 1 1 1 1 1 第 4章 快速傅里叶变换 (FFT) 课件 58 第二次分解： 先对图 4.4.3中 N/2点 DFT进行分解 。 令 X1(l)=X(2l)， 则有 X1(2l)=DFT y2(n) , 0l3 X1(4l+1)=DFT y14(n) , 0l1 X1(4l+3)=DFT y24(n) , 0l1 第 4章 快速傅里叶变换 (FFT) 课件 59 其中 y2(n)=x2(n)+x2(n+4), 0n3 y14(n)= x2(n)-x2(n+4) - x2(n+2)x(n+6) Wn8,n=0,1 y24(n)= x2(n)-x2(n+4) +j x2(n+2)x2(n+6) W3n8,n=0,1 第 4章 快速傅里叶变换 (FFT) 课件 60 图 4.4.4 图 4.4.4中 N/2点 DFT的分解 L形流图 ( 4 ) 点 D F T x 2 ( 0 ) x 2 ( 1 ) x 2 ( 2 ) x 2 ( 3 ) x 2 ( 4 ) x 2 ( 5 ) x 2 ( 6 ) x 2 ( 7 ) y 2 ( 0 ) y 2 ( 1 ) y 2 ( 2 ) y 2 ( 3 ) X 1 ( 0 ) X ( 0 ) X 1 ( 2 ) X ( 4 ) X 1 ( 4 ) X ( 8 ) X 1 ( 6 ) X ( 1 2 ) X 1 ( 1 ) X ( 2 ) X 1 ( 5 ) X ( 1 0 ) X 1 ( 3 ) X ( 6 ) X 1 ( 7 ) X ( 1 4 ) X 1 (2 l ) X 1 (4 l 1 ) X 1 (4 l 3 ) 4N )0( 1 4 y )1( 1 4 y )1( 2 4 y )0( 2 4 y 1 2N W 3 2N W j j 1 1 1 1 1 1 1 1 第 4章 快速傅里叶变换 (FFT) 课件 61 图 4.4.5 4点分裂基 L形运算流图 v ( 0 ) v ( 1 ) v ( 2 ) v ( 3 ) V ( 0 ) V ( 2 ) V ( 1 ) V ( 3 ) j 1 1 1 1 第 4章 快速傅里叶变换 (FFT) 课件 62 图 4.4.6 16点分裂基 FFT运算流图 x ( 0 ) x ( 1 ) x ( 2 ) x ( 3 ) x ( 4 ) x ( 5 ) x ( 6 ) x ( 7 ) x ( 8 ) x ( 9 ) x ( 1 0 ) x ( 1 1 ) x ( 1 2 ) x ( 1 3 ) x ( 1 4 ) x ( 1 5 ) X ( 0 ) X ( 1 ) X ( 2 ) X ( 3 ) X ( 4 ) X ( 5 ) X ( 6 ) X ( 7 ) X ( 8 ) X ( 9 ) X ( 1 0 ) X ( 1 1 ) X ( 1 2 ) X ( 1 3 ) X ( 1 4 ) X ( 1 5 ) j 1 1 1 1 j j 1 1 1 1 j j 1 1 1 1 1 1 1 1 1 1 1 1 j j j j W 1 W 2 W 3 W 3 W 6 W 9 W 2 W 6 1 1 1 1 1 1 1 1 1 1 1 1 N N N N N N N N 第 4章 快速傅里叶变换 (FFT) 课件 63 4.4.2 分裂基 FFT算法的运算量 设第 j级有 lj个 L形 ， j=1,2,M-1,M=log2N， 则有 l1=N/4。 由图 4.4.2(b)可见 ， 第 j-1列中的 L形包含了第 j 列中的一部分结点的计算 ， 即空白部分 ， 所占结点数 刚好等于第 j-1列中所有 L形对应结点的一半 ， 所以第 j 列 L形个数就减少 l j-1/2个 ， 即 第 4章 快速傅里叶变换 (FFT) 课件 64 1 1 1 2 2 3 1 0 42 4 1 ( 1 ) 4 2 4 2 11 ( 1 ) 4 2 4 2 4 1 1 1 ( ) ( 1 ) 4 2 4 2 4 j j j ij j i lN l N l N l N l N l N l NN l 第 4章 快速傅里叶变换 (FFT) 课件 65 由于每个 L形有两次复 (数 )乘运算 ， 所以全部复 乘次数为 1 1 2 2 2 1 2 ( ) 3 3 3 2 1 2 2 l o g ( 1 ) 3 9 9 M M Mj j M N C l M N N N (4.4.5) 第 4章 快速傅里叶变换 (FFT) 课件 66 4.5 离散哈特莱变换 (DHT) 4.5.1 离散哈特莱变换定义 设 x(n),n=0,1,N-1， 为一实序列 ， 其 DHT定义为 1 0 2( ) ( ) ( ) c o s( ) , 0 , 1 , , 1N H n X k DH T x n x n k n k NN 式中 ， cas()=cos+sin。 其逆变换 (IDHT)为 1 0 12( ) ( ) ( ) c o s( ) , 0 , 1 , , 1N HH k x n I DHT X k X k k n n NNN (4.5.3) 第 4章 快速傅里叶变换 (FFT) 课件 67 逆变换证明如下： 1 0 1 0 1 0 1 0 22 c o s( ) c o s( ) 2 2 2 2 c o s( ) si n( ) c o s( ) si n( ) 2 2 2 2 c o s( ) c o s( ) si n( ) si n( ) 2 2 2 2 c o s( ) si n( ) si n( ) c o s( ) 22 c o s ( ) si n N k N k N k N k k n k NN k n k n k k N N N N k n k k n k N N N N k n k k n k N N N N kn N ( ) , 0, kn N Nn n (4.5.4) 第 4章 快速傅里叶变换 (FFT) 课件 68 将式 (4.5.2)代入式 (4.5.3)得 11 00 11 00 1 0 1 2 2 ( ) c o s( ) c o s( ) 1 2 2 ( ) c o s( ) c o s( ) ,01 () 0 , 0 NN k NN k N k x k k n N N N x k n k N N N N x N 第 4章 快速傅里叶变换 (FFT) 课件 69 4.5.2 DHT与 DFT之间的关系 为了便于比较 ， 重写 DFT如下： 211 00 211 00 22 ( ) ( ) ( ) ( ) c o s ( ) s i n ( ) 1 1 2 2 ( ) ( ) ( ) c o s ( ) s i n ( ) NN j kn N nn NN j kn N kk X k D F T x n x n e x n k n j k n NN x n X k e X k k n j k n N N N N (4.5.5) (4.5.6) 容易看出， DHT的核函数 DFT的核函数 的实部与虚部之和。 2 2 2c o s( ) c o s( ) si n( )k n k n k n N N N 2 22co s ( ) ( )j kn Ne kn j knNN 第 4章 快速傅里叶变换 (FFT) 课件 70 将 XH(k)分解为奇对称分量 XHo(k)与偶对称分量 XHe(k)之和 ( ) ( ) ( ) 1 ( ) ( ) ( ) 2 1 ( ) ( ) ( ) 2 H He Ho He H H Ho H H X k X k X k X k X k X N k X k X k X N k (4.5.7) (4.5.8) (4.5.9) 由 DHT定义有 1 0 1 0 2 ( ) ( ) c o s( ) 2 ( ) ( ) sin ( ) N He n N Ho n X k x n k n N X k x n k n N (4.5.10a) (4.5.10b) 第 4章 快速傅里叶变换 (FFT) 课件 71 所以 ， x(n)的 DFT可表示为 同理 ， x(n)的 DHT可表示为 因此 ， 已知 x(n)的 DHT， 则 DFT可用下式求得： ( ) ( ) ( )H e H oX k X k j X k (4.5.11) ( ) ( ) I m ( ) HeX k H k X k (4.5.12) 11( ) ( ) ( ) ( ) ( ) 22H H H HX k X k X N k j X k X N k (4.5.13) 第 4章 快速傅里叶变换 (FFT) 课件 72 4.5.3 DHT的主要优点 (1)DHT是实值变换 ， 在对实信号或实数据进行谱 分析时避免了复数运算 ， 从而提高了运算效率 ， 相应 的硬件也更简单 、 更经济； (2)DHT的正 、 反变换 (除因子 1/N外 )具有相同的形 式 ， 因而 ， 实现 DHT的硬件或软件既能进行 DHT， 也 能进行 IDHT； (3)DHT与 DFT间的关系简单，容易实现两种谱之 间的相互转换。 第 4章 快速傅里叶变换 (FFT) 课件 73 4.5.4 DHT的性质 1. 线性性质 1 1 2 2 1 2 1 2 ( ), ( ) ( ) ( ) ( ) ( ) ( ) HH HH x X k x n X k a x n b x n a X k b X k (4.5.14) 2. x(N-n)的 DHT ( ) ( ) , ( ) ( )HHx n X k x N n X N n 1 0 22( ) ( ) c o s( ) si n( ) , 0 , 1 , , 1N H n X N k x n k n k n k NNN (4.5.15) 其中 ， 当 k=0时 ， XH(N-k)=XH(N)=XH(0)。 第 4章 快速傅里叶变换 (FFT) 课件 74 证明 由 DHT定义 1 0 1 0 1 0 2 ( ) ( ) c o s ( ) 2 ( ) c o s ( ( ) ) 22 ( ) c o s ( ) s i n ( ) N n N n N n DF T x N n x N n k n N x n k N n N x n k n k n NN 而 1 0 1 0 2 ( ) ( ) c o s( ( ) ) 22 ( ) c o s( ) sin( ) ( ) N H n N n X N k x n N k n N x n k n k n DF T x N n NN 第 4章 快速傅里叶变换 (FFT) 课件 75 3. 循环移位性质 0 0 0 0 0 0 22 ( ( ) ) ( ) ( ) c o s( ) ( ) si n( ) 22 ( ( ) ) ( ) ( ) c o s( ) ( ) si n( ) N N H N N H x n n R n X k k n H N k k n NN x n n R n X k k n H N k k n NN (4.5.16) (4.5.17) 证明 由 DHT定义有 1 0 1 0 1 0 ( ) ( ) 2 ( ( ) ) c o s ( ) 2 ( ) c o s ( ( ) ) 2 2 2 2 ( ) c o s ( ) c o s ( ) s i n ( ) s i n ( ) 2 2 2 2 s i n ( ) c o s ( ) c o s ( ) s i n ( ) o N N N oN n N o n N oo n oo DH T x n n R n x n n k n N x n k n n N x n k n k n k n k n N N N N k n k n k n k n N N N N 第 4章 快速傅里叶变换 (FFT) 课件 76 1 0 1 0 2 2 2 ( ) c o s ( ) s i n( ) c o s ( ) 2 2 2 ( ) c o s ( ) s i n( ) s i n( ) 22 ( ) c o s ( ) ( ) s i n( ) N o n N o n H o H o x n k n k n k n N N N x n k n k n k n N N N X k k n X N k k n NN 第 4章 快速傅里叶变换 (FFT) 课件 77 4. 奇偶性 奇对称序列和偶对称序列的 DHT仍然是奇对称序 列或偶对称序列 ， 即 DHT不改变序列的奇偶性 。 5.循环卷积定理 1 1 2 2 1 2 2 1 2 1 1 2 1 2 1 2 ( ) ( ) , ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) HH H H e H H o H H e H H o x n X k x n X k x n x n X k X k X N k X k x n x n X k X k X N k X k (4.5.18) (4.5.19) 第 4章 快速傅里叶变换 (FFT) 课件 78 证明 下面利用 DFT的循环卷积定理和 DHT与 DFT 之间的关系来证明 其中 ， X1(k)=DFT x1(n) ,X2(k)=DFT x2(n) , 根据 DHT与 DFT之间的关系 ， 则有 1 2 1 2 ( ) ( ) ( ) ( )D F T x n x n X k X k 1 1 1 2 2 2 2 2 2 ( ) ( ) ( ) ( ) ( ) ( ) 11 ( ) ( ) ( ) 22 H e H o H e H o H H H X k X k j X k X k X k j X k X k X N k j X N k 第 4章 快速傅里叶变换 (FFT) 课件 79 将上面两式代入式 (4.5.20)并整理后 ， 得 2 1 1 1 1 2 1 1 1 1 12 2 1 2 1 1 ( ) ( ) ( ) ( ) ( ) ( ) 2 1
展开阅读全文