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

将图4.6与图4.4比较，可知频率抽选法的计算量与时间抽选法相同，而且都能够同址计算。时间抽选法是输入序列按奇偶分组，故x(n)的顺序要按倒序重排，而输出序列按前后分半，故X(k)的顺序不需要重排；频率抽选法则是输出序列按奇偶分组，故X(k)的顺序要按倒序重排，而输入序列按前后分半，故x(n)不需要重排。4.5快速傅里叶反变换（IFFT）IFFT是IDFT的快速算法。由于DFT的正变换和反变换的表达式相似，因此IDFT也有相似的快速算法。可以用三种不同的方法来导出IFFT算法。方法1设，则有：，n=0,1,┅,N-1根据基2FFT的时间抽选法的第一次分解的结果：可以得到：图4.8由X(k)、X(k+N/2)得到G(k)、P(k)再由N/2点的DFT求得N/4点的DFT，依次类推下去，就可推到求出x(n)的各点，如图4.9所示。将此流图与图4.4比较，相当于整个流向反过来，此外，因子WNk成为WN-k，还增加了因子1/2。但是，图4.9的IFFT算法不能直接利用按照图4.4编写的FFT算法程序，却可以利用图4.6的频率抽选FFT算法的程序，只需要将X(k)作为输入序列，因子WNk变为WN-k，并且将最后所得的输出序列的每个元素都除以N。ABC将DFT的正变换式：与其反变换式：方法2比较，很容易知道，可以利用FFT算法的程序来计算IFFT，只需要将X(k)作为输入序列，x(n)则是输出序列，另外将因子WNk变为WN-k，当然，最后还必须将输出序列的每个元素除以N。第4章FFT引言离散傅里叶变换的矩阵表示及其运算量DFT在数字信号处理中起着非常重要的作用，这是与DFT存在着高效算法，即快速傅里叶变换(FFT)分不开的。快速运算的关键是减少运算量。离散傅里叶变换对为：(4.1)(4.2)1式中。下面要用矩阵来表示DFT关系。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因子的特性DFT和IDFT的快速算法的导出主要是根据因子的特性。周期性： 对离散变量n有同样的周期性。对称性： 或 其它: 基2时间抽选的FFT算法01算法推导已经知道：令DFT的长度N=2M，M为正整数。02STEP01STEP02令：于是有：其中， 01是由x(n)的偶数抽样点形成的DFT；而02是由x(n)的奇数抽样点形成的DFT。但是这两个式子并不完全是N/2点的DFT，因为k的范围仍然是由0到N-1，因此，还应该进一步考虑k由N/2到N-1范围的情况。现在令，故对于后半段有：同理：又知：图4.1N点DFT分解为两个N/2点的DFT(N=8)图4.2N/2点的DFT分解为两个N/4点的DFT(N=8)综上所述，可以得到： 01其中G(k)、P(k)分别是x(n)的偶数点和奇数点的N/2点DFT。02这样，我们就将一个N点的DFT分解成了两个N/2点的DFT，由于DFT的运算量与其点数的平方成正比，因此使运算量减少了。但是，还应该将每一个N/2点的DFT再分解为两个N/4点的DFT，如此下去，直到分解为2点的DFT为止，总共需要进行log2N-1=log2(N/2)次分解。图4.32点DFT信号流图（蝶形图）对于2点DFT，有：所以