傅里叶变换

傅里叶变换（Fourier transform）是一种线性积分变换，用于信号在时域和频域之间的变换。而快速傅里叶变换（Fast Fourier Transform，FFT）, 是一种可在O（nlogn）时间内完成离散傅里叶变换（Discrete Fourier transform，DFT）的高效、快速计算方法集的统称。最初的快速傅里叶变换方法早在1805年就已由高斯推导出来，并于1965年由Cooley和Tukey重新提出，并渐渐被大众所熟知。从此，对快速傅里叶变换（FFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法。

简单的说，傅里叶变换就是信号展开为一系列三角函数的和。因为三角函数是周期对称函数，所以展开也就是把对称性进行分解。一般来说对称性分为奇对称性（f(x)=-f(-x) ；即中心对称）和偶对称性（f(x)=f(-x)；即轴对称）。经过傅里叶变换，奇对称性的分量构成了傅里叶变换的虚部，而偶对称性的部分就构成了变换后的实部。