In some applications in coding theory, it is necessary to compute a 63-point circular convolution of two 63-point sequences x[n] and h[n]. Suppose that the only computational devices a available are multipliers, adders, and processors that compute N-point DFT s, with N restricted to be a power of 2.

(a) It is possible to compute the 63-point circular convolution of x[n] and h[n] using a number of 64-point DFTs, inverse DFTs, and the overlap-add method. How many DFTs are needed? Consider each of the 63-point sequences as the sum of a 32-point sequence and 31-pont sequence.

(b) Specify an algorithm that computes the 63-point circular convolution of x[n] and h[n] using two 1278-point DFTs and one 128-point inverse DFT.

(c) We could also compute the 63-point circular convolution of x[n] and h[n] by computing their linear convolution in the rime domain and then aliasing the results. In terms of multiplications, which of these three methods is most efficient? Which is least efficient? (Assume that one complex multiplication requires four real multiplications and that x[n] and h[n] are real.)