《ch循环卷积》PPT课件.ppt

华中科技大学电信系,1,3. 3 利用循环卷积计算线性卷积（重点）,为快速计算线性卷积，根据前面讨论的DFT的循环卷积性质，以及循环卷积和线性卷积可能存在的某种关系。因此，可以考虑利用循环卷积计算线性卷积。 首先需要讨论在什么条件下，循环卷积与线性卷积相等的问题。,在许多实际问题中常需要计算线性卷积，例如一个FIR数字滤波器的输出等于输入与滤波器的单位取样响应的线性卷积。,设x1(n)和x2(n)都是长度为N的有限长因果序列，它们的线性卷积为,华中科技大学电信系,2,它是长为2N-1的序列。,华中科技大学电信系,3,现将x1(n)和x2(n)延长至L(LN)，延长部分(从N到L-1)均填充为零值，计算x1(n)和x2(n)的L点循环卷积，得到,为了下面分析方便，先将x1(n)和x2(n)以L为周期进行延拓，得到两个周期序列,和,它们的周期卷积为,华中科技大学电信系,4,注意到在区间0mL-1中，x1(m)L=x1(m)；并交换求和次序得,上式表明，x1(n)和x2(n)的周期卷积是它们的线性卷积的周期延拓。对周期卷积取主值，得到循环卷积,结论：x1(n)和x2(n)的循环卷积可被看作是它们的线性卷积的周期延拓的主值。,华中科技大学电信系,5,那么，如何确定延拓的周期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。,华中科技大学电信系,6,例1 已知序列x1(n)和x2(n)如下：,(1)求x1(n)和x2(n)的25点循环卷积y1(n) (2)求x1(n)和x2(n)的34点循环卷积y2(n),解：,(1),(2),华中科技大学电信系,7,例2：已知,请问序列y1(n)中的哪些值与序列y2(n)的值相同？,解：,所以，当n=2,3,4,5,6时， y1(n) = y2(n),华中科技大学电信系,8,两种取样 时域取样: 对一个带限的离散时间信号，根据取样定理对其进行时域取样，所得取样信号的频谱是原带限信号频谱的周期延拓，因此，完全可以由取样信号恢复原信号。 频域取样:,3. 4 频率取样,DFT与DTFT的关系示意图,希望在频域上也可以进行采样而不丢失任何信息。而DFT实现了频域离散化，使得频域上抽样也是可能的。,华中科技大学电信系,9,频率取样是指对序列的傅里叶变换或系统的频率特性进行取样。,本节讨论在什么条件下能够用得到的频谱取样值无失真地恢复原信号或系统。,设任意长序列x(n)绝对可和，其Z变换表示为,如果在单位圆上对X(z)进行等角距取样，取样点数为M，则得,根据DFT的定义，对X(k)求反变换得,华中科技大学电信系,10,根据上面两式可得：,结论：在z平面的单位圆上对序列的Z域进行等角距取样，将导致时间序列的周期延拓。这一结果与对连续时间信号取样导致频谱周期延拓类似。,现在我们来考察xp(n)与原序列x(n)的关系，看它如何才能代表原序列x(n)。,华中科技大学电信系,11,对比：,华中科技大学电信系,12,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)。 （见下图）,华中科技大学电信系,13,当N=5，M=5时，时域延拓恰好无混叠现象，此时原序列可以完全恢复，如下图所示,图中，红色为原信号，蓝色为恢复信号。,华中科技大学电信系,14,当N=5，M=4时，时域延拓存在混叠现象，此时原序列不能完全恢复，如下图所示,图中，红色为原信号，蓝色为恢复信号。,思考：当N=5，M=8时，恢复出的信号是什么样？,华中科技大学电信系,15,华中科技大学电信系,16,因此，对于长度为N的有限长序列，对Z变换取样即频率取样不失真的条件，是取样点数 M应等于或大于原序列的长度N，即MN。在M=N时，Z变换的取样即DFT X(k)，利用IDFT公式可由X(k)恢复原序列x(n)，即,这就是频域采样定理。,在x(n)为无限长的情况下，对Z变换取样必然导致混叠失真，因此xN(n)不能代表原序列x(n)。,华中科技大学电信系,17,x(n)X(z)X(k)xp(n)xN(n),ZT,IDFT,Z=WM-k,主值,华中科技大学电信系,18,例1：已知序列：,若X(z)为x(n)的ZT，如果对X(z)在,处采样后得到：,画出由X(k)的IDFT所得到的序列x1(n)的略图，说明理由。,华中科技大学电信系,19,解：,图略。,说明：IDFT前后的序列长度应当相等。,华中科技大学电信系,20,例2：已知因果序列,设：,试写出x(n)与y(n)之间的关系式，并画出y(n)的波形图。,华中科技大学电信系,21,解：,图略,华中科技大学电信系,22,对于有限长序列x(n)，满足频域采样定理时，M点频域采样X(k)就足以不失真地代表序列的频域特性。,如何由频域取样值恢复出X(z)或X(ej)？,在M=N时，Z变换的取样即DFT X(k)，利用IDFT公式可由X(k)恢复原序列x(n)。因此以下的讨论中，令M=N。,因此，由这M个采样值X(k)应能完全地表达整个X(z)函数及频率特性X(ej)。即由M点X(k)可内插恢复出X(z)或X(ej)。,华中科技大学电信系,23,改写为,，其中,上式就是用X(z)在单位圆上的N个取样值X(k)来表示X(z)的内插公式，内插函数为F (z),，,华中科技大学电信系,24,如果z=ej则可以得到傅里叶变换的内插公式，,注：,，,华中科技大学电信系,25,令,其中 就是内插函数。,长度为N的序列x(n)的傅里叶变换X(ejw)可通过Z平面单位圆上的N个取样值，即N个频域取样值X(k)来恢复。,华中科技大学电信系,26,一些说明 在 每 个 抽 样 点 上X(ejw) 就 精 确 地 等 于 X(k) （因 为 其 他 的 内 插 函 数 在 这 一 点 上 的 值 为 零，无 影 响）， 即 各 抽 样 点 之 间 的X(ejw) 值, 则 由 各 抽 样 点 的 加 权 内 插 函 数 在 所 求 点 上 的 值 的 叠 加 而 得到. 频 率 响 应 的 内 插 函 数 j (w) 具 有 线 性 相 位.,华中科技大学电信系,27,华中科技大学电信系,28,本节结论： 长度为N的序列x(n)，其N个频域取样值X(k)可以不失真地代表它，而且X(k)还能完整的表示序列的Z变换X(z)和傅里叶变换X(ejw) 。 频率取样理论是用频率取样法设计FIR数字滤波器（DF）的理论基础。,华中科技大学电信系,29,3. 5 快速傅里叶变换(FFT),3.5.1 DFT的计算量,1965年库利 (Cooley)和图基(Tukey)在前人的研究成果的基础上提出了FFT的算法。FFT的出现，使计算DFT的计算量减少了两个数量级，极大地推动了DSP的理论和技术的发展。,当N很大时，计算量太大，所花的时间也太多。,如果使用,来直接计算DFT，,离散傅里叶变换在实际应用中是非常重要的，利用它可以计算信号的频谱、功率谱和线性卷积等。,华中科技大学电信系,30,Cooley and Tukey, 1965,J. W. Cooley and J. W. Tukey, Mathematics of Computation, Vol. 19, pp. 297-301, 1965.,华中科技大学电信系,31,DFT的定义：,在导出FFT算法之前，首先来估计一下直接计算DFT所需的计算量。,其中,华中科技大学电信系,32,将DFT定义式展开成方程组,将方程组写成矩阵形式,用向量表示,华中科技大学电信系,33,用复数表示：,其中： X为N维列向量，称为变换列向量，为复数；W为NN维方阵，称为系数矩阵，为复数； x为N维列向量，表示离散时间信号，可以是复数。,华中科技大学电信系,34,若计算一个X(k)(一个频率成分)的值， 例k=1则 要进行N次复数乘法+(N-1)次复数加法,所以直接计算N点DFT，计算量为：,复数乘法次数：N2次，复数加法次数：N(N-1)次,其运算量相当于：,实数乘法次数：4N2次，实数加法次数：2N22N(N-1)次,华中科技大学电信系,35,FFT算法的改进主要利用了WNk的两个性质： (1)对称性，即 (2)周期性，即,，r为任意整数。,从 看，提高DFT,运算速度，唯一可以利用的是旋转因子WNk,华中科技大学电信系,36,FFT算法是利用旋转因子的周期性和对称性，并利用把长序列的DFT逐次分解为较短序列的DFT来提高计算速度的。,因为DFT的运算量与N2成正比的 如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到减少运算工作量的效果。,华中科技大学电信系,37,在本章中我们集中讨论两类基本的FFT算法。 第一类：称为按时间抽取(Decimation-in-Time)的基2FFT算法，在这类算法中是将时间序列x(n) 逐次分解为较短的子序列。 第二类：称为按频率抽取(Decimation-in-Frequency)的基2FFT算法，在这类算法中是将离散傅里叶变换系数序列X(k)逐次分解为较短的子序列。 这两种算法特别适用于N等于2的幂的情况。,华中科技大学电信系,38,Decimation-In-Time FFT，简称时间抽选FFT算法 基本出发点：利用旋转因子WNk的对称性和周期性，将一个大的DFT分解成一些逐次变小的DFT来计算，分解直至2点的变换。 分解过程遵循两条规则： 对时间序列进行偶奇分解； 对频率序列进行前后分解。,设N=2M，M为正整数。为了推导方便，取N=23=8，即离散时间信号为,3. 5. 2 时间抽选基2FFT算法(库里图基算法),华中科技大学电信系,39,按照规则(1)，将序列x(n)分为奇偶两组，一组序号为偶数，另一组序号为奇数，即,分别表示为：,根据DFT的定义,华中科技大学电信系,40,因为 WN2=WN/21，所以上式变为,上式中的G(k)和H(k)都是N/2点的DFT。,(3.64),(3.65),所以，前N/2=4个k值的DFT可表示为,华中科技大学电信系,41,后4个k值的X(k)表示为：,因为,所以,(3.66),按照规则(2)，将X(k)分成前后两组，即,华中科技大学电信系,42,上式相当于把原来N点的DFT计算分解成两个N/2点的DFT计算。 G(k)是原序列偶数项g(r)的N/2点DFT； H(k)是原序列奇数项h(r)的N/2点DFT 。,(3.66),(3.65),注意：,华中科技大学电信系,43,按照式(3.65)和式(3.66)可画出图3.15所示的信号流程图。,华中科技大学电信系,44,式(3.65)和式(3.66)把原来N点DFT的计算分解成两个N/2点DFT的计算。照此可进一 步把每个N/2点DFT的计算再各分解成两个N/4点DFT的计算。,此时G(k)和H(k)分别计算如下:,x(0)，x(2)，x(4)，x(6) x(0)，x(4) | x(2)，x(6),x(1)，x(3)，x(5)，x(7) x(1)，x(5) | x(3)，x(7),原信号序列被分成4个2项信号: x(0)，x(4) | x(2)，x(6) | x(1)，x(5) | x(3)，x(7),华中科技大学电信系,45,(3.67),(3.68),华中科技大学电信系,46,(3.69),(3.70),这样，用式(3.67)(3.70) 4个公式就可计算图3.15中的两组N/2点DFT。图3.16所示的是其中一组G(k)的计算。,华中科技大学电信系,47,将图3.16与图3.15所示的信号流程图合并，便得到图3.17所示的信号流程图。,N=8，上图中N/4点的DFT就是2点的DFT，不能再分解了。,华中科技大学电信系,48,将2点DFT的信号流程图移入图3.17，得到图3.19所示的8点时间抽选的完整的FFT流程图。,m=1,m=2,m=3,华中科技大学电信系,49,作图要素： (1)左边为输入 (2)右边为输出 (3)如果在某一支路上信号需要进行相乘运算，则在该支路上标出要相乘的系数。 (4)当支路上没有系数时，则该支路的传输比为1。,华中科技大学电信系,50,16点FFT,华中科技大学电信系,51,将N 点DFT先分成两个N/2点DFT，再是四个N/4点DFT直至N/2个两点DFT。每分一次称为“一级”运算。 因为N=2M ，所以N点DFT可分成M级 如图3.19所示，依次m=1, 2,M，共M级,“级”的概念,华中科技大学电信系,52,从图3.19中可看出几个特点： (1)流程图的每一级的基本计算单元都是一个蝶形； (2)输入x(n)不按自然顺序排列，称为“混序”排列，而输出 X(k)按自然顺序排列，称为“正序”排列，因而要对输入进行“变址”； (3)由于流程图的基本运算单元为蝶形，所以可以进行“同址”或“原位”计算。,华中科技大学电信系,53,1. 蝶形运算,任何一个N为2的整数幂(即N=2M)的DFT，都可以通过M次分解，最后成为2点的 DFT来计算。M次分解构成了从x(n)到X(k)的M级迭代计算，每级由N/2个蝶形组成。图3.20表示了蝶形的一般形式表示。,其输入和输出之间满足下列关系：,3. 5. 3 蝶形、同址和变址计算,华中科技大学电信系,54,完成一个蝶形运算需2次复加法和1次复乘法。 完成N=2M点的DFT计算需log2N级迭代计算，每级N/2个蝶形； 完成N点的时间抽选FFT的总计算量为：,华中科技大学电信系,55,大多数情况下复数乘法所花的时间最多，因此下面仅以复数乘法的计算次数为例来与直接计算进行比较。,直接计算DFT需要的复数乘法次数为aD=N2，于是有,例如，当N=1024时，则：aD / aF205，即直接计算DFT所需复数乘法次数约为FFT的205倍。即：DFT需205小时，FFT需1小时。显然，N越大，FFT的速度优势越大。,表3. 2列出了不同N值所对应的两种计算方法的复数乘法次数和它们的比值。,华中科技大学电信系,56,华中科技大学电信系,57,2同址(原位)计算,N点FFT，包含log2N级迭代运算，每级由N/2个蝶形计算构成。蝶形计算的优点是可以进行所谓同址或原位计算。,现在来考察第一级的计算规律。设将输入x(0)，x(4)，x(2)，x(6)， x(1)，x(5)，x(3)，x(7)分别存入计算机的存储单元M(1), M(2), M(3),，M(7)和M(8)中。首先，存储单元M(5)和M(6)中的数据x(1)和x(5)进入运算器并进行蝶形运算。,注意：流图中各蝶形的输入量或输出量是互不相重的，任何一个蝶形的二个输入量经蝶形运算后，便失去了利用价值，不再需要保存。,华中科技大学电信系,58,第1级运算:x(1)和x(5)运算后，结果送到M(5)和M(6)保存，,x(3)和x(7)运算后，结果送到M(7)和M(8)保存。,第2级运算: M(5)和M(7)运算后，结果送到M(5)和M(7)保存，,M(6)和M(8)运算后，结果送到M(6)和M(8)保存。,所以，蝶形运算后的结果便可以送到M(5)和M(6)存储起来。,直至完成最后一级运算，中间不需要其它存贮器。,同址运算的好处：节省存贮单元。当N越大，好处越明显。,华中科技大学电信系,59,与图3.22比较,华中科技大学电信系,60,可以看出， 每一级的蝶形的输入与输出在运算前后可以存储在同一地址(原来位置上)的存储单元中，这种同址运算的优点是可以节省存储单元，从而降低对计算机存储量的要求或降低硬件实现的成本。,蝶形运算的特点是，首先每一个蝶形运算都需要两个输入数据，计算结果也是两个数据，与其它结点的数据无关，其它蝶形运算也与这两结点的数据无关。 因此，一个蝶形运算一旦计算完毕，原输入数据便失效了。这就意味着输出数据可以立即使用原输入数据结点所占用的内存。原来的数据也就消失了。 输出、输入数据利用同一内存单元的这种蝶形计算称为原位(同址)计算。,华中科技大学电信系,61,3变址计算,从图3. 19所示的流程图看出，输入x(n)是“混序”排列的。所谓输入为“混 序”，并不是说输入是杂乱无章的，实际上它是有规律的。如果输入x(n)的序号用二进制码来表示，就可以发现输入的顺序恰好是正序输入的“码位倒置”，表3. 3列出了这种规律。,华中科技大学电信系,62,在实际运算中，按码位倒置顺序输入数据x(n)，特别当N较大时，是很不方便的。因此，数据总是按自然顺序输入存储，然后通过“变址”运算将自然顺序转换成码位倒置顺序存储。实现这种转换的程序可用图3. 21来说明。,华中科技大学电信系,63,图中用n表示自然顺序的标号，用l表示码位倒置的标号。 当l=n时，x(n)和x(l)不必互相调换。 当ln时， 必须将x(l)和x(n)互相调换，但只能调换一次，为此必须规定每当ln时，要将x(l)和x(n)相互调换，即把原来存放x(n)的存储单元中的数据调入存储x(l)的存储单元中，而把原来存储x(l)的存储单元中的数据调入到存储x(n)的存储单元中。,这样，按自然序输入的数据x(n)经过变址计算后变成了码位倒置的排列顺序，便可进入第1级的蝶形运