ToolSphere
Back to all articles
student

Discrete Convolution Example: Step by Step

2026-11-109 min read

Try it: free Discrete Convolution Calculator

Compute linear convolution, circular convolution, and DFT

Open →

Discrete convolution is the foundation of digital signal processing (DSP) and discrete-time signals and systems. Whenever an input sequence passes through a Linear Time-Invariant (LTI) system, the output sequence equals the discrete convolution of the input with the system unit impulse response.

Whether you are designing digital filters, processing audio streams, blurring image matrices, or preparing for a signals and systems midterm, understanding how convolution works mechanically is essential. This guide walks through:

  1. Linear convolution using the step-by-step flip-and-slide method with a complete arithmetic table.
  2. The fast tabular/matrix multiplication method used to verify manual calculations.
  3. Handling sequences with negative indices and non-zero origins.
  4. Circular (cyclic) convolution and how periodic boundary wrapping leads to time-domain aliasing.
  5. The Circular Convolution Theorem connecting time-domain convolution directly to the Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT).

1. Mathematical definition and length rules

In discrete time, the linear convolution of two signals x[n] and h[n] is denoted by the asterisk operator (*) and defined by the convolution sum:

y[n] = x[n] * h[n] = ∑_{k = -∞}^{∞} x[k] · h[n - k]

Because discrete convolution is commutative, flipping either signal produces the exact same output:

x[n] * h[n] = h[n] * x[n] = ∑_{k = -∞}^{∞} h[k] · x[n - k]

Output length and index support

When convolving two finite-duration sequences of lengths Lx and Lh:

  1. Total output samples: The convolved sequence contains exactly Ly = Lx + Lh - 1 samples.
  2. Starting index: If x[n] begins at index n_x and h[n] begins at index n_h, the output y[n] begins at n_start = n_x + n_h.
  3. Ending index: The output ends at n_end = n_start + Ly - 1.

For standard causal sequences starting at n = 0, an input of length 4 and an impulse response of length 3 yield an output of length 4 + 3 - 1 = 6 samples, spanning indices n = 0, 1, 2, 3, 4, 5.


2. Linear convolution via flip-and-slide (worked example)

Let us solve a classic textbook example step by step:

  • Input sequence: x[n] = [1, 2, 3, 4] (length Lx = 4, non-zero for n = 0, 1, 2, 3)
  • Impulse response: h[n] = [1, 1, 1] (length Lh = 3, non-zero for n = 0, 1, 2)

Because both signals start at n = 0, the output y[n] spans from n = 0 to n = 4 + 3 - 1 = 5 (6 output samples).

The 4 mechanical steps

To compute each output sample y[n]:

  1. Change the independent variable: Plot x[k] and h[k] against a dummy index k.
  2. Flip (time-reversal): Reflect h[k] across the vertical axis k = 0 to form h[-k] = [1, 1, 1], running backwards across k = 0, -1, -2.
  3. Slide (shift by n): Shift the reversed sequence rightward by n positions to create h[n - k]. The leading sample now sits at k = n.
  4. Multiply and sum: Multiply the overlapping samples of x[k] and h[n - k] point-for-point along the k axis, then sum all products to get y[n].

Full flip-and-slide calculation table

The following table traces every shift index n from 0 to 5, listing the active overlap range of k, the individual product terms, and the resulting sum:

Output sample n Shifted impulse response h[n - k] over active k Overlapping products x[k] · h[n - k] Arithmetic steps y[n]
n = 0 h[0 - k] overlaps x[k] only at k = 0 x[0] · h[0] (1)(1) 1
n = 1 h[1 - k] overlaps x[k] at k = 0, 1 x[0] · h[1] + x[1] · h[0] (1)(1) + (2)(1) = 1 + 2 3
n = 2 h[2 - k] overlaps x[k] at k = 0, 1, 2 x[0] · h[2] + x[1] · h[1] + x[2] · h[0] (1)(1) + (2)(1) + (3)(1) = 1 + 2 + 3 6
n = 3 h[3 - k] overlaps x[k] at k = 1, 2, 3 x[1] · h[2] + x[2] · h[1] + x[3] · h[0] (2)(1) + (3)(1) + (4)(1) = 2 + 3 + 4 9
n = 4 h[4 - k] overlaps x[k] at k = 2, 3 x[2] · h[2] + x[3] · h[1] (3)(1) + (4)(1) = 3 + 4 7
n = 5 h[5 - k] overlaps x[k] only at k = 3 x[3] · h[2] (4)(1) 4

For any shift n < 0 or n > 5, there is zero overlap between x[k] and h[n - k], producing y[n] = 0.

The complete convolved sequence is:

y[n] = [1, 3, 6, 9, 7, 4]   for n = 0, 1, 2, 3, 4, 5

3. The matrix multiplication / grid method

On exams, writing out full flip-and-slide sketches for long sequences takes valuable time. The multiplication grid (polynomial multiplication table) computes identical answers much faster and avoids indexing errors.

Write the samples of x[n] along the rows and the samples of h[n] along the columns:

  x \ h  |    1    |    1    |    1   
---------+---------+---------+--------
    1    |    1    |    1    |    1   
    2    |    2    |    2    |    2   
    3    |    3    |    3    |    3   
    4    |    4    |    4    |    4   

Now sum the numbers along the anti-diagonals (from top-right down to bottom-left):

  • Diagonal 0 (n = 0): 1 = 1
  • Diagonal 1 (n = 1): 1 + 2 = 3
  • Diagonal 2 (n = 2): 1 + 2 + 3 = 6
  • Diagonal 3 (n = 3): 2 + 3 + 4 = 9
  • Diagonal 4 (n = 4): 3 + 4 = 7
  • Diagonal 5 (n = 5): 4 = 4

This yields y[n] = [1, 3, 6, 9, 7, 4].

The sum verification check

You can instantly check your manual arithmetic using the discrete convolution sum property: the sum of the output samples must equal the sum of the input samples multiplied by the sum of the impulse response samples:

∑ y[n] = (∑ x[n]) × (∑ h[n])
  • Input sum: 1 + 2 + 3 + 4 = 10
  • Impulse response sum: 1 + 1 + 1 = 3
  • Expected output sum: 10 × 3 = 30
  • Actual output sum: 1 + 3 + 6 + 9 + 7 + 4 = 30

Because 30 = 30, the arithmetic is verified.


4. Handling negative origins and non-causal signals

Not all signals start at n = 0. When sequences contain negative indices, track the origin (n = 0) carefully.

Consider:

  • x[n] = [2, 1, -1] with origin at index 1 (x[-1] = 2, x[0] = 1, x[1] = -1)
  • h[n] = [1, 2] with origin at index 0 (h[0] = 1, h[1] = 2)

Step 1: Find the index range

  • x[n] spans n ∈ [-1, 1] (Lx = 3)
  • h[n] spans n ∈ [0, 1] (Lh = 2)
  • Output length: Ly = 3 + 2 - 1 = 4 samples
  • Starting index: n_start = -1 + 0 = -1
  • Ending index: n_end = 1 + 1 = 2

Step 2: Compute each sample

  • n = -1: x[-1] · h[0] = (2)(1) = 2
  • n = 0: x[-1] · h[1] + x[0] · h[0] = (2)(2) + (1)(1) = 4 + 1 = 5
  • n = 1: x[0] · h[1] + x[1] · h[0] = (1)(2) + (-1)(1) = 2 - 1 = 1
  • n = 2: x[1] · h[1] = (-1)(2) = -2

The convolved result is y[n] = [2, 5, 1, -2] spanning n = -1, 0, 1, 2, with the origin sample y[0] = 5.


5. Circular convolution and time-domain aliasing

While linear convolution models real physical LTI filters acting on continuous or streaming discrete signals, digital computers compute frequency representations via the Discrete Fourier Transform (DFT) and Fast Fourier Transform (FFT). The DFT operates fundamentally on finite, periodic blocks of length N.

The circular (cyclic) convolution of two N-point sequences x[n] and h[n] is defined by:

y_c[n] = x[n] ⊛_N h[n] = ∑_{k = 0}^{N - 1} x[k] · h[((n - k) mod N)]

Instead of shifting samples indefinitely into zero-padded space, the circular shift wraps samples that slide off the right boundary back into the left boundary modulo N.

The circulant matrix formulation

Circular convolution can be expressed as a matrix-vector product y_c = H_circ · x, where H_circ is an N × N circulant matrix formed by circularly shifting h[n] downward:

Let us compute the circular convolution of our earlier signals with N = 4:

  • x[n] = [1, 2, 3, 4] (length 4)
  • h[n] = [1, 1, 1, 0] (zero-padded to length N = 4)

The circulant matrix H_circ is:

[ 1   0   1   1 ]   [ 1 ]     [ (1)(1) + (0)(2) + (1)(3) + (1)(4) ]     [ 8 ]
[ 1   1   0   1 ]   [ 2 ]     [ (1)(1) + (1)(2) + (0)(3) + (1)(4) ]     [ 7 ]
[ 1   1   1   0 ] × [ 3 ]  =  [ (1)(1) + (1)(2) + (1)(3) + (0)(4) ]  =  [ 6 ]
[ 0   1   1   1 ]   [ 4 ]     [ (0)(1) + (1)(2) + (1)(3) + (1)(4) ]     [ 9 ]

The resulting circular convolution sequence is:

y_c[n] = [8, 7, 6, 9]   for n = 0, 1, 2, 3

Notice that y_c = [8, 7, 6, 9] does not match the linear convolution y = [1, 3, 6, 9, 7, 4].

Why they differ: Time-domain aliasing

Circular convolution equals the periodic summation of the linear convolution folded over intervals of length N:

y_c[n] = ∑_{r = -∞}^{∞} y_linear[n + r · N]

For N = 4, our linear convolution has 6 samples (y_linear[0] through y_linear[5]). The samples at index n ≥ 4 wrap around and add into the front of the block:

  • n = 0: y_c[0] = y_linear[0] + y_linear[0 + 4] = 1 + 7 = 8
  • n = 1: y_c[1] = y_linear[1] + y_linear[1 + 4] = 3 + 4 = 7
  • n = 2: y_c[2] = y_linear[2] = 6
  • n = 3: y_c[3] = y_linear[3] = 9

The tail samples y_linear[4] = 7 and y_linear[5] = 4 wrap into samples 0 and 1. This distortion is known as time-domain aliasing.


6. How circular convolution relates to the DFT

Why do DSP textbooks and hardware systems emphasize circular convolution if it causes aliasing? Because of the Circular Convolution Theorem:

DFT_N{ x[n] ⊛_N h[n] } = X[k] · H[k]

Pointwise multiplication of two DFT spectra in the frequency domain corresponds to circular convolution in the discrete-time domain.

Let us verify this theorem step by step using the 4-point DFT of our sequences.

Step 1: 4-point DFT of x[n] = [1, 2, 3, 4]

Using X[k] = ∑_{n=0}^{3} x[n] · e^(-j · 2π · k · n / 4):

  • X[0] = 1 + 2 + 3 + 4 = 10
  • X[1] = 1(1) + 2(-j) + 3(-1) + 4(j) = -2 + j2 (magnitude 2.8284 ∠ 135°)
  • X[2] = 1(1) + 2(-1) + 3(1) + 4(-1) = -2 (magnitude 2 ∠ 180°)
  • X[3] = 1(1) + 2(j) + 3(-1) + 4(-j) = -2 - j2 (magnitude 2.8284 ∠ -135°)

Step 2: 4-point DFT of h[n] = [1, 1, 1, 0]

  • H[0] = 1 + 1 + 1 + 0 = 3
  • H[1] = 1(1) + 1(-j) + 1(-1) + 0(j) = -j1 (magnitude 1 ∠ -90°)
  • H[2] = 1(1) + 1(-1) + 1(1) + 0(-1) = 1 (magnitude 1 ∠ 0°)
  • H[3] = 1(1) + 1(j) + 1(-1) + 0(-j) = j1 (magnitude 1 ∠ 90°)

Step 3: Pointwise frequency multiplication X[k] · H[k]

  • k = 0: (10) · (3) = 30
  • k = 1: (-2 + j2) · (-j1) = 2 + j2
  • k = 2: (-2) · (1) = -2
  • k = 3: (-2 - j2) · (j1) = 2 - j2

Step 4: Compare with the 4-point DFT of circular output y_c[n] = [8, 7, 6, 9]

Evaluating the DFT of y_c[n]:

  • Y_c[0] = 8 + 7 + 6 + 9 = 30
  • Y_c[1] = 8(1) + 7(-j) + 6(-1) + 9(j) = 2 + j2
  • Y_c[2] = 8(1) + 7(-1) + 6(1) + 9(-1) = -2
  • Y_c[3] = 8(1) + 7(j) + 6(-1) + 9(-j) = 2 - j2

The frequency-domain product X[k] · H[k] matches Y_c[k] across every single bin.


7. Computing linear convolution via DFT/FFT (Zero-padding)

Because direct linear convolution takes O(Lx · Lh) arithmetic operations, evaluating long filters on long audio signals directly in the time domain is computationally expensive.

The FFT allows us to perform convolution in O(N log N) time, but we must prevent time-domain aliasing so that circular convolution yields the true linear convolution.

The zero-padding rule

To ensure circular convolution produces exact linear convolution without aliasing:

N ≥ Lx + Lh - 1

For our signals (Lx = 4, Lh = 3), the minimum transform size is:

N ≥ 4 + 3 - 1 = 6

Zero-pad both sequences to N = 6:

  • x_padded = [1, 2, 3, 4, 0, 0]
  • h_padded = [1, 1, 1, 0, 0, 0]

When we compute the 6-point circular convolution:

y_c[n] = [1, 3, 6, 9, 7, 4]   for n = 0, 1, 2, 3, 4, 5

Because N = 6, no samples fold over r ≥ 1. The circular result matches the linear convolution y[n] sample-for-sample.

Practical DSP workflow (Fast Convolution)

In real-world DSP applications (such as graphic equalizers, room impulse response simulation, and software-defined radio):

  1. Choose a power-of-two FFT size N ≥ Lx + Lh - 1 (for example, N = 8 or 1024).
  2. Zero-pad input x[n] and impulse response h[n] to length N.
  3. Compute X[k] = FFT{x_padded} and H[k] = FFT{h_padded}.
  4. Multiply bin-by-bin: Y[k] = X[k] · H[k].
  5. Compute the inverse transform: y[n] = IFFT{Y[k]}.
  6. Discard numerical rounding residue to retrieve the exact linear convolution.

For streaming continuous signals where input length is infinite, block-processing techniques such as overlap-add and overlap-save divide the stream into segments, convolve each block via FFT, and stitch the outputs together seamlessly.


8. Summary and exam checklist

Concept Linear convolution Circular convolution
Notation x[n] * h[n] x[n] ⊛_N h[n]
Output length Lx + Lh - 1 Exactly N
Shift mechanism Slides linearly to ±infinity Circular shift modulo N
Frequency domain dual DTFT: X(e^{jω}) · H(e^{jω}) DFT: X[k] · H[k]
Aliasing None Aliased unless N ≥ Lx + Lh - 1
Primary application Physical filter response Fast block convolution via FFT

5-Step homework verification checklist

  1. Calculate output length first: Before convolving, check Ly = Lx + Lh - 1. If your answer has fewer or more terms, look for missing overlap shifts.
  2. Find starting index: Add the starting index of x to the starting index of h.
  3. Use the sum property to check arithmetic: Make sure ∑ y[n] = (∑ x[n]) × (∑ h[n]).
  4. Distinguish circular vs. linear: If an exam asks for circular convolution of length N, pad both signals to N and wrap indices modulo N.
  5. Zero-pad before using DFT: Never multiply DFT coefficients to find linear convolution without checking that N ≥ Lx + Lh - 1.

Use the Discrete Convolution Calculator to work through your own convolution example. Use the Fourier Series Drawing to explore a visual Fourier example alongside the signal calculations. For a related walkthrough, read Bode Plot: Gain and Phase Margin Example.

Looking for other tools?

Explore ToolSphere Homepage →