《数字信号处理》课程教学课件（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)