ch335循环卷积课件

3.3

利用循环卷积计算线性卷积（重点）

为快速计算线性卷积，根据前面讨论的DFT的循环卷积性质，以及循环卷积和线性卷积可能存在的某种关系。因此，可以考虑利用循环卷积计算线性卷积。首先需要讨论在什么条件下，循环卷积与线性卷积相等的问题。在许多实际问题中常需要计算线性卷积，例如一个FIR设x1(n)和x2(n)都是长度为N的有限长因果序列，它们的线性卷积为1它是长为2N-1的序列。2华中科技大学电信系现将x1(n)和x2(n)延长至L(L>N)，延长部分(从N到L-1)均填充为零值，计算x1(n)和x2(n)的L点循环卷积，得到为了下面分析方便，先将x1(n)和x2(n)以L为周期进行延拓，得到两个周期序列和它们的周期卷积为3华中科技大学电信系那么，如何确定延拓的周期L呢？因为两个长度为N的序列的线性卷积是一个长度为2N-1的序列，所以(1)如果L<2N-1，则x3(n)的周期延拓必有一部分非零值序列相重叠，从而产生混叠失真，这时L点的循环卷积不等于N点的线性卷积。(2)如果L≥2N-1，则x3(n)的周期延拓不会产生混叠失真，这时由此得出结论：两个长度为N的序列的线性卷积可用长度为L的循环卷积来代替，但L必须满足条件

L≥2N-1。这时N到L之间的值用零填充。若x1(n)和x2(n)长度分别为N和M，则L应满足条件:L≥M+N-1。5华中科技大学电信系例1已知序列x1(n)和x2(n)如下：(1)求x1(n)和x2(n)的25点循环卷积y1(n)(2)求x1(n)和x2(n)的34点循环卷积y2(n)解：(1)(2)6华中科技大学电信系例2：已知请问序列y1(n)中的哪些值与序列y2(n)的值相同？解：所以，当n=2,3,4,5,6时，y1(n)=y2(n)7华中科技大学电信系频率取样是指对序列的傅里叶变换或系统的频率特性进行取样。本节讨论在什么条件下能够用得到的频谱取样值无失真地恢复原信号或系统。设任意长序列x(n)绝对可和，其Z变换表示为如果在单位圆上对X(z)进行等角距取样，取样点数为M，则得根据DFT的定义，对X(k)求反变换得9华中科技大学电信系根据上面两式可得：∵∴

结论：在z平面的单位圆上对序列的Z域进行等角距取样，将导致时间序列的周期延拓。这一结果与对连续时间信号取样导致频谱周期延拓类似。现在我们来考察xp(n)与原序列x(n)的关系，看它如何才能代表原序列x(n)。10华中科技大学电信系对比：11华中科技大学电信系当N=5，M=5时，时域延拓恰好无混叠现象，此时原序列可以完全恢复，如下图所示

图中，红色为原信号，蓝色为恢复信号。

13华中科技大学电信系当N=5，M=4时，时域延拓存在混叠现象，此时原序列不能完全恢复，如下图所示

图中，红色为原信号，蓝色为恢复信号。

思考：当N=5，M=8时，恢复出的信号是什么样？14华中科技大学电信系15华中科技大学电信系

x(n)－－X(z)－－X(k)－－xp(n)－－xN(n)ZTIDFTZ=WM-k主值17华中科技大学电信系例1：已知序列：若X(z)为x(n)的ZT，如果对X(z)在处采样后得到：画出由X(k)的IDFT所得到的序列x1(n)的略图，说明理由。18华中科技大学电信系解：图略。说明：IDFT前后的序列长度应当相等。19华中科技大学电信系解：图略21华中科技大学电信系对于有限长序列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ω)。22华中科技大学电信系改写为，其中上式就是用X(z)在单位圆上的N个取样值X(k)来表示X(z)的内插公式，内插函数为F(z)∵∴，23华中科技大学电信系令

其中就是内插函数。∴长度为N的序列x(n)的傅里叶变换X(ejw)可通过Z平面单位圆上的N个取样值，即N个频域取样值X(k)来恢复。25华中科技大学电信系一些说明在每个抽样点上X(ejw)就精确地等于X(k)（因为其他的内插函数在这一点上的值为零，无影响），即各抽样点之间的X(ejw)

值,则由各抽样点的加权内插函数在所求点上的值的叠加而得到.频率响应的内插函数j(w)

具有线性相位.26华中科技大学电信系3.5快速傅里叶变换(FFT)3.5.1DFT的计算量1965年库利(Cooley)和图基(Tukey)在前人的研究成果的基础上提出了FFT的算法。FFT的出现，使计算DFT的计算量减少了两个数量级，极大地推动了DSP的理论和技术的发展。当N很大时，计算量太大，所花的时间也太多。如果使用来直接计算DFT，离散傅里叶变换在实际应用中是非常重要的，利用它可以计算信号的频谱、功率谱和线性卷积等。29华中科技大学电信系CooleyandTukey,1965J.W.CooleyandJ.W.Tukey,MathematicsofComputation,Vol.19,pp.297-301,1965.30华中科技大学电信系DFT的定义：在导出FFT算法之前，首先来估计一下直接计算DFT所需的计算量。其中31华中科技大学电信系将DFT定义式展开成方程组将方程组写成矩阵形式用向量表示32华中科技大学电信系用复数表示：其中：X为N维列向量，称为变换列向量，为复数；W为N×N维方阵，称为系数矩阵，为复数；x为N维列向量，表示离散时间信号，可以是复数。33华中科技大学电信系若计算一个X(k)(一个频率成分)的值，例k=1则要进行N次复数乘法+(N-1)次复数加法所以直接计算N点DFT，计算量为：复数乘法次数：N2次，复数加法次数：N(N-1)次其运算量相当于：实数乘法次数：4N2次，实数加法次数：2N2＋2N(N-1)次34华中科技大学电信系FFT算法的改进主要利用了WNk的两个性质：(1)对称性，即(2)周期性，即，r为任意整数。从看，提高DFT运算速度，唯一可以利用的是旋转因子WNk

35华中科技大学电信系

FFT算法是利用旋转因子的周期性和对称性，并利用把长序列的DFT逐次分解为较短序列的DFT来提高计算速度的。因为DFT的运算量与N2成正比的如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到减少运算工作量的效果。36华中科技大学电信系在本章中我们集中讨论两类基本的FFT算法。第一类：称为按时间抽取(Decimation-in-Time)的基2FFT算法，在这类算法中是将时间序列x(n)逐次分解为较短的子序列。第二类：称为按频率抽取(Decimation-in-Frequency)的基2FFT算法，在这类算法中是将离散傅里叶变换系数序列X(k)逐次分解为较短的子序列。这两种算法特别适用于N等于2的幂的情况。37华中科技大学电信系Decimation-In-TimeFFT，简称时间抽选FFT算法基本出发点：利用旋转因子WNk的对称性和周期性，将一个大的DFT分解成一些逐次变小的DFT来计算，分解直至2点的变换。分解过程遵循两条规则： ①对时间序列进行偶奇分解； ②对频率序列进行前后分解。设N=2M，M为正整数。为了推导方便，取N=23=8，即离散时间信号为3.5.2

时间抽选基2FFT算法(库里—图基算法)38华中科技大学电信系按照规则(1)，将序列x(n)分为奇偶两组，一组序号为偶数，另一组序号为奇数，即分别表示为：根据DFT的定义39华中科技大学电信系因为WN2=WN/21，所以上式变为上式中的G(k)和H(k)都是N/2点的DFT。(3.64)(3.65)所以，前N/2=4个k值的DFT可表示为40华中科技大学电信系后4个k值的X(k)表示为：因为所以(3.66)按照规则(2)，将X(k)分成前后两组，即41华中科技大学电信系上式相当于把原来N点的DFT计算分解成两个N/2点的DFT计算。G(k)是原序列偶数项g(r)的N/2点DFT；H(k)是原序列奇数项h(r)的N/2点DFT。(3.66)(3.65)注意：42华中科技大学电信系按照式(3.65)和式(3.66)可画出图3.15所示的信号流程图。43华中科技大学电信系式(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)}44华中科技大学电信系(3.67)(3.68)45华中科技大学电信系(3.69)(3.70)这样，用式(3.67)～(3.70)4个公式就可计算图3.15中的两组N/2点DFT。图3.16所示的是其中一组G(k)的计算。46华中科技大学电信系将图3.16与图3.15所示的信号流程图合并，便得到图3.17所示的信号流程图。∵N=8，∴上图中N/4点的DFT就是2点的DFT，不能再分解了。G(0)G(3)H(0)H(3)47华中科技大学电信系将2点DFT的信号流程图移入图3.17，得到图3.19所示的8点时间抽选的完整的FFT流程图。m=1m=2m=348华中科技大学电信系作图要素：(1)左边为输入(2)右边为输出(3)如果在某一支路上信号需要进行相乘运算，则在该支路上标出要相乘的系数。(4)当支路上没有系数时，则该支路的传输比为1。49华中科技大学电信系2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT4点DFT4点DFT4点DFT4点DFT8点DFT8点DFT16点DFTX(k)x(n)16点FFT50华中科技大学电信系将N点DFT先分成两个N/2点DFT，再是四个N/4点DFT…直至N/2个两点DFT。每分一次称为“一级”运算。因为N=2M，所以N点DFT可分成M级如图3.19所示，依次m=1,2,…,M，共M级“级”的概念51华中科技大学电信系从图3.19中可看出几个特点：(1)流程图的每一级的基本计算单元都是一个蝶形；

(2)输入x(n)不按自然顺序排列，称为“混序”排列，而输出X(k)按自然顺序排列，称为“正序”排列，因而要对输入进行“变址”；(3)由于流程图的基本运算单元为蝶形，所以可以进行“同址”或“原位”计算。52华中科技大学电信系1.蝶形运算任何一个N为2的整数幂(即N=2M)的DFT，都可以通过M次分解，最后成为2点的DFT来计算。M次分解构成了从x(n)到X(k)的M级迭代计算，每级由N/2个蝶形组成。图3.20表示了蝶形的一般形式表示。其输入和输出之间满足下列关系：3.5.3

蝶形、同址和变址计算53华中科技大学电信系∵完成一个蝶形运算需2次复加法和1次复乘法。∴完成N=2M点的DFT计算需log2N级迭代计算，每级N/2个蝶形； ∴

∴完成N点的时间抽选FFT的总计算量为：54华中科技大学电信系大多数情况下复数乘法所花的时间最多，因此下面仅以复数乘法的计算次数为例来与直接计算进行比较。直接计算DFT需要的复数乘法次数为aD=N2，于是有例如，当N=1024时，则：aD/

aF≈205，即直接计算DFT所需复数乘法次数约为FFT的205倍。即：DFT需205小时，FFT需1小时。显然，N越大，FFT的速度优势越大。表3.2列出了不同N值所对应的两种计算方法的复数乘法次数和它们的比值。55华中科技大学电信系56华中科技大学电信系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)进入运算器并进行蝶形运算。注意：流图中各蝶形的输入量或输出量是互不相重的，任何一个蝶形的二个输入量经蝶形运算后，便失去了利用价值，不再需要保存。57华中科技大学电信系第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越大，好处越明显。58华中科技大学电信系M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(8)与图3.22比较59华中科技大学电信系可以看出，每一级的蝶形的输入与输出在运算前后可以存储在同一地址(原来位置上)的存储单元中，这种同址运算的优点是可以节省存储单元，从而降低对计算机存储量的要求或降低硬件实现的成本。蝶形运算的特点是，首先每一个蝶形运算都需要两个输入数据，计算结果也是两个数据，与其它结点的数据无关，其它蝶形运算也与这两结点的数据无关。因此，一个蝶形运算一旦计算完毕，原输入数据便失效了。这就意味着输出数据可以立即使用原输入数据结点所占用的内存。原来的数据也就消失了。输出、输入数据利用同一内存单元的这种蝶形计算称为原位(同址)计算。60华中科技大学电信系3．变址计算从图3.19所示的流程图看出，输入x(n)是“混序”排列的。所谓输入为“混序”，并不是说输入是杂乱无章的，实际上它是有规律的。如果输入x(n)的序号用二进制码来表示，就可以发现输入的顺序恰好是正序输入的“码位倒置”，表3.3列出了这种规律。61华中科技大学电信系在实际运算中，按码位倒置顺序输入数据x(n)，特别当N较大时，是很不方便的。因此，数据总是按自然顺序输入存储，然后通过“变址”运算将自然顺序转换成码位倒置顺序存储。实现这种转换的程序可用图3.21来说明。62华中科技大学电信系图中用n表示自然顺序的标号，用l表示码位倒置的标号。当l=n时，x(n)和x(l)不必互相调换。当l≠n时，必须将x(l)和x(n)互相调换，但只能调换一次，为此必须规定每当l>n时，要将x(l)和x(n)相互调换，即把原来存放x(n)的存储单元中的数据调入存储x(l)的存储单元中，而把原来存储x(l)的存储单元中的数据调入到存储x(n)的存储单元中。这样，按自然序输入的数据x(n)经过变址计算后变成了码位倒置的排列顺序，便可进入第1级的蝶形运算。63华中科技大学电信系时间抽选FFT算法的其他形式的流程图：对于任何流程图，只要保持各节点所连支路及其传输系数不变，则不论节点位置怎样排列，所得到的流程图总是等效的，因而都能得到DFT的正确结果，只是数据的提取和存储次序不同而已。

图3.2