第四章 快速傅里叶变换课件

1、第四章第四章 快速傅里叶变换快速傅里叶变换n4.1 4.1 引言引言n4.2 4.2 直接计算直接计算DFTDFT的问题及改进的途径的问题及改进的途径n4.3 4.3 按时间抽选按时间抽选( (DIT)DIT)的基的基-2 -2 FFTFFT算法算法n4.4 4.4 按频率抽选按频率抽选( (DIF)DIF)的基的基-2 -2 FFTFFT算法算法n4.5 4.5 离散傅里叶反变换离散傅里叶反变换( (IDFT) IDFT) 的快速计算方法的快速计算方法n4.10 4.10 线性卷积与线性相关的线性卷积与线性相关的FFTFFT算法算法n4.11 4.11 数字信号处理的实现数字信号处理的实现第

2、四章第四章 快速傅里叶变换快速傅里叶变换4.1 引言引言0nXN(k)0kxN(n)N-1N-10nXN(k)0kxN(n)N-1N-1DFTDFS0nX(ej)*D(ej)0 x(n)d(n)DTFT0n|X(ej)|0 x(n)DTFT0|Xa(j)|0 xa(t) FTT022第四章第四章 快速傅里叶变换快速傅里叶变换4.1 引言引言0nXN(k)0kxN(n)N-1N-10nXN(k)0kxN(n)N-1N-1DFTDFS0nX(ej)*D(ej)0 x(n)d(n)DTFT0n|X(ej)|0 x(n)DTFT0|Xa(j)|0 xa(t) FTT022)()()()(1)()(10

3、nRnxnRWkXNkXDFTnxNNNknkN)()()()()()(10kRkXkRWnxnxDFTkXNNNnnkN第四章第四章 快速傅里叶变换快速傅里叶变换 4.2 直接计算直接计算DFT的问题及改进的途径的问题及改进的途径1, 1 , 0,)()(10NkWnxkXNnnkN运算量：运算量：对某一对某一k值，复乘值，复乘N次，复加次，复加N-1次；次； 对对DFT，复乘复乘N2次次，复加，复加N(N-1)次次(近似为近似为N2)；例：例：N=1024，则则N2=106，难以实现实时处理；难以实现实时处理；DFT:改进途径：改进途径：将较长的将较长的DFT分解为几个较短的分解为几个较短

4、的DFT，并利用旋转因子并利用旋转因子WN的的周期性、对称性和可约性周期性、对称性和可约性(伸缩性伸缩性)等特性减少运算次数。等特性减少运算次数。NjNeW21. 周期性：周期性：NknNkNnNnkNWWW2. 对称性：对称性：nkNnkNWW3. 可约性：可约性：mnkmNnkNmnkmNnkNWWWW/,nkNknNNkNnNWWW, 12/NNWkNNkNWW2/设序列设序列x(n)的长度为的长度为N，且满足且满足,2LN 12/02/212/02/112/02212/02112/0)12(12/0210)()()()() 12()2()()()()(NrkrNkNNrkrNNrkrN

5、kNNrkrNNrrkNNrkrNnnkNnnkNNnnkNWrxWWrxWrxWWrxWrxWrxWnxWnxWnxnxDFTkX奇偶 12/,1 , 0,12,221Nrrxrxrxrx令令1, 1 , 0Nk令令12, 1 , 0Nk kXWkXkXkN21 rxDFTkX11)( rxDFTkX22)(1, 12,22NNNNk kXWkXNkXkN212令令即即N点点DFT分解为两个分解为两个N/2点点DFT后按上述两公式合成，后按上述两公式合成，这种分解可用蝶形符号表示。这种分解可用蝶形符号表示。1. 周期性：周期性：NknNkNnNnkNWWW2. 对称性：对称性：nkNnkNW

6、W3. 可约性：可约性：mnkmNnkNmnkmNnkNWWWW/,nkNknNNkNnNWWW, 12/NNWkNNkNWW2/12, 1 , 0Nk kXWkXkXkN21 kXWkXNkXkN212N/2点DFTWN0N/2点DFTWN1WN2WN3x(0)X1(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7) rx1 rx2 nx一次抽选分解后运算量：一次抽选分解后运算量： 复乘：复乘：2 (N/2)2+N/2=N(N+1)/2 N2/2 复

7、加：复加：2 (N/2) (N/2-1)+2 (N/2) =N2/2分解前，分解前，复乘复乘N2次次，复加，复加N(N-1)次次(近似为近似为N2)；CABA BCA BC蝶形运算蝶形运算复乘复乘1次，复加次，复加2次次12, 1 , 0Nk kXWkXkXkN21 kXWkXNkXkN212N/2点DFTWN0N/2点DFTWN1WN2WN3x(0)X1(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7) rx1 rx2 nxN/4点DFTWN12W

8、N12WN0WN1WN2WN3X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4点DFTN/4点DFTN/4点DFTWN02WN02 lxlxrxlxlxrx652431,CABA BCA BC lxlxrxlxlxrx652431,CABA BCA BCN/4点DFTWN12WN12WN0WN1WN2WN3X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0

9、)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4点DFTN/4点DFTN/4点DFTWN02WN02对任意对任意N=2N=2L L，按同样方法，都可分解为按同样方法，都可分解为N/2N/2个个2 2点点DFTDFTN/4点DFTWN12WN12WN0WN1WN2WN3X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(

10、6)x(1)x(5)x(3)x(7)N/4点DFTN/4点DFTN/4点DFTWN02WN02对任意对任意N=2N=2L L，按同样方法，都可分解为按同样方法，都可分解为N/2N/2个个2 2点点DFTDFT1, 1 , 0,)()(10NkWnxkXNnnkN对2点DFT：knnkNWxWxWnxkX20210) 1 ()0()()() 1 ()0() 1 () 1 ()0()0(xxXxxXN/4点DFTWN12WN12WN0WN1WN2WN3X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(

11、0)X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4点DFTN/4点DFTN/4点DFTWN02WN021, 1 , 0,)()(10NkWnxkXNnnkN对2点DFT：knnkNWxWxWnxkX20210) 1 ()0()()() 1 ()0() 1 () 1 ()0()0(xxXxxXWN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A

12、(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)1, 1 , 0,)()(10NkWnxkXNnnkN对2点DFT：knnkNWxWxWnxkX20210) 1 ()0()()() 1 ()0() 1 () 1 ()0()0(xxXxxXWN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A

13、(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)第四章第四章 快速傅里叶变换快速傅里叶变换 4.3 按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法二、二、DIT-FFT的运算量的运算量第四章第四章 快速傅里叶变换快速傅里叶变换 4.3 按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5

14、)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7) FFT: 每一级：每一级：N/2次复数、次复数、N次复加；次复加； L级共需：级共需：复乘复乘 ： 1, 1 , 0,)()(10NkWnxkXNnnkN 复乘复乘N2次次，复加，复加N(N-1)次次(近似为近似为N2)；例：例：N=1024，则则N2=106DFT:NNN2log22LNNN2log22L复加：复加：第四章第四章 快速傅里叶变换快速傅里叶变换 4.3

15、按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法FFT算法与直接计算算法与直接计算DFT所需乘法次数的比较曲线所需乘法次数的比较曲线第四章第四章 快速傅里叶变换快速傅里叶变换 4.3 按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法三、三、DIT-FFT的运算规律及编程思想的运算规律及编程思想4.3 按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法 三、三、DIT-FFT的运算规律及编程思想的运算规律及编程思想1. 1. 原位运算原位运算( (同址运算同址运算) )WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x

16、(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)原位运算原位运算：利用同一存储单元存：利用同一存储单元存储蝶形计算输入、输出数据。储蝶形计算输入、输出数据。优点优点：节省内存，降低硬件成本，：节省内存，降低硬件成本，尤其在使用专用集成电路芯片实尤其在使用专用集成电路芯片实现现FFT的情况下更为重要。的情况下更为重要。4.3 按时间抽选按

17、时间抽选(DIT)的基的基-2 FFT算法算法 三、三、DIT-FFT的运算规律及编程思想的运算规律及编程思想1. 1. 原位运算原位运算( (同址运算同址运算) )WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)2. 2. 倒位序规律倒

18、位序规律倒位序及形成原因倒位序及形成原因形成倒序的树状图形成倒序的树状图(N=23) 顺序和倒序二进制数对照表顺序和倒序二进制数对照表 4.3 按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法 三、三、DIT-FFT的运算规律及编程思想的运算规律及编程思想1. 1. 原位运算原位运算( (同址运算同址运算) )WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(

19、7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)2. 2. 倒位序规律倒位序规律顺序和倒序二进制数对照表顺序和倒序二进制数对照表 3. 3. 倒位序的实现倒位序的实现变址运算变址运算n012nnnn 210nnn4.3 按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法 三、三、DIT-FFT的运算规律及编程思想的运算规律及编程思想1. 1. 原位运算原位运算( (同址运算同址运算) )2. 2. 倒位序规律倒位序规律顺序和倒序二进制数对照表顺序和倒序二进制数对照表 3. 3. 倒位序的实现倒位序的实现

20、变址运算变址运算n012nnnn 210nnn存储单元存储单元自然顺序输入自然顺序输入变址变址倒位序倒位序存储单元存储单元4.3 按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法 三、三、DIT-FFT的运算规律及编程思想的运算规律及编程思想1. 1. 原位运算原位运算( (同址运算同址运算) )WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(7)X(0)X

21、(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)2. 2. 倒位序规律倒位序规律3. 3. 倒位序的实现倒位序的实现4. 4. 蝶形运算两结点的蝶形运算两结点的“距离距离” 对对N=2N=2L L点点FFTFFT，当输入为倒位序，输出为正常顺序时，第当输入为倒位序，输出为正常顺序时，第m m级运算中级运算中每个蝶形的两结点每个蝶形的两结点“距离距离”为为2 2m-1m-1。m=1m=1m=2m=2m=3m=34.3 按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法 三、三、DIT-FFT的运算规律及编程思想的运算规

22、律及编程思想1. 1. 原位运算原位运算( (同址运算同址运算) )WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)2. 2. 倒位序规律倒位序规律3. 3. 倒位序的实现倒位序的实现4. 4. 蝶形运算两结点的蝶形运算两结点的“距离距离

23、” 对第对第m m级运算，级运算，5. 5. 的确定的确定rNW rNmmmmmrNmmmmWkXkXkXWkXkXkX1111111222m=1m=1m=2m=2m=3m=34.3 按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法 三、三、DIT-FFT的运算规律及编程思想的运算规律及编程思想1. 1. 原位运算原位运算( (同址运算同址运算) )WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(

24、4)A(5)A(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)2. 2. 倒位序规律倒位序规律3. 3. 倒位序的实现倒位序的实现4. 4. 蝶形运算两结点的蝶形运算两结点的“距离距离” 对第对第m m级运算，级运算，5. 5. 的确定的确定rNW12 , 2 , 1 , 0,12mjNrNjWWmLm=1m=1m=2m=2m=3m=3P189 C+P189 C+程序实现程序实现4.3 按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法 三、三、DIT-FFT的运算规律及编程思

25、想的运算规律及编程思想1. 1. 原位运算原位运算( (同址运算同址运算) )WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)2. 2. 倒位序规律倒位序规律3. 3. 倒位序的实现倒位序的实现4. 4. 蝶形运算两结点的蝶形运算两结点的

26、“距离距离” 对第对第m m级运算，级运算，5. 5. 的确定的确定rNW12 , 2 , 1 , 0,12mjNrNjWWmLm=1m=1m=2m=2m=3m=3P189 C+P189 C+程序实现程序实现6. 6. 存储单元存储单元4.3 按时间抽选按时间抽选(DIT)的基的基-2 FFT算法算法 四、按时间抽选的四、按时间抽选的FFT算法的其他形式流图算法的其他形式流图第四章第四章 快速傅里叶变换快速傅里叶变换 4.4 按频率抽选按频率抽选(DIF)的基的基-2 FFT算法算法DIFFFT一次分解运算流图(N=8) N/2点DFTWN0N/2点DFTWN1WN2WN3X(0)x1(0)X

27、(2)X(4)X(6)X(1)X(3)X(5)X(7)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第四章第四章 快速傅里叶变换快速傅里叶变换 4.4 按频率抽选按频率抽选(DIF)的基的基-2 FFT算法算法DIFFFT二次分解运算流图(N=8) N/4点DFTWN0WN1WN2WN3x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)WN0WN2WN0WN2N/4点DFTN/4点DFTN/4点DFT第四章第四章 快速傅里叶变换快

28、速傅里叶变换 4.4 按频率抽选按频率抽选(DIF)的基的基-2 FFT算法算法DIFFFT运算流图(N=8) WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)DITIFFT运算流图 WN0WN1WN2WN3WN0WN0N1x(0)x(4)x(2)x(6)x(4)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN2WN2N1N1N1N1N1N1N1第四章第四章 快速傅里叶变换快速傅里叶变换 4.5 离散

29、傅里叶反变换离散傅里叶反变换(IDFT)的快速计算方法的快速计算方法1, 1 , 0,)()(10NkWnxkXNnnkNDFT :IDFT:1, 1 , 0,)(1)(10NnWkXNnxNknkNWN02121x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)212121WN121WN221WN3212121WN021WN2212121WN021WN22121WN02121WN0212121WN021WN021第四章第四章 快速傅里叶变换快速傅里叶变换 4.5 离散傅里叶反变换离散傅里叶反变换(IDFT)的快速计

30、算方法的快速计算方法1, 1 , 0,)()(10NkWnxkXNnnkNDFT :IDFT:DITIFFT运算流图(防止溢出) 1, 1 , 0,)(1)(10NnWkXNnxNknkNWN02121x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)212121WN121WN221WN3212121WN021WN2212121WN021WN22121WN02121WN0212121WN021WN021第四章第四章 快速傅里叶变换快速傅里叶变换 4.5 离散傅里叶反变换离散傅里叶反变换(IDFT)的快速计算方法的快速

31、计算方法1, 1 , 0,)()(10NkWnxkXNnnkNDFT :IDFT:1, 1 , 0,)(1)(10NnWkXNnxNknkN*10*)(1)(1)(kXDFTNWkXNnxNknkN直接利用直接利用DFT的的FFT算法计算算法计算IDFT:第四章第四章 快速傅里叶变换快速傅里叶变换 4.64.9 进一步减少进一步减少DFT运算量的措施运算量的措施第四章第四章 快速傅里叶变换快速傅里叶变换 4.10 线性卷积与线性相关的线性卷积与线性相关的FFT算法算法 10)()(Mmmnxmhnxnhny设设x(n)为为L点，点，h(n)为为M点，输出点，输出y(n)为为直接计算的运算量：乘

32、法次数直接计算的运算量：乘法次数LMmd对线性相位对线性相位FIR滤波器系统滤波器系统)1()(nMhnh2LMmd nRmnxmxnxnxnyLLmL102121)()()()(Nn0 x1(n)1nx2(n)1nyl(n)=x1(n)*x2(n)11 20 1 2 3 40 1 2 3 4 5 6ny3(n)=x1(n) x2(n)0 1 2 3 4 5 67ny4(n)=x1(n) x2(n)0 1 2 3 4 5 687ny1(n)=x1(n) x2(n)100 1 2 3 4723453 691295869121369129513691295 nRrLnynRmrLnxmxnRmrLnxmxLrlLrLmLLmr 10211021)()()()( 结论：结论：L点圆周卷积点圆周卷积y(n)是线性卷积是线性卷积yl(n)以以L为周期为周期的周期延拓序列的主值序列。的周期延拓序列的主值序列。 当当L N1+N2-1，则则L点圆周卷积能代表线性卷积。点圆周卷积能代表线性卷积。LL圆周卷积线性卷积 102121211)()()()()()(Nmmmnxmxmnxmxnxnxny第四章第四章 快速傅里叶变换快速傅里叶变换 4.10 线性卷积与线性相关的线性卷积与线性相关的FFT算法算法 nhnxny)()(N乘法次数乘法次数2LMmd直接计算的运