循环卷积和线性卷积的区别
线性卷积：翻折—>乘加—>移位 ：y（n）=x（n）*h（n）=∑h（k）x（n-k） 循环卷积：补零—>周期延拓—>翻折—>循环移位—>对应值相加
例：计算下面给出的两个长度为4的序列h(n)与x(n)的4点和8点循环卷积。
解：按照循环卷积矩阵写出h(n)与x(n)的4点循环卷积矩阵形式为
?yc(0)??1 ???y?c(1)???2 ???y3c(2)? ???yc(3)??4
412334122??1??10?????3???1???10?4??1??10??????1??1??10?h(n)与x(n)的8点循环卷积矩阵形式为
?yc(0)??1?y(1)???c??2?yc(2)??3???y(3)c????4?y(4)??0?c???yc(5)??0?y(6)??0?c???yc(7)????0?0123400000123400000123400000123440000123340000122??1??1?????3???1??3?4??1??6??????0??1??10??0??0??9??????0??0??7?0??0??4??????1??0????0????【补充】①计算h(n)与x(n)的线性卷积？②哪一种情况下计算的循环卷积结果就等于线性卷积？ 【说明】当循环卷积区间长度L大于等于y(n) = h(n)*x(n)的长度时，循环卷积结果就等于线性卷积。 3） 时域循环卷积定理
设h(n)和x(n)的长度分别为N和M，其L点循环卷积为 Lx(n)??h(m)x((n?m))LRL(n) yc(n)?h(n)○
m?0L?1且
H(k)?DFT[h(n)]LX(k)?DFT[x(n)]L 0?k?L?1
则由DFT的循环卷积定理有
Yc(k)?DFT[yc(n)]L?H(k)X(k) 0?k?L?1
4 复共轭序列的DFT（重点） 性质：设x*(n)是x(n)的复共轭序列，长度为N，X(k)?DFT[x(n)]N，
*则DFT[x(k)]N?X(N?k)*0?k?N?1
例：给定一16-点实序列x（n）, 其 16-点 DFT 记为X(k), 已知X(13)= 2 + j3,则 X(3) = ( 2 + j3 )。
说明：DFT的性质。实序列的DFT的共轭对称性：X(k) ＝X*(N-k)，或X(N-k) ＝X*(k)。（牢记）
26
*
3.4 频域采样定理
离散傅里叶变换相当于信号傅里叶变换的等间隔采样，也就是说实现了频域的采样，便于计算机计算。那么是否任一序列都能用频域采样的方法去逼近呢？这是一个很吸引人的问题。 我们考虑一个任意的绝对可和的序列x(n)，它的z变换为
如果对X(z)单位圆上进行等距离采样
现在要问，这样采样以后，信息有没有损失？或者说，采样后所获得的有限长序列xN(n)能不能代表原序列x(n)。
为了弄清这个问题，我们从周期序列
开始
由于
所以
也即
是原非周期序列x(n)的周期延拓序列，其时域周期为频域采样点数N。在第一章我们看到，
时域的采样造成频域的周期延拓，这里又对称的看到，频域采样同样造成时域的周期延拓。
因此，如果序列x(n)不是有限长的，则时域周期延拓时，必然造成混叠现象，因而一定会产生误差。 对于长度为M的有限长序列，只有当频域采样点数N大于或等于序列长度M时，才有
即可由频域采样值X(k)恢复出原序列x(n)，否则产生时域混叠现象，这就是所谓的频域采样定理。（重点—记住！！）
1?z?NX(z)?N内插公式：
简答题：
X(k)??k?1k?01?WNz
27
N?1
有限长序列x(n)的长度为M，对其进行频域采样，不失真的条件是什么？
3.5 DFT的应用举例 1.用DFT计算线性卷积
用循环（周期）卷积计算有限长序列的线性卷积(重点)
对周期要求：N?N1?N2?1（N1、N2分别为两个序列的长度）(记住!!) 简答题： 两个有限长序列
x1(n),0?n?M，x2(n),0?n?N，对它们进行线性卷积，结果用y(n)表示，
y(n)的长度是多少？如果进行圆周卷积，那么什么时候线性卷积和圆周卷积的结果相等？
2.用DFT进行谱分析的误差问题 （1）混叠现象
利用DFT逼近连续时间信号的傅里叶变换，为避免混叠失真，按照抽样定理的要求，采样频率至少是信号最高频率的两倍。
解决混叠问题的唯一方法是保证采样频率足够高。 （2）频谱泄露
任何带限信号都是非时限的，任何时限信号都是非带限的。实际问题中遇到的离散时间序列可能是非时限的、无限长序列，在对该序列利用DFT进行处理时，由于作DFT的点数总是有限的，因此就有一个必须将该序列截断的问题。序列截断的过程相当于给该序列乘上一个矩形窗口函数RN(n)。如果原来序列的频谱为
，矩形窗函数的频谱为
，则截断后有限长序列的频谱为
由于矩形窗函数频谱的引入，使卷积后的频谱被展宽了，即为频谱泄露。
在进行DFT时，由于取无限个数据是不可能的，所以序列的时域截断是必然的，泄露是难以避免的。为了尽量减少泄露的影响，截断时要根据具体的情况，选择适当形状的窗函数，如汉宁窗或汉明窗等。 （3）栅栏效应
由于DFT是有限长序列的频谱等间隔采样所得到的样本值，这就相当于透过一个栅栏去观察原来信号的频谱，因此必然有一些地方被栅栏所遮挡，这些被遮挡的部分就是未被采样到的部分，这种现象称为栅栏效应。由于栅栏效应总是存在的，因而可能会使信号频率中某些较大的频率分量由于被“遮挡”而无法得到反映。此时，通常在有限长序列的尾部增补若干个零值，借以改变原序列的长度。这样对加长的序列作DFT时，由于点数增加就相当于调整了原来栅栏的间隙，可以使原来得不到反映的那些较大的频率分量落在采样点上而得到反映。
简答题：用DFT进行谱分析带来哪些误差问题？采取什么措施可以减少这些误差？
的频谱“泄露”到其它频率处，称
28
第四章：快速傅里叶变换并不是一种新的变换，它是离散傅里叶变换的一种快速算法。
4.1 直接计算DFT的问题及改进的途径
直接计算DFT，需要次复数乘法，次复数加法。
2
直接计算离散傅里叶变换，由于计算量近似正比于N，显然对于很大的N值，直接计算离散傅里叶变换要求的算术运算量非常大。我们可以利用系数WN的特性来改善离散傅里叶变换的计算效率。
nk
（1）的对称性
（2）的周期性
利用的对称性和周期性，将大点数的DFT分解成若干个小点数的DFT，FFT正是基于这个基本思路
发展起来的。
分类：按时间抽取（DIT）算法和按频率抽取（DIF）算法。 4.2
基2FFT的算法原理和FFT运算特点
1）数据要求：N?2 2）计算效率（乘法运算次数：
M1NM，加法计算次数：NM ）（复数运算） 222（DFT运算：乘法运算次数：N，加法计算次数：N）（复数运算）
对于算法原理，要求能够看懂分解流图。
29
1 时域抽取法如下(重点)：
设序列x(n)长度为N，且满足N=2，M为正整数。按n的奇偶把x(n)分解为两个N/2点的子序列：
Mx(2r)?x1(r)r?0,1,N?1 2Nx(2r?1)?x2(r)r?0,1,,?1
2,N?12r?0N?12r?0则x(n)的DFT为
nk2rk(2r?1)k X(k)?DFT[x(n)]??x(n)WN??x(2r)WN??x(2r?1)WNn?0N?1
2rkk??x1(r)WN?WN?x2(r)WN2rk r?0r?0N?12N?12rkkrk ??x1(r)WN/2?WN?x2(r)WN/2r?0r?0N?12N?12k?X1(k)?WNX2(k)
kX2(k)k?0,1,???N/2?1 所以X(k)?X1(k)?WNNN?1?1?22rkrk?X(k)?x1(r)WN??x1(r)WN?1/2/2?DFT[x1(r)]N/2??r?0r?0 ?NN?1?1?22rkrk?X2(k)??x2(r)WN?x2(r)WN?/2/2?DFT[x2(r)]N/2?r?0r?0?将X(k)又可以写为
kX(k)?X1(k)?WNX2(k)k?0,1,k?0,1,N??X?k???X1(k)?WNkX2(k)2??N?12 N,?12,上式将N点DFT分解为两个N/2点的DFT运算，运算过程如下图示
利用蝶形运算求解。
DIT-FFT算法与DFT运算量的比较
直接计算DFT与FFT算法的计算量之比为
N2Nlog2N2?2NN越大，FFT的优点越为明显
log2N说明：至少掌握第一次分解的过程（要能写出相关数学表达式分析）并画出至少第一次分解的蝶形图(重
30