《数字信号处理》课程教学课件（2020讲稿）第四章 快速傅里叶变换 §4-5 N为复合数的FFT算法（统一的FFT算法）

第四章快速傅里叶变换

第四章 快速傅里叶变换

S4-5N为复合数的FFT算法一统一的FFT算法如何理解P140N=2基-2 FFT“无害的”？N≠2"，如何快速计算DFT？处理方法：(1)通过补零，使序列长度=2v→基-2 FFT(2)N=ML（复合数）→统一的FFT算法(3)N+ML （素数）→ Chirp-Z 变换(CZT)一、算法原理0≤n≤N-1，N=ML（复合数）Vx(n),:N-DFT~N2M个L-DFT~M×L2>减少了运算如果N-DFTL个M-DFT~L xM?

3 / 30 N  2 基2 FFT  N 2 ，如何快速计算DFT ?   (1)通过补零，使序列长度=2ν→ 基-2 FFT 一、算法原理 (2)N=ML（复合数） → 统一的FFT算法 (3)N≠ML（素数） → Chirp-Z 变换(CZT) 处理方法： x(n), 0  n  N 1, N  ML（复合数） ∵N-DFT~N2 ∴如果N-DFT M个L-DFT~M×L2 L个M-DFT~L×M2 减少了运算 §4-5 N为复合数的FFT算法——统一的FFT算法 如何理解P140 “无害的”？

为此，令M一列号n=Mn,+no ,no=0,1,...,M-1 -n,=0,1,..,L-1 — 行号x(n)x(nj, no)(L,M)x(0,1)x(0,0)x(0)x(0, M -1)-----------X(M -)--x(1)-x(1,0)x(1,1)x(1, M - 1)x(M).--x(M+1) .. x(2M-1)..x(M(L-1)x6ML-1x(L-1,0) x(L-1,I) ... x(L-1, M-I)横着进L行M列，LxM

4 / 30 为此，令 n=Mn1+n0 , n0=0,1,.,M-1 —— 列号 n1=0,1,.,L-1 —— 行号                  ( ( 1)) ( 1) ( ) ( 1) (2 1) (0) (1) ( 1) x M L x M L x M x M x M x x x M                           ( 1,0) ( 1,1) ( 1, 1) (1,0) (1,1) (1, 1) (0,0) (0,1) (0, 1) x L x L x L M x x x M x x x M        x(n) x( n1 , n0 ) L行M列，L x M L M (L,M) 横着进

M同理，对DFT的输出X(k)做类似的处理：令 k=Lk,+kok,=0,1,...,L-1 ~ nik,=0,l,..,M-1~ no转置X(k)X(ki, ko)X2(ko, k))(M,L)(L,M)X(0)X(0,0)X(1,0)X(L)X(M-1,0)X(M -1)L)X(1)X(L+1)X(M-1)L+1)X(0,1)X(1, 1)X(M -1,1).....X(ML-1)X(L-1)/X(2L-1)X(M-1,L-1)LX(0, L-1)X(1, L-1)竖着出X( ko, k))L行M列，LxM

5 / 30 同理，对DFT的输出X(k)做类似的处理： 令 k=Lk1+k0 k0=0,1,.,L-1 ~ n1 k1=0,1,.,M-1~ n0 (0) ( ) (( 1) ) (1) ( 1) (( 1) 1) ( 1) (2 1) ( 1) X X L X M L X X L X M L X L X L X ML                    (0,0) (1,0) ( 1,0) (0,1) (1,1) ( 1,1) (0, 1) (1, 1) ( 1, 1) X X X M X X X M X L X L X M L                   X(k) X( k1 , k0 ) L行M列，L x M L M (M,L) X2 ( k0 , k1 ) (L,M) 转置 竖着出 X2 ( k0 , k1 )

Sx(n,式中,no)WkonX,(ko,no)(M,L)nj=0AX(k)= X(Lk, +ko)= X(kj,ko)一列一列= DFT, [x(n,no)]N-1求DFTZx(n)Wkn0≤k≤L-1, Vnox(Mn,+no)n=0M-1 L-IX(ko, no)Wkon"oX, (ko,no).x(n, n。)W(Mm+no)Lk +ko)NNno=0 n;=00≤n≤M-1, VkM-1 L-1VLkinoWkong)wMLknWMnkoWNNx(n,no=Zx, (ko, no)WkinoNAX,(ko,k)no=0n=0no=0M-1L-一行一行x(n,n,)Wko"Wko"oWkinoZM= DFT, [X, (ko, no)]求DFTno=0 n,=0L行M列，LxM0≤k,≤M-1,M-WkinoZ[X,(ko, no)WkongMO≤k≤L-1,Vnono=0转置M-EX, (ko, no)wkinoX,(ko,k)月X(kj,ko) X(Lk, +ko)= X(k)no=00≤k≤L-10<≤k≤M-10≤k≤N-1L行M列,M行L列，LXMMXL

6 / 30 ( ) ( ) ( , ) 1 0 1 0 X k  X Lk  k  X k k     1 0 ( ) N n kn WN x n 1 0 1 0 0 1 1 1 ( )( ) 1 0 0 0 ( , ) M L Mn n Lk k N n n x n n W          1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 ( , ) M L MLk n Mn k Lk n k n N N N N n n x n n W W W W        0 1 0 0 1 0 0 1 1 1 1 0 0 0 ( , ) M L k n k n k n L N M n n x n n W W W        x(Mn1+n0 )     1 0 1 0 0 0 0 0 1 0 [ ( , ) ] M n k n M k n X k n WN W      1 0 1 0 0 0 1 0 ( , ) M n k n n WM X k ( , ) ( , ) ( ) ( ) 2 0 1 1 0 1 0  X k k  X k k  X Lk  k  X k 0  k0  L 1, 0  k1  M 1 0  k  N 1 L行M列，L x M L行M列， L x M M行L列， M x L 转置      1 0 1 0 0 1 0 1 0 1 ( , ) ( , ) L n k n n n WL 式中 X k n x 1 1 0 0 0 [ ( , )] 0 1, DFT x n n n k L n       0 0 1 0 0 1 0 0 0 ( , ) ( , ) 0 1, k n X k n X k n WN n M k        1 0 0 1 2 0 1 1 0 0 0 ( , ) ( , ) L k n M n X k k X k n W      0 1 0 0 1 0 0 [ ( , )] 0 1, 0 1, DFT X k n n k M k L n           一列一列 求DFT 一行一行 求DFT (M,L)

理解：1. x(n)，X(k)都是一维数据；且输入为正序；X(k)= X(Lk, +ko)= X(kj,ko)N-12.x(n)“横着进”使正序输入变为Ex(n)WknL行M列二维结构(x(n1,no))，经过x(Mn,+no)Nn=0复合数算法对二维数据处理；M-1 L-1x(n, n )W(Mmg+n )Lk +ko)ZZ①若X(k)“竖着出”输出可以使二维数据X2(ko,k)(仍然为L行M列)还no=0 n;=0M-1 L-1原为一维正序X(k)输出;LknoWkonWMLknWMnkoWNMLx(n,noIAA②若X(k)经过将二维数据X(ko,k)no=0n=0译序，X(k)=X(Lk,+ko)输出(“横着M-1 L-(n,no)Wko"wko"oWkinoZZ出”)，这时一维X(k)输出不是正序M；但经过X(ko,k)转置成X(k,ko)no=0n,=0L行M列，LxM再将二维数据x(k1,ko)译序，M-X(k)=X(Lk,+ko)输出（“横着出”WkinoE[X,(ko,no)wkonM这时一维X(k)输出是正序。no=0转置M-EX, (ko, no)wkinoX,(ko,k)月X(kj,ko) X(Lk +ko) = X(k)no=00≤k≤L-10≤k≤M-10≤k≤N-1L行M列,M行L列，LXMMXL

7 / 30 ( ) ( ) ( , ) 1 0 1 0 X k  X Lk  k  X k k     1 0 ( ) N n kn WN x n 1 0 1 0 0 1 1 1 ( )( ) 1 0 0 0 ( , ) M L Mn n Lk k N n n x n n W          1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 ( , ) M L MLk n Mn k Lk n k n N N N N n n x n n W W W W        0 1 0 0 1 0 0 1 1 1 1 0 0 0 ( , ) M L k n k n k n L N M n n x n n W W W        x(Mn1+n0 )     1 0 1 0 0 0 0 0 1 0 [ ( , ) ] M n k n M k n X k n WN W      1 0 1 0 0 0 1 0 ( , ) M n k n n WM X k ( , ) ( , ) ( ) ( ) 2 0 1 1 0 1 0  X k k  X k k  X Lk  k  X k 0  k0  L 1, 0  k1  M 1 0  k  N 1 L行M列，L x M L行M列， L x M M行L列， M x L 转置 理解： 1. x(n)， X(k)都是一维数据；且输 入为正序； 2. x(n)“横着进” 使正序输入变为 L行M列二维结构(x(n1 ,n0 )) ，经过 复合数算法对二维数据处理； ①若X(k)“竖着出”输出可以使二 维数据X2 (k0 ,k1 )(仍然为L行M列)还 原为一维正序X(k)输出； ②若X(k)经过将二维数据X2 (k0 ,k1 ) 译序，X(k)=X(Lk1+k0 )输出(“横着 出”)，这时一维X(k)输出不是正序 ；但经过X2 (k0 ,k1 ) 转置成X(k1 ,k0 ) ，再将二维数据X(k1 ,k0 )译序， X(k)=X(Lk1+k0 )输出(“横着出”) ，这时一维X(k)输出是正序

式中一列一列X(ko, no)=x(n, no)Wkon求DFTn,=0A=DFT, [x(ni, no)],0≤k.≤L-1, VnoX, (ko, no)= X,(ko, no)Wko"o0≤no ≤M-1,Vk旋转一行一行因子求DFTX,(ko,n)=Zx (ko,no)Wknono=0= DFT,[X, (ko,no)],0≤k ≤M-1,0≤ko≤L-1, Vn

8 / 30      1 0 1 0 0 1 0 1 0 1 ( , ) ( , ) L n k n n n WL X k n x 1 0 0 0 [ ( , )], 0 1, 1  DFTn x n n  k  L  n  X k n X k n W n M k k n  N       ( , ) ( , ) , 0 1, 1 0 0 1 0 0 0 0 0       1 0 2 0 1 1 0 0 0 1 0 ( , ) ( , ) L n k n n WM X k n X k 1 0 0 1 0 0 [ ( , )], 0 1,0 1, 0 DFTn X k n  k  M   k  L  n    一列一列 求DFT 旋转 因子 一行一行 求DFT 式中

二、运算步骤(I) x(n)→x(n,no)行号n, =0,1..., L-1个列号n。 =0,1., M-1n= mn +no(针对每一列)(2) Vno, 0≤n≤M-1L1X(ko,no)= DFT,[x(n, no)] = Zx(n, no)Wlo",ko =0,1...,L-1ni=0(3)X, (ko, no)= X(ko, no)W.kono0≤k≤L-10<n≤M-1(4)ko，0≤k≤L-1（针对每一行)X,(ko,k)= DFT,[X, (ko,no)]= Zx, (ko, no)Whk", ko =0,1.., M-1No=(5)译序0≤k≤N-1X2(ko,k) → X(kj,ko) → X(k)个0≤k,≤L-1k = Lk, + ko.0≤k,≤M-1

9 / 30 二、运算步骤 1 0 1 0 (1) ( ) ( , ) n mn n x n x n n     列号 行号 0,1,., 1 0,1,., 1 0 1     n M n L 0 0 (2) , 0 1     n n M （针对每一列） ( , ) [ ( , )] 1 0 0 1 n1 n0 X k n DFT x  n ( , ) , 0 0,1,., 1 1 0 1 0 1 0 1       x n n W k L L n k n L 0 1 (3) ( , ) ( , ) 0 1 0 1 0 0 1 0 0 0 0 0         n M X k n X k n W k L k n N (4) k0 , 0  k0  L 1 （针对每一行） ( , ) [ ( , )] 2 0 1 0 1 0 n0 X k k DFT X k n   ( , ) , 0 0,1,., 1 1 0 1 0 0 0 1 0        X k n W k M M n k n M (5) 译序 X2 (k0 , k1 )  X (k1 , k0 )  X (k) 0  k  N 1 , 1 0 k  Lk  k  0 1 0 1 1 0       k M k L

例: N=12=4×3,L=3, M=4算法流图：图4-20.P.144Wt"oX,(ko,k,)Wh"oX,'(kono)X,(koono)=X(Lki+kor(n)r(n,no)Wo"译序X,(0,0)X(0)X,(0,0)r(0)=r(0,0)X(0,0)Wi2W?X,(0,1)X:(0,1)X(3)X,(0,1)r(1)=r(0,1)Wi.公X,(0,2)X(0,2)2(2)-2(0,2)0X(6)X,(0,2)Wi.r(3)=r(0,3)eWX,(0,3)X,(0,3)X(9)xi(0.3)Wi.WX2(1,0)X.(1,0)r(4)=r(1,0)X(1)X(1,0)WWi2X,(1,1)X2(1,1)(5)=r(1,1)0X(4)X(1,1)WisA X,(1,2)X,(1,2)r(6)=1(1,2)。M=4-X(7)X(1,2)Wi2X(1,3)X,(1,3)Wsr(7)=r(1,3)X(10)X,(1,3)W的顺序Wi. X,(2,0)X,(2,0)1(8)=r(2.0)X,(2,0)X(2)(wwww)WiWi.X,(2,1)X(2,1)X(2,1)X(5)r(9)=2(2.1)(wwwiw)Wi.@Xi(2,2)X2(2,2)-X(8)r(10)=(2,2)eX,(2,2)wwww)L=3WisX, (2,3)X1(2.3)X(2,3)-X(11)r(11)=r(2.3)0(www)Wi.图4-20N=M×L=4×3=12时的FFT运算流图同理：n，0≤n≤L-l详见(4-38)P.142YM

例：N=12=4×3, L=3, M=4 算法流图：图4-20,P.144 同理：n1 , 0  n  L 1 详见(4-38) P.142 L M

例:N=12=4×3,M=4, L=3算法流图：图4-20.P.144Wte"oX,(ko,k1)X,'(ko,no)Wh"=X(Lki+koX,(ko,no)r(n)r(n,noW"i译序X,(0,0)X(0)X,(0,0)r(0)=r(0,0)X(0,0)Wi2W?X1(0,1)X:(0,1)X(3)r(1)=r(0,X,(0,1)Wi.,(0,2)X,(0,2)r(2)=z(0,2X(6)X,(0,2)Wi.ew'r(3)=r(0,3)X(0,3)X,(0,3)X(9)xi(0.3)Wi.WX2(10)X.(1,0)r(4)=r(1,0)X(1)(1,0)Wi2X.(1,1)X2(1,1)r(5)=r(1,)X(4)X,(1,1)Wi.X,(1,2)●X,(1,2)(6)=1(1,2)M=4X(7)●X(1,2)Wi2X,(1,3)X(1,3)r(7)=r(1,3)Ws-X(10)X,'(1,3)Wb"的顺序Wi.0 X:(2,0)X(2,0)1(8)=r(2,0X,(2,0)(wwww)X(2)WIWi.X,(2,1)X:(2,1)X(2,1)X(5)r(9)=r(2.1)(wwww)Wi.Xi(2,2)X2(2,2)-X(8)r(10)=2(2,2)eX,(2,2)O(WWWIW)L=3WisX, (2,3)0 X1(2.3)r(11)=r(2.3)0 X(2,3)-X(11)www)Wi.N=MXL=4X3=12时的FFT运算流图图4-20这是一个蝶形这仍然是一个蝶形三点蝶形四点蝶形

例：N=12=4×3, M=4 , L=3 算法流图：图4-20,P.144 这是一个蝶形 三点蝶形 这仍然是一个蝶形 四点蝶形