Let x[n] and h[n] be two real finite-length sequences such that
We wish to compute the sequence y[n] = x[n]∗h[n], where ∗ denotes ordinary convolution.
(a) What is the length of the sequence y[n]?
(b) For direct evaluation of the convolution sum, how many real multiplications are required to compute all of the nonzero samples of y[n]? The following identity may be usefuL
(c) State a procedure for using the DFT to compute all of the nonzero samples of y[n]. Determine the minimum size of the DFTs and inverse DFTs in terms of L and P.
(d) Assume that L = P = N/2, where N = 2ν is the size of the DFT. Determine a formula for the number of real multiplications required to compute all the nonzero values of y[n] using the method of part
(c) if the DFTs are computed using a radix- 2 FFT algorithm. Use this formula to determine the minimum value of N for which the FFT method requires fewer real multiplications than the direct evaluation of the convolution sum