第四章快速傅里叶变换 43进一步减少运算量的措施 43.1多类碟形单元运算 1、无关紧要的旋转因子 当L=1时,只有一个旋转因子W0=1 L=2时,有两个旋转因子WQ=1和W4=-j; 对于这两种情况,在DFT中称值为±1和±j的旋转因子为无关紧要的旋转因 子,蝶形运算可以不进行乘法运算。这样复数乘法运算次数由MN/2可以减少为 ●进一步,从L=3至L=M级蝶形运算中因为无关紧要的旋转因子存在,如: W,wN等,还可减少复数乘法次数为 (3.1) L=3 L=3 因此, DIT-FFT的复数乘法次数可以减少为 (2)=(M-2)--2|=(M-3)+2 2、蝶形运算中的特殊复数乘法 般实现一次复数乘法运算需要四次实数乘,两次实数加,但对某些特殊复 数,乘法运算的运算量可以降低。如对W=(-∥2,与任一复数相乘时, (1+/)(x+)=2[(x+y)-(x-y) 只需要两次复数加和两次复数乘即可。所以从实数运算考虑,计算N=2M点 DIT-FFT所需实数乘法次数为
第四章 快速傅里叶变换 4.3 进一步减少运算量的措施 4.3.1 多类碟形单元运算 1、无关紧要的旋转因子 ⚫ 当 L=1 时，只有一个旋转因子 0 1 WN = ； ⚫ L=2 时，有两个旋转因子 0 1 WN = 和 4 N W j N = − ； 对于这两种情况，在 DFT 中称值为 1 和 j 的旋转因子为无关紧要的旋转因 子，蝶形运算可以不进行乘法运算。这样复数乘法运算次数由 MN/2 可以减少为 (2 2 ) ( ) 2 M N C M = − ⚫ 进一步，从 L=3 至 L=M 级蝶形运算中因为无关紧要的旋转因子存在，如： 0 WN ， N 4 WN 等，还可减少复数乘法次数为 1 3 3 1 2 2 2 2 2 M M L L L L N N − N = = = = − (3.1) 因此，DIT-FFT 的复数乘法次数可以减少为 (2 2 2 3 2 ) ( ) ( ) 2 2 2 M N N N C M M = − − − = − + (3.2) 2、蝶形运算中的特殊复数乘法 一般实现一次复数乘法运算需要四次实数乘，两次实数加，但对某些特殊复 数，乘法运算的运算量可以降低。如对 ( ) 8 2 1 2 N W j N = − ，与任一复数相乘时， ( )( ) ( ) ( ) 2 2 1 2 2 + + = + − − j x jy x y x y 只需要两次复数加和两次复数乘即可。所以从实数运算考虑，计算 2 M N = 点 DIT-FFT 所需实数乘法次数为
R/(2)=4(M-3)+2 2|=M2M-+10 2 3、基2FFT算法的分类 在基2FFT程序中,若包含了所有旋转因子,则称该算法为一类蝶形单元运 算;若去掉W=±1的旋转因子,则称之为二类蝶形单元运算;若再去掉W=土j 的旋转因子,则称为三类蝶形单元运算:若再处理W=(1-/) √2 则称之为四 类蝶形运算。我们将后三种运算称为多类蝶形单元运算 显然,蝶形单元类型越多,编程就越复杂,但当N较大时,乘法运算的减少 量就越可观。 432旋转因子的生成 在FFT运算中,旋转因子W=co/xm-j5(M/求正弦和余弦函数 2m N 值的计算量是很大的。所以编成时,产生旋转因子的方法直接影响运算速度 种方法是在每级运算中直接产生;另一种方法是在FFT程序开始前预先计算出 WN,m=0,1 存放在数组中,作为旋转因子表,在程序执行过程中直接 査表得到所需旋转因子值,不再计算。这样使运算速度大大提高,其不足之处是 占用内存较多。 433实序列的FFT算法 在实际工作中,数据一般都是序列若直接按FFT运算流图计算就是把x(m) 看成一个虚部为零的复序列进行计算。这就增加了存储量和运算时间。处理该问 题有三种方法 1、用一个N点FFT计算两个N点实序列的FFT,一个实序列作为x(m)的实 部,另一个作为虚部,计算完FFT后,根据DFT的共轭对称性,由输出X(k)分 别得到两个实序列的N点DFT
( ) ( ) 13 2 4 3 2 2 2 10 2 2 2 M N N R M N M = − + − − = − + (3.3) 3、基 2FFT 算法的分类 在基 2FFT 程序中，若包含了所有旋转因子，则称该算法为一类蝶形单元运 算；若去掉 1 r WN = 的旋转因子，则称之为二类蝶形单元运算；若再去掉 r W j N = 的旋转因子，则称为三类蝶形单元运算；若再处理 ( ) 2 1 2 r W j N = − ，则称之为四 类蝶形运算。我们将后三种运算称为多类蝶形单元运算。 显然，蝶形单元类型越多，编程就越复杂，但当 N 较大时，乘法运算的减少 量就越可观。 4.3.2 旋转因子的生成 在 FFT 运算中，旋转因子 2 2 cos sin m N m m W j N N = − ，求正弦和余弦函数 值的计算量是很大的。所以编成时，产生旋转因子的方法直接影响运算速度。一 种方法是在每级运算中直接产生；另一种方法是在 FFT 程序开始前预先计算出 , 0,1, 1 2 m N N W m = − ，存放在数组中，作为旋转因子表，在程序执行过程中直接 查表得到所需旋转因子值，不再计算。这样使运算速度大大提高，其不足之处是 占用内存较多。 4.3.3 实序列的 FFT 算法 在实际工作中，数据一般都是序列。若直接按 FFT运算流图计算，就是把 x n( ) 看成一个虚部为零的复序列进行计算。这就增加了存储量和运算时间。处理该问 题有三种方法： 1、用一个 N 点 FFT 计算两个 N 点实序列的 FFT，一个实序列作为 x n( ) 的实 部，另一个作为虚部，计算完 FFT 后，根据 DFT 的共轭对称性，由输出 X k( ) 分 别得到两个实序列的 N 点 DFT
2、用二点FFT计算一个N点实序列的DFT。 设x(m)为N点实序列,取x(n)的偶数点和奇数点分别作为新构造的序列 y(n)的实部和虚部,即 x(n)=x(2n),x2(m)=x(2n+1),n=01 y(n)=x(n)+x2(n),n=0,1 对y(m)进行,点FFT,输出Y(k),则 X1(k)=DFT[x(m)]=() x:(k)=D[x()]=-mn() k=0,1, 2 根据 DIT-FFT的思想可得 X(k)=X1(k)+WX2(k),k=01 由于x(m)为实序列,所以X(k)具有共轭对称性,X(k)的另外点的值为 (N-k)=x^(k),k 相对一般的FFT算法,上述算法的运算效率η 2M n=1,运算速度提高近一倍。 44分裂基FFT算法 自从基2快速算法出现以来,人们仍不断寻求更快的算法。从理论上讲,用 较大的基数可以进一步减少运算次数,但同时会使计算程序变得更为复杂。所以 取大于8的基数没有多大的实际意义。1984年,法国的杜梅尔和霍尔曼将基2 分解和基4分解糅合在一起,提出了分裂基FFT算法。其运算量比前述几种算 法都有所减少,运算流程却与基2FFT很接近,运算程序也很短。所以说分裂基 FFT算法是一种适用的高效新算法。 441分裂基FFT算法原理 442分裂基FFT算法的运算量
2、用 2 N 点 FFT 计算一个 N 点实序列的 DFT。 设 x n( ) 为 N 点实序列，取 x n( ) 的偶数点和奇数点分别作为新构造的序列 y n( ) 的实部和虚部，即 1 2 ( ) (2 , 2 1 , 0,1, , 1 ) ( ) ( ) 2 N x n x n x n x n n = = + = − ( ) 1 2 ( ) ( ), 0,1, , 1 2 N y n x n jx n n = + = − 对 y n( ) 进行 2 N 点 FFT，输出 Y k( ) ，则 ( ) ( ) ( ) ( ) ( ) ( ) 1 1 2 2 , 0,1, , 1 2 ep op X k DFT x n Y k N k X k DFT x n jY k = = = − = = − 根据 DIT-FFT 的思想可得 ( ) 1 2 ( ) ( ), 0,1, , 1 2 k N N X k X k W X k k = + = − 由于 x n( ) 为实序列，所以 X k( ) 具有共轭对称性， X k( ) 的另外 2 N 点的值为 ( ) ( ) * , 1,2, , 1 2 N X N k X k k − = = − 相对一般的 FFT 算法，上述算法的运算效率 2 1 M M = + ，当 10 2 2 M N = = 时， 20 11 = ，运算速度提高近一倍。 4.4 分裂基 FFT 算法 自从基 2 快速算法出现以来，人们仍不断寻求更快的算法。从理论上讲，用 较大的基数可以进一步减少运算次数，但同时会使计算程序变得更为复杂。所以 取大于 8 的基数没有多大的实际意义。1984 年，法国的杜梅尔和霍尔曼将基 2 分解和基 4 分解糅合在一起，提出了分裂基 FFT 算法。其运算量比前述几种算 法都有所减少，运算流程却与基 2FFT 很接近，运算程序也很短。所以说分裂基 FFT 算法是一种适用的高效新算法。 4.4.1 分裂基 FFT 算法原理 4.4.2 分裂基 FFT 算法的运算量
4.5离散哈特莱变换(DHT) 个实序列的N点DFT完全可以由N个实数数据确定。下面就介绍一种直 接对实序列进行实数域变换的离散哈特莱变换,记为DHT。 451离散哈特莱变换的定义 设x(m),n=0,1…,N-1,为一实序列,其DHT定义为 X(k)=DH[x()=∑x(7)a(x,k=01…N (5.1) 式中,cas(a)=cosa+sina 其逆变换为 )D820--1652 证明:[略] 452DHT与DFT之间的关系 将Xn(k)分解为奇对称分量Xm(k)与偶对称分量Xm(k)之和 XH(k)=XHe( k)+XHo(k) 其中 Xm(4)=5[Xn(k)+x(N-k) XHo( k)=LXH(k)-XH(N-k) (55) 由DHT定义有 xn(4)=∑x(n)cs如 (56) X(k)=∑x(msin|如 所以,已知x(m)的DFI X(k)=XHe(k)-jXHo(k) (58)
4.5 离散哈特莱变换（DHT） 一个实序列的 N 点 DFT 完全可以由 N 个实数数据确定。下面就介绍一种直 接对实序列进行实数域变换的离散哈特莱变换，记为 DHT。 4.5.1 离散哈特莱变换的定义 设 x n n N ( ), 0,1, , 1 = − ，为一实序列，其 DHT 定义为 ( ) ( ) ( ) 1 0 2 , 0,1, , 1 N H n X k DHT x n x n cas kn k N N − = = = = − (5.1) 式中， cas( ) = + cos sin 。 其逆变换为 ( ) ( ) ( ) 1 0 1 2 , 0,1, , 1 N H H k x n IDHT X k X k cas kn n N N N − = = = = − (5.2) 证明：[略] 4.5.2 DHT 与 DFT 之间的关系 将 X k H ( ) 分解为奇对称分量 X k Ho ( ) 与偶对称分量 X k He ( ) 之和 X k X k X k H He Ho ( ) = + ( ) ( ) (5.3) 其中 ( ) ( ) ( ) 1 2 X k X k X N k He H H = + − (5.4) ( ) ( ) ( ) 1 2 X k X k X N k Ho H H = − − (5.5) 由 DHT 定义有 ( ) ( ) 1 0 2 cos N He n X k x n kn N − = = (5.6) ( ) ( ) 1 0 2 sin N Ho n X k x n kn N − = = (5.7) 所以，已知 x n( ) 的 DFT， X k X k jX k ( ) = − He Ho ( ) ( ) (5.8)
同理,x(m)的DHT可表示为 X (5.9) 因此,已知x(n)的DHT,则DFT可用表示为 x(k)=5[xn(k)+X(N-k)-xn(k)-x1(N-k)(510) 如果不考虑因子1/2,只要增加2N次实数加法运算就能由x(n)的DHT谱求出 (n)的DFT谱 453DHT的主要优点 l、DHIT是实值变换,在对实信号或数据进行谱分析避免了复数运算,从而 提高了运算效率,相应的硬件也更简单、更经济 2、DHT的正、反变换具有相同的形式(除因子1N外),因而,实现DHT 的硬件或软件既能进行DHT,也能进行IDHT 3、DHT与DFT间的关系简单,容易实现两种谱之间的相互转换。 454DHT的性质 为了叙述方便,用符号x(m)分n()表示Xn(k)=DHT[x(n)] 1、线性性质 若x(n)分Mn(k),x2(m)X/(k),则 (n)+bx2(n)+aYH(k)+bX2H(k) (5.11) 2、x(N-n)的DHT 若x(m)Xn(k),则x(N-n)4Xn(N-k),且 XH(N-k x( n cos sIn k|k=0,1…,N-1(5.12) 其中,当k=0时,Xn(N-k)=XB(N)=Xn(O)
同理， x n( ) 的 DHT 可表示为 X k X k X k H ( ) = − Re Im ( ) ( ) (5.9) 因此，已知 x n( ) 的 DHT，则 DFT 可用表示为 ( ) ( ) ( ) ( ) ( ) 1 1 [ 2 2 X k X k X N k j X k X N k = + − − − − H H H (5.10) 如果不考虑因子 1/2，只要增加 2N 次实数加法运算就能由 x n( ) 的 DHT 谱求出 x n( ) 的 DFT 谱。 4.5.3 DHT 的主要优点 1、DHT 是实值变换，在对实信号或数据进行谱分析避免了复数运算，从而 提高了运算效率，相应的硬件也更简单、更经济； 2、DHT 的正、反变换具有相同的形式（除因子 1/N 外），因而，实现 DHT 的硬件或软件既能进行 DHT，也能进行 IDHT； 3、DHT 与 DFT 间的关系简单，容易实现两种谱之间的相互转换。 4.5.4 DHT 的性质 为了叙述方便，用符号 x n X k ( ) H ( ) 表示 X k DHT x n H ( ) = ( ) 。 1、线性性质 若 x n X k 1 1 ( ) H ( ) ， x n X k 2 2 ( ) H ( ) ，则 ax n bx n aX k bX k 1 2 1 2 ( ) + + ( ) H H ( ) ( ) (5.11) 2、 x N n ( − ) 的 DHT 若 x n X k ( ) H ( ) ，则 x N n X N k ( − − ) H ( ) ，且 ( ) ( ) 1 0 2 2 cos sin , 0,1, , 1 N H n X N k x n kn kn k N N N − = − = − = − (5.12) 其中，当 k=0 时， X N k X N X H H H ( − = = ) ( ) (0)
3、循环移位性质 若x(n)←>Xn(k),则 x(n-no)) R(n)<>XH(k)cos[xr kno +X(N-k)sin(x kno)(5. 13) x(n+)&()()(如x(N=6)m(61 奇偶性 奇对称序列和偶对称序列的DHT仍然是奇对称序列或偶对称序列,即DHT 不改变序列的奇偶性 5、循环卷积定理 若x()分M(k),x2(m)分x2(k),则 x(n)*x2(n)<>X2H()XIHe (k)+ X2H(N-k)XiHo(k) (5.15) 或 (k)X2He()+XH(N-k)X2Ho(k) 其中,Xmh(k)和X1h(k)分别是x1(k)的偶对称分量和奇对称分量 455DHT的快速算法(FHT) 1、基2DIT-FHT算法及运算流程图 设有N=2点时域序列x(n),则 对x(n)进行抽取 ,0≤ r)=x(2r+1
3、循环移位性质 若 x n X k ( ) H ( ) ，则 (( 0 0 0 )) ( ) ( ) ( ) 2 2 cos sin N N H x n n R n X k kn X N k kn N N − + − (5.13) (( 0 0 0 )) ( ) ( ) ( ) 2 2 cos sin N N H x n n R n X k kn X N k kn N N + − − (5.14) 4、奇偶性 奇对称序列和偶对称序列的 DHT 仍然是奇对称序列或偶对称序列，即 DHT 不改变序列的奇偶性。 5、循环卷积定理 若 x n X k 1 1 ( ) H ( ) ， x n X k 2 2 ( ) H ( ) ，则 x n x n X k X k X N k X k 1 2 2 1 2 1 ( )* ( ) + − H He H Ho ( ) ( ) ( ) ( ) (5.15) 或 x n x n X k X k X N k X k 1 2 1 2 1 2 ( )* ( ) + − H He H Ho ( ) ( ) ( ) ( ) (5.16) 其中， X k 1He ( ) 和 X k 1Ho ( ) 分别是 X k 1 ( ) 的偶对称分量和奇对称分量。 4.5.5 DHT 的快速算法（FHT） 1、基 2DIT-FHT 算法及运算流程图 设有 2 M N = 点时域序列 x n( ) ，则 ( ) ( ) 1 0 2 ,0 1 N H n X k x n cas kn k N N − = = − (5.17) 对 x n( ) 进行抽取 ( ) ( ) ( ) ( ) 0 1 2 ,0 1 2 1 2 x r x r N r x r x r = − = + (5.18) 有
XH(k) rk cOS k kx()a(k+m(2k反 2兀rk+c N N 2 (5.19) 2、基2DI-FHT的运算量 总的乘法次数Mn为 N =NM-3N+ (520) L=1 2 总的加法次数A为 NM--N+2 (521) 运算量约为基2 DIT-FFT算法的一半。 4.56实信号的快速循环卷积
( ) ( ) ( ) ( ) ( ) 1 1 1 1 2 2 2 2 0 1 1 1 0 0 0 0 2 2 2 2 2 2 2 cos sin cos 2 2 2 2 N N N N H r r r r X k x r cas rk k x r cas rk k x r cas rk k x r cas rk N N N N N N N − − − − = = = = = + + − + (5.19) 2、基 2DIT-FHT 的运算量 总的乘法次数 MH 为 2 1 2 2 3 4 2 M L H L L N M NM N − = = − = − + (5.20) 总的加法次数 AH 为 3 3 2 2 2 A NM N H = − + (5.21) 运算量约为基 2DIT-FFT 算法的一半。 4.5.6 实信号的快速循环卷积