Linear convolution via circular convolution

The linear convolution of sequences of lengths L = 4 and M = 2 has L + M − 1 = 5 samples. A circular convolution equals the linear convolution if the DFT length is N ≥ 5. So pad both sequences with zeros to N = 5:

• x[n] = {1, 1, 1, 1, 0}
• h[n] = {2, 3, 0, 0, 0}

y[n] = Σ (m = 0 to 4) x[m] h[(n − m) mod 5]

Matrix form (circulant formed from x, multiplied by the column h):

| 1 0 1 1 1 |   | 2 |   | 2 |
| 1 1 0 1 1 |   | 3 |   | 5 |
| 1 1 1 0 1 | · | 0 | = | 5 |
| 1 1 1 1 0 |   | 0 |   | 5 |
| 0 1 1 1 1 |   | 0 |   | 3 |

Row by row:

• y[0] = 1×2 + 0×3 = 2
• y[1] = 1×2 + 1×3 = 5
• y[2] = 1×2 + 1×3 = 5
• y[3] = 1×2 + 1×3 = 5
• y[4] = 0×2 + 1×3 = 3

Result: y[n] = {2, 5, 5, 5, 3}.

Check by direct linear convolution: y[n] = 2x[n] + 3x[n−1] gives {2, 5, 5, 5, 3}. The sum of the output (20) equals Σx × Σh = 4 × 5.

Method by DFT: y[n] = IDFT{ DFT₅(x) · DFT₅(h) } gives the same sequence.

Answer: y[n] = {2, 5, 5, 5, 3}.