下载文档原格式
第四章快速付里叶变换(FFT) Fast Fourier Transforming第一节引言、快速付里叶变换FFT •有限反序列通过离散傅里叶变换(DFT)将其频域离散化成有限K序列•但其计算量太大(与N 的平方成正比)，很难实时地处理问题，因此引出了快速傅里叶变换(FFT)・•FFT并不是一种新的变换形式，它只是DFT的一种快速算法•并且根据对序列分解与选取方法的不同而产生了FFT的多种算法.•FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重耍应用・。
二、FFT产生故事当时加文(Garwin)在自已的研究中极需要一个计算付里叶变换的快速方法。
他注意到图基(J.W.Turkey)iE 在写有关付里叶变换的文章，因此详细询问了图基关于计算付里叶变换的技术知识。
图基概括地対加文介绍了一种方法，它实质上就是后来的著名的库利(Cooley J.W)图基算法。
在加文的迫切要求下，库利很快设计出一个计算机程序o 1965年库利-图基在v计算数学〉、Mathematic of Computation 杂志上发表了著乞的“机器计算付里级数的一种算法”文章，提出一种快速计算DFT的方法和计算机程序-揭开了FFT发展史上的第一页，促使FFT算法产牛原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件，使DFT的运算大简化了。
、本章主要内容•1 •立接计算DFT算法存在的问题及改进途径。
•2•多种DFT算法（时间抽取算法DIT算法，频率抽取算法DIF算法，线性调频Z变换即CZT 法）• 3.FFT的应用直接计算DFT算法存在的问题及改进逐径\直接计算DFT计算量•问题提出：设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT 运算，共需多大的运算工作量？1 •比较DFT与IDFT之间的运算量N—1x(n) DFT > X 伙)=工上=0,1,…N -1n=0N-\X伙)u)n > x(n) = Y X伙)A2 = 0,1,・・・ N -1 k=0其中x(n)为复数，W严之G"也为复数所以DFT与IDFT二者计算量相同。
快速傅立叶变换（FFT ）的实现一、实验目的在数字信号处理系统中，FFT 作为一个非常重要的工具经常使用，甚至成为DSP 运算能力的一个考核因素。
FFT 是一种高效实现离散付氏变换的算法。
离散付氏变换的目的是把信号由时域变换到频域，从而可以在频域分析处理信息，得到的结果再由付氏逆变换到时域。
本实验的目的在于学习FFT 算法，及其在TMS320C54X 上的实现，并通过编程掌握C54X 的存储器管理、辅助寄存器的使用、位倒序寻址方式等技巧，同时练习使用CCS 的探针和图形工具。
另外在BIOS 子目录下是一个使用DSP/BIOS 工具实现FFT 的程序。
通过该程序，你可以使用DSP/BIOS 提供的分析工具评估FFT 代码执行情况。
二、实验原理1）基 2 按时间抽取FFT 算法对于有限长离散数字信号{x[n]} ，0 ≤n ≤-1 N，其离散谱{x[k]} 可以由离散付氏变换（DFT）求得。
DFT 的定义为：X(k) x[n]e N k 0,1,...,N 1 n0可以方便的把它改写为如下形式：N1nkX(k) x[n]W n N k k 0,1,..., N 1n0不难看出，WN 是周期性的，且周期为N，即( n mN )(k lN ) nkm,l 0, 1, 2...W N W NWN 的周期性是DFT 的关键性质之一。
为了强调起见，常用表达式WN 取代W 以便明确其周期是N。
2) 实数FFT 运算对于离散傅立叶变换( DFT)的数字计算，FFT 是一种有效的方法。
一般假定输入序列是复数。
当实际输入是实数时，利用对称性质可以使计算DFT 非常有效。
一个优化的实数FFT 算法是一个组合以后的算法。
原始的2N 个点的实输入序列组合成一个N 点的复序列，之后对复序列进行N 点的FFT 运算，最后再由N 点的复数输出拆散成2N 点的复数序列，这2N点的复数序列与原始的2N点的实数输入序列的DFT 输出一致。
