Find x3[n] from X3=X1X2 (1,2,4)

The DFT length is not stated; the smallest size that holds both sequences is N = 4 (the length of x2), so x1[n] is padded with one zero and 4-point DFTs are used. (If a 6-point DFT were used, the result would equal the linear convolution {-1, 0, 3, 15, 14, 4}.) Since X3(k) = X1(k)·X2(k), x3[n] is the 4-point circular convolution of x1[n] and x2[n] (multiplication of DFTs ⇔ circular convolution). Pad the shorter sequence(s) with zeros to N = 4:

• x1[n] = {1, 2, 4, 0}
• x2[n] = {-1, 2, 3, 1}

x3[n] = Σ (m = 0 to 3) x1[m] · x2[(n − m) mod 4]

Written as a matrix product (first column of the circulant is x1, each later column is the previous one shifted down circularly):

|    1    0    4    2 |   | -1 |
|    2    1    0    4 |   | 2 |
|    4    2    1    0 |   | 3 |
|    0    4    2    1 |   | 1 |

Row by row:

• x3[0] = (1)(-1) + (0)(2) + (4)(3) + (2)(1) = 13
• x3[1] = (2)(-1) + (1)(2) + (0)(3) + (4)(1) = 4
• x3[2] = (4)(-1) + (2)(2) + (1)(3) + (0)(1) = 3
• x3[3] = (0)(-1) + (4)(2) + (2)(3) + (1)(1) = 15

Check using DFTs: X1(k)·X2(k) for k = 0 … 3 has the inverse DFT {13, 4, 3, 15} (Σx3 = 35 = X1(0)·X2(0) = 7×5 = 35).

Answer: x3[n] = {13, 4, 3, 15}, n = 0 … 3.