离散傅里叶变换的矩阵表示及其运算量PPT讲稿.ppt

《离散傅里叶变换的矩阵表示及其运算量PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《离散傅里叶变换的矩阵表示及其运算量PPT讲稿.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散傅里叶变换的矩阵表示及其运算量第1页，共50页，编辑于2022年，星期日n离散傅里叶变换对为：离散傅里叶变换对为：(4.1)(4.2)n式中式中 。下面要用矩阵来表示下面要用矩阵来表示DFT关系。关系。第2页，共50页，编辑于2022年，星期日n 一般情况下，信号序列一般情况下，信号序列x(n)及其频谱序列及其频谱序列X(k)都是用复数来表示都是用复数来表示的，的，WN当然也是复数。因此，计算当然也是复数。因此，计算DFT的一个值的一个值X(k)需要进行需要进行N次次复数乘法（与复数乘法（与1相乘也包括在内）和相乘也包括在内）和N-1次复数加法；所以，直接次复数加法；所以，直接计算计算N点

2、的点的DFT需要进行需要进行N2 次复数乘法和次复数乘法和N(N-1)复数加法。复数加法。第3页，共50页，编辑于2022年，星期日n显显然然，直直接接计计算算N点点的的IDFT所所需需的的复复乘乘和和复复加加的的次次数数也也是是这这么么多多。当当N足足够够大大时时，N2 N(N-1),因因此此，DFT与与IDFT的的运运算算次次数数与与N2 成成正正比比，随随着着N的的增增加加，运运算算量量将将急急剧剧增增加加，而而在在实实际际问问题题中中，N往往是较大的，因此有必要对往往是较大的，因此有必要对DFT与与IDFT的计算方法予以改进。的计算方法予以改进。第4页，共50页，编辑于2022年，星期

3、日 4.1.2 因子的特性因子的特性n DFT和和IDFT的快速算法的导出主要是根据的快速算法的导出主要是根据 因子的特性。因子的特性。1周期性：周期性：n对离散变量对离散变量n有同样的周期性。有同样的周期性。第5页，共50页，编辑于2022年，星期日 2对称性：对称性：n或或 3.其它其它:第6页，共50页，编辑于2022年，星期日4.2 4.2 基基2 2时间抽选的时间抽选的FFTFFT算法算法 4.2.1 算法推导算法推导n 已经知道：已经知道：n令令DFT的长度的长度N=2M，M为正整数。为正整数。第7页，共50页，编辑于2022年，星期日n令：令：n于是有：于是有：第8页，共50页，

4、编辑于2022年，星期日n其中，其中，n是由是由x(n)的偶数抽样点形成的的偶数抽样点形成的DFT；而；而 第9页，共50页，编辑于2022年，星期日n是是由由x(n)的的奇奇数数抽抽样样点点形形成成的的DFT。但但是是这这两两个个式式子子并并不不完完全全是是N/2点点的的DFT，因因为为k的的范范围围仍仍然然是是由由0到到N-1，因因此此，还还应应该该进进一一步步考考虑虑k由由N/2到到N-1范围的情况。范围的情况。第10页，共50页，编辑于2022年，星期日n现在令现在令 ，故对于后半段有：，故对于后半段有：n同理：同理：n又知：又知：第11页，共50页，编辑于2022年，星期日 图图 4

5、.1 N点点DFT分解为两个分解为两个N/2点的点的DFT(N=8)第12页，共50页，编辑于2022年，星期日 图图 4.2 N/2 点的点的DFT 分解为两个分解为两个N/4点的点的DFT(N=8)第13页，共50页，编辑于2022年，星期日n综上所述，可以得到：综上所述，可以得到：n其中其中G(k)、P(k)分别是分别是x(n)的偶数点和奇数点的的偶数点和奇数点的N/2点点DFT。第14页，共50页，编辑于2022年，星期日n 这这样样，我我们们就就将将一一个个N点点的的DFT分分解解成成了了两两个个N/2点点的的DFT，由由于于DFT的的运运算算量量与与其其点点数数的的平平方方成成正正

6、比比，因因此此使使运运算算量量减减少少了了。但但是是，还还应应该该将将每每一一个个N/2点点的的DFT再再分分解解为为两两个个N/4点点的的DFT，如如此此下下去去，直直到到分解为分解为2点的点的DFT为止，总共需要进行为止，总共需要进行loglog2 2N-1=logN-1=log2 2(N/2)(N/2)次分解。次分解。第15页，共50页，编辑于2022年，星期日图图 4.3 2 点点 DFT 信号流图（蝶形图）信号流图（蝶形图）第16页，共50页，编辑于2022年，星期日n对于对于2点点DFT，有：，有：n所所以以2点点DFT的的运运算算只只需需一一次次加加法法和和一一次次减减法法，这这

7、样样的的运运算算叫叫做做蝶蝶形运算，这样的信号流图叫做蝶形图。形运算，这样的信号流图叫做蝶形图。第17页，共50页，编辑于2022年，星期日n该该算算法法每每次次分分解解都都是是将将时时域域序序列列按按奇奇偶偶分分为为两两组组，因因此此要要求求N等等于于2的正整数幂，故将这种的正整数幂，故将这种FFT算法叫做基算法叫做基2时间抽选法。时间抽选法。第18页，共50页，编辑于2022年，星期日 4.2.2 算法特点算法特点 1.倒序重排倒序重排n这种这种FFT算法的每次分解都是将输入序列按照奇偶分为两组，故要不断算法的每次分解都是将输入序列按照奇偶分为两组，故要不断地将每组输入数据按奇偶重排，直到

8、最后分解为地将每组输入数据按奇偶重排，直到最后分解为2点的点的DFT，输入数据，输入数据才不再改变顺序。这样做的结果，使得作才不再改变顺序。这样做的结果，使得作FFT运算时，输入序列的运算时，输入序列的次序要按其序号的倒序进行重新排列。次序要按其序号的倒序进行重新排列。第19页，共50页，编辑于2022年，星期日n现现在在将将图图4.4中中输输入入序序号号以以及及重重排排后后的的序序号号按按二二进进制制写写出出如如下下（注注：下下标标“2”表表示示二二进进制制数数）。可可以以看看出出，将将输输入入序序号号的的二二进进制制表表示示（n2n1n0）位位置置颠颠倒倒，得得到到（n0n1n2），就就是

9、是相相应应的的倒倒序序的的二二进进制制序序号号。因因此此，输输入入序序列列按按倒倒序序重重排排，实实际际上上就就是是将将序序号号为为（n2n1n0）的元素与序号为（）的元素与序号为（n0n1n2）的元素的位置相互交换。）的元素的位置相互交换。第20页，共50页，编辑于2022年，星期日第21页，共50页，编辑于2022年，星期日 2.同址计算同址计算 n 从图从图4.4可以看出，整个算法流图可以分为四段，（可以看出，整个算法流图可以分为四段，（0）段为倒序）段为倒序重排，后面重排，后面3段为段为3(log28=3)次迭代运算：首先计算次迭代运算：首先计算2点点DFT，然后，然后将将2点点DFT

10、的结果组合成的结果组合成4点点DFT，最后将，最后将4点点DFT组合为组合为8点点DFT。因。因此，对于此，对于N点点FFT，只需要一列存储，只需要一列存储N个复数的存储器。个复数的存储器。第22页，共50页，编辑于2022年，星期日 3.运算量运算量n观观察察图图4.4可可知知，图图4.3所所示示的的蝶蝶形形图图实实际际上上代代表表了了FFT的的基基本本运运算算，它它实实际际上上只只包包含含了了两两次次复复数数加加法法运运算算。一一个个N(N=2M)点点的的FFT，需需要要进进行行M=log2N次次迭迭代代运运算算。每每次次迭迭代代运运算算包包含含了了N/2个个蝶蝶型型，因因此此共共有有N次

11、次复复数数加加法法；此此外外，除除了了第第一一次次的的2点点DFT之之外外，每每次次迭迭代代还还包包括括了了N/2次次复复数数乘乘法法（即即乘乘WN的的幂幂）。因因此此，一一个个N点点的的FFT共有复数乘法的次数为：共有复数乘法的次数为：第23页，共50页，编辑于2022年，星期日 n复数加法的次数为：复数加法的次数为：n因此，因此，FFT算法比直接计算算法比直接计算DFT大大减少了运算量，尤其是当大大减少了运算量，尤其是当N较较大时，计算量的减少更为显著。比如，当大时，计算量的减少更为显著。比如，当N=1024时，采用时，采用FFT算法算法时复数乘法的次数，不超过直接计算时复数乘法的次数，不

12、超过直接计算DFT时复乘次数的千分之五。时复乘次数的千分之五。第24页，共50页，编辑于2022年，星期日4.3 4.3 基基2 2频率抽选的频率抽选的FFTFFT算法算法n 时间抽选法是在时域内将输入序列时间抽选法是在时域内将输入序列x(n)逐次分解为偶数点子序列和奇逐次分解为偶数点子序列和奇数点子序列，通过求子序列的数点子序列，通过求子序列的DFT而实现整个序列的而实现整个序列的DFT。而频率。而频率抽选法则是在频域内将抽选法则是在频域内将X(k)逐次分解成偶数点子序列和奇数点子逐次分解成偶数点子序列和奇数点子序列，然后对这些分解得越来越短的子序列进行序列，然后对这些分解得越来越短的子序列

13、进行DFT运算，从而求运算，从而求得整个的得整个的DFT。当然，同样要求。当然，同样要求N为为2的正整数幂。的正整数幂。第25页，共50页，编辑于2022年，星期日n 设设 ，则可以分别表示出，则可以分别表示出k为偶数和奇数时的为偶数和奇数时的X(k)。n其中，其中，第26页，共50页，编辑于2022年，星期日第27页，共50页，编辑于2022年，星期日n其中，其中，n 显显然然，X(2r)为为g(n)的的N/2点点DFT，X(2r+1)为为p(n)WNn 的的N/2点点DFT。这这样样，一一个个N点点的的DFT分分解解为为两两个个N/2点点的的DFT。将将分分解解继继续续下下去去，直直到到分

14、分解解为为2点点的的DFT为为止止。当当N=8时时，基基2频频率率抽抽选选的的FFT算法的整个信号流图如图算法的整个信号流图如图4.6所示。所示。第28页，共50页，编辑于2022年，星期日n将将图图4.6与与图图4.4比比较较，可可知知频频率率抽抽选选法法的的计计算算量量与与时时间间抽抽选选法法相相同同，而而且且都都能能够够同同址址计计算算。时时间间抽抽选选法法是是输输入入序序列列按按奇奇偶偶分分组组，故故x(n)的的顺顺序序要要按按倒倒序序重重排排，而而输输出出序序列列按按前前后后分分半半，故故X(k)的的顺顺序序不不需需要要重重排排；频频率率抽抽选选法法则则是是输输出出序序列列按按奇奇偶

15、偶分分组组，故故X(k)的的顺顺序序要要按按倒倒序序重重排，而输入序列按前后分半，故排，而输入序列按前后分半，故x(n)不需要重排。不需要重排。第29页，共50页，编辑于2022年，星期日 4.5 4.5 快速傅里叶反变换（快速傅里叶反变换（IFFTIFFT）nIFFT是是IDFT的的快快速速算算法法。由由于于DFT的的正正变变换换和和反反变变换换的的表表达达式式相相似似，因因此此IDFT也也有有相相似似的的快快速速算算法法。可可以以用用三三种种不不同同的的方方法法来来导导出出IFFT算法。算法。n方法方法1n 设设 ，则则有有：，n=0,1,N-1n=0,1,N-1第30页，共50页，编辑于

16、2022年，星期日n根据基根据基2 FFT的时间抽选法的第一次分解的结果：的时间抽选法的第一次分解的结果：第31页，共50页，编辑于2022年，星期日n可以得到：可以得到：第32页，共50页，编辑于2022年，星期日 图图 4.8 由由 X(k)、X(k+N/2)得到得到 G(k)、P(k)第33页，共50页，编辑于2022年，星期日n再再由由N/2点点的的DFT求求得得N/4点点的的DFT，依依次次类类推推下下去去，就就可可推推到到求求出出x(n)的的各各点点，如如图图4.9所所示示。将将此此流流图图与与图图4.4比比较较，相相当当于于整整个个流流向向反反过过来来，此此外外，因因子子WNk成

17、成为为WN-k-k，还还增增加加了了因因子子1/2。但但是是，图图4.9的的IFFT算算法法不不能能直直接接利利用用按按照照图图4.4编编写写的的FFT算算法法程程序序，却却可可以以利利用用图图4.6的的频频率率抽抽选选FFT算算法法的的程程序序，只只需需要要将将X(k)作作为为输输入入序序列列，因因子子WNk变变为为WN-k-k，并并且且将将最最后后所所得得的的输输出出序序列列的的每每个个元元素素都都除除以以N。第34页，共50页，编辑于2022年，星期日n方法方法2n 将将DFT的正变换式：的正变换式：n与其反变换式：与其反变换式：第35页，共50页，编辑于2022年，星期日n比比较较，很

18、很容容易易知知道道，可可以以利利用用FFT算算法法的的程程序序来来计计算算IFFT，只只需需要要将将X(k)作作为为输输入入序序列列，x(n)则则是是输输出出序序列列，另另外外将将因因子子WNk 变变为为WN-k-k，当当然然，最最后后还还必必须须将输出序列的每个元素除以将输出序列的每个元素除以N。第36页，共50页，编辑于2022年，星期日n 方法方法3n 对对DFT的反变换式取共轭，有：的反变换式取共轭，有：第37页，共50页，编辑于2022年，星期日n与与DFT的的正正变变换换式式比比较较，可可知知完完全全可可以以利利用用FFT的的计计算算程程序序，只只需需要要将将X*(k)作作为为输输

19、入入序序列列，并并将将最最后后结结果果取取共共轭，再除以轭，再除以N就得到就得到x(n)。第38页，共50页，编辑于2022年，星期日4.7.1 两个长度相同的实序列两个长度相同的实序列n 可可以以将将两两个个长长度度相相同同的的实实序序列列组组合合成成一一个个复复序序列列来来进进行行FFT运运算算，从而一次完成这两个实序列的从而一次完成这两个实序列的FFT，减少了总的计算量。，减少了总的计算量。第39页，共50页，编辑于2022年，星期日n 设设p(n)和和g(n)是两个长度均为是两个长度均为N的实序列，并设：的实序列，并设：n又设又设 n ，n则由则由DFT的线性有：的线性有：(4.36)

20、第40页，共50页，编辑于2022年，星期日nP(k)和和G(k)这这两两个个复复序序列列的的实实部部都都是是周周期期性性的的偶偶序序列列，而而其其虚虚部都是周期性的奇序列。部都是周期性的奇序列。n 对复序列对复序列Y(k)又有又有 (4.37)n这这里里下下标标 r、i 分分别别表表示示实实部部和和虚虚部部，Y(k)与与其其实实部部、虚虚部部的的长长度度都为都为 N。现将。现将(4.37)式中各序列作周期延拓，有式中各序列作周期延拓，有 (4.38)(4.38)第41页，共50页，编辑于2022年，星期日n由周期性有：由周期性有：(4.39)(4.40)第42页，共50页，编辑于2022年，

21、星期日n现在将序列现在将序列 与与 作如下分解：作如下分解：(4.41)(4.42)第43页，共50页，编辑于2022年，星期日n 由由（4.394.39）式式和和（4.404.40）式式，容容易易证证明明在在(4.41)(4.41)和和(4.42)(4.42)这这两两个个式式子中，前一项都是偶序列，而后一项都是奇序列。子中，前一项都是偶序列，而后一项都是奇序列。n 将将（4.414.41）式式和和（4.424.42）式式代代入入（4.384.38）式式，并并将将各各项项进进行行重重新组合，得到：新组合，得到：第44页，共50页，编辑于2022年，星期日第45页，共50页，编辑于2022年，星

22、期日n令令0kN-10kN-1，则上式为：，则上式为：n这这里里的的P P(k)(k)和和G G(k)(k)的的实实部部都都是是周周期期性性偶偶序序列列，而而它它们们的的虚虚部部都都是是周周期期性性奇奇序序列列，此此情情况况与与（4.364.36）式式中中的的复复序序列列P(k)P(k)和和G(k)G(k)的情况相同。因此有：的情况相同。因此有：第46页，共50页，编辑于2022年，星期日 n上两式中上两式中0kN-10kN-1。第47页，共50页，编辑于2022年，星期日 4.7.2 4.7.2 一个一个2N2N点的实序列点的实序列 n 将将一一个个2N2N点点的的实实序序列列x(n)x(n

23、)按按偶偶数数点点和和奇奇数数点点分分组组形形成成两两个个N N点实序列：点实序列：第48页，共50页，编辑于2022年，星期日n则有：则有：n k=0,1,N-1 (4.48)k=0,1,N-1 (4.48)第49页，共50页，编辑于2022年，星期日n其中：其中：n实实序序列列p(n)p(n)和和g(n)g(n)的的DFT DFT P(k)P(k)和和G(k)G(k)可可以以采采用用4.7.14.7.1节节所所说说的的方方法法作作一一次次N N点点复复序序列列的的FFTFFT而而同同时时得得到到，然然后后再再按按（4.484.48）式式进进行行组组合便得到了合便得到了2N2N点实序列点实序列x(n)x(n)的的DFTDFT。第50页，共50页，编辑于2022年，星期日