数字信号处理第4章快速傅里叶变换(FFT)

1、第第4章章 快速傅里叶变换快速傅里叶变换 通信与信息工程学院第第4 4章章 快速傅里叶变换快速傅里叶变换 4.1 4.1 引言引言 4.2 4.2 直接计算直接计算DFTDFT的问题及改进的途径的问题及改进的途径 4.3 4.3 按时间抽取（按时间抽取（DITDIT）的基）的基2-FFT2-FFT算法算法4.4 4.4 按频率抽取（按频率抽取（DIFDIF）的基）的基2-FFT2-FFT算法算法4.5 IDFT4.5 IDFT的高效算法的高效算法 4.64.6 FFTFFT的的其他应用其他应用快速卷积快速卷积 学习目标 理解按时间抽取的基理解按时间抽取的基-2FFT算法的原理、算法的原理、运算

2、流图、所需计算量和算法特点；运算流图、所需计算量和算法特点； 理解按频率抽取的基理解按频率抽取的基-2FFT算法的原理、算法的原理、运算流图、所需计算量和算法特点；运算流图、所需计算量和算法特点； 理解理解IFFT算法；算法；4.1 引引 言言 快速傅里叶变换（快速傅里叶变换（FFTFFT）并不是一种新的变换，而是离散傅里叶变换）并不是一种新的变换，而是离散傅里叶变换（DFTDFT）的一种快速算法。）的一种快速算法。 在信号的频谱分析、在信号的频谱分析、 系统的分析、系统的分析、 设计和实现中都会用到设计和实现中都会用到DFTDFT的计的计算。算。 DFTDFT的计算量太大，很难对问题进行实时

3、处理，难以实用。的计算量太大，很难对问题进行实时处理，难以实用。 19651965年首次发现了年首次发现了DFTDFT运算的一种快速算法以后，人们开始认识到运算的一种快速算法以后，人们开始认识到DFTDFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法，法， 这就是快速傅里叶变换（这就是快速傅里叶变换（FFTFFT）的算法。）的算法。 FFTFFT出现后使出现后使DFTDFT的运算大大简化，运算时间一般可缩短一二个数量级的运算大大简化，运算时间一般可缩短一二个数量级之多，使之多，使DFTDFT的运算在实际中真正得到

4、了广泛的应用。的运算在实际中真正得到了广泛的应用。 4.2 直接计算直接计算DFT的问题及改进的途径的问题及改进的途径 一、一、 直接计算直接计算DFT的运算量问题的运算量问题设设x(n)为为N点有限长序列点有限长序列，其其DFT为为 10)()(NnnkNWnxkXk=0, 1, , N-1 反变换反变换（IDFT）为为 10)(1)(NknkNWkXNnXn=0, 1, , N-1 运算量一个一个X(k)复数乘法复数乘法复数加法复数加法NN-1N2N(N-1)N个个X(k)10NnknNWnx)Re)(ImIm)(ReIm)(ImRe)(ReIm)Re(Im)(Re)()(101010nk

5、NnkNnkNNnnkNNnnkNnkNNnnkNWnxWnxjWnxWnxWjWnxjnxWnxkX一次复数乘法需用四次实数乘法和二次实数加法；一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法需二次实数加法。一次复数加法需二次实数加法。 一个一个X(k)实数乘法实数乘法实数加法实数加法4N2N+2(N-1)=2(2N-1)4N22N(2N-1)N个个X(k)二、 改进的途径x(n)u长序列长序列短序列短序列WNkn10NnknNWnx4.3 按时间抽取按时间抽取（DIT）的基的基 -2 FFT算法算法 一、一、 算法原理算法原理 1. 一次分解一次分解 NN/2 设序列设序列x(n)

6、长度为长度为N，且满足且满足N=2M，M为正整数为正整数。按按n的的奇偶把奇偶把x(n)分解为两个分解为两个N/2点的子序列点的子序列： 12, 1 , 0)()12()()2(21NrrxrxrxrxrkNNrkNrkNNrkrNNrrkNNrNnnnkNNnNnnnkNnkNWrxWWrxWrxWrxWnxWnxWnxnxDFTkX)()( )() 12()2()()()()()(2120221201)12(1202120101010为奇数为偶数1202/22/1120)()()(NrrkNkNrkNNrWrxWWrxkXk=0,1,.,N/2-1222222NNjNjNWeeWX1(k)

7、与与X2(k)分别是分别是x1(r)及及x2(r)的的N/2点点DFT： rkNNrrkNNrrkNNrrkNNrWrxWrxkXWrxWrxkX2/1202/212022/1202/11201) 12()()()2()()(一个一个N点点DFT已分解成两个已分解成两个N/2点的点的DFT)()(21kXWkXkN利用周期性求利用周期性求X(k)的后半部分的后半部分 kNkNNNNkNWWWWkXNkXkXNkXNkXkX22221121222,又为周期的是以X2(k)X1(k)kNW 1X1(k)kNWX2(k)X1(k)kNWX2(k) kX2NkX 12,.,1 ,022121NkkXW

8、kXNkXkXWkXkXkNkNN点点（N=8）DFTx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(1)X2(2)X2(3)X2(0)-1-1-1-1WN0WN1WN2WN3N/2点点DFTN/2点点DFTx(0)=x1(0)x(2)=x1(1)x(4)=x1(2)x(6)=x1(3)x(1)=x2(0)x(3)=x2(1)x(5)=x2(2)x(7)=x2(3llxlxlxlx, ,)()()()(141012242314044214043

9、14012211402211NkkXWkXWlxWWlxWlxWlxkXkNNllkNkNNllkNNlklNNllkN,)()()()()()()(/)(/2. 二次分解二次分解 N/2N/4)()(/kXWkXkNXkN4231414, 1 , 0NkX2(k)也可进行同样的分解：也可进行同样的分解： )()(4)()()(62/5262/52kXWkXkNXkXWkXkXkNkN14, 1 , 0Nk1404/21404/661404/21404/55)12()()()2()()(NllkNNllkNNllkNNllkNWlxWlxkXWlxWlxkXx(0)=x1(0)x(2)=x1(

10、1)x(4)=x1(2)x(6)=x1(3)x(1)=x2(0)x(3)=x2(1)x(5)=x2(2)x(7)=x2(3)N/2点点 DFTN/2点点 DFTX1(0)X(0)X1(1)X(1)X1(2)X(2)X1(3)X(3)X2(1)X(5)X2(2)X(6)X2(3)X(7)X2(0)X(4)-1-1-1-1WN0WN1WN2WN3 N/2点点DFT分解为两个分解为两个N/4点点DFT DFT4点NX3(0)X3(1)x3(0) x1(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4点NX4(0)X4(1)x4(0) x1(1) x(2)x4(1) x1(3

11、) x(6)X1(2)X1(3) 1 102/NW12/NW一个一个N=8点点DFT分解为四个分解为四个N/4点点DFT DFT4点NX3(0)X3(1)x3(0) x1(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4点NX4(0)X4(1)x4(0) x1(1) x(2)x4(1) x1(3) x(6)X1(2)X1(3) 1 10NW2NWX(0)X(1)X(2)X(3)DFT4点NX5(0)X5(1)x5(0) x2(0) x(1)x5(1) x2(2) x(5)X2(0)X2(1)DFT4点NX6(0)X6(1)x6(0) x2(1) x(3)x6(1) x

12、2(3) x(7)X2(2)X2(3) 1 1X(4)X(5)X(6)X(7)0NW1NW2NW3NW 1 1 1 10NW2NWN=8，四个四个N/4点DFT即四个即四个2点点DFT，其输出分别为：其输出分别为：X3(k)，X4(k)，X5(k)，X6(k)，k=0, 1)4()0()4()0()1 ()0()1 ()4()0()4()0()1 ()0()0(012311210233002301200233xWxxWxxWWxXxWxxWxxWWxXNN0122121NjjWeeW140433NllkNWlxkX/)()(N=8 按时间抽取的按时间抽取的FFTFFT运算流图运算流图x(0)X

13、(0)x(4)X(1) 10NWx(2)X(2)x(6)X(3) 10NW0NW2NW 1 1x(1)X(4)x(5)X(5) 10NWx(3)X(6)x(7)X(7) 10NW0NW2NW 1 10NW1NW2NW3NW 1 1 1 1X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)N=8时共有三级蝶形运算，每一级有时共有三级蝶形运算，每一级有N/2=4个蝶形个蝶形X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)二、二、 按时间抽取的按时间抽取的FF

14、T算法与直接计算算法与直接计算DFT运算量的比较运算量的比较u N=2M时，共有时，共有M级级蝶形，蝶形， 每级都由每级都由N/2个蝶形个蝶形运算组成；运算组成；u每个蝶形需要每个蝶形需要一次复乘一次复乘、 二次复加二次复加；u每级运算都需每级运算都需N/2次复乘次复乘和和N次复加次复加；uM级运算总共需要：级运算总共需要： 复乘数复乘数 22log22logFFNNmMNaNMNN=复加数复加数 以乘法为例，直接以乘法为例，直接DFT复数乘法次数是复数乘法次数是N2，FFT复数乘法复数乘法次数是次数是(N/2) log2N； 直接计算直接计算DFT与与FFT算法的复数乘法计算量之比为算法的复

15、数乘法计算量之比为 ：bNNbNNNMNN1212222当当N=2048时，这一比值为时，这一比值为372.4，即直接计算，即直接计算DFT的运算的运算量是量是FFT运算量的运算量的372.4倍；倍；当点数当点数N越大时，越大时，FFT的优点更为明显。的优点更为明显。 对一个连续时间信号对一个连续时间信号xa(t)采样采样1秒得到一个秒得到一个4096个采样点的序个采样点的序列，若计算采样信号的列，若计算采样信号的4096点点DFT。假定仅对假定仅对200f300Hz频率范围所对应的频率范围所对应的DFT采样点感兴趣。采样点感兴趣。（1）若直接用）若直接用DFT，要计算这些值需要多少次复乘？，

16、要计算这些值需要多少次复乘？ MN=1014096=413696（2）若用基）若用基2的的DIT-FFT计算，则需要多少次复乘？计算，则需要多少次复乘？ N/2log2N=4096/2log24096=24576思考题思考题N点点x(n)序列，构造新序列序列，构造新序列 y(n)=x(n/2),n为偶数时，为偶数时， y(n)=0，n为奇数时，为奇数时， n=0,1,2,2N-1，求：求：Y(K)与与X(K)的关系，的关系，K=0,1,2,. 2N-1例例 题：题： KRKXKYNKKXKYWKYNKYKXKYWKYKYNNkNkN22212211,.1 , 0解：由解：由DIT-FFT可得可

17、得y(2n)= y1(n)=x(n), Y1(K)=X(K) y(2n+1)= y2(n)= 0, Y2(K)=0n=0,1,.,N-1已知已知x(n)长度为长度为N（N为偶数）。定义两个长度为为偶数）。定义两个长度为N/2的序列的序列如下如下:其中，其中，G(k)=DFTg(n), H(k)=DFTh(n),分别为分别为N/2长。长。试利用试利用G(k)和和H(k)表示出表示出X(k)=DFTx(n)，k=0,1,N-1。补充题补充题 1222112221nxnxnhnxnxng三、三、 按时间抽取的按时间抽取的FFT算法的特点算法的特点 1. 原位运算（同址运算）原位运算（同址运算）x(0

18、)X(0)x(4)X(1) 10NWx(2)X(2)x(6)X(3) 10NW0NW2NW 1 1x(1)X(4)x(5)X(5) 10NWx(3)X(6)x(7)X(7) 10NW0NW2NW 1 10NW1NW2NW3NW 1 1 1 1第一级蝶形运算第一级蝶形运算第二级蝶形运算第二级蝶形运算第三级蝶形运算第三级蝶形运算 1rNWXm1(k)Xm1( j)Xm(k) Xm1(k) Xm1( j)Xm( j) Xm1(k) Xm1( j)rNWrNWrNmmmrNmmmWjXkXjXWjXkXkX)()()()()()(1111m表示第表示第m级迭代，级迭代，k, j为数据所在行数；为数据所

19、在行数； 某一级的两个节点某一级的两个节点k和和j的节点变量进行蝶形运算的节点变量进行蝶形运算后，得到结果为下一级后，得到结果为下一级k, j两节点的节点变量，即两节点的节点变量，即每个蝶形的输入、输出数据节点同在一条水平线上；每个蝶形的输入、输出数据节点同在一条水平线上；与其他节点变量无关，即蝶形的两个输出值仍放与其他节点变量无关，即蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中；回蝶形的两个输入所在的存储器中； 每级的每级的N/2 个蝶形运算全部完成后，再开始下一个蝶形运算全部完成后，再开始下一级的蝶形运算；级的蝶形运算；这样经过这样经过M级运算后，原存放输入数据的级运算后，原存放输入

20、数据的N个存个存储单元中依次存放输出的储单元中依次存放输出的N个值；个值；这种利用同一存储单元存放蝶形计算输入、输出这种利用同一存储单元存放蝶形计算输入、输出数据的方法称为数据的方法称为原位运算原位运算。可以节省存储单元。可以节省存储单元, ,降降低设备成本。低设备成本。 2. 倒位序规律倒位序规律基基2 2的的DIT-FFTDIT-FFT的的输出输出X(k)按按正常顺序正常顺序排列在存储排列在存储单元中，即按单元中，即按X(0)，X(1)，X(7)的顺序排列；的顺序排列；输入输入x(n)却不是按自然顺序存储的，而是按却不是按自然顺序存储的，而是按x(0)，x(4)， ， x(7)的顺序存入存

21、储单元，看起来好像的顺序存入存储单元，看起来好像是是“混乱无序混乱无序”的；的；实际上是有规律的，我们称之为实际上是有规律的，我们称之为倒位序倒位序。 n用二进制数表示为用二进制数表示为(n2n1n0)2（当（当N=8=23时，二进制为三位时，二进制为三位） 第一次分组，第一次分组，n为偶数为偶数（相当于相当于n的二进制数的最低位的二进制数的最低位n0=0）在上半部分在上半部分，n为奇数为奇数（相当于相当于n的二进制数的最低位的二进制数的最低位 n0=1）在下半部分在下半部分。 下一次则根据次最低位下一次则根据次最低位n1为为“0”或是或是“1”来分偶奇来分偶奇（而不而不管原来的子序列是偶序列

22、还是奇序列管原来的子序列是偶序列还是奇序列），）， 如此继续分下去，直到最后如此继续分下去，直到最后N个长度为个长度为1的子序列的子序列。倒位序倒位序x(000)x(100)x(010)x(110)010101x(001)x(101)x(011)x(111)01010101x(n2n1n0)n2n1n0 N=8时的自然顺序二进制数和相应的倒位序二进制数时的自然顺序二进制数和相应的倒位序二进制数 自然顺序自然顺序（I） 二进制数二进制数 倒位序二进制数倒位序二进制数 倒位序倒位序（J） 0123456700000101001110010111011100010001011000110101111

23、104261537先按自然顺序将输入序列存入存储单元，先按自然顺序将输入序列存入存储单元， 为了得为了得到倒位序的排列，我们通过到倒位序的排列，我们通过变址运算变址运算来完成；来完成；如果输入序列的自然顺序号如果输入序列的自然顺序号I用二进制数（例如用二进制数（例如n2n1n0）表示）表示，则其倒位序则其倒位序J对应的二进制数就是对应的二进制数就是（n0n1n2），），这样，在原来自然顺序时应该放这样，在原来自然顺序时应该放x(I)的的单元，现在倒位序后应放单元，现在倒位序后应放x(J)。顺序数顺序数I的起始、终止值分别为的起始、终止值分别为1和和N-2；倒序数倒序数J J的起始值为的起始值为

24、N/2；为避免重复调换，只对为避免重复调换，只对IN L=M+N-1M1log231log2322MNMMMNKm短序列补很多零，长序列需全部输入后才能计算短序列补很多零，长序列需全部输入后才能计算存储容量大存储容量大运算时间长，处理延时很大，难于实时处理运算时间长，处理延时很大，难于实时处理怎么解决？怎么解决？块卷积（重叠相加和重叠保留法）块卷积（重叠相加和重叠保留法） 2 2重叠相加法重叠相加法 设设h(n)的点数为的点数为N，将，将x(n)分解为很多段，每段分解为很多段，每段为为m点，各段互不重叠，点，各段互不重叠，m和和N的数量级相同，用的数量级相同，用xi(n)表示表示x(n)的第的

25、第i段：段： 0)()(nxnxiimn(i+1)m-1 其他其他n i=0, 1, 0)()(iinxnx00iiiilnynhnxnhnxny)()()()()()(xi(n)为为m点，点，yi(n)为为（m+N-1）点；点；相邻两段输出序列必然有相邻两段输出序列必然有（N-1）个点发生重叠，个点发生重叠，即前一段的后即前一段的后（N-1）个点和后一段的前个点和后一段的前（N-1）个个点相重叠；点相重叠；将重叠部分相加再和不重叠的部分共同组成输出将重叠部分相加再和不重叠的部分共同组成输出。 特点：特点： x(n)x(n)分段各数据子段互不重叠；分段各数据子段互不重叠； h(n)h(n)与与

26、x xi i(n)(n)各子段所作为线性卷积得各子段所作为线性卷积得y yi i(n)(n)； y yi i(n)(n)数据间有数据间有N-1N-1点重叠；点重叠； 最后的卷积结果最后的卷积结果y(n)y(n)为各子段线性卷积为各子段线性卷积y yi i(n)(n) 之和。之和。 3 重叠保留法重叠保留法 将将x(n)分段，每段分段，每段L个点，序列中补零处不补零，而在每个点，序列中补零处不补零，而在每一段的前边补上前一段保留下来的（一段的前边补上前一段保留下来的（M-1）个输入序列值，）个输入序列值， 组成组成N=L+M-1点序列点序列xi(n)； 如果如果L+M-12m， 则可在每段序列末

27、端补零值点，补到则可在每段序列末端补零值点，补到长度为长度为2m； 用用DFT实现实现h(n)和和xi(n)的的N点圆周卷积，则其每段圆周卷点圆周卷积，则其每段圆周卷积结果的前（积结果的前（M-1）个点的值不等于线性卷积值，必须舍去。）个点的值不等于线性卷积值，必须舍去。 重叠保留法示意图重叠保留法示意图 nN 1M 2N 1LM 2L0 x0(n)x1(n)0nx2(n)N 1nLM 20(a)重叠保留法示意图重叠保留法示意图 y0(n)0M 2M 1N 1ny1(n)0M 1M 2N 1y2(n)M 2M 1N 1nn(b)用保留信号代替补零后的局部混叠现象用保留信号代替补零后的局部混叠现

28、象 mmm0h ( m )M 1N 1xi( m )0N 1N 1h (0m )NRN( m )n 00( a )( b )( c )用保留信号代替补零后的局部混叠现象用保留信号代替补零后的局部混叠现象 mmmnN 1h (M 2m)NRN( m)n M 2N 1h (M 1m)NRN( m)n M 1N 1h (N 1m)NRN( m)n N 1N 1M 2yi( n )0000( d )( e )( f )( g ) 为了说明以上说法的正确性，我们来看一看图为了说明以上说法的正确性，我们来看一看图3-29。任。任一段一段xi(n)（为（为N点）与点）与h(n)（原为（原为M点，补零值后也为点，补零值后也为N点）点）的的N点圆周卷积点圆周卷积 10)()()()()()(NmNNiiinRmnhmxnhnxnyN由于由于h(m)为为M点，补零后作点，补零后作N点圆周移位时，在点圆周移位时，在n=0,1,M-2的每一种情况下，的每一种情况下，h(n-m)NRN(m)在在0mN-1范围的末端出现范围的末端出现非零值，非零值， 而此处而此处xi(m)是有数值存在的，图是有数值存在的，图4-27（c），（），（d）为为n=0, n=M-2的情况，所以在的情况，所以在 0nM-