文档介绍：《数字信号处理》课程论文离散傅里叶变换( DFT) 算法简介及其应用举例姓名:安昱学号: ********** 专业:通信工程班级: 2011 级( 1 )班指导老师:武永峰学院:物理电气信息学院完成日期: 2013 年 11月 11日离散傅里叶变换( DFT) 算法简介及其应用举例(安昱 ********** 2011 级1 班) [摘要]: 离散傅立叶变换( DFT )实现了信号首次在频域表示的离散化,使得频域也能够用计算机进行处理。并且这种 DFT 变换可以有多种实用的快速算法。使信号处理在时、频域的处理和转换均可离散化和快速化。最后就该项目做了总结。[ 关键词]DFT 算法 Matlab 语言频域采样 DFT 应用一、 DFT 算法原理快速傅氏变换( FFT )是离散傅氏变换的快速算法,它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现,但是对于在计算机系统或者说数字系统中应用离散傅立叶变换,可以说是进了一大步。设x(n) 为N 项的复数序列,由 DFT 变换,任一 X(m )的计算都需要 N 次复数乘法和 N-1 次复数加法,而一次复数乘法等于四次实数乘法和两次实数加法,一次复数加法等于两次实数加法,即使把一次复数乘法和一次复数加法定义成一次“运算”(四次实数乘法和四次实数加法),那么求出 N项复数序列的 X(m), 即N点DFT 变换大约就需要 N2 次运算。当 N=1024 点甚至更多的时候,需要 N2=1048576 次运算,在FFT 中,利用 WN的周期性和对称性,把一个 N项序列(设 N=2k,k 为正整数),分为两个 N/2 项的子序列,每个 N/2 点DFT 变换需要(N/2 ) 2次运算,再用 N次运算把两个 N/2 点的 DFT 变换组合成一个 N点的 DFT 变换。这样变换以后,总的运算次数就变成 N+2 (N/2 )2=N+N2/2 。继续上面的例子, N=1024 时,总的运算次数就变成了 525312 次,节省了大约 50% 的运算量。而如果我们将这种“一分为二”的思想不断进行下去,直到分成两两一组的 DFT 运算单元,那么 N点的 DFT 变换就只需要 Nlog2N 次的运算,N在1024 点时,运算量仅有 10240 次,是先前的直接算法的 1% ,点数越多,运算量的节约就越大,这就是 FFT 的优越性。二、 FFT 的算法原理 FFT 算法的输出 X(K) 为自然顺序,但为了适应原位计算,其输入序列不是按 x(n) 的自然顺序排序,这种经过 M-1 次奇偶抽选后的排序为序列的倒序。因此, 在运算之前应先对序列 x(n) 进行倒序。倒序的规律就是把顺序数的二进制位倒置,即可得到倒序值。倒序数是在 M位二进制数最高位加一,逢 2向右进位。 M 位二进制数最高位的权值为 N/2 ,且从左到右二进制位的权值依次为你 N/4 , N/8 ,…,2,1 。因此,最高位加一相当于十进制运算 J+N/2 。(J 表示当前倒序数的十进制数值) 三、 DFT 的定义设序列 x(n) 长度为 M,定义 x(n) 的N点DFT 为1,..., 1,0,)( )]([)( 210???????? Nkenxnx DFT kX knN j Nn N ?式中, N称为离散