DSP_13离散傅立叶变换-FFT

1、快速傅立叶变换快速傅立叶变换 Fast Fourier Transform (FFT)Lesson 132022-4-92复习提问l如何利用循环卷积计算线性卷积？如何利用循环卷积计算线性卷积？l什么是频率取样，其特点是？什么是频率取样，其特点是？lDFT的计算量是多少？的计算量是多少？2022-4-93DFT的计算量的计算量离散傅立叶变换离散傅立叶变换(DFT)在实际应用中是非常重要的，利用在实际应用中是非常重要的，利用它可以计算信号的频谱、功率谱和线性卷积等。但当它可以计算信号的频谱、功率谱和线性卷积等。但当 N 很很大时，利用大时，利用DFT直接计算运算量太大直接计算运算量太大，因此，如何

2、提高计，因此，如何提高计算算DFT的速度成为很重要的课题。的速度成为很重要的课题。1965年库利年库利(Cooley)和和图基图基(Tukey)在前人研究成果的基础上提出了快速计算在前人研究成果的基础上提出了快速计算DFT的算法，之后，又出现了各种各样快速计算的算法，之后，又出现了各种各样快速计算DFT的方的方法，这些方法统称为法，这些方法统称为快速傅立叶变换快速傅立叶变换(Fast Fourier Transform 或或 FFT)。2022-4-94DFT的计算量的计算量介绍介绍FFT之前，先估计一下直接计算之前，先估计一下直接计算DFT所需的运算量。先展开计算所需的运算量。先展开计算DF

3、T为方程组形式如下为方程组形式如下从上式可以看出，假设从上式可以看出，假设 是复数，则计算一个是复数，则计算一个 需要需要 N 次次复数乘法复数乘法和和 (N-1) 次复数加法次复数加法。 1121110112221202112111011020100012101121021210112100NNNNNNNNNNNNNNNNNNNNNNNNWNxWxWxWxNXWNxWxWxWxXWNxWxWxWxXWNxWxWxWxX nx kX2022-4-95DFT的计算量的计算量所以计算所以计算 N 个个 值，共需值，共需 次复数乘法和次复数乘法和 次复数加法。而且我们知道：次复数加法。而且我们知道：

4、即每次复数乘法包括即每次复数乘法包括 4 次实数乘法和次实数乘法和 2 次实数加法，每次复数加法包次实数加法，每次复数加法包括括 2 次实数加法，因此计算次实数加法，因此计算 N 点点 DFT 共需要共需要 次实数乘法次实数乘法和和 次实数加法。当次实数加法。当 N 很大时，这是一个非很大时，这是一个非常大的计算量。常大的计算量。 kX2N1NN dbjcajdcjbaadbcjbdacjdcjba24N1222NNN2022-4-96复数乘法 复数加法一个X(k)NN 1N个X(k)(N点DFT)N 2N (N 1)实数乘法实数加法一次复乘42一次复加2一个X (k)4N2N+2 (N 1)

5、=2 (2N 1)N个X (k)(N点DFT)4N 22N (2N 1)10( )NnkNnx n Wajbcjdacbdj adcbDFT的计算量的计算量2022-4-97nkNW 的特性*()() ()nknkN n kn N kNNNNWWWW对称性()() nkN n kn N kNNNWWW周期性 nkmnkNmNWW可约性/nknk mNN mWW0/2(/2) 11Nk NkNNNNWWWW 特殊点：2jnknkNNWeNknkNNWWnNnkNNWW2jmnkmNe221NjjNee DFT的计算量的计算量2022-4-98DFT的计算量的计算量平面Z8N0k1k2k7kN2k

6、NWFFT算法主要利用了算法主要利用了 的两个的两个性质：性质：(1)对称性对称性(2)周期性周期性r 为整数。左图是为整数。左图是 N=8 时这两个时这两个性质的情况。性质的情况。FFT算法有很多种，我们只介绍其中算法有很多种，我们只介绍其中两种两种，即，即时间抽选时间抽选基基2FFT算法和算法和频频率抽选率抽选基基2FFT算法，这两个名字的含义在介绍它们时解释。这两种算算法，这两个名字的含义在介绍它们时解释。这两种算法特别适用于法特别适用于 N 等于等于 2 的幂次的幂次的情况。的情况。kNWkNNWNrkNWNjNeW22022-4-99DFT的计算量的计算量21/2222/2221NN

7、NNkkkNNNNNNkkNNWWWW WWWWW 2022-4-910时间抽取时间抽取基基2 FFT算法算法(库里图基算法库里图基算法)这种算法简称为时间抽取这种算法简称为时间抽取FFT算法，其基本出发点是，利算法，其基本出发点是，利用旋转因子用旋转因子 的对称性和周期性，将一个大的的对称性和周期性，将一个大的DFT分分解成一些逐次变小的解成一些逐次变小的DFT来计算。分解过程遵循两条规则：来计算。分解过程遵循两条规则：(1) 对时间进行奇偶分解对时间进行奇偶分解；(2) 对频率进行前后分解对频率进行前后分解。设设 ，M 为正整数。为了推导方便，取为正整数。为了推导方便，取 ，即离散时间信号

8、为即离散时间信号为kNWMN2823N 7,6,5,4,3,2,1,0 xxxxxxxxnx2022-4-911时间抽取时间抽取基基2 FFT算法算法(库里图基算法库里图基算法)按照规则按照规则(1)，将序列，将序列 分为两组，一组序号为偶数，分为两组，一组序号为偶数，另一组序号为奇数，即另一组序号为奇数，即并分别表示为并分别表示为并利用性质并利用性质 重写重写DFT如下：如下： 7,5,3,16,4,2,0 xxxxxxxx nx 12, 2 , 1 , 0122Nrrxrhrxrg奇数项偶数项12/2NNWW NjNeW22022-4-912时间抽取时间抽取基基2 FFT算法算法(库里图基

9、算法库里图基算法)NjNeW2 12, 2 , 1 , 012212/02/12/02/12/012/12/012/12/0212/0212/01212/0210NkkHWkGWrhWWrgWrhWWrgWrhWWrgWrxWrxWnxWnxWnxnxDFTkXkNNrkrNkNNrkrNNrkrNkNNrkrNNrkrNkNNrkrNNrkrNNrkrNnnkNnnkNNnnkN，奇数偶数2022-4-913时间抽取时间抽取基基2 FFT算法算法(库里图基算法库里图基算法)NjNeW2 12, 2 , 1 , 047,6,5,43,2,1,0)2(DFT212, 2 , 1 , 0NkkHW

10、kGkXkXkXXXXXXXXkXkXNkHkGNkkHWkGkXkNkN，可表示为值的个根据上式，前分成前后两组，即，将按照规则。点的都是和中的，式子2022-4-914时间抽取时间抽取基基2 FFT算法算法(库里图基算法库里图基算法)NjNeW2 /2 1/2 1222/2/200222/2 1/2 1/2/20042,12 NNNNNr kkr kNNNrrNNkkNNNNNrkkrkNNNrrkX kNX kg r WWh r WWWWNX kg r WWh r W 后 个 值的可表示为因为，所以 0,1,2,12kNNG kW H kk，2022-4-915时间抽取时间抽取基基2 F

11、FT算法算法(库里图基算法库里图基算法)NjNeW2 DFT2/DFT2/DFT2DFTN12, 2 , 1 , 0212, 2 , 1 , 0 点的是，而点的是注意号流图如下图所示。实现上面两个式子的信少。了，从而使得计算量减和间结果后，就可以重复利用中前后分成两部分来求，将点的可以由两个点的说明，前面两个式子NrhkHNrgkGkHkGkXNNkkHWkGNkXNkkHWkGkXkNkN2022-4-916时间抽取时间抽取基基2 FFT算法算法(库里图基算法库里图基算法)DFT2点NDFT2点N 0 x 4x 2x 6x 1x 5x 3x 7x 0G 1G 2G 3G 0H 1H 2H 3

12、H 0000HWGXN3NW2NW1NW0NW1111 1111HWGXN 2222HWGXN 3333HWGXN 0040HWGXN 1151HWGXN 2262HWGXN 3373HWGXN)8(DFT2/DFTNNN计算的时间抽取流程图点的分解成两个点2022-4-917时间抽取时间抽取基基2 FFT算法算法(库里图基算法库里图基算法) NDFT/ 2DFT/ 2DFT/ 4DFT/ 2 0 ,2 ,4 ,6/ 2DFT 0 ,42 ,6x nNNNG kNxxxxNxxxx前面介绍了 点的可以通过把分成奇偶两部分，再求点的来求得。照次类推，把点的可以分解成两个点的来求得。以为例，它是点

13、序列的点，我们把该序列分成奇偶两部分，即再求上述两/ 4DFT/ 4DFT/ 2DFTNNN个点序列的，从而利用类似的方法由这两个点序列的合成原来要求的点的。用数学公式说明上述过程如下：2022-4-918时间抽取时间抽取基基2 FFT算法算法(库里图基算法库里图基算法)NjNeW2 /2 1/4 1/4 1212/2/2/2000/4 1/4 1/4/2/40022212210,1,2,14NNNlkrklkNNNrllNNlkklkNNNllkNG kg r Wgl WglWgl WWglWNM kWN kk， 14, 2 , 1 , 0 12242214/044/4214/044/Nkk

14、NWkMWlgWWlgNkGkGkkNNlNklNNkNNlNklN，可表示为值的个后2022-4-919时间抽取时间抽取基基2 FFT算法算法(库里图基算法库里图基算法) 如右图所示。实现上述算法的流程图。点的是而点的是其中来求得，即点的过两个可以通点的上两式说明DFT4/6,2DFT4/4,014, 2 , 1 , 04 DFT4/DFT2/22NxxkNNxxkMNkkNWkMNkGkNWkMkGNNkNkNDFT4点N 0 x 2x 4x 6x 0M 1M 0N 1N2NW0NWDFT4点N 0G 1G 2G 3G11)8(DFT4/DFT2/NNN计算的时间抽取流程图点的分解成两个点

15、2022-4-920时间抽取时间抽取基基2 FFT算法算法(库里图基算法库里图基算法) 图所示。的分解计算流程图如下点个为计算经两次分解点的到解的计算过程，我们得这样，合并前面两次分。点的是，而点的是其中到作同样的分解计算，得类似地，对DFT4/4DFTNDFT4/7,3DFT4/5,114, 2 , 1 , 01224122 214/04/2/14/04/214/04/2/14/04/NNxxkQNxxkPNkkQWkPWlhWWlhNkHkQWkPWlhWWlhkHkHkNNlklNkNNlklNkNNlklNkNNlklN2022-4-921时间抽取时间抽取基基2 FFT算法算法(库里图

16、基算法库里图基算法)DFT4点N 0 x 2x 4x 6x2NW0NWDFT4点N11DFT4点N 1x 3x 5x 7x2NW0NWDFT4点N113NW2NW1NW0NW1111 0X 1X 2X 3X 4X 5X 6X 7X)8(DFT4/DFTNNN的时间抽取点的经两次分解成四个点2022-4-922时间抽取时间抽取基基2 FFT算法算法(库里图基算法库里图基算法) 0 x 4x10NW流程图两点DFT 位”计算。以进行“同址”或“原单元为堞形，所以可由于流程图的基本运算”。输入序列要进行“变址“正序”，按自然顺序排列，称为而输出为“混序”，不按自然顺序排列，称输入计算都是一个堞形；流程图的每一级的基本流程图有以下特点：从图可看出，该流程图如下图所示