文档介绍：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滤波器的设计问题在于寻求一系统函数,使其频率响应逼近滤波器要求的理想频率响应,其对应的单位脉冲响应。
设计思想:从时域从发,设计逼近理想。设理想滤波器的单位脉冲响应为。以低通线性相位FIR数字滤波器为例。
一般是无限长的,且是非因果的,不能直接作为FIR滤波器的单位脉冲响应。要想得到一个因果的有限长的滤波器h(n),最直接的方法是截断,即截取为有限长因果序列,并用合适的窗函数进行加权作为FIR滤波器的单位脉冲响应。按照线性相位滤波器的要求,h(n)必须是偶对称的。对称中心必须等于滤波器的延时常数,即
用矩形窗设计的FIR低通滤波器,所设计滤波器的幅度函数在通带和阻带都呈现出振荡现象,且最大波纹大约为幅度的9%,这个现象称为吉布斯(Gibbs)效应。为了消除吉布斯效应,一般采用其他类型的窗函数。
(1)矩形窗(Rectangle Window)
其频率响应和幅度响应分别为:
,
(2)三角形窗(Bartlett Window)
其频率响应为:
(3)汉宁(Hannin