ch循环卷积PPT课件

1、13. 3 利用循环卷积计算线性卷积（重点） 为快速计算线性卷积，根据前面讨论的DFT的循环卷积性质，以及循环卷积和线性卷积可能存在的某种关系。因此，可以考虑利用循环卷积计算线性卷积。 首先需要讨论在什么条件下，循环卷积与线性卷积相等的问题。 在许多实际问题中常需要计算线性卷积，例如一个FIR数字滤波器的输出等于输入与滤波器的单位取样响应的线性卷积。 设x1(n)和x2(n)都是长度为N的有限长因果序列，它们的线性卷积为第1页/共71页2它是长为2N-1的序列。x1(m)x1(m)N-1N-10 0 x2(n-m)x2(n-m)n nn-N+1n-N+1x2(n-m)x2(n-m)n-N+1n

2、-N+1n n第2页/共71页3 现将x1(n)和x2(n)延长至L(LN)，延长部分(从N到L-1)均填充为零值，计算x1(n)和x2(n)的L点循环卷积，得到 为了下面分析方便，先将x1(n)和x2(n)以L为周期进行延拓，得到两个周期序列和它们的周期卷积为第3页/共71页4注意到在区间0mL-1中，x1(m)L=x1(m)；并交换求和次序得 上式表明，x1(n)和x2(n)的周期卷积是它们的线性卷积的周期延拓。对周期卷积取主值，得到循环卷积 结论：x1(n)和x2(n)的循环卷积可被看作是它们的线性卷积的周期延拓的主值。第4页/共71页5那么，如何确定延拓的周期L呢？因为两个长度为N的序

3、列的线性卷积是一个长度为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。第5页/共71页6例1 已知序列x1(n)和x2(n)如下：othersnnx, 0240 , 1)(1othersnnx, 090 , 1)(2(1)求x1

4、(n)和x2(n)的25点循环卷积y1(n)(2)求x1(n)和x2(n)的34点循环卷积y2(n)解：21212( )( )( )( )*( )1,2,3,.,10,10,.,10,9,8,.,10,1,2,.,9,10,.,24,25,26,.330y nx nx nx nx nnothers110024( )0ny nothers(1)(2)1225( )(25 )( )qy ny nq Rn另外：第6页/共71页7othersnnx, 04 , 3 , 2 , 1 , 0, 1 , 2 , 3 , 2 , 1)(1othersnnx, 04 , 3 , 2 , 1 , 0, 3 , 2

5、 , 1 , 2 , 3)(2)(*)()(211nxnxny7212| )()()(Lnxnxny例2：已知请问序列y1(n)中的哪些值与序列y2(n)的值相同？解：217( )(7 )( )ry ny nr R n所以，当n=2,3,4,5,6时， y1(n) = y2(n)第7页/共71页8两种取样 时域取样: 对一个带限的离散时间信号，根据取样定理对其进行时域取样，所得取样信号的频谱是原带限信号频谱的周期延拓，因此，完全可以由取样信号恢复原信号。 频域取样: 3. 4 频率取样DFT与与DTFT的关系示意图的关系示意图 希望在频域上也可以进行采样而不丢失任何信息。而DFT实现了频域离散

6、化，使得频域上抽样也是可能的。第8页/共71页9 频率取样是指对序列的傅里叶变换或系统的频率特性进行取样。 本节讨论在什么条件下能够用得到的频谱取样值无失真地恢复原信号或系统。 设任意长序列x(n)绝对可和，其Z变换表示为如果在单位圆上对X(z)进行等角距取样，取样点数为M，则得 根据DFT的定义，对X(k)求反变换得 第9页/共71页10根据上面两式可得： 结论：在z平面的单位圆上对序列的Z域进行等角距取样，将导致时间序列的周期延拓。这一结果与对连续时间信号取样导致频谱周期延拓类似。 现在我们来考察xp(n)与原序列x(n)的关系，看它如何才能代表原序列x(n)。第10页/共71页11( )

7、()prxnx nrM对比：101( )()NpskXXkN第11页/共71页12 xp(n)是原非周期信号x(n)的周期延拓序列，因此xp(n)是一个周期序列，其主值为 在x(n)为有限长度N的情况下，如果取样点数MN，那么x(n)周期延拓的结果不会产生混叠。这时，xp(n)的主值xN(n)与原序列x(n)一样，因此xN(n)完全能代表原序列x(n)。 如果Mn时，要将x(l)和x(n)相互调换，即把原来存放x(n)的存储单元中的数据调入存储x(l)的存储单元中，而把原来存储x(l)的存储单元中的数据调入到存储x(n)的存储单元中。 这样，按自然序输入的数据x(n)经过变址计算后变成了码位倒

8、置的排列顺序，便可进入第1级的蝶形运算。 第63页/共71页64时间抽选FFT算法的 其他形式的流程图： 对于任何流程图，只要保持各节点所连支路及其传输系数不变，则不论节点位置怎样排列，所得到的流程图总是等效的，因而都能得到DFT的正确结果，只是数据的提取和存储次序不同而已。 图3. 22所示的流程图相当于最初由库利和图基给出的时间抽选算法。输入正序，输出混序 第64页/共71页65与图3. 19比较第65页/共71页66输入和输出都是正序排列这类流程图不能进行同址计算，因而需要两列长度为N的复数存储器。M(1)M(2)M(3)M(4)M(5)M(6)M(7)M(8)第66页/共71页67De

9、cimation-In-Frequency FFT 频率抽选基2FFT算法简称为频率抽选它的推导过程遵循两个规则： 对时间序列前后分； 对频率序列偶奇分。对比：时间抽选的分解过程遵循两条规则： 对时间序列偶奇分； 对频率序列前后分。3.5.4 频率抽选基2FFT算法第67页/共71页68 FFT算法同样可以应用于IDFT的计算，称为快速傅里叶反变换，简写为IFFT。前述DFT和IDFT公式为 比较上面两式，可以看出，只要把DFT公式中的系数 改为 ，并乘以系数1/N，就可用FFT算法来计算IDFT，这就得到了IFFT的算法。 3. 5. 5 IFFT的计算方法第68页/共71页69当把时间抽选FFT算法用于IFFT计算时，由于原来输入的时间序列x(n)现在变为频率序列X(k)，原来是将x(n)偶奇分的，而现在变成对X(k)进行偶奇分了，因此这种算法改