离散傅立叶变换

第3章 离散傅立叶变换§DFS§DFS的性质§DFT§DFT的性质§圆周卷积圆周卷积§利用DFT计算线性卷积§频率域抽样有限长序列的傅里叶分析有限长序列的傅里叶分析一、四种信号傅里叶表示一、四种信号傅里叶表示1. 周期为周期为T0的连续时间周期信号的连续时间周期信号频谱特点： 离散非周期谱2. 2. 连续时间非周期信号连续时间非周期信号连续时间非周期信号连续时间非周期信号频谱特点：   连续非周期谱3. 3. 离散非周期信号离散非周期信号离散非周期信号离散非周期信号频谱特点： 周期为2的连续谱4. 4. 周期为周期为N N 的离散周期信号的离散周期信号频谱特点：周期为N的离散谱为了便于更好地理解DFT的概念，先讨论周期序列及其离散傅里叶级数（DFS）表示一个周期为N的周期序列，即                                                                                                  ， k为任意整数，N为周期周期序列不能进行Z变换，因为其在 n=-到+ 都周而复始永不衰减，即 z 平面上没有收敛域。

但是，正象连续时间周期信号可用傅氏级数表达，周期序列也可用离散的傅氏级数来表示，也即用周期为N的正弦序列来表示 离散傅里叶级数（DFS）周期为N的正弦序列其基频成分为： K次谐波序列为：      但离散级数所有谐波成分中只有N个是独立的，这是与连续傅氏级数的不同之处，       即           因此                 将周期序列展成离散傅里叶级数时，只需取 k=0 到(N-1) 这N个独立的谐波分量，所以一个周期序列的离散傅里叶级数只需包含这N个复指数，          利用正弦序列的周期性可求解系数             将上式两边乘以                                  ，并对一个周期求和               上式中[ ]部分显然只有当k=r时才有值为1,其他任意k值时均为零,所以有     或写为    1)  可求 N 次谐波的系数   2）              也是一个由 N 个独立谐波分量组成的傅立叶级数    3）          为周期序列，周期为N•时域上周期序列的离散傅里叶级数在频域上仍是一个周期序列。

  是一个周期序列的离散傅里叶级数(DFS)变换对，这种对称关系可表为：           习惯上：记                                                 ，                  DFS变换对公式表明，一个周期序列虽然是无穷长序列，但是只要知道它一个周期的内容（一个周期内信号的变化情况），其它的内容也就都知道了，所以这种无穷长序列实际上只有N个序列值的信息是有用的，因此周期序列与有限长序列有着本质的联系则则DFSDFS变换对可写为变换对可写为DFS[·] ——离散傅里叶级数变换IDFS[·]——离散傅里叶级数反变换DDFS的几个主要特性：的几个主要特性：        假设                     都是周期为 N 的两个周期序列，各自的离散傅里叶级数为：      1）线性）线性                                                                                                                             a,b为任意常数  2）序列移位）序列移位           证因为         及    都是以N为周期的函数，所以有                    由于             与     对称的特点，同样可证明  3））共轭对称性共轭对称性 对于复序列         其共轭序列                满足 证证:同理同理:进一步可得共轭偶对称分量 共轭奇对称分量 4）周期卷积）周期卷积若   则                     或 周 期 卷 积证：     这是一个卷积公式，但与前面讨论的线性卷积的差别在于，这里的卷积过程只限于一个周期内（即 m=0~N-1），称为周期卷积。

例：                  、            ，周期为 N=7, 宽度分别为 4 和 3 ，求周期卷积   结果仍为周期序列，周期为 N        由于DFS与IDFS的对称性，对周期序列乘积，存在着频域的周期卷积公式，若  则   我们知道周期序列实际上只有有限个序列值有意义，因此它的许多特性可推广到有限长序列上      一个有限长序列 x(n)，长为N，                                                    为了引用周期序列的概念，假定一个周期序列           ，它由长度为 N 的有限长序列 x(n) 延拓而成，它们的关系：       离散傅里叶变换（离散傅里叶变换（DFT））周期序列的主值区间与主值序列：        对于周期序列           ，定义其第一个周期 n=0~N-1，为               的“主值区间”，主值区间上的序列为主值序列 x(n)x(n)与           的关系可描述为：       数学表示：  RN（n）为矩形序列符号（（n））N 是余数运算表达式，表示 n 对 N 求余数。

例：           是周期为 N=8 的序列，求 n=11 和 n=-2 对 N的余数因此 频域上的主值区间与主值序列：频域上的主值区间与主值序列：           周期序列            的离散付氏级数              也是一个周期序列，也可给它定义一个主值区间                                 ，以及主值序列  X(k)数学表示：                再看周期序列的离散傅里叶级数变换（DFS）公式：       这两个公式的求和都只限于主值区间（0~N-1），它们完全适用于主值序列 x(n) 与 X(k) ，因而我们可得到一个新的定义——有限长序列离散傅里叶变换定义       长度为N的有限长序列 x(n) ，其离散傅里叶变换 X(k) 仍是一个长度为N 的有限长序列，它们的关系为：         x(n) 与 X(k)  是一个有限长序列离散傅里叶变换对，已知 x(n) 就能唯一地确定 X(k) ，同样已知 X(k) 也就唯一地确定 x(n) ，实际上 x(n) 与 X(k) 都是长度为 N 的序列（复序列）都有N个独立值，因而具有等量的信息。

有限长序列隐含着周期性1. 线性线性需将较短序列补零后，再按长序列的点数做需将较短序列补零后，再按长序列的点数做DFT2. 循环位移循环位移(Circular shift of a sequence) 循环位移定义为离散傅里叶变换的性质离散傅里叶变换的性质DFT频域循环位移特性DFT时域循环位移特性3. 3. 对称性对称性对称性对称性(symmetry)(symmetry)周期共轭对称(Periodic conjugate symmetry)定义为 周期共轭反对称(Periodic conjugate antisymmetry)定义为当序列x[k]为实序列时，周期偶对称序列满足当序列x[k]为实序列时，周期奇对称序列满足对称特性对称特性当x[k]是实序列时4.循环卷积循环卷积h[(-n)N]h[(1-n)N]h[(2-n)N]h[(3-n)N]卷积定理卷积定理序列序列DFT与与z变换的关系变换的关系x[k]的 X[m]等于其z变换X(z)在单位圆上等间隔取样设序列设序列x[k]的长度为的长度为N][mX¾¾®¾IDFT][kx¾¾¾®¾变换Z)(zX(内插公式)问题提出:实际需要：    LTI系统响应      y[k]=x [k]h[k]可否利用DFT计算线性卷积？例：x1[k]={1,1,1},  x 2[k]={1,1,0,1} ,  N=4一、两个有限长序列的线性卷积一、两个有限长序列的线性卷积利用利用DFT计算线性卷积计算线性卷积线性卷积的矩阵表示线性卷积的矩阵表示线性卷积的矩阵表示线性卷积的矩阵表示循环卷积的矩阵表示循环卷积的矩阵表示循环卷积的矩阵表示循环卷积的矩阵表示循环卷积的矩阵表示循环卷积的矩阵表示循环卷积的矩阵表示循环卷积的矩阵表示若若x x[ [k k] ]的长度为的长度为N N，，h h[ [k k] ]的长度为的长度为MM，则，则L L= =N N+ +MM- -1 1点点循环卷积等于循环卷积等于x x[ [k k] ] 与与h h[ [k k] ]的线性卷积。

的线性卷积直接计算与由DFT间接计算结果比较若若x1[k]为为 M 点序列点序列, x2[k]为为L 点序列点序列 ，， L> >Mx1[k] L x2[k]中哪些点不是线性卷积的点中哪些点不是线性卷积的点?问题讨论0  k   M- -2不是线性卷积不是线性卷积的结果，即前的结果，即前(M- -1)个点与个点与线性卷积不一样线性卷积不一样线性卷积的矩阵表示线性卷积的矩阵表示线性卷积的矩阵表示线性卷积的矩阵表示循环卷积的矩阵表示循环卷积的矩阵表示 x1[k] L x2[k]k=0 ~M- -2, 前前M- -1个点不是线性卷积的点个点不是线性卷积的点k= M- -1 ~ L- -1 , L- -M+1个点与线性卷积的点对应个点与线性卷积的点对应线性卷积线性卷积 L ~ L+M- -2 后后M - -1点没有计算点没有计算  则则L点循环卷积点循环卷积结论若若x1[k]为为 M 点序列点序列, x2[k]为为L 点序列点序列 ，， L> >M长序列和短序列的线性卷积直接利用直接利用DFT计算的缺点：计算的缺点：(1) 信号要全部输入后才能进行计算，延迟太多信号要全部输入后才能进行计算，延迟太多(2) 内存要求大内存要求大(3) 算法效率不高算法效率不高解决问题方法：采用分段卷积解决问题方法：采用分段卷积分段卷积可采用分段卷积可采用重叠相加法重叠相加法 和和 重叠保留法重叠保留法1. 重叠相加（重叠相加（overlap add））将长序列x[k] 分为若干段长度为L的序列其中y0[k]的非零范围y1[k-L]的非零范围 序列 y0[k],  y1[k]的重叠部分重叠的点数L+M-2-L+1=M-1依次将相邻两段的依次将相邻两段的M-1个重叠点相加，即得到最终的个重叠点相加，即得到最终的线性卷积结果。

线性卷积结果重叠相加法分段卷积举例重叠相加法分段卷积举例方法：(1) 将x[k]长序列分段，每段长度为L；  (2) 各段序列xn[k]与 M点短序列h[k]循环卷积；(3) 从各段循环卷积中提取线性卷积结果2.重叠保留法重叠保留法(overlap save)前M-1个点不是线性卷积的点因 yn[k]=xn [k] L h[k]故分段时，每段与其前一段有M-1个点重叠--x [k (M 1)]M-1--L  (M 1)L-1x 0[k]x 1[k]2L-Mk第一段前需补M-1个零记     yn[k] =xn [k] L h[k]y y0[ [k k] ]中的中的[ [MM- -1, 1, L L- -1]1]点对应于线性卷积点对应于线性卷积 x x[ [k k] ] h h[ [k k] ]中的中的[0 , [0 , L L- -MM] ]点点y1[k]中的[M-1, L-1]点对应于线性卷积x[k]h[k]中的 [ L-(M-1), 2L-M-(M-1)]点例例例例 已知序列已知序列x x[ [k k]=]=k k+2,0+2,0 k k 12, 12, h h[ [k k]={1,2,1}]={1,2,1}试分别利试分别利用重叠相加和保留法计算线性卷积用重叠相加和保留法计算线性卷积, , 取取L L=5 =5 。

y[k]={2, 7, 12, 16, 20,  24, 28, 32, 36, 40, 44, 48, 52, 41, 14}解: 重叠相加法x1[k]={2, 3, 4, 5, 6}x2[k]={7, 8, 9, 10, 11}x3[k]={12,13, 14}y1[k]={2,  7, 12, 16,  20,  17,  6}y2[k]={ 7,  22, 32, 36, 40, 32, 11}y3[k]={12, 37, 52, 41, 14}解解: : 重叠保留法重叠保留法y[k]={2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14}x1[k]={0, 0, 2, 3, 4}x2[k]={3, 4, 5, 6 ,7}x3[k]={6 ,7 , 8, 9, 10}y1[k]= x1[k]h[k]= {11,  4,  2,  7,  12}x4[k]={9, 10 , 11, 12,13}y2[k]= x2[k]h[k]= {23,  17,  16,  20,  24}y3[k]= x3[k]h[k]= {35,  29,  28,  32,  36}y4[k]= x4[k]h[k]= {47,  41,  40,  44,  48}x5[k]={12,13, 14, 0, 0}y5[k]= x5[k]h[k]= {12,   37,   52,   41,   14}。