8.9用离散傅里叶变换实现线性卷积 根据线性卷积的原理 :
x[n] ? y[n] DTF T X(e jω)Y( e jω), 且，
w[n] = x[n] ? y[n] 可用下式求得： F－1 {X(e jω)Y( e jω)}. 线性与圆周卷积分别由下式给出：
w[n]?x[n]?y[n]?m????x[m]y[n?m]N?1m?0?wp[n]?x[n] y[n]??x[m]y[((n?m))N]RN[n]N 何时 wp[n] 等于 w[n] ? 注意:
设: x[n] : 0≤n ≤P －1 ? 0≤m ≤P －1
y[n]: 0≤n ≤L －1 ? 0≤n － m ≤L －1 w[n]的最大长度为 ：L+P-1. 单 wp[n] 的长度为 N. 时域分析：
wp[n]??x[m]y[((n?m))N]RN[n]m?0N?1 ??(x[m]?y[n?m?kN])RN[n]m?0?k???N?1? ? ?k???m?0???x[m]y[(n?kN)?m]R?w[n?kN]RN?1m?0NN?1N[n] [n]k???其中, w[n]??x[m]y[n?m].若 N?L?P-1, w[n]?x[n]?y[n]?wp[n].频域分析：
w[n]?x[n]?y[n],???n??.W(ej?)?X(ej?)Y(ej?),???R.For??2?k/N,~~~j2?k/NW(k)?W(e)?X(e)Y(e)?X(k)Y(k)~~W(k)?X(k)Y(k)RN(k)?X(k)Y(k).jj2?kN2?kNIf N?L?P-1, W(k)?WP(k)?X(k)Y(k), so W(k) is 下列两项的DFT : ?r????w[n?rN],?0?n?N?1x[n] N y[n]
?X(k)Y(k)
?若无重叠，则, wp[n] = w[n]
8.9.2用 DFT实现线性卷积的例子 例8-13 N1=P=11 N2= L=15
x[n] y[n] y[?n] y[1?n] y[2?n]y[23?n]y[24?n]8-23 图
x[n] y[n] y[N?n] y[N?n?1] y[N?n?2]y[N?n?23]y[ N?n?24]
例8-14 N1= N2= 15
x[n] y[n] y[?n] y[1?n] y[2?n]y[13?n]y[14?n]
x[n] y[n]y[((?n))15]y[((1?n))15]]y[((2?n))15]y[((13?n))15]y[((14?n))15]图8-24
例8-15 N1= N2= 15
x[n] y[n] y[?n] y[1?n] y[2?n]y[13?n]y[14?n] x[n] y[n]y[((?n))15]y[((1?n))15]]y[((2?n))15]y[((13?n))15] y[((14?n))15]图8-25
小结:
当N≥L+P －1 , wp[n] = w[n]; 当 N ≤ L+P－1, wp[n] ≠ w[n]; 线性与圆周卷积一致的样本为:
P+L－N－1≤n≤N －1 8.9.3 用DFT的LTI系统的实现 （1）原理
LTI 系统: 如 x[n] (0?n?L-1) 为输入信号； h[n] (0?n?P-1)为 为系统的脉冲响应：则 , y[n]?x[n]?h[n] , (0?n?L?P-2).进一步，若 DFT(x[n])?X(k), DFT(h[n])?H(k) x[n] y[n]?X[k]H[k] N?L?P-1, x[n]?h[n]?x[n] y[n]?IDFT(X(k)H(k)).用DFT 实现 LTI 系统 DFT:(1) x[n]?X(k); h[n]?H[k](2) Y(k)?X(k)H(k)(3) y[n]?IDFT?X(k)Y(k)?当x(n)的点数很多时，即当L>>M。通常不允许等x(n)全部采集齐后再进行卷积; 否则，使输出相对于输入有较长的延时。此外，若
N=L+M-1 太大，h(n)必须补很多个零值点，很不经济，且FFT的计算时间也要很长。这时FFT法的优点就表现不出来了，因此需要采用分段卷积或称分段过滤的办法。即将x(n)分成点数和h(n)相仿的段，分别求出每段的卷积结果，然后用一定方式把它们合在一起，便得到总的输出，其中每一段的卷积均采用FFT方法处理。有两种分段卷积的办法: 重叠相加法和重叠保留法。
（２）重叠相加法
设h(n)的点数为M，信号x(n)为很长的序列。我们将x(n)分解为很多段，每段为L点，L选择成和M的数量级相同，用xi(n)表示x(n)的第i段：
?x(n)xi(n)???0iL≤n≤(i+1)L-1 其他n
i=0, 1, … （8-68）
则输入序列可表示成
? （8-69）
x((nn))和??)i(这样，xh(xn)n的线性卷积等于各xi(n)与h(n)的线性卷积
i?0之和，即
? （8-70） (n)?x(n)?h(n)?yxi(n)?h(n)每一个xi(n)*h(n)都可用上面讨论的快速卷积办法来运算。 i?0由于xi(n)*h(n)为L+M-1 点，故先对xi(n)及h(n)补零值点，补到N点。 为便于利用基-2 FFT算法，一般取N=2m≥L+M-1，然后作N点的圆周卷积：
?yi(n)?xi(n)N 由于xi(n)为L点，而yi(n)为（L+M-1）点（设N=L+M-1），
故相邻两段输出序列必然有（M-1）个点发生重叠，即前一段的后（M-1）个点和后一段的前（M-1）个点相重叠，如图8-26 所示。按照式（8-70），应该将重叠部分相加再和不重叠的部分共同组成输出y(n)。
h(n) 0N－1nM－1 x(n)
L
0x0(n)0x(n)L－1N－1L＋N－1n2L3Lnh(n)