第3章1-4 离散傅里叶变换及其快速算法

1、Discrete Fourier Transform and Fast Algorithm本章习题（ 第三版课本P155）3.4，3.6(2)(4)，3.8，3.103.13，3.14，3.16，3.18，3.20选做：3.28离散傅里叶变换 (Discrete Fourier Transform，DFT)是时间函数是离散的，而且频谱函数也是离散的变换。3. 1 讨论周期序列的 傅里叶级数及其性质。3. 2 导出有限长序列的傅里叶表示离散傅里叶变换，并较详细地 介绍了离散傅里叶变换的基本性质，其中包括循环卷积的重要概念。3. 3 介绍利用循环卷积 计算线性卷积的方法。3. 4 讨论频率取样理论

2、。3. 5 以较大篇幅介绍本章的重点内容 快速傅里叶变换的时间抽选算法和频率抽选算法及一些细节上的考虑。3. 6 介绍变换点数 为合数时的快速傅里叶变换算法。3. 7 介绍快速傅里叶变换算法的应用实例。3. 8 介绍线性调频Z变换。（参考） 连续时间、离散频率的傅里叶变换对于周期为T的连续时间信号，可以采用傅里叶级数展开：连续时间、连续频率的傅里叶变换对于非周期的连续时间信号，可以进行傅里叶变换：它在时域和频域都是连续的。离散时间、连续频率的傅里叶变换对于非周期的序列，其傅里叶变换在频域是以2为周期的连续函数。3. 1. 1 离散傅里叶级数离散傅里叶级数(DFS)定义定义 一个周期为N的周期序

3、列可表示为：这样的周期序列的Z变换是不收敛的。如果用离散傅里叶级数表示，则可以讨论其收敛性。用傅里叶级数表示，其基波频率为：用复指数表示：第k次谐波为：由于是周期序列，且k次谐波也是周期为N的序列：因此，对于离散傅里叶级数，只取下标从0到N-1的N个谐波分量就足以表 示原来的信号。这样可把离散傅里叶级数表示为 式中，乘以系数1/N是为了下面计算的方便； 为k次谐波的系数。将上式两边同乘以并从n=0到N-1求和，得到：由复指数序列的正交性：所以，得到周期序列的离散傅里叶级数表达式：令则得到周期序列的离散傅里叶级数(DFS)变换对n和k均为离散变量。如果将n当作时间变量，k当作频率变量，则第一式表

4、示的是时域到频域的变换，称为DFS的正变换。第二式表示的是频域到时域的变换，称为DFS的反变换。由于故 是周期为N的离散周期信号。周期序列的信息可以用它在一个周期中的N个值来代表。设周期序列 和 的周期都为N，且若则有设则如果mN，则m=m1+Nm23.1.2 离散傅里叶级数的性质设和都是周期为N的周期序列，它们的DFS系数分别为令则上式表示的是两个周期序列的卷积，称为周期卷积。周期为N的两个序列的周期卷积的离散傅里叶级数等于它们各自离散傅里叶级数的乘积。周期卷积的计算：周期卷积中的序列 和 对m都是周期为N的周期序列，它们的乘积对m也是以N为周期的，周期卷积仅在 一个周期内求和。 相乘和相加

5、运 算仅在m=0到N-1的区间内进行。计算出n=0到N-1(一个周期)的结果后，再将其进行周期延拓，就得到周期卷积 。 周期卷积满足交换律两个周期序列的乘积 的DFS为：有限长序列的傅里叶变换称为离散傅里叶变换，简写为DFT。DFT可以按3个步骤由 DFS推导出来：将有限长序列延拓成周期序列；求周期序列的DFS；从DFS中取出一个周期便得到有限长 序列的DFT。将x(n)延拓成周期为N的周期序列如上图所示。显然有的第一个周期，即n0到N-1的序列称为主值序列，n=0到N-1的范围称为主值区间。上述两式可分别表示为 其中RN(n)是矩形序列。符号(n)N表示n对模N的余数，即 这里k是商。 同理

6、，可以认为周期序列 的DFS系数 是有限长序列X(k)周期延拓的结果，而 X(k)是 的主值序列。即 由此便可以得出有限长序列的离散傅里叶变换(DFT)的表示式为由此可见，有限长序列x(n)的DFT即X(k)仍是有限长序列。在一般情况下，X(k)是一个复量，可表示为或式中例3. 1 求有限长序列的DFT，其中a=0.8，N=8。 解：因此得 X(0)=4.16114 X(1)=0.71063-j0.92558 X(2)=0.50746-j0.40597 X(3)=0.47017-j0.16987 X(4)=0.46235X(5)= 0.47017+j0.16987X(6)= 0.50746+j

7、0.40597X(7)= 0.71063+j0.92558Matlab实现 fft1.m将x(n)的Z变换与x(n)的DFT进行对比，可以看出式中，表示z平面单位圆上辐角(k=0,1,N-1)的N个等间隔点。Z变换在这些点上的取样值就是X(k)。在图3.4(b)中的虚线包络是单位圆(z=ej)上的Z变换，即傅里叶变化X(ej)。序列序列x(n)在时域是有限长的在时域是有限长的(长度为长度为N)，它的离散傅里叶变，它的离散傅里叶变换换X(k)也是离散、有限长的也是离散、有限长的(长度也为长度也为N)。n为时域变量，为时域变量，k为频域变量。为频域变量。离散傅里叶变换与离散傅里叶级数没有本质区别，

8、离散傅里叶变换与离散傅里叶级数没有本质区别，DFT实实际上是离散傅里叶级数的主值，际上是离散傅里叶级数的主值，DFT也隐含有周期性。也隐含有周期性。离散傅里叶变换离散傅里叶变换(DFT)具有唯一性。具有唯一性。DFT的物理意义：序列的物理意义：序列x(n)的的Z变换在单位圆上的等角距取变换在单位圆上的等角距取样。样。 DFT隐含着周期性，因此在讨论DFT的性质时，常与DFS的概念联系起来，并把有限长序列看作周期序列的一个周期来处理。设x1(n)和x2(n)的长度都为N，且它们对应的DFT分别为X1(k)和X2(k)。 设x3(n)=ax1(n)+bx2(n)，a和b都为常数，则 若它们长度不等

9、，取长度最大者，将短的序列通过补零加长，注意此时DFT与未补零的DFT不相等。 此性质可以直接由DFT的定义进行证明。2对称性对称性 最常遇到的是实序列。设x(n)是一个长度为N的实序列，且DFTx(n)=X(k)，则有 这意味着或 这就是说，实序列的DFT系数X(k)的模是偶对称序列，辐角是奇对称序列。 对于复序列也有相应的共轭对称性。 一个长度为N的序列x(n)的循环移位定义为 循环移位分3步计算：(1)将x(n)延拓成周期为N的周期序列 ； (2)将 移位得 或x(n+m)N；(3)对x(n+m)N取主值得x(n+m)NRN(n)。这个过程如下图所示。 从图中两虚线之间的主值序列的移位情

10、况可以看出，当主值序列左移m个样本时，从右边会同时移进m个样本，而且好像是刚向左边移出的那些样本又从右边循环移了进来。因此取名“循环移位”。 显然，循环移位不同于线性移位 序列循环移位后的DFT为 证明：由周期序列的移位性质得因x(n+m)NRN(n)是 的主值序列，所以它的DFT就是的主值，即根据时域和频域的对偶关系，可以得出若则 设Y(k)=Xl(k)X2(k)，则或由上式表示的卷积称为循环卷积，常记为利用DFT的隐含周期性，将Y(k)周期延拓计算后再取主值m取值的0N-1范围是主值区间，故因此循环卷积的计算是对序列按循环移位后求对应项的乘积之和，实际上就是周期卷积取主值。循环卷积的计算可

11、用图3.6来说明。 在图3.6(a)中，x1(n)的N个值按顺时针方向均匀分布在内圆周上，x2(n)的N个值按反时针方向均匀分布在外圆周上，把内外圆周上对应的数值两两相乘，然后把乘积相加就得到y(0)。若将外圆周顺时针方向转动一格(如图3.6(b)所示)，将内外圆周上对应的数值两两相乘并把乘积相加，便得到y(1)。依次类推，可以得出y(n)的其它值。因此循环卷积也叫做圆卷积。图3.7表示的是序列x1(n)和x2(n)的4点(即N=4)循环卷积的计算过程。图中，x1(n)=(n)+(n-1)+(n-2)，x2(n)(n)+1.5(n-1)+2(n-2)+2.5(n-3)。这一计算过程分5步：(1

12、)周期延拓 (2)折叠 (3)移位和取主值 (4)相乘 (5)相加考虑到DFT关系的对偶性，可以证明，长为N的两序列之积的DFT等于它们的DFT的循环卷积除以N，即 3种卷积：线性卷积 线性卷积不受主值区间限制周期卷积循环卷积 是周期卷积取主值，在一定条件下与线性卷积相等。两个长度都为N的因果序列的循环卷积仍是一个长度为N的序列，而它们的线性卷积却是一个长度为2N-1的序列。 如果能将线性卷积转化成循环卷积，那么根据DFT的循环卷积性质，就能够用循环卷积来计算线性卷积，而循环卷积可以用FFT 进行快速计算。因此，首先需要讨论在什么条件下，循环卷积与线性 卷积相等的问题。 在许多实际问题中常需要

13、计算线性卷积，例如一个FIR数字滤波器的输出等于输入与滤波器的单位取样响应的线性卷积。 设x1(n)和x2(n)都是长度为N的有限长因果序列，它们的线性卷积为它是长为2N-1的序列。 现将x1(n)和x2(n)延长至L(LN)，延长部分(从N到L-1)均填充为零值，计算x1(n)和x2(n)的L点循环卷积，得到 为了下面分析方便，先将x1(n)和x2(n)以L为周期进行延拓，得到两个周期序列和它们的周期卷积为注意到在区间0mL-1中，x1(m)L=x1(m)；并交换求和次序得 上式表明，x1(n)和x2(n)的周期卷积是它们的线性卷积的周期延拓。对周期卷积取主值，得到循环卷积 因此，x1(n)

14、和x2(n)的循环卷积可被看作是它们的线性卷积的周期延拓的主值。那么，如何确定延拓的周期L呢？因为两个长度为N的序列的线性卷积是一个长度为2N-1的序列，所以(1)如果L2N-1，则x3(n)的周期延拓必有一部分非零值序列相重叠，从而产生混叠失真，这时L点的循环卷积不等于N点的线性卷积。(2)如果L2N-1，则x3(n)的周期延拓不会产生混叠失真，这时由此得出结论：两个长度为N的序列的线性卷积可用长度为L的循环卷积来代替，但L必须满足条件 L2N-1。这时N到L之间的值用零填充。如果x1(n)和x2(n)的长度分别为N和M，则L应满足条件LM+N-1。 这意味着，对于时间有限信号，可以像频带有

15、限信号进行时域采样而不丢失任何信息一样，可以在频域上进行采 样而不丢失任何信息。这正是傅里叶变换中时域和频域对偶关系的反映，这有着十分重要的意 义。DFT实现了频域离散化，开辟了在频域采用数字技术处理的新领域。 这使我们自然想到，对于任意一个频率特性，是否均能用频域采样的办法来逼近，这是一个很吸引人的问题，因为用频率采样来逼近，可使问题大大简化。因此我们要讨论频率采样的可行性以及所带来的误差。 频率取样是指对序列的傅里叶变换或系统的频率特性进行取样 。本节讨论在什么条件下能够用得到的频谱取样值无失真地恢复原信号或系统。 设任意长序列x(n)绝对可和，其Z变换表示为如果在单位圆上对X(z)进行等

16、角距取样，取样点数为M，则得 根据DFT的定义，对X(k)求反变换得 根据上面两式可得：因为所以 上式表明，在z平面的单位圆上对序列的Z变换进行等角距取样，将导致时间序列的周期延拓。这一结果与对连续时间信号取样导致频谱周期延拓类似。 现在我们来考察xp(n)与原序列x(n)的关系，看它如何才能代表原序列x(n)。 xp(n)是原非周期信号x(n)的周期延拓序列，因此xp(n)是一个周期序列，其主值为 在x(n)为有限长度N的情况下，如果取样点MN，那么x(n)周期延拓的结果不会产生混叠。这时，xp(n)的主值xN(n)与原序列x(n)一样，因此xN(n)完全能代表原序列x(n)。 如果MN，即延拓的周期M小余有限序列的长度N，则x(n)周期延拓后一定产生混叠，因而xN(n)不能无失真地代表原信号x(n)。在x(n)为无限长的情况下，对Z变换取样必然导致混叠失真，因此xN(n)不能代表原序列x(n)。（见下图） 因此，对于长度为N的有限长序列，对Z变换取样即频率取样不失真的条件，是取样点数 M应等于或大于原序列的长度N，即MN。在MN时，Z变换的取样即DFT X(k)，利用IDFT公式可由X(k)恢复原序列x(n