Let $x[n]$ and $h[n]$ be two real finite$-$length sequences such that

$x[n]=0$ for $n$ outside the interval $0nL-1$

$h[n]=0$ for $n$ outside the interval $0nP-1$

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 the nonzero samples of $y[n]?$ The following identity may be useful:

${\displaystyle \underset{k=1}{\overset{N}{}}}k=\frac{N(N+1)}{2}$

$($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 the inverse DFTs in terms of L and P $.$

$($d$)$ Assume that $L=P=\frac{N}{2},$ where $N=2^v$ 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.