9,0 Introduction Implement a convolution of two sequences by the following procedure: 1.Compute the N-point DFTXk and X2k of two sequencen and x2[n; X[闪-∑W 2.Compute for0≤k≤W-1i ◆3.Compute x,m=x[mx,[刊as the inverse DFT ofX[W· 网N-大空[kw -C Why not convolve the two sequences directly? Since DFT has efficient FFT(Fast Fourier Transform algorithms that can be orders of magnitude(数量级 2n,10)more efficient than others. 33 9.0 Introduction ◆1. Compute the N-point DFT and of two sequence and ; X k 1   X k 2   x n1   x n2   ◆2. Compute for ; X k X k X k 3 1 2  =     0  k  N −1 ◆3. Compute as the inverse DFT of . X k 3   x3 n=x n1  N x n2   ◆Implement a convolution of two sequences by the following procedure: ◆Why not convolve the two sequences directly? ◆Since DFT has efficient FFT ( Fast Fourier Transform ) algorithms that can be orders of magnitude(数量级 2 n ,10n ) more efficient than others. 1 2       1 3 0 1 N kn N k x n N X k N x n W − − = =          (( ))  1 3 1 2 0 1 2 N N m x n x m x n N n x x n m − = = = −      1 0 N kn N n X k n x W − = =