第二章数字信号处理的基本算法ppt.ppt

DSP原理与实训指导 第二章 数字信号处理的基本算法 2.1　数字信号处理的一般程序 2.2　傅立叶变换的四种形式 2.2　傅立叶变换的四种形式 设f(t)是周期为T的连续时间函数，展开成傅立叶级数后的系数为F(jkΩ0)，则由f(t)求取F(jkΩ0)的正变换为： 2.6.2　频域抽取法FFT 2.6　基-2FFT算法 上式第二项表示成： 将n-N/2用n取代，有 2.6.2　频域抽取法FFT 2.6　基-2FFT算法 则F(k)为： 又： 2.4　离散傅立叶变换的运算特征 Fe(k)=DFT[fr(n)] Fo(k)=DFT[fi(n)] e：共轭偶部 o：共轭奇部 f(n)=fr(n)+jfi(n) r：实部 i：虚部 共轭对称性 也为奇（偶）对称序列 f(n)为奇（偶）对称序列 奇偶对称性 f(n)、x(n) 线性 f(n) 周期性 傅立叶变换表示 信号序列 性质 a、b为常数 r=0,±1,±2,… f(n) Parseval （巴塞菲尔）定理 f(n) y(n)=f(n)h(n) 频移特性 卷积特性 f(n+n0) 时移特性 2.4　离散傅立叶变换的运算特征 2.5　DFT的快速算法—快速傅立叶变换FFT 2.5.1　FFT的种类 按照离散时间序列是输入有序还是输出有序，FFT算法可分为时域抽取法(Decimation In Time FFT)和频域抽取法(Decimation In Frequency FFT)两种，前者简称DIT-FFT，后者简称DIF-FFT。 把输入有限长离散时间序列划分成两个子序列分别计算的FFT算法，称为基-2FFT算法，（或“基2FFT算法”）。把输入有限长离散时间序列划分成4个子序列分别计算的FFT算法，称为基-4FFT算法，（或“基4FFT算法”）。 2.5　DFT的快速算法—快速傅立叶变换FFT 2.5.2　FFT算法设计思路 设f(n)是长度为N的有限长序列，它的离散傅立叶变换DFT为： 对于所有F(k) 的N个值，运算的总次数为N2次复数乘法和N×（N-1）次复数加法。 减少运算量的有效做法是将N个点的DFT分成几个较短的DFT分头计算，例如等份成M个，每一个短的DFT长度只有N/M。 2.5　DFT的快速算法—快速傅立叶变换FFT 2.5.2　FFT算法设计思路 计算F(k)总的运算工作量为： 与不等分成M时的计算相比，总的工作量下降了1/M。 如果把每一个短的DFT继续分解成P个更短序列的DFT，计算的工作量将又下降1/P，继续等分下去再计算，结果将使离散傅立叶变换进行得更快，能使DFT的运算速度提高几个数量级。 此外，利用的周期性质、对称性质及一些特殊值还能进一步加快运算速度。 利用分解长序列的DFT、的性质快速实现DFT运算的算法被称为快速傅立叶变换(Fast Fourier Transform，FFT)算法。 2.5　DFT的快速算法—快速傅立叶变换FFT 2.5.2　FFT算法设计思路 将序列f(n)不断分成2个的这种FFT算法称为基-2FFT算法。 将序列f(n)不断分成4个的这种FFT算法称为基-4FFT算法。 2.6　基-2FFT算法 2.6.1　时域抽取法FFT 将f(n)分成奇序列和偶序列 1 设f(n)的离散傅立叶变换为F(k)，其中n、k的取值范围均为[0，N-1]。不失一般计，设长度N为偶数，若N为奇数，可补充一个零使N为偶数。 将f(n)分成两部分，偶数部分组成一个偶序列，奇数部分组成一个奇序列，分别用f1(i)和f2(i)表示，偶序列f1(i)为： f1(i)=f(2i) 式中 奇序列f2(i)为： f2(i)=f(2i+1) 2.6　基-2FFT算法 2.6.1　时域抽取法FFT 将f(n)分成奇序列和偶序列 1 各自的离散傅立叶变换：F1(k)=DFT[f1(i)] F2(k)=DFT[f2(i)] 有 2.6　基-2FFT算法 2.6.1　时域抽取法FFT 将f(n)分成奇序列和偶序列 1 考虑到f1(i)=f(2i)， f2(i)=f(2i+1)且 则F(k)可写成： 2.6　基-2FFT算法 2.6.1　时域抽取法FFT 将f(n)分成奇序列和偶序列 1 上式表明，按照n的奇偶性能将f(n)分解成两个序列f1(i)和f2(i)，每个序列的长度均为N/2。