延安大学：《数字信号处理》课程教学讲稿（DigitalSignal Processing，DSP）第4章 快速傅里叶变换（2/3）

第四章快速傅里叶变换 43进一步减少运算量的措施 43.1多类碟形单元运算 1、无关紧要的旋转因子 当L=1时,只有一个旋转因子W=1; ·L=2时,有两个旋转因子W=1和W=-j 对于这两种情况,在DFT中称值为±和±的旋转因子为无关紧要的旋转因 子,蝶形运算可以不进行乘法运算。这样复数乘法运算次数由MN2可以减少为 N 2 进一步,从L=3至L=M级蝶形运算中因为无关紧要的旋转因子存在,如: W0,W等,还可减少复数乘法次数为 2 因此, DIT-FFT的复数乘法次数可以减少为 CM M-2 (M-3)+2 (32) 2、蝶形运算中的特殊复数乘法 般实现一次复数乘法运算需要四次实数乘,两次实数加,但对某些特殊复 数,乘法运算的运算量可以降低。如对形=(1-j)2,与任一复数相乘时, 2(+)(x+m)=2(x+y(x-y) 只需要两次复数加和两次复数乘即可。所以从实数运算考虑,计算N=2“点 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 所需实数乘法次数为

Rn(2)=417(M-3)+2(N2=N、1+10 (3.3) 3、基2FFT算法的分类 在基2FFT程序中,若包含了所有旋转因子,则称该算法为一类蝶形单元运 算;若去掉W=土1的旋转因子,则称之为二类蝶形单元运算;若再去掉W=±j 的旋转因子,则称为三类蝶形单元运算若再处理=(1-)2,则称之为四 类蝶形运算。我们将后三种运算称为多类蝶形单元运算 显然,蝶形单元类型越多,编程就越复杂,但当N较大时,乘法运算的减少 量就越可观 4.32旋转因子的生成 在FFT运算中,旋转因子W=cos 丌n M)(),求正弦和余弦函数 值的计算量是很大的。所以编成时,产生旋转因子的方法直接影响运算速度。 种方法是在每级运算中直接产生;另一种方法是在FFT程序开始前预先计算出 WN,m=0,1, 1,存放在数组中,作为旋转因子表,在程序执行过程中直接 査表得到所需旋转因子值,不再计算。这样使运算速度大大提高,其不足之处是 占用内存较多。 4.3.3实序列的FFT算法 在实际工作中,数据一般都是序列。若直接按FFT运算流图计算,就是把x(n) 看成一个虚部为零的复序列进行计算。这就增加了存储量和运算时间。处理该问 题有三种方法 1、用一个N点FFT计算两个N点实序列的FFT,一个实序列作为x(m)的实 部,另一个作为虚部,计算完FT后,根据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)的实部和虚部,即 x1(m)=x(2n),x(n)=x(2n+1),n=0.1- y(n)=x(n)+x2(n),n=01 对y(n)进行点FFT,输出Y(k),则 X, (k)=DFTLx,(n)=Y(k k=0,1, X2(k)=DFTL,(n)=-yr(K) 根据 DIT-FFT的思想可得 X(k)=X1(k)+Wx2(k),k=01N-1 由于x(m)为实序列,所以X(k)具有共轭对称性,X(k)的另外,点的值为 X(N-k)=x(k=1.2…,-1 相对一般的FFT算法,上述算法的运算效率η 2M 当N=2M=20时 M+1 运算速度提高近一倍。 44分裂基FFT算法 自从基2快速算法出现以来,人们仍不断寻求更快的算法。从理论上讲,用 较大的基数可以进一步减少运算次数,但同时会使计算程序变得更为复杂。所以 取大于8的基数没有多大的实际意义。1984年,法国的杜梅尔和霍尔曼将基2 分解和基4分解糅合在一起,提出了分裂基FFT算法。其运算量比前述几种算 法都有所减少,运算流程却与基2FFT很接近,运算程序也很短。所以说分裂基 FFT算法是一种适用的高效新算法。 44.1分裂基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(mn),n=0,1…N-1,为一实序列,其DHT定义为 x()=Dm(0(0301-116 式中,cas(a)=c osa+sina 其逆变换为 x(n)=IDHTLXn(K)=2X(k) Cas kn=0,1…,N-1(52) 证明:[略] 452DHT与DFT之间的关系 将Xn(k)分解为奇对称分量Xm2(k)与偶对称分量Xm(k)之和 XH(k)=XH(k)+XHo(k) 其中 XHe(k)=Xn(k)+Xn(N-k) xm(4)=2[x(k)-x/(N-k (5.5) 由DHT定义有 xm()-=∑x()o kn (56) xm()=∑x(n)sn 所以,已知x(m)的DFT, x(k)=X(k)-jXHo(k) (5.8)

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可表示为 XH(k)=RelX(k)]-Im[LX(k)I (5.9) 因此,已知x(n)的DHT,则DFT可用表示为 X(k)=互[xn()+X(N-k)-xn()-xn(N-k)(510) 如果不考虑因子12,只要增加2N次实数加法运算就能由x(m)的DHT谱求出 x(n)的DFT谱。 453DHT的主要优点 l、DHI是实值变换,在对实信号或数据进行谱分析避免了复数运算,从而 提高了运算效率,相应的硬件也更简单、更经济 2、DHT的正、反变换具有相同的形式(除因子1N外),因而,实现DHT 的硬件或软件既能进行DHT,也能进行IDHT; 3、DHT与DFT间的关系简单,容易实现两种谱之间的相互转换 454DHT的性质 为了叙述方便,用符号x(n)Xn(k)表示Xn(k)=DHT[x(n) 1、线性性质 若x(n)Xn(k),x2(n)X2/(k),则 ax(n)+bx2(n)<>aIu(k)+bX2H(K) (5.11) 2、x(N-n)的DHT 若x(m)分Xn(k),则x(N-n)分Xn(N-k),且 Xu(N-k x(n) co sin 2k)k=01 N-1(5 其中,当k=0时,Xn(N-k)=Xn(N)=xn(0)

同理， 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(m)4Xn(k),则 x(-4)2(o)x((+x(N-()61) (n+m)R()x1() N kno1-X (N-k)sin N(514) 4、奇偶性 奇对称序列和偶对称序列的DHT仍然是奇对称序列或偶对称序列,即DHT 不改变序列的奇偶性 5、循环卷积定理 若x1(n)Xm(k),x2(m)X2(k),则 x,(n)*x2(n)<>X2H(k)XH(k)+X2H(N-k)XiHo(k) x(n)*(n)+X,H(k)X2He (k)+ Xu(N-k)X2Ho(k) (5.16 其中,Xm(k)和xm2(k)分别是X(k)的偶对称分量和奇对称分量。 4.55DHT的快速算法(FHT) 1、基2 DIT-FHT算法及运算流程图 设有N=2点时域序列x(m),则 Xn(k)=∑x(nla3k0≤ksN-1 (5.17) 对x(n)进行抽取 x0()=x(2r) N 0<r≤ 有

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) 有

Xn()=∑x(r)a + cos k2x,(r)cas 2兀rk+sinl k>x,(r) rk 2、基2DIT-FHT的运算量 总的乘法次数Mn为 ∑ 2|=NM-3N+4 (520) 总的加法次数A为 AH=-NM-N+ (5.21) 运算量约为基2 DIT-FFT算法的一半。 456实信号的快速循环卷积

          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 实信号的快速循环卷积