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

理解：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