DFT算法原理、FFT的算法原理

快速傅氏变换（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要求的理想频率响应Hd(ej)逼近滤波器

)，其对应的单位脉冲响应hd(n)。

1．用窗函数设计FIR滤波器的基本方法

设计思想：从时域从发，设计h(n)逼近理想hd(n)。设理想滤波器Hd(e冲响应为hd(n)。以低通线性相位FIR数字滤波器为例。

j)的单位脉

Hd(e)hd(n)12jnhd(n)ejn

dH(ej)ejndhd(n)一般是无限长的，且是非因果的，不能直接作为FIR滤波器的单位脉冲响应。

要想得到一个因果的有限长的滤波器h(n)，最直接的方法是截断h(n)hd(n)w(n)，即截取为有限长因果序列，并用合适的窗函数进行加权作为FIR滤波器的单位脉冲响应。按照线性相位滤波器的要求，h(n)必须是偶对称的。对称中心必须等于滤波器的延时常数，即

h(n)hd(n)w(n) a(N1)/2用矩形窗设计的FIR低通滤波器，所设计滤波器的幅度函数在通带和阻带都呈现出振荡现象，且最大波纹大约为幅度的9%，这个现象称为吉布斯（Gibbs）效应。为了消除吉布斯效应，一般采用其他类型的窗函数。

2．典型的窗函数

（1）矩形窗(Rectangle Window)

w(n)RN(n)

其频率响应和幅度响应分别为：

N12sin(N/2)jW(e)esin(/2)j，WR()sin(N/2)

sin(/2)（2）三角形窗(Bartlett Window)

2nN1,w(n)2n2,N1jN12

N1nN120n2sin(N/4)2jN21]e其频率响应为：W(e)[

Nsin(/2)（3）汉宁(Hanning)窗，又称升余弦窗

12nw(n)[1cos()]RN(n)

2N1其频率响应和幅度响应分别为：

j(22W(e){0.5WR()0.25[WR()WR()]}eN1N1W()eja22W()0.5WR()0.25[WR()WR()]N1N1jN1)2（4）汉明(Hamming)窗，又称改进的升余弦窗

w(n)[0.540.46cos(2nN1)]RN(n) 其幅度响应为：W()0.54W2R()0.23[WR(N1)W2R(N1)] （5）布莱克曼(Blankman)窗，又称二阶升余弦窗

w(n)[0.420.5cos(2nN1)0.08cos(4nN1)]RN(n) W()0.42W25[W22R()0.R()WR(其幅度响应为：N1N1)]0.04[W44

R(N1)WR(N1)]（6）凯泽(Kaiser)窗

w(n)I0(1[12n/(N1)]2)I(),0nN1

0其中：β是一个可选参数，用来选择主瓣宽度和旁瓣衰减之间的交换关系，一般说来，β越大，过渡带越宽，阻带越小衰减也越大。I0(·)是第一类修正零阶贝塞尔函数。

若阻带最小衰减表示为As20log10s，β的确定可采用下述经验公式：

0As210.5842(A4s21)0.0.07886(As21)21A50 s0.1102(As8.7)As50若滤波器通带和阻带波纹相等即δp=δs时，滤波器节数可通过下式确定：

NAs7.9514.36F1

式中：Fsp223．利用窗函数设计FIR滤波器的具体步骤如下：

（1）按允许的过渡带宽度△ω及阻带衰减AS，选择合适的窗函数，并估计节数N：其中A由窗函数的类型决定。

（2）由给定的滤波器的幅频响应参数求出理想的单位脉冲响应hd(n)。（3）确定延时值

（4）计算滤波器的单位取样响应h(n)，h(n)hd(n)w(n)。（5）验算技术指标是否满足要求。

IIR数字滤波器的原理和方法。

(1) 脉冲响应不变法

用数字滤波器的单位脉冲响应序列h(n)模仿模拟滤波器的冲激响应ha(t),让h(n)正好等于ha(t)的采样值，即 的Z变换(2)

双线性变换法

以低通数字滤波器为例，将设计步骤归纳如下：

确定数字滤波器的性能指标：通带临界频率fp、阻带临界频率fr；通带内的最大衰减Ap；阻带内的最小衰减Ar；采样周期T； 确定相应的数字角频率，ωp=2πfpT；ωr=2πfrT； 计算经过预畸的相应模拟低通原型的频率

根据Ωp和Ωr计算模拟低通原型滤波器的阶数N，并求得低通原型的传递函数Ha(s)；

用上面的双线性变换公式代入Ha(s)，求出所设计的传递函数H(z)； 分析滤波器特性，检查其指标是否满足要求

h(n)= ha(nT)

其中T为采样间隔，如果以Ha(S)及H(z)分别表示ha(t)的拉式变换及h(n)