DFT算法原理、FFT的算法原理文.pdfVIP

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 滤波器 j FIR 滤波器的设计问题在于寻求一系统函数 H ( z) ，使其频率响应 H (e ) 逼近滤波器 要求的理想频率响应 H d (e j ) ，其对应的单位脉冲响应 hd (n) 。 1．用窗函数设计 FIR 滤波器的基本方法 设计思想：从时域从发，设计 h(n) 逼近理想 hd ( n) 。设理想滤波器 H d (ej ) 的单位脉 冲响应为 hd ( n) 。以低通线性相位 FIR 数字滤波器为例。 j jn H d (e ) hd (n)e n 1 j jn hd (n) H d (e )e