Amodified discrete Fourier transform (MDFT) was proposed (Vernet, 1971) that computes sa...

Amodified discrete Fourier transform (MDFT) was proposed (Vernet, 1971) that computes samples of the z-transform on the unit circle offset from those computed by the DFT. In particular, with XM [k] denoting the MDFT of x(n),

Assume that N is even.

(a) The N-point MDFT of a sequence x[n] corresponds to the N-point DFT of a sequence xM [n], which is easily constructed from x[n]. Determine xM [n] in terms of x[n].

(b) If x[n] is real, not all the points in the DFT are independent, since the DFT is conjugate symmetric; i.e., X [k] = X ∗[((−k))N ] for 0 ≤ k ≤ N − 1. Similarly, if x[n] is real, not all the points in the MDFT are independent. Determine, for x[n] real, the relationship between points in XM [k].

(c) (i) Let R[k] = XM [2k]; that is, R[k] contains the even-numbered points in XM [k]. From your answer in part (b), show that XM [k] can be recovered from R[k]. (ii) R[k] can be considered to be the N/2-pointMDFTof an N/2-point sequence r[n]. Determine a simple expression relating r[n] directly to x[n]. According to parts (b) and (c), the N-point MDFT of a real sequence x[n] can be computed by forming r[n] from x[n] and then computing the N/2-point MDFT of r[n]. The next two parts are directed at showing that the MDFT can be used to implement a linear convolution.

(d) Consider three sequences x1[n], x2[n], and x3[n], all of length N. Let X1M [k], X2M [k], and X3M [k], respectively, denote the MDFTs of the three sequences. If X3M [k] = X1M [k]X2M [k], express x3[n] in terms of x1[n] and x2[n]. Your expression must be of the form of a single summation over a “combination” of x1[n] and x2[n] in the same style as (but not identical to) a circular convolution.

(e) It is convenient to refer to the result in part (d) as a modified circular convolution. If the sequences x1[n] and x2[n] are both zero for n ≥ N/2, show that the modified circular convolution of x1[n] and x2[n] is identical to the linear convolution of x1[n] and x2[n].