In Section 8.7.3, we showed that linear time-invariant filtering can be implemented by sectioning the input signal into finite-length segments and using the DFT to implement circular convolutions on these segments. The two methods discussed were called the overlap-add and the overlap-save methods. If the DFTs are computed using an FFT algorithm, these sectioning methods can require fewer complex multiplications per output sample than the direct evaluation of the convolution sum.
(a) Assume that the complex input sequence x[n] is of infinite duration and that the complex impulse response h[n] is of length P samples, so that h[n] ≠ 0 only for 0 ≤ n ≤ P - 1. Also, assume that the output is computed using the overlap-save method, with the DFTs of length L = 2ν , and suppose that these DFTs are computed using a radix-2 FFT algorithm. Determine an expression for the number of complex multiplications required per output sample as a function of ν and P.
(b) Suppose that the length of the impulse response is P = 500. By evaluating the formula obtained in part (a), plot the number of multiplications per output sample as a function of ν for the values of ν ≤ 20 such that the overlap-save method applies. For what value of ν is the number of multiplications minimal? Compare the number of complex multiplications per output sample for the overlap-save method using the FFT with the number of complex multiplications per output sample required for direct evaluation of the convolution sum.
(c) Show that for large FFT lengths, the number of complex multiplications per output sample is approximately ν. Thus, beyond a certain FFT length, the overlap-save method is less efficient than the direct method. If P = 500, for what value of ν will the direct method be more efficient?
(d) Assume that the FFT length is twice the length of the impulse response (i.e., L = 2P), and assume that L = 2ν . Using the formula obtained in part (a), determine the smallest value of P such that the overlap-save method using the FFT requires fewer complex multiplications than the direct convolution method.