离散傅里叶变换的矩阵表示及其运算量.doc

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

1、离散傅里叶变换的矩阵表示及其运算量 导读：就爱阅读网友为您分享以下“离散傅里叶变换的矩阵表示及其运算量资讯，希望对您有所帮助，感谢您对92to 的支持!第4章4.1 引言FFT4.1.1 离散傅里叶变换的矩阵表示及其运算量nDFT在数字信号处理中起着非常重要的作用， 这是与DFT 存在着高效算法， 即快速傅里叶变换(FFT) 分不开的。快速运算的关键是减少运算量。n离散傅里叶变换对为：DFT : X (k ) = x(n )W Nn =0 N -1 nk, k = 0,1, L N - 1 (4.1)n1 N -1 (4.2) - nk IDFT : x (n ) = X (k )W N ,

2、n = 0,1, L N - 1 N k =0 2p -j 式中 。 下面要用矩阵来表示DFT关系。 WN = e Nn一般情况下，信号序列x(n) 及其频谱序列X(k) 都是用复数来表示的，WN当然也是复数。因此，计算DFT的一个值X(k)需要进行N次复数乘法与1相乘也包括在内和N-1次复数 加法；所以，直接计算N点的DFT需要进行N2 次复数乘法和 N(N-1) 复数加法。n显然，直接计算N点的IDFT所需的复乘和复加的次数也是这 么多。当N足够大时，N2 N(N-1), 因此，DFT与IDFT的运 算次数与N2 成正比，随着N的增加，运算量将急剧增加，而 在实际问题中，N往往是较大的，因

3、此有必要对DFT与IDFT 的计算方法予以改良。4.1.2nWnk因子的特性 NDFT和IDFT的快速算法的导出主要是根据性。 1周期性：因子的特 W NnknkWNn(k +N )= WNnk WNnN= WNn对离散变量n有同样的周期性。2对称性：nW = Wnk * N- nk N= WN(-n)k= WN( N -n) k或 3. 其它:W = Wnk * NN ) 2- kn N= WNN 2 N-j(-k )n= WN-j 2p N N 2( N -k ) nWN(k +k = WN W2p - j 2 k Nk = WN e2p k N 2k = -WN2 WN k = e=e=

4、 W Nk24.2基2时间抽选的FFT算法4.2.1 算法推导nN -1 已经知道： nk X (k ) = DFT x(n) = x(n)WN n =0k = 0,1, L, N - 1n令DFT的长度N=2M，M为正整数。ng ( r ) = x ( 2r ) 令： 于是有：N -1 2 r =0 N -1 2 r =0 p(r ) = x(2r + 1)N r = 0,1, L, - 1 2n2 ( k X (k ) = x(2r )WN rk + x(2r + 1)WN2 r +1) k = g (r )WN rk2 + WN p(r )WN rk2 / / r =0 r =0 k =

5、 G (k ) + WN P(k )N -1 2N -1 2k = 0,1, L, N - 1n其中，G(k ) = g (r )WN r/ k = x(2r )WN r/ k 2 2r =0 r =0N -1 2N -1 2P(k ) = p(n)WN r/ k = x(2r + 1)WN r/ k 2 2r =0 r =0N -1 2N -1 2n是由x(n)的偶数抽样点形成的DFT；而n是由x(n)的奇数抽样点形成的DFT。但是这两个式子并不完 全是N/2点的DFT，因为k的范围仍然是由0到N-1，因此，还 应该进一步考虑k由N/2到N-1范围的情况。n现在令 k = 0,1, L, N

6、 - 1，故对于后半段有：2N G (k + ) = g (r )W 2 r =0N -1 2 r =0N -1 2N r (k + ) 2 N /2= g (r )W Nr =02N -1 2rN 2W N2rk= g (r )W Nr k = G (k )2n同理：N P(k + ) = P(k ) 2n又知：WNk+N 2= -WNk图 4.1 N点DFT分解为两个N/2点的DFT (N=8)图 4.2 N/2 点的DFT 分解为两个N/4点的DFT (N=8)n综上所述，可以得到：k X (k ) = G (k ) + W N P(k ) N k = 0,1,L, - 1 N k 2

7、X (k + 2 ) = G (k ) - W N P(k ) 其中G(k)、P(k) 分别是x(n)的偶数点和奇数点的N/2点DFT。nn这样，我们就将一个N点的DFT分解成了两个N/2点的DFT，由于DFT的运算量与其点数的平方成正比，因此使运算量减少了。但是，还应该将每一个N/2点的DFT再分解为两个N/4点的DFT，如此下去，直到分解为2点的DFT为止，总共需要进行log2N-1=log2(N/2)次分解。图 4.3 2 点 DFT 信号流图蝶形图nn1 1 1 1 对于2点DFT，有： T = 2 1 W 1 = 1 - 1 2 所以2点DFT的运算只需一次加法和一次减法，这样的运算

8、叫做蝶形运算，这样的信号流图叫做蝶形图。n该算法每次分解都是将时域序列按奇偶分为两组，因此要求N等于2的正整数幂，故将这种FFT算法叫做基2时间抽选法。4.2.2 算法特点1. 倒序重排n这种FFT算法的每次分解都是将输入序列按照奇偶分为两组，故要不断地将每组输入数据按奇偶重排，直到最后分解为2 点的DFT，输入数据才不再改变顺序。这样做的结果，使得 作FFT运算时，输入序列的次序要按其序号的倒序进行重新 排列。n现在将图4.4中输入序号以及重排后的序号按二进制写出如下注：下标“2表示二进制数。可以看出，将输入序号的二进制表示n2n 1n0 位置颠倒，得到n0 n1n2 ，就是相应的倒序的二进

9、制序号。因此，输入序列按倒序重排，实际上就是将序号为n2 n1n0 的元素与序号为n 0n1n2的元素的位置相互交换。2. 同址计算n从图4.4可以看出，整个算法流图可以分为四段，0段 为倒序重排，后面3段为3(log28=3)次迭代运算：首先计算2 点DFT，然后将2点DFT的结果组合成4点DFT，最后将4点 DFT组合为8点DFT。因此，对于N点FFT，只需要一列存储N个复数的存储器。3. 运算量n观察图4.4可知，图4.3所示的蝶形图实际上代表了FFT的基本运算，它实际上只包含了两次复数加法运算。一个N(N=2M) 点的FFT，需要进行M=log2N次迭代运算。每次迭 代运算包含了N/2

10、个蝶型，因此共有N次复数加法；此外，除 了第一次的2点DFT之外，每次迭代还包括了N/2次复数乘法 即乘WN的幂。因此，一个N点的FFT共有复数乘法的次 数为：M c2nN N N = (log 2 N - 1) = log 2 2 2 2c2复数加法的次数为： AN = 2 log 2 N = N log 2 N 2n因此，FFT算法比直接计算DFT大大减少了运算量，尤其是当N较大时，计算量的减少更为显著。比方，当N=1024时，采用FFT算法时复数乘法的次数，不超过直接计算DFT时复乘次数的千分之五。4.3n基2频率抽选的FFT算法时间抽选法是在时域内将输入序列x(n)逐次分解为偶数点子序

11、列和奇数点子序列，通过求子序列的DFT而实现整个序列的DFT。而频率抽选法那么是在频域内将X(k)逐次分解成偶 数点子序列和奇数点子序列，然后对这些分解得越来越短的 子序列进行DFT运算，从而求得整个的DFT。当然，同样要 求N为2的正整数幂。nN 设 r = 0,1, L , - 1 ，那么可以分别表示出k为偶数和奇数时 2的X(k)。X ( 2r ) = x( n)W Nn =0 N -1 2 rn= x(n)Wn =0 N -1 2 n =0N -1 22 nr NN N 2( n+ ) r 2 + x( n + )W N 2 n =0N -1 2=n x(n)WN n/ 2r + x(

12、n +n =0N -1 2N rN r )W N n 2 W N = / 2 g (n)Wn =0N -1 2nr N /2其中，N g ( n ) = x ( n) + x ( n + ) 2N n = 0, ,L , - 1 1 2N ( 2 r +1)( n + 2 ) n 2 nr X (2r + 1) = x(n)W N W N + x(n + )W N 2 n =0 n =0 N = x(n)W Nn/ r2 W Nn + x(n + )W N2 nr W Nn W NrN W N2 2 n =0 n =0 = x(n)W N n/ 2r W Nn + x(n +n =0 n =0

13、 N -1 2 N -1 2 N -1 2 N -1 2 NN -1 2N -1 2NN )W N n/ 2r WNn (-1) = p(n)W Nn W N n/ 2r 2 n =0N -1 2n其中， p(n) = x(n) - x(n +N ) 2n = 0, ,L , 1N -1 2n显然，X(2r) 为g(n) 的N/2点DFT，X(2r+1) 为p(n)WNn 的 N/2点DFT。这样，一个N点的DFT分解为两个N/2点的DFT。 将分解继续下去，直到分解为2点的DFT为止。当N=8时， 基2频率抽选的FFT算法的整个信号流图如图4.6所示。n将图4.6与图4.4比拟，可知频率抽选

14、法的计算量与时间抽选 法相同，而且都能够同址计算。时间抽选法是输入序列按奇 偶分组，故x(n)的顺序要按倒序重排，而输出序列按前后分 半，故X(k) 的顺序不需要重排；频率抽选法那么是输出序列按 奇偶分组，故X(k) 的顺序要按倒序重排，而输入序列按前后分半，故x(n) 不需要重排。4.5n快速傅里叶反变换IFFTIFFT是IDFT的快速算法。由于DFT的正变换和反变换的表达式相似，因此IDFT也有相似的快速算法。可以用三种不同的方法来导出IFFT算法。n方法1 设nx(n) X (k ) DFT， 那么有：n=0,1,N-11 x(n ) = N X (k )Wk =0N -1- nk N，

15、n根据基2 FFT的时间抽选法的第一次分解的结果：k X (k ) = G (k ) + W N P(k ) N k X (k + ) = G (k ) - W N P(k ) 2 N k = 0,1, L , - 1 2n可以得到：1 N G(k ) = X (k ) + X (k + ) N 2 2 k = 0,1, L , - 1 1 -k N 2 P(k ) = WN X (k ) - X (k + ) 2 2 图 4.8 由 X(k)、X(k+N/2) 得到 G(k)、P(k)n再由N/2点的DFT求得N/4点的DFT，依次类推下去，就可推到求出x(n)的各点，如图4.9所示。将此流

16、图与图4.4比拟，相当于整个流向反过来，此外，因子WNk成为WN-k，还增加了 因子1/2。但是，图4.9的IFFT算法不能直接利用按照图4.4编 写的FFT算法程序，却可以利用图4.6的频率抽选FFT算法的 程序，只需要将X(k)作为输入序列，因子WNk变为WN-k，并 且将最后所得的输出序列的每个元素都除以N。n方法2 将DFT的正变换式： X ( k ) =n x(n)WNn =0N -1nkn与其反变换式： x ( n ) = 1N X (k )WNk =0N -1- nkn比拟，很容易知道，可以利用FFT算法的程序来计算IFFT，只需要将X(k) 作为输入序列，x(n) 那么 是输出

17、序列，另外将因子WNk 变为WN-k， 当然， 最后还必须将输出序列的每个元素除以N。n方法3 对DFT的反变换式取共轭，有：1 N -1 1 N -1 * - nk * nk x ( n ) = X ( k )W N = X (k )W N , n = 0,1, L, N - 1 N k =0 N k =0*nn与DFT的正变换式比拟，可知完全可以利用FFT 的计算程序，只需要将X*(k) 作为输入序列，并将 最后结果取共轭，再除以N就得到x(n)。4.7.1 两个长度相同的实序列n可以将两个长度相同的实序列组合成一个复序列来进行FFT运算，从而一次完成这两个实序列的FFT，减少了总的计算量

18、。n设p(n) 和g(n) 是两个长度均为N的实序列，并设：y(n) = p(n) + jg (n)n又设DFT y (n) Y (k ) p(n) P(k ) ， g (n) G(k ) ， DFTDFTnn那么由DFT的线性有： Y (k ) = P(k ) + jG (k )(4.36)nP(k) 和G(k) 这两个复序列的实部都是周期性的偶序列，而 其虚部都是周期性的奇序列。n对复序列Y(k) 又有 Y (k ) = Y (k ) + jY (k ) r i(4.37)n这里下标 r、i 分别表示实部和虚部，Y(k) 与其实部、虚部 的长度都为 N。现将 (4.37) 式中各序列作周期

19、延拓，有 Y (k ) = Yr (k ) + jYi (k )( 4.3 8)n由周期性有： Yr (k ) = Yr ( N + k ), Yr ( -k ) = Yr ( N - k )(4.39) (4.40) Yi (k ) = Yi ( N + k ), Yi ( -k ) = Yi ( N - k )n现在将序列 Yr( k ) 与 Yi ( k ) 作如下分解：(4.41)1 1 Yr (k ) = Yr (k ) + Yr ( N - k ) + Yr (k ) - Yr ( N - k ) 2 21 1 Yi (k ) = Yi (k ) + Yi ( N - k ) +

20、Yi (k ) - Yi ( N - k ) 2 2(4.42)n由4.39式和4.40式，容易证明在(4.41)和(4.42) 这两个式子中，前一项都是偶序列，而后一项都是奇序列。n将4.41式和4.42式代入4.38式，并将各项 进行重新组合，得到：1 1 Y (k ) = Yr (k ) + Yr ( N - k ) + j Yi (k ) - Yi ( N - k ) 2 2 1 1 + j Yi (k ) + Yi ( N - k ) - j Yr (k ) - Yr ( N - k ) 2 2 = P ( k ) + jG ( k )n令0kN-1，那么上式为：Y (k ) = P

21、 (k ) + jG (k ) = P(k ) + jG (k ) 这里的P(k) 和G(k) 的实部都是周期性偶序列，而它 们的虚部都是周期性奇序列，此情况与4.36式中的复n序列P(k)和G(k)的情况相同。因此有：1 1 P(k ) = P (k ) = Yr (k ) + Yr ( N - k ) N ) + j Yi (k ) - Yi ( N - k ) N ) 2 21 1 G(k ) = G (k ) = Yi (k ) + Yi ( N - k ) N ) - j Yr (k ) - Yr ( N - k ) N ) 2 2n上两式中0kN-1。4.7.2n一个2N点的实序列

22、 将一个2N点的实序列x(n)按偶数点和奇数点分组形成两个N点实序列： p ( n) = x ( 2n) g (n) = x(2n + 1)n = 0,1, L, N - 1n那么有： X (k ) = P (k ) + W2 k G (k ) k=0,1,N-1 N X ( k + N ) = P ( k ) - W2 k G ( k ) N n(4.48)n其中：nk nk P (k ) = p (n)W N G (k ) = g (n)WNN -1 n =0N -1 n =0k = 0,1,L, N - 1n实序列p(n) 和g(n) 的DFT P(k) 和G(k) 可以采用4.7.1节 所说的方法作一次N点复序列的FFT而同时得到，然后再按 4.48式进行组合便得到了2N点实序列x(n) 的DFT。百度搜索“就爱阅读,专业资料,生活学习,尽在就爱阅读网92to ,您的在线图书馆