第4章快速傅里叶变换(FFT)

knNW NN第四章 快速傅里叶变换有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT ）的快 速算法，将 DFT 的运算量减少了几个数量级。

从此，对快速傅里叶变换（FFT ） 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。

根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基２DIT 和基２DIF 。

FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。

快速傅里叶变换（FFT ）是计算离散傅里叶变换（DFT ）的快速算法。

DFT 的定义式为N −1X (k ) = ∑ x (n )W NR N (k )n =0在所有复指数值 W kn 的值全部已算好的情况下，要计算一个 X (k ) 需要 N 次复数乘法和 N －1 次复数加法。

算出全部 N 点 X (k ) 共需 N 2次复数乘法和 N ( N − 1) 次复数加法。

即计算量是与 N 2 成正比的。

FFT 的基本思想：将大点数的 DFT 分解为若干个小点数 DFT 的组合， 从而减少运算量。

W N 因子具有以下两个特性，可使 DFT 运算量尽量分解为小点数的 DFT运算：（1） 周期性：( k + N ) nN= W kn= W ( n + N ) k（2） 对称性：W( k + N / 2 )= −WkN N利用这两个性质，可以使 DFT 运算中有些项合并，以减少乘法次数。

例子： 求当 N ＝4 时，X(2)的值4 N N N3∑44444X (2) = n =0x (n )W 2 n = x (0)W 0 + x (1)W 2 + x (2)W 4 + x (3)W 6= [ x (0) + x (2)]W 0 + [ x (1) + x (3)]W 2(周期性)4＝[ x (0) + x (2)]－[ x (1) + x (3)]W 04(对称性)通过合并，使乘法次数由 4 次减少到 1 次，运算量减少。

⽂中内容均为个⼈理解，如有错误请指出，不胜感激前⾔先解释⼏个⽐较容易混淆的缩写吧FMT 快速莫⽐乌斯变化—>感谢stump提供多项式复数在介绍复数之前，⾸先介绍⼀些可能会⽤到的东西(好像画的不是很标准。

)设$a,b$为实数，$i^2=-1$，形如$a+bi$的数叫复数，其中$i$被称为虚数单位，复数域是⽬前已知最⼤的域在复平⾯中，$x$代表实数，$y$轴（除原点外的点）代表虚数，从原点$(0,0)$到$(a,b)$的向量表⽰复数$a+bi$模长：从原点$(0,0)$到点$(a,b)$的距离，即$\sqrt{a^2+b^2}$幅⾓：假设以逆时针为正⽅向，从$x$轴正半轴到已知向量的转⾓的有向⾓叫做幅⾓运算法则加法：因为在复平⾯中，复数可以被表⽰为向量，因此复数的加法与向量的加法相同，都满⾜平⾏四边形定则（就是上⾯那个）乘法：⼏何定义：复数相乘，模长相乘，幅⾓相加代数定义：$$(a+bi)*(c+di)$$$$=ac+adi+bci+bdi^2$$$$=ac+adi+bci-bd$$$$=(ac-bd)+(bc+ad)i$$单位根下⽂中，默认$n$为$2$的正整数次幂在复平⾯上，以原点为圆⼼，$1$为半径作圆，所得的圆叫单位圆。

以圆点为起点，圆的$n$等分点为终点，做$n$个向量，设幅⾓为正且最⼩的向量对应的复数为$\omega_n$，称为$n$次单位根。

根据复数乘法的运算法则，其余$n-1$个复数为$\omega_n^2,\omega_n^3,\ldots,\omega_n^n$注意$\omega_n^0=\omega_n^n=1$（对应复平⾯上以$x$轴为正⽅向的向量）那么如何计算它们的值呢？这个问题可以由欧拉公式解决$$\omega_{n}^{k}=\cos\ k *\frac{2\pi}{n}+i\sin k*\frac{2\pi}{n}$$例如图中向量$AB$表⽰的复数为$8$次单位根单位根的幅⾓为周⾓的$\frac{1}{n}$在代数中，若$z^n=1$，我们把$z$称为$n$次单位根单位根的性质$\omega _{n}^{k}=\cos k\dfrac{2\pi}{n}+i\sin k\dfrac {2\pi }{n}$（即上⾯的公式）$\omega _{2n}^{2k}=\omega _{n}^{k}$证明：$$\omega _{2n}^{2k}=\cos 2k*\frac{2\pi}{2n}+i\sin2k*\frac{2\pi}{2n}$$$$=\omega _{n}^{k}$$$\omega _{n}^{k+\frac{n}{2}}=-\omega _{n}^{k}$$$\omega _{n}^{\frac{n}{2}}=\cos\frac{n}{2}*\frac{2\pi}{n}+i\sin\frac{n}{2}*\frac{2\pi}{n}$$$$=\cos \pi+i\sin\pi$$$$=-1$$$\omega _{n}^{0}=\omega _{n}^{n}=1$讲了这么多，貌似跟我们的正题没啥关系啊。

快速傅⾥叶变换（FFT）其实很早就想学习⼀下 FFT 了，不过⽐赛的时候和 FFT 有关的题⽬我都交给了队友，所以也没什么动⼒学- -今天看到 Gilbert Strang 的线性代数书中竟然也介绍了 FFT，就顺便学习了⼀下。

FFT 解决的问题我们知道，⼀个 $n-1$ 次多项式可以这样表⽰：$$\sum_{k=0}^{n-1}a_kx^k$$ 这种表⽰⽅法称为多项式的“系数表⽰法”。

容易看出，只要确定了 $a_0,a_1,\dots,a_{n-1}$ 的值，就能唯⼀确定⼀个 $n-1$ 次多项式。

事实上，⼀个 $n-1$ 次多项式还可以⽤“点值表⽰法”进⾏表⽰。

我们把多项式看成函数 $f(x)$，只要给出 $n$ 个点 $(x_1,f(x_1)),(x_2,f(x_2)),\dots,(x_n,f(x_n))$，且这 $n$ 个点的 x 值互不相同，我们也能唯⼀确定⼀个 $n-1$ 次多项式。

确定这个多项式的过程称为“插值”。

为什么 $n$ 个点可以唯⼀确定多项式呢？我们可以把给出的 $n$ 个点看作⼀个⽅程组，⽤矩阵表⽰为 $$\begin{bmatrix}1 & x_1 & x_1^2 & \dots & x_1^n \\ 1 & x_2 & x_2^2 & \dots & x_2^n \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & x_n & x_n^2 & \dots &x_n^n\end{bmatrix} \begin{bmatrix}a_0 \\ a_1 \\ \vdots \\ a_{n-1}\end{bmatrix} = \begin{bmatrix}f(x_1) \\ f(x_2) \\ \vdots \\ f(x_n)\end{bmatrix}$$简记为 $Xa = f$，根据线性代数的知识我们知道，矩阵 $X$ 是范德蒙矩阵，其⾏列式为 $$\prod_{i\ne j}(x_i-x_j)$$ 显然，只要 x 的值各不相等，该矩阵的⾏列式就不为 0，说明该矩阵可逆，则我们能唯⼀确定多项式的系数向量为 $a = X^{-1}f$。

快速傅里叶变换FFT的C语言算法彻底研究LED音乐频谱显示的核心算法就是快速傅里叶变换，FFT的理解和编程还是比较难的，特地撰写此文分享一下研究成果。

一、彻底理解傅里叶变换快速傅里叶变换（Fast Fourier Transform)是离散傅里叶变换的一种快速算法，简称FFT，通过FFT可以将一个信号从时域变换到频域。

模拟信号经过A/D转换变为数字信号的过程称为采样。

为保证采样后信号的频谱形状不失真，采样频率必须大于信号中最高频率成分的2倍，这称之为采样定理。

假设采样频率为fs，采样点数为N，那么FFT结果就是一个N点的复数，每一个点就对应着一个频率点，某一点n(n 从1开始)表示的频率为：fn=(n-1)*fs/N。

举例说明：用1kHz的采样频率采样128点，则FFT结果的128个数据即对应的频率点分别是0，1k/128，2k/128，3k/128，…，127k/128 Hz。

这个频率点的幅值为：该点复数的模值除以N/2（n=1时是直流分量，其幅值是该点的模值除以N）。

二、傅里叶变换的C语言编程1、对于快速傅里叶变换FFT，第一个要解决的问题就是码位倒序。

假设一个N 点的输入序列，那么它的序号二进制数位数就是t=log2N.码位倒序要解决两个问题：①将t位二进制数倒序；②将倒序后的两个存储单元进行交换。

如果输入序列的自然顺序号i用二进制数表示，例如若最大序号为15，即用4位就可表示n3n2n1n0，则其倒序后j对应的二进制数就是n0n1n2n3，那么怎样才能实现倒序呢？利用C语言的移位功能！程序如下，我不多说，看不懂者智商一定在180以下！复数类型定义及其运算#define N 64 //64点#define log2N 6 //log2N=6/*复数类型*/typedef struct{float real;float img;}complex;complex xdata x[N]; //输入序列/*复数加法*/complex add(complex a,complex b){complex c;c.real=a.real+b.real;c.img=a.img+b.img;return c;}/*复数减法*/complex sub(complex a,complex b){complex c;c.real=a.real-b.real;c.img=a.img-b.img;return c;}/*复数乘法*/complex mul(complex a,complex b){complex c;c.real=a.real*b.real - a.img*b.img;c.img=a.real*b.img + a.img*b.real;return c;}/***码位倒序函数***/void Reverse(void){unsigned int i,j,k;unsigned int t;complex temp;//临时交换变量for(i=0;i<N;i++)//从第0个序号到第N-1个序号{k=i;//当前第i个序号j=0;//存储倒序后的序号，先初始化为0for(t=0;t<log2N;t++)//共移位t次，其中log2N是事先宏定义算好的{j<<=1;j|=(k&1);//j左移一位然后加上k的最低位k>>=1;//k右移一位，次低位变为最低位}if(j>i)//如果倒序后大于原序数，就将两个存储单元进行交换（判断j>i是为了防止重复交换）{temp=x[i];x[i]=x[j];x[j]=temp;}}}2、第二个要解决的问题就是蝶形运算①第1级（第1列）每个蝶形的两节点“距离”为1，第2级每个蝶形的两节点“距离”为2，第3级每个蝶形的两节点“距离”为4，第4级每个蝶形的两节点“距离”为8。

FFT 程序设计报告快速傅里叶变换法（FFT ）是离散傅立叶变换的一种快速计算方法，它能使N 点DFT 的乘法计算量由N 2次降为N N2log 2次。

下图是采样点数为8点FFT 时间抽取算法信号流图，本程序也是以这种形式设计的。

程序设计的基本思路是在程序开始时刻要求输入采样点数，如果采样点数是2的整数次方（不包括0次方），则要求输入采样点的数值，并根据采样点数分配响应的数组大小，计算迭代次数。

然后对采样点进行逆二进制排序，再按上图所示的算法进行计算，程序流程图如下图所示：本程序运用VC 语言对程序进行设计，下面分别对程序设计中复数类的应用，判断和求迭代次数，逆二进制排序，蝶形运算进行具体说明。

1． 复数类的应用C 语言本身并不包含复数数据类型，但C 语言可以根据需要定义自己的数据类型，本程序定义了一个复数结构体complex ，包括实部real 和虚部img 两部分，代码如下： typedef struct { double real; double img; }complex;在FFT 程序设计中，复数类主要被用来计算两复数的加法和乘法以及旋转因子Wk N，其中Nj NW/2π-=，式中N=2的m+1次方，m 代表计算流图的第m 级，而k 代表第k 次蝶形运算，由于C 中的math.h 函数库中没有带参数的复数运算函数，所以本程序编写了带参数的复数运算cw(double x,double y)，用于计算Nj NW/2π-=，设计的基本思路，首先把e 的次幂用欧拉公式化成三角函数，然后化复数乘法和除法运算为几个复数基本单元的加法运算和除法运算，其中运算的次数由函数输入参量double x 决定。

函数mul(complex x1, complex x2)用于计算复数的乘运算。

2． 判断和求迭代次数本程序编写iternumb(int numb)函数对采样点数进行判断，如果采样点数不符合2的整数次方或采样点数为1或0，则跳出程序，程序设计基本思路是对输入采样点数的十进制形式进行模2运算和除法运算，在除法运算结果大于1之前，一旦模2运算的结果等于1，则说明输入采样点数不符合要求，而如果符合要求，则把出发结果存入数组当中，函数代码如下：int iternumb(int numb) {int iternumb1=0;if((numb==0)||(numb==1)) {printf("numb error!\n"); exit(0); }while ((numb!=0)&&(numb!=1)) {if (numb%2) {printf("numb error!\n"); exit(0); }numb=numb/2;iternumb1=iternumb1+1; }return iternumb1; }3． 码位倒置在逆二进制排序程序中，设置for 循环分别将输入数据数组input[i]的索引号i 进行模2运算，所得的结果按逆序存入inverse[ ]数组（存入inverse[ ]数组的顺序是从数组尾部开始）。