文档介绍：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 表示当前倒序数的十进制数值) 实验原理与方法 FIR 滤波器 FIR 滤波器的设计问题在于寻求一系统函数)(zH ,使其频率响应)( ?jeH 逼近滤波器要求的理想频率响应)( ?jdeH , 其对应的单位脉冲响应)(nh d 。 1 .用窗函数设计 FIR 滤波器的基本方法设计思想:从时域从发,设计)(nh 逼近理想)(nh d 。设理想滤波器)( ?jdeH 的单位脉冲响应为)(nh d 。以低通线性相位 FIR 数字滤波器为例。?????????????????? deeHnh enheH jnjdd jn n d jd)(2 1)( )()()(nh d 一般是无限长的,且是非因果的, 不能直接作为 FIR 滤波器的单位脉冲响应。要想得到一个因果的有限长的滤波器 h(n) , 最直接的方法是截断)()()(nwnhnh d?,即截取为有限长因果序列,并用合适的窗函数进行加权作为 FIR 滤波器的单位脉冲响应。按照线性相位滤波器的要求, h(n) 必须是偶对称的。对称