In many applications, there is a need to convolve long sequences x[n] and h[n] whose sam...

In many applications, there is a need to convolve long sequences x[n] and h[n] whose samples are integers. Since the sequences have integer coefficients, the result of the convolution y[n] = x[n] ∗ h[n] will naturally also have integer coefficients as well. A major drawback of computing the convolution of integer sequences with FFTs is that floating-point arithmetic chips are more expensive than integer arithmetic chips. Also, rounding noise introduced during a floating-point computation may corrupt the result. In this problem, we consider a class of FFT algorithms known as number-theoretic transforms (NTTs), which overcome these drawbacks.

(a) Let x[n] and h[n] be N-point sequences and denote their DFTs by X[k] and H[k], respectively. Derive the circular convolution property of the DFT. Specifically, show that Y [k] = X[k]H[k], where y[n] is the N-point circular convolution of x[n] and h[n]. Show that the circular convolution property holds as long as WN in the DFT satisfies

The key to defining NTTs is to find an integer-valued WN that satisfies Eq. (P9.59- 1). This will enforce the orthogonality of the basis vectors required for the DFT to function properly. Unfortunately, no integer-valued WN exists that has this property for standard integer arithmetic. In order to overcome this problem, NTTs use integer arithmetic defined modulo some integer P. Throughout the current problem, we will assume that P = 17. That is, addition and multiplication are defined as standard integer addition and multiplication, followed by modulo P = 17 reduction. For example, ((23+18))17 = 7, ((10+7))17 = 0, ((23×18))17 = 6, and ((10×7))17 = 2. (Just compute the sum or product in the normal way, and then take the remainder modulo 17.)

(b) Let P = 17, N = 4, and WN = 4. Verify that

(c) Let x[n] and h[n] be the sequences

Compute the 4-point NTT X[k] of x[n] as follows:

Compute H [k] in a similar fashion. Also, compute Y [k] = H[k]X[k]. Assume the values of P,N, and WN given in part (a). Be sure to use modulo 17 arithmetic for each operation throughout the computation, not just for the final result!

(d) The inverse NTT of Y [k] is defined by the equation

In order to compute this quantity properly, we must determine the integers (1/N)⁻¹ and such that

Use the values of P, N, andWN given in part (a), and determine the aforesaid integers.

(e) Compute the inverse NTT shown in Eq. (P9.59-2) using the values of (N) −1 and W −1 N determined in part (d). Check your result by manually computing the convolution y[n] = x[n] ∗ h[n].