快速傅立叶变换算法-DSP实验

下载后可任意编辑快速傅立叶变换(FFT)算法实验摘要：FFT（Fast Fourier Transformation），即为快速傅里叶变换，是离散傅里叶变换的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。这种算法大大减少了变换中的运算量，使得其在数字信号处理中有了广泛的运用。本实验主要要求掌握在 CCS 环境下用窗函数法设计 FFT 快速傅里叶的原理和方法；并且熟悉 FFT 快速傅里叶特性；以及通过本次试验了解各种窗函数对快速傅里叶特性的影响等。引言：快速傅里叶变换 FFT 是离散傅里叶变换 DFT 的一种快速算法。起初 DFT 的计算在数字信号处理中就非常有用，但由于计算量太大，即使采纳计算机也很难对问题进行实时处理，所以并没有得到真正的运用。1965 年 J.W.库利和 T.W.图基提出快速傅里叶变换，采纳这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少,特别是被变换的抽样点数 N 越多,FFT 算法计算量的节约就越显著。从此，对快速傅里叶变换（FFT）算法的讨论便不断深化，数字信号处理这门新兴学科也随 FFT 的出现和进展而迅速进展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算法，基本算法是基下载后可任意编辑2DIT 和基 2DIF。FFT 的出现，使信号分析从时域分析向频域分析成为可能，极大地推动了信号分析在各领域的实际应用。FFT 在离散傅里叶反变换、线性卷积和 线性相关 等方面也有重要应用。一、 实验原理：FFT 并不是一种新的变换，它是离散傅立叶变换（DFT）的一种快速算法。由于我们在计算 DFT 时一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法则需二次实数加法。每运算一个X（k）需要 4N 次复数乘法及 2N+2（N-1）=2（2N-1）次实数加法。所以整个 DFT 运算总共需要 4N^2 次实数乘法和 N*2(2N-1)=2N(2N-1)次实数加法。如此一来，计算时乘法次数和加法次数都是和 N^2 成正比的，当 N 很大时，运算量是可观的，因而需要改进对 DFT 的算法减少运算速度。根据傅立叶变换的对称性和周期性，我们可以将 DFT 运算中有些项合并。我们先设序列长度为 N=2^L，L 为整数。将 N=2^L 的序列x(n)(n=0,1,……，N-1)，按 N 的奇偶分成两组，也就是说我们将一个 N点的 DFT 分解成两个 N/2 点的 DFT，他们又从新组合成一个如下式所表达的 N 点 DFT：下载后可任意编辑其中，，设 x(n）为 N 项的复数序列，由 D...