数字信号处理4人文科技

《数字信号处理4人文科技》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章FFT4.1引言4.1.1离散傅里叶变换的矩阵表示及其运算量DFT在数字信号处理中起着非常重要的作用，这是与DFT存在着高效算法，即快速傅里叶变换(FFT)分不开的。快速运算的关键是减少运算量。离散傅里叶变换对为：(4.1)(4.2)式中。下面要用矩阵来表示DFT关系。令：并令TN、表示两个变换方阵，有：如果用i(0≤i≤N-1)表示这两个N阶方阵的行号，用j(0≤j≤N-1)表示这两个N阶方阵的列号，那末很容易看出，TN方阵中i行j列的元素为，而方阵中i行j列的元素为。于是（4.1）式可以写成：而（4.2）式可以写成

2、：一般情况下，信号序列x(n)及其频谱序列X(k)都是用复数来表示的，WN当然也是复数。因此，计算DFT的一个值X(k)需要进行N次复数乘法（与1相乘也包括在内）和N-1次复数加法；所以，直接计算N点的DFT需要进行N2次复数乘法和N(N-1)复数加法。显然，直接计算N点的IDFT所需的复乘和复加的次数也是这么多。当N足够大时，N2≈N(N-1),因此，DFT与IDFT的运算次数与N2成正比，随着N的增加，运算量将急剧增加，而在实际问题中，N往往是较大的，因此有必要对DFT与IDFT的计算方法予以改进。4.1.2因子的特性D

3、FT和IDFT的快速算法的导出主要是根据因子的特性。1．周期性：对离散变量n有同样的周期性。2．对称性：或3.其它:4.2基2时间抽选的FFT算法4.2.1算法推导已经知道：令DFT的长度N=2M，M为正整数。令：于是有：其中，是由x(n)的偶数抽样点形成的DFT；而是由x(n)的奇数抽样点形成的DFT。但是这两个式子并不完全是N/2点的DFT，因为k的范围仍然是由0到N-1，因此，还应该进一步考虑k由N/2到N-1范围的情况。现在令，故对于后半段有：同理：又知：图4.1N点DFT分解为两个N/2点的DFT(N=8)图4.2

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

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

6、1n0）位置颠倒，得到（n0n1n2），就是相应的倒序的二进制序号。因此，输入序列按倒序重排，实际上就是将序号为（n2n1n0）的元素与序号为（n0n1n2）的元素的位置相互交换。2.同址计算从图4.4可以看出，整个算法流图可以分为四段，（0）段为倒序重排，后面3段为3(log28=3)次迭代运算：首先计算2点DFT，然后将2点DFT的结果组合成4点DFT，最后将4点DFT组合为8点DFT。因此，对于N点FFT，只需要一列存储N个复数的存储器。开始时，输入序列的N个数放于此N个存储器内，倒序重排后仍存于这N个存储器中，每一次

7、迭代运算后的结果也仍然存于这N个存储器中，整个运算完成后，这N个存储器中即为所求的频谱序列X(k)（k=0、1、…..、N-1）。这就是所谓的同址计算，这样可以大大节约存储元件。3.运算量观察图4.4可知，图4.3所示的蝶形图实际上代表了FFT的基本运算，它实际上只包含了两次复数加法运算。一个N(N=2M)点的FFT，需要进行M=log2N次迭代运算。每次迭代运算包含了N/2个蝶型，因此共有N次复数加法；此外，除了第一次的2点DFT之外，每次迭代还包括了N/2次复数乘法（即乘WN的幂）。因此，一个N点的FFT共有复数乘法的次

8、数为：复数加法的次数为：因此，FFT算法比直接计算DFT大大减少了运算量，尤其是当N较大时，计算量的减少更为显著。比如，当N=1024时，采用FFT算法时复数乘法的次数，不超过直接计算DFT时复乘次数的千分之五。4.2.3关于FFT算法的计算机程序在一般情况下，进行FFT运算的序列至少都有