数字信号处理dsp教程-ch2课件

1、第 2 章 离散变换及其快速算法本章内容：离散傅里叶级数（DFS）离散傅立叶变换（DFT）基2快速傅立叶变换（FFT）利用DFT做连续信号的频谱分析 FFT在分段卷积等中的应用2.1 DFT对于有限长序列，可以用离散傅里叶变换（Discrete Fourier Transform，DFT）来分析，DFT能反映信号的频域特征且更便于用计算机处理。傅里叶变换的几种可能形式四种傅里叶变换形式的归纳时间函数 频率函数 连续和非周期 非周期和连续 连续和周期 非周期和离散 离散和非周期 周期和连续 离散和周期 周期和离散 一个域的离散对应另一个域的周期延拓， 一个域的连续必定对应另一个域的非周期。2.1

2、.1 周期序列的离散傅里叶级数(DFS)设 是一个周期为N的周期序列， 即 k次谐波周期序列 基频（2/N）离散傅里叶级数取k=0 到N-1的N个独立谐波分量谐波系数是以N为周期的周期序列即呈周期性，其周期为N， 推导 离散傅里叶级数（DFS）只要知道周期序列一个周期的内容，其他的内容也都知道了。所以，这种无限长序列实际上只有一个周期中的N个序列值有信息。 因而周期序列和有限长序列有着本质的联系。 例求所示周期序列的离散傅里叶级数表示式。解：离散傅里叶级数（DFS）的性质1 线性2 序列的移位证：由于都是以N为周期的，即因此 离散傅里叶级数（DFS）的性质3 共轭对称性复序列 共轭偶对称分量

3、共轭奇对称分量 离散傅里叶级数（DFS）的性质4 周期卷积证 例N=7，计算解：两个周期序列的周期N=7，周期卷积过程用图示。周期卷积过程用图解表示m012345622220000022100000122020000122020000124220000181220000100122000100012200600012202周期卷积过程列表表示周期卷积结果2.1.2 有限长序列离散傅里叶变换(DFT)周期序列实际上只有有限个序列值有意义设x(n)为有限长序列，长度为N，x(n)在n=0到N-1点上有值。把 的第一个周期n=0 到n=N-1 定义为“主值区间”， 故x(n)是 的“主值序列”，即主

4、值区间上的序列。主值序列把 的第一个周期n=0 到n=N-1 定义为“主值区间”， 故x(n)是 的“主值序列”，即主值区间上的序列。0n1N-1，n2为整数 例例离散傅里叶变换(DFT)0kN-1 0nN-1 离散傅里叶变换隐含着周期性x(n)和X(k)是一个有限长序列的离散傅里叶变换对。已知其中的一个序列，就能惟一地确定另一个序列。这是因为x(n)与X(k)都是点数为N的序列，都有N个独立值（可以是复数），所以信息等量。 此外，值得强调得是，在使用离散傅里叶变换时，必须注意所处理的有限长序列都是作为周期序列的一个周期来表示的。 离散傅里叶变换隐含着周期性。简记为简记为矩阵方程来表示 例x(

5、n)=(n)，求它的N点DFT不论对它进行多少点的DFT，结果都是一个离散矩形序列解例矩形序列x(n)=RN(n)，求它的N点DFT结果只有一个非零值N解例求复数序列x(n)=1+j， 1-j，j，1的DFT。求得 解 例x(n)=cos(n/6) ，N=12， 求它的N点DFT解离散傅里叶变换的性质（1） 线性（2） 循环移位，圆周移位一个长度为N的有限长序列x(n)的圆周移位定义为f(n)=x(n+m)NRN(n) 圆周移位过程示意图x(n)向左循环移位（圆周移位）时，此圆是顺时针旋转; x(n)向右循环移位（圆周移位）时，此圆是逆时针旋转。如果围绕圆周观察几圈， 那么看到的就是周期序列循

6、环移位时域循环移位定理表明，有限长序列的圆周移位在离散频域中引入一个和频率成正比的线性相移 ，而对频谱的幅度没有影响。 频域循环移位定理调制特性：说明时域序列的调制等效于频域的圆周移位（3） 循环卷积 (圆周卷积)它和周期卷积过程是一样的，只不过这里要取主值序列。时域循环卷积定理推导 频域循环卷积定理例计算解（1） 循环卷积图示法 N=7N=7解（2） m0123456f(n)x(m)2222000y(m)0022100y(0-m)NRN(n)00012202y(1-m)NRN(n)00001220y(2-m)NRN(n)20000124y(3-m)NRN(n)22000018y(4-m)NR

7、N(n)122000010y(5-m)NRN(n)012200010y(6-m)NRN(n)00122006y(7-m)NRN(n)00012202循环卷积列表法 例：循环卷积（圆周卷积）过程示意图求这两个矩形序列的循环卷积。 例 设两个有限长序列相等，各为N点，同为矩形序列解：矩形序列的DFT等于N点的循环卷积5点的循环卷积9点的循环卷积两个序列各增加5个零点，为10点的序列进行循环卷积9点的循环卷积与线性卷积比较9点的循环卷积=线性卷积一定条件下，循环卷积可以等于线性卷积研究循环卷积与线性卷积的关系 设x1(n)是N1点的有限长序列（0nN1-1）， x2(n)是N2点的有限长序列（0nN

8、2-1）。 线性卷积y (n)是N1+N2-1 点有限长序列周期卷积循环卷积两序列补充零值至L点 循环卷积等于线性卷积而不产生混叠的必要条件循环卷积等于线性卷积而不产生混叠的必要条件y (n)是N1+N2-1 点有限长序列例：线性卷积与圆周卷积线性卷积圆周卷积（4） 共轭对称性x*(n)为x(n)的共轭复序列DFTx*(n)=X*(-k)NRN(k)=X*(N-k)NRN(k) =X*(N-k) 0kN-1 X(N)=X(0) X*(N)=X*(0) 证X(k)的隐含周期性，故有X(N)=X(0)共轭对称性同样的方法可以证明对称性是指关于坐标原点的纵坐标的对称性。DTFT一些对称性质，定义了共

9、轭对称序列与共轭反对称序列的概念。 DFT有类似的对称性，但在DFT中，涉及的序列x(n)及其离散傅里叶变换X(k)均为有限长序列，且定义区间为 0 到N-1，DFT的对称性是指关于N/2 点的对称性。 x(n) 的实部与虚部的DFT共轭（偶）对称分量共轭奇（反）对称分量x(n) 的实部与虚部的DFTx(n) 的 共轭对称和共轭反对称的DFT共轭（偶）对称分量共轭奇（反）对称分量x(n) 的 共轭对称和共轭反对称的DFTx(n) 为实序列的偶对称和奇对称偶对称分量奇对称分量（5） 选频性例（6） DFT与zT、DTFTx(n)是一个有限长序列，长度为NDFT与序列傅里叶变换、Z变换的关系X(k

10、) 是X(z)在Z平面单位圆上N点等间隔采样值， X(k)也可以看作x(n)的X(ej)在区间0， 2上的N点等间隔采样，其采样间隔为N=2/N， 这就是DFT的物理意义。显而易见，DFT的变换区间长度N不同， 表示对X(ej)在区间0， 2上的采样间隔和采样点数不同， 所以DFT的变换结果也不同。例0n4 求其N=5 点离散傅里叶变换X(k)k=0, N, 2N, 其他 DFS k=0, 1, 2, 3, 4 k=0 k=0, 1, 2, 3, 4 DFTDFT举例说明x(n)的5点DFT（a） 有限长序列x(n)（b） 由x(n)形成的周期N=5的周期序列（c） 对应于 的傅里叶级数和x(

11、n)的|X(ej)|（d） x(n)的5点DFTDFT举例说明x(n)的10点DFT（a） 有限长序列x(n) （b） 由x(n)（补零）形成的周期N=10的周期序列（c） x(n)的10点DFT（7） DFT形式下的Parseval定理证进一步例2.2 利用DFT做连续信号的频谱分析由于DFT具有选频特性，所以常用它对连续信号进行频谱分析。这一分析过程是一次次的近似过程。其步骤：（1）采样连续信号用离散采样信号的DTFT来近似连续信号的傅里叶变换 （2）将x(n)截短 用有限长度序列的DTFT来近似无限长度序列的DTFT（3）对截短的信号做DFT对有限长度序列的DTFT采样前置低通滤波器LP

12、F，是为了消除或减少时域连续信号转换成序列时可能出现的频谱混叠的影响。 在实际工作中，时域离散信号x(n)的时宽是很长的， 甚至是无限长的（例如语音或音乐信号）。由于DFT的需要(实际应用FFT计算)，必须把x(n)限制在一定的时间区间之内，即进行数据截断。 数据的截断相当于加窗处理。 因此， 在计算FFT之前，用一个时域有限的窗函数w(n)加到x(n)上是非常必要的。可能出现的问题及其解决方法 （1）混叠采样序列的频谱是被采样模拟信号频谱的周期延拓，当采样频率不满足奈奎斯特采样定理时，就会发生频谱的混叠，不能真实地反映原信号的频谱。解决混叠问题的惟一方法是保证采样频率足够高，以防止频谱混叠，

13、这意味着通常需要知道原信号的频谱范围，以确定采样频率。但很多情况下可能无法预计信号频率，为确保无混叠现象，可在采样前利用一模拟低通滤波器（抗混叠滤波器） 。（2）泄漏一个时间有限的信号其频带宽度为无限，一个时间无限的信号其频带宽度则为有限。在实际DFT运算中，时间长度总是取有限值，在将信号截短的过程中，出现了分散的扩展谱线的现象，称为频谱泄漏或功率泄漏。由于泄漏使信号的频谱展宽，泄漏也会引起混叠。 （3）栅栏效应DFT是对单位圆上z变换的均匀采样，频谱是一组离散谱线。有限长序列的频谱是连续状的。用DFT来观察频谱就如同通过一个栅栏来观看景象一样，只能在离散点上看到真实的频谱，这样一些频谱的峰点

14、或谷点就有可能被“尖桩的栅栏”挡住，也就是正好落在两个离散采样点之间，不能被观察到。减小栅栏效应的一个方法是在原序列的末端填补一些零值，增加了DFT的点数，从而离散谱线（栅）目加大，相当于搬动了“尖桩栅栏”的位置，从而使得频谱的峰点或谷点暴露出来。栅栏效应举例（4）DFT的分辨率DFT的频率分辨率通常规定为fs/N，这里的N是指信号x (n)的有效长度，而不是补零的长度。填补零值可以改变对DTFT的采样密度，不能提高DFT的频率分辨率。不同长度的x(n)，其DTFT的结果是不同的；而相同长度的x(n)只是反映了对相同的DTFT采用了不同的采样密度。要提高DFT分辨率只有增加信号x/(n)的截取

15、长度N。 例 设模拟信号xa(t)的最高频率fmax=5Hz，试求最低采样频率fs，在这一采样频率下采得256点数据，对其做DFT，给出所能得到的最大频率分辨率f 。解：由采样定理得 fs=2fmax=10Hzf=10/256= 0.039Hz用FFT进行频谱分析时参数选择的一般原则：（一）若已知信号的最高频率fmax，选定采样频率（二）据实际需要，选定频率分辨率f，再确定所需DFT长度f越小越好，但f越小，N越大，使计算量、存储量也随之增大。（三）根据fs和N确定模拟信号的时间长度（）周期信号的谱分析图 (c)和图 (d)分别是N=16时的截取信号和DFT结果，由于截取了两个整周期，得到单一

16、谱线的频谱。上述频谱的误差主要是由于时域中对信号的非整周期截断产生的频谱泄漏。图（a）和图（b）分别是N=20时的截取信号和 DFT结果，由于截取了两个半周期，频谱出现泄漏；2.3 FFT DFT的运算量每计算一个X(k)值，需要N次复数乘法和N-1次复数加法。X(k)一共有N个点（k从0取到N-1），所以完成整个DFT运算总共需要N2次复数乘法及N(N-1)次复数加法。一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法需二次实数加法。 每运算一个X(k)需4N次实数乘法和2N+2(N-1)=2(2N-1)次实数加法。 整个DFT运算总共需要4N2次实数乘法和2N(2N-1)次实数加法。

17、 IDFT与DFT的差别只在于WN的指数符号不同，以及差一个常数1/N，所以IDFT与DFT具有相同的运算工作量。 FFT的运算量复数乘法复数加法例 对一幅NN点的二维图像进行DFT变换，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解 直接计算DFT所需复乘次数为（N2)21012次，因此用每秒可做10万次复数乘法的计算机，则需要近3000小时。 这对实时性很强的信号处理来说，要么提高计算速度，而这样，对计算速度的要求太高了。另外，只能通过改进对DFT的计算方法，以大大减少运算次数。2.3.1 按时间抽取（DIT）的基 -2 FFT算法（1）

18、WNnk的对称性Wnk的以下固有特性（2） WNnk的周期性（3） WNnk的可约性按时间抽取 (DIT）法序列x(n)长度为N，且满足N=2M，M为正整数。按n的奇偶把x(n)分解为两个N/2点的子序列：蝶形运算结构 利用G（k）、H（k）的周期特性，有 一个8点DFT由两个4点DFT组成 由四个2点DFT组成8点DFT 按时间抽取的8点FFT 基2-DIT-FFT N点DFT的一次时域抽取分解图(N=8)N点DFT的第二次时域抽取分解图(N=8)一个N=8点DFT分解为四个N/4点DFT按时间抽取的FFT算法与直接计算DFT运算量的比较N=2M，共有M级蝶形， 每级都由N/2个蝶形运算组成

19、，每个蝶形需要一次复乘、 二次复加，因而每级运算都需N/2次复乘和N次复加，这样M级运算总共需要 复乘复加直接计算DFT与FFT算法的计算量之比N=2048时，这一比值为372.4，即直接计算DFT的运算量是FFT运算量的372.4倍例 用FFT算法处理一幅NN点的二维图像，如用每秒可做10万次复数乘法的计算机，当N=1024时，问需要多少时间（不考虑加法运算时间）？解 当N=1024点时，FFT算法处理一幅二维图像所需复数乘法约为107次，仅为直接计算DFT所需时间的10万分之一。 即原需要3000小时，现在只需要2 分钟。FFT算法DFT按时间抽取的FFT算法的特点（1） 蝶形运算N=2M

20、，共有M级蝶形， 每级都由N/2个蝶形运算组成，每个蝶形需要一次复乘、 二次复加，因而每级运算都需N/2次复乘和N次复加。（2） 原位运算（同址运算）原位运算， 即某一列的N个数据送到存储器后，经蝶形运算，其结果为下一列数据，它们以蝶形为单位仍存储在这同一组存储器中，直到最后输出，中间无需其他存储器。也就是蝶形的两个输出值仍放回蝶形的两个输入所在的存储器中。 每列的N/2 个蝶形运算全部完成后， 再开始下一列的蝶形运算。 这样存储器数据只需N个存储单元。下一级运算仍采用这种原位方式，只是进入蝶形结的组合关系有所不同。 这种原位运算结构可以节省存储单元， 降低设备成本。N点DITFFT运算流图(

21、N=8) 输入倒序输出顺序（3） 蝶形类型随迭代次数成倍增加（4） 序数重排（倒位序规律）X(k)按正常顺序，即按X(0)，X(1)，X(7)的顺序排列，x(n)不是按自然顺序存储的，而是按x(0)，x(4)， ， x(7)的顺序存入存储单元，称之为倒位序。倒位序的形成如输入序列的自然顺序号为n2n1n0，则其倒位序就是n0n1n2N=8序数重排过程 十进制二进制第一次分偶、奇第二次分偶、奇第三次分偶、奇十进制0000n0=0000n1=0000n2=000001001010100n2=110042010100n1=1010n2=001023011110110n2=111064100n0=10

22、01n1=0001n2=000115101101101n2=110136110011n1=1011n2=001157111111111n2=11117N=8时的自然顺序二进制数和相应的倒位序二进制数自然顺序（I） 二进制数 倒位序二进制数 倒位序（J） 0123456700000101001110010111011100010001011000110101111104261537N=8 倒位序的变址处理DIT-FFT程序框图倒序程序框图DIT-FFT运算程序框图按时间抽取的FFT算法的其他形式流图时间抽取、 输入自然顺序、 输出倒位序的FFT流图 基2-DIT-FFT 输入顺序输出倒序基2-D

23、IT-FFT 输入顺序输出顺序2.3.2 按频率抽取（DIF）的基 -2 FFT算法设序列点数为N=2M，M为正整数。把输入序列按前一半、后一半分开（不是按偶数、 奇数分开）， 把N点DFT写成两部分。输出X(k)按k的奇偶分组。 按频率抽取（DIF）法按频率抽取的第一次分解按频率抽取的第二次分解按频率抽取的FFT（N=8）信号流图按频率抽取法的运算特点（）蝶形运算（）原位计算（）蝶形类型随迭代次数成减少尽管蝶形结构不同于按时间抽取FFT，但总的计算量与按时间抽取算法相同。 （）序数重排 与时间抽取法不同，按频率抽取法的输入是自然顺序，而输出是以按位反转的规律重排。将频率抽取法的流图反转，并且

24、将输入变输出，输出变输入，正好得到时间抽取法的流图。按频率抽取法与按时间抽取法是两种等价的FFT运算 2.3.3 N为组（复）合数的FFT算法 问题: N为任意因子的组合数，N=P1P2 Pm，(Pi是正整数)，如何提高计算效率?最简单的情况: N=PQ为两个数的乘积。(1)将DFT的时间顺序n和频率顺序k分别表示成二维的形式 n=n1Q+n0 k=k1P+k0 式中n0, k1分别为0,1,，Q-1;n1, k0分别为0,1,，P-12.3.4 线性调频Z变换（Chirp-Z变换）算法螺线采样Chirp-Z变换的线性系统表示Chirp-Z变换的圆周卷积图2.4 关于FFT应用中的几个问题2.

25、4.1 用FFT计算 IDFTIFFT计算分三步： 将X(k)取共轭(虚部乘以-1) 对X*(k)直接作FFT 对FFT的结果取共轭并乘以1/N，得x(n)2.4.2 实数序列的FFT大多数场合下,信号是实数序列,任何实数都可看成虚部为零的复数：x(n)+j0求某实信号y(n)的复谱,可认为是将实信号加上数值为零的虚部变成复信号,再用FFT求其离散付里叶变换。不经济,存储器要增加一倍,且计算机运行时,即使虚部为零,也要涉及虚部的运算,浪费了运算量。合理的解决方法是利用复数据FFT对实数据进行有效计算(1)用 一个N点FFT同时计算两个N点实序列的DFT设x(n)、y(n)是彼此独立的两个N点实

26、序列,且 X(k)=DFTx(n) ，Y(k)=DFTy(n) 则X(k)、Y(k)可通过一次FFT运算同时获得。算法：将x(n)、y(n)构成一复序列 g(n)=x(n)+jy(n)通过FFT运算可获得g(n)的DFT值 G(k)=DFTx(n)+jDFTy(n)=X(k)+jY(k) Gr(k)+jGi(k) =Xr (k)-Yi (k)+j Xi (k)+Yr (k)g(n)的FFT运算结果G(k), 由上式可得到X(k)、Y(k)。(2)用N点的FFT运算获得2N点实序列的DFT设x(n)是2N点实序列,并分为偶数组x1(n)和奇数组x2(n) x1(n)=x(2n) x2(n)=x(

27、2n+1) n=0,1,N-1将x1(n)及x2(n)组成一复序列： y(n)=x1(n)+jx2(n)通过N点FFT运算可得到： Y(k)=X1(k)+jX2(k) N点根据共轭对称性，得X1(k)和X2(k) 。再按下式复合成X(k)2.4.3 线性卷积的FFT算法线性卷积是求离散系统响应的主要方法之一许多重要应用都建立在这一理论基础上,如卷积滤波等。用圆周卷积计算线性卷积的方法：长为N2的序列x(n)延长到L,补L-N2个零长为N1的序列h(n)延长到L,补L-N1个零如果LN1+N2-1,则圆周卷积与线性卷积相等,此时,可用FFT计算线性卷积可用FFT计算线性卷积方法a. 计算X(k)

28、=FFTx(n)b. 求 H(k)=FFTh(n)c. 求 Y(k)=H(k)X(k) k=0L-1d. 求 y(n)=IFFTY(k) n=0L-1进行二次FFT,一次IFFT就可完成线性卷积计算L32时,上述计算线性卷积的方法比直接计算线卷积有明显的优越性圆周卷积方法为快速卷积法将 x(n) 分为许多段,每段的长度与 h(n) 接近上述结论适用于 x(n)、h(n) 两序列长度比较接近或相等的情况如果x(n)、h(n) 长度相差较多如, h(n) 为某滤波器的单位脉冲响应,长度有限,用来处理一个很长的输入信号 x(n),或者处理一个连续不断的信号，按上述方法, h(n) 要补许多零再进行计

29、算,计算量有很大的浪费，或者根本不能实现。为了保持快速卷积法的优越性,可将 x(n) 分为许多段,每段的长度与 h(n) 接近处理方法有两种(1)重叠相加法由分段卷积的各段相加构成总的卷积输出N=N1+N2-1重叠相加法xi(n) 表示 x(n)的第i段只要将x(n)的每一段分别与h(n)卷积，再将这些卷积结果相加就可得到输出序列。每一段的卷积都可用快速卷积来计算： 1)先对h(n)及xi(n)补零，补到具有N点长度，N=N1+N2-1。 一般选 N=2M。 2)用基2 FFT计算 yi(n)=xi(n)*h(n) 3)重叠部分相加构成最后的输出序列。由于yi(n)的长度为N，而xi(n)的长

30、度为N2，因此相邻两段yi(n)序列必然有N-N2=N1-1点发生重叠重叠相加法L=N=N1+N2-1重叠相加法N=N1+N2-1计算步骤a. 准备好滤波器N点参数 H(k)=DFTh(n)b. N点FFT计算Xi(k)=DFTxi(n)c. Yi(k)=Xi(k)H(k)d. N点IFFT求yi(n)=IDFTYi(k)e. 将重叠部分相加N=N1+N2-1重叠相加法例 n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16h (n) 1 1 1x (n)15 14 13 12 1110 9 8 7 6 5 4 3 2 1x0(n)15 14 13 12 11x1(n)10 9 8 7 6x2(n) 5 4 3 2 1y0(n)15 29 42 39 3623 11y1(n) 10 19 27 24 2113 6y2(n) 5 9 12 9 6 3 1y(n)15 29 42 39 3633 30 27 24 2118 15 12 9 6 3 1 n N1-1 N2-1 N-1 N2+N-1 2N2+N-1N1=3 N2=5 N= N1+ N2-