基数为2的FFT算法

从上节所述，FFT算法快速的关键在于将原来傅氏矩阵分解为每一行仅含有两个非零项l与Wi的矩阵的乘积。下面用基数为2，即N=2n的情形讨论矩阵的分解过程.并主要按时间分解的情况讨论。

按时间分解的FFT算法

设N=2n，n为正整数。考虑输入序列x0(l)的DFT

物探数字信号分析与处理技术

将l与m用二进制表示

物探数字信号分析与处理技术

将(7-2-2)代入(7-2-1)中，得到

物探数字信号分析与处理技术

为了说明问题，我们取N=8，于是从(7-2-2)得到

物探数字信号分析与处理技术

从(7-2-4)和(7-2-3)得到

物探数字信号分析与处理技术

将(7-2-5)中的W的指数按时间l进行分解，有

物探数字信号分析与处理技术

因为

物探数字信号分析与处理技术

故从(7-2-6)得到

物探数字信号分析与处理技术

将上式代入(7-2-5)中得到

物探数字信号分析与处理技术

物探数字信号分析与处理技术

我们在公式(7-2-7)中由里往外求和，并置

物探数字信号分析与处理技术

于是得到

物探数字信号分析与处理技术

首先写出(7-2-8)的所有式子

物探数字信号分析与处理技术

将方程组(7-2-12)写成袜拿烂矩阵形式，得到

物探数字信号分析与处理技术

我们看到(7-2-13)中的方阵，正好是(7-1-13)中的方阵，也就是(7-1-12)中被分解出来的第3个矩阵，只不过这里的x1(l)与x0(l)中的l是用二进制数表示而已。

再写出(7-2-9)的所有式子，得到

物探数字信号分析与处理技术

将方程组写成矩阵形式，则有

物探数字信号分析与处理技术

显然(7-2-15)中的矩阵，正好是(7-1-14)中的方阵，也就是(7-1-12)中被分解出来的第二个矩阵，只不过这里的x2(l)与x1(l)是用二进制数表示而已，最后将(7-2-10)中的全部式子写出，得到

物探数字信告漏号分析与处理技术

将方程组(7-2-16)写成矩阵形式，则有

物探数字信号分析与处理技术

显然，(7-2-17)中的方阵正是(7-1-15)中的方阵，也就是(7-1-12)中被分解出来的第1个矩阵，只不过这里的x3(l)与x2(l)中的l是用二进制数表示。

由此可见，(7-2-7)中由里往外的三个求和式(7-2-8)、(7-2-9)及(7-2-10)，完全确定了(7-1-12)中三个被分解的矩阵因子。求和得到的最终结果x3(m0，m1，m2)，与我们所要求的X(m2，m1，m0)正好是逆序的。

到此为止，我们就看到(7-1-11)中的方阵是怎样被分解成三个方阵因子的。对于N=8，方程(7-2-8)～(7-2-11)就是计算DFT的FFT算法。为了对FFT算法有一个直观的了解并便于编制程序，我们以N=8为例，画出其流程图(图7-2-1)。

根据(7-2-13)，将其中的W4用-W0代替，画出从x0(r)到x1(r)的流程图。这一迭代过程用符号#1表示再根据(7-2-15)，将其中的与W4、W6分别换成-W0与-W2，画出从x1(r)到x2(r)的流程图，这一迭代过程记为#2最后，根据(7-2-17)，将其中的W4、W6、W5、W7分别换成-W0、-W2、-W1、-W3，画出流程图7-2-3合并图7-2-1～7-2-3，就得到从x0(r)到x3(r)的完整流程图7-2-4。

图7-2-1 第一次递推

图7-2-2 第二次递推

在图7-2-5中，画出N=16=24的FFT算法流程图:

根据从x0到谱X的FFT算法流程图7-2-4与图7-2-5，我们总结出如下几点:

(1)从x0到终值xr的最大迭代次数r，由r=log2N确定。

例如，N=8，最大迭代次数r=3N=16，最大迭代次数r=4。

(2)在第r次迭代中，要乘的W因子为

图7-2-3 第三次递推

例如，N=8，在第一次迭代中，要乘因子W0在第二次迭代中要乘因子W0，W1，W2，W3。

(3)在第r次迭代中，包含2r-1个组，每个组

包含 。例如N=8，第一次迭代r=1，有

一个组，每组包含8个x(s)在第二次迭代中包含2个组，每组包含4个x(s)第三次迭代中包含4个组，每组2个x(s)。

图7-2-4 x0(r)到x3(r)的完整流程图

(4)在第r次迭代中，各组包含的W因子各不相同，且每一组仅包含一种类型的因子 ，此因子在组中一半数为正，另一半数为负。例如N=8，第二次迭代中，第一组包含因子W0，且在该组中一半数为正敏宴，另一半数为负第二组包含因子W2，在该组中也是一半数为正，另一半数为负。

(5)在第r次迭代中，各组包含的W因子除正负号外类型均相同。所以只须确定每组中第一个因子，之后按半数反号，即得到所求W因子。具体做法是，在每组第一个因子WSN2r对应的xr(k)中，将k表示成n位的二进制数，n=log2N，并把这个二进制数右移n-r位，左边空出的地方添零补足n位，之后再将此n位二进制数逆位，即得到所求W因子的指数。例如，N=8，迭代#2包含两组，每组包含4个x2(k)，第二组第一个因子W对应于x2(4)。将4表示成3位的二进制数为100，把它右移1位成10，右边添零补成3位为010，逆位仍为010，故所求因子为W2，第2组全部W因子为W2，W2，-W2，-W2。又如，N=16，迭代#3中包含4个组，每组包含4个x3(k)，第4组第1个因子W对应于x3(12)。将12表示成4位的二进制数为1100。右移1位变成110，将左边空处添零补成4位为0110，逆位仍为0110，故所求因子为W6，从而第4组全部W因子为W6，W6，-W6与-W6。

图7-2-5 N=16=24的FFT算法流程图

(6)如果已知N=2的FFT算法，容易从它求得n=2的FFT算法。具体作法是，在n=2n-1的FFT算法中，将所有xr(l)的个数加倍，所有W的个数及其乘幂加倍，就得N=2n中前n-1次迭代的全部结果。之后，将新得到的第n-1次迭代中乘幂相同的W个数减半，就是第n次迭代中前2n/2个W，将这些W的乘幂依次加1，就得到后2n/2个W。例如N=16的前3次迭代，都是N=8的三次迭代中所有xr(l)的个数加倍，W的个数及其乘幂加倍的结果。再将N=16的第三次迭代中乘幂相同的W个数减半，就是第4次迭代中前8个W。

(7)在第r-1次迭代中的xr-1(i)与xr-1(j)仅用于计算r次迭代中的xr(i)与xr(j)，而不会用于计算任何其它的xr(k)与xr(l)。例如N=16的第二次迭代中的x2(0)与x2(2)，只用于计算第三次迭代中的x3(0)与x3(2)第三次迭代中的x3(8)与x3(9)也只用于计算第四次迭代中的x4(8)与x4(9)。因此，我们可以把第r次迭代中的xr(i)与xr(j)，存放到r-1次迭代xr-1(i)与xr-1(j)所占用的原存储单元中去，这样，所需要的计算机存储容量就只限于原数据序列占据的单元数。如果是复序列的话，存储单元要加倍。

(8)上述FFT算法也可用于计算逆离散傅氏变换(IDFT)(图7-2-6)，只不过在计算时要将上述FFT算法中的W因子用其共轭W*代替，并将最后迭代计算的结果统统乘以1/N.

图7-2-6 N=8的逆离散富氏变换流程图

sintcost=1/2sin2t

F(1/2sin2t)

=∫(-∞，+∞) 1/2sin2t · e^-jwt dt

用氏神欧拉公式可得原式=

1/2∫(-∞，+∞则胡) j/2( e^-2jt - e^2jt )e^-jwt dt

=j/4∫(-∞，+∞) e^-j(w+2)t - e^-j(w-2)t dt

用δ函数的傅氏变换 得原式=

j/2 π[δ(w+2)-δ(w-2)]

欧拉公式: sin2t=j/2 (e^-2jt - e^2jt)

δ函数的傅氏变换:

F(e^jw。t)=∫(-∞，+∞) e^j(w。-w)t dt =2πδ(w。-w)

扩展资料：

傅歼盯亏氏变换的意义

傅里叶原理表明：任何连续测量的时序或信号，都可以表示为不同频率的正弦波信号的无限叠加。

而根据该原理创立的傅里叶变换算法利用直接测量到的原始信号，以累加方式来计算该信号中不同正弦波信号的频率、振幅和相位。

和傅里叶变换算法对应的是反傅里叶变换算法。该反变换从本质上说也是一种累加处理，这样就可以将单独改变的正弦波信号转换成一个信号。

因此，可以说，傅里叶变换将原来难以处理的时域信号转换成了易于分析的频域信号（信号的频谱），可以利用一些工具对这些频域信号进行处理、加工。最后还可以利用傅里叶反变换将这些频域信号转换成时域信号。

参考资料来源：百度百科-傅里叶变换

---