ToolSphere

Discrete Convolution Calculator

Computer science

Calculate linear convolution with the flip-and-slide table, circular convolution, and N-point DFT with magnitude and phase steps online.

Signals & Systems Output

Linear Convolution y[n]

Output Sequence:[1, 3, 6, 9, 7, 4]
Length L_y = 6Range: n = 0 to 5Origin n=0 at index 0

Sequence Parameters

Comma, space, or bracket-separated samples. Fractions like 1/2 or -3/4 are supported.

Filter kernel or second sequence for convolution.

Index in the sequence array where sample time n = 0 is located (default 0).

Index in the kernel array where sample time n = 0 is located (default 0).

Flip-and-Slide Step-by-Step Table

h[n - k] is flipped to h[-k] and shifted by n, then multiplied term-by-term with x[k].

nOverlapping kx[k] · h[n - k] ProductsSum y[n]
n = 0k ∈ {0}(1)(1) = 11
n = 1k ∈ {0, 1}(1)(1) + (2)(1) = 33
n = 2k ∈ {0, 1, 2}(1)(1) + (2)(1) + (3)(1) = 66
n = 3k ∈ {1, 2, 3}(2)(1) + (3)(1) + (4)(1) = 99
n = 4k ∈ {2, 3}(3)(1) + (4)(1) = 77
n = 5k ∈ {3}(4)(1) = 44

Multiplication Table (Matrix Grid)

Rows represent x[i], columns represent h[j]. Antidiagonals sum directly to y[n].

x \ hh[0] = 1h[1] = 1h[2] = 1
x[0] = 1111
x[1] = 2222
x[2] = 3333
x[3] = 4444

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Discrete Convolution Calculator

  1. 1Enter sample values for discrete sequence x[n] and filter kernel h[n] separated by commas or spaces.
  2. 2Optionally set the 0-based index of origin n=0 for each sequence if samples start at negative time indices.
  3. 3Switch between Linear Convolution, Circular Convolution, and N-Point DFT tabs to inspect different signal representations.
  4. 4Examine the flip-and-slide table to trace x[k] and flipped, shifted h[n - k] products for every sample point n.
  5. 5Check the circulant matrix and time-domain aliasing table to verify whether circular convolution matches linear convolution.
  6. 6Review the N-point DFT table for frequency bin magnitudes, phases in degrees, rectangular coordinates, and Parseval energy.

About Discrete Convolution Calculator

Discrete linear convolution in signals and systems

Discrete convolution is the foundational operation of discrete-time Linear Time-Invariant (LTI) systems. When an arbitrary digital sequence x[n] enters an LTI system characterized by its unit impulse response h[n], the system output y[n] is completely determined by the convolution sum:

y[n] = (x * h)[n] = ∑ x[k] · h[n - k]

In introductory signals and systems courses (such as MIT 6.003, UC Berkeley EECS 16A/B, and Georgia Tech ECE 2026), students learn to compute this sum using two primary representations: the graphical or tabular flip-and-slide method, and the polynomial multiplication matrix table.

The flip-and-slide method step by step

The flip-and-slide technique visualizes convolution as a five-step procedure along a dummy time index k:

  1. Plot against k: Express both sequences as functions of the independent variable k, yielding x[k] and h[k].
  2. Reflect (flip): Invert the kernel sequence h[k] about the origin k = 0 to produce the time-reversed sequence h[-k].
  3. Shift (slide): Advance or delay the flipped sequence by n sample intervals along k, producing h[n - k]. When n is negative, the sequence slides left; when n is positive, it slides right.
  4. Multiply: Take the point-by-point product of x[k] and the shifted sequence h[n - k] wherever both signals have nonzero overlapping values.
  5. Sum: Add all the resulting products together to obtain the single output sample y[n]. Repeat for each integer n where an overlap exists.

Consider the textbook example where input sequence x[n] = [1, 2, 3, 4] (length Lx = 4, starting at n = 0) and filter kernel h[n] = [1, 1, 1] (length Lh = 3, starting at n = 0). The total length of the linear convolution output is Ly = Lx + Lh - 1 = 4 + 3 - 1 = 6 samples, spanning n = 0 through n = 5:

  • n = 0: Overlap occurs only at k = 0. We compute x[0] · h[0] = (1)(1) = 1. Thus y[0] = 1.
  • n = 1: Overlap spans k = 0 and k = 1. We compute x[0] · h[1] + x[1] · h[0] = (1)(1) + (2)(1) = 1 + 2 = 3. Thus y[1] = 3.
  • n = 2: Overlap spans k = 0, 1, and 2. We compute (1)(1) + (2)(1) + (3)(1) = 1 + 2 + 3 = 6. Thus y[2] = 6.
  • n = 3: Overlap spans k = 1, 2, and 3. We compute (2)(1) + (3)(1) + (4)(1) = 2 + 3 + 4 = 9. Thus y[3] = 9.
  • n = 4: Overlap spans k = 2 and 3. We compute (3)(1) + (4)(1) = 3 + 4 = 7. Thus y[4] = 7.
  • n = 5: Overlap occurs only at k = 3. We compute (4)(1) = 4. Thus y[5] = 4.

The resulting linear convolution output sequence is y[n] = [1, 3, 6, 9, 7, 4].

Multiplication matrix and polynomial equivalence

Discrete convolution is algebraically identical to multiplying two polynomials whose coefficients correspond to sequence values. Arranging sequence x[n] along the rows and h[n] along the columns creates a rectangular multiplication grid:

  • Row 0 (x[0] = 1): 1×1 = 1, 1×1 = 1, 1×1 = 1
  • Row 1 (x[1] = 2): 2×1 = 2, 2×1 = 2, 2×1 = 2
  • Row 2 (x[2] = 3): 3×1 = 3, 3×1 = 3, 3×1 = 3
  • Row 3 (x[3] = 4): 4×1 = 4, 4×1 = 4, 4×1 = 4

Summing entries along each antidiagonal (lines of constant r + c = n) directly yields the convolved sequence: diagonal 0 gives 1; diagonal 1 gives 1 + 2 = 3; diagonal 2 gives 1 + 2 + 3 = 6; diagonal 3 gives 2 + 3 + 4 = 9; diagonal 4 gives 3 + 4 = 7; and diagonal 5 gives 4.

Circular convolution and time-domain aliasing

Unlike linear convolution, circular (cyclic) convolution operates on periodic sequences or finite sequences of fixed length N evaluated modulo N:

y_c[n] = (x ⊛ h)[n] = ∑ x[k] · h[((n - k) mod N)]

In matrix notation, circular convolution corresponds to matrix-vector multiplication y_c = H_circ · x, where H_circ is an N × N circulant matrix whose columns are successive cyclic right shifts of h[n].

According to the Circular Convolution Theorem, circular convolution is equivalent to the periodic folding of linear convolution:

y_c[n] = ∑ y_lin[n + r · N]

When N is smaller than the linear output length (N < Lx + Lh - 1), trailing samples wrap around and add back onto earlier samples, producing time-domain aliasing. For example, computing circular convolution of x = [1, 2, 3, 4] and h = [1, 1, 1] with N = 4 produces:

  • y_c[0] = y_lin[0] + y_lin[4] = 1 + 7 = 8
  • y_c[1] = y_lin[1] + y_lin[5] = 3 + 4 = 7
  • y_c[2] = y_lin[2] = 6
  • y_c[3] = y_lin[3] = 9

The resulting aliased circular sequence is y_c[n] = [8, 7, 6, 9]. To prevent aliasing and make circular convolution equal to linear convolution, both sequences must be zero-padded to at least N ≥ Lx + Lh - 1. For this example, setting N = 6 yields y_c = [1, 3, 6, 9, 7, 4], matching the linear result exactly. This principle forms the basis for fast convolution algorithms using the Fast Fourier Transform (FFT).

Discrete Fourier Transform (DFT) and Parseval relation

The Discrete Fourier Transform converts a finite sequence x[n] of length N into its frequency spectrum X[k] across N discrete bins:

X[k] = ∑ x[n] · e^(-j · 2π · k · n / N)

Each bin k corresponds to continuous frequency ω = 2πk / N radians per sample. For a real-valued input sequence, the DFT exhibits conjugate symmetry: X[N - k] = X*[k].

For x[n] = [1, 2, 3, 4] with N = 4:

  • k = 0 (DC component): X[0] = 1 + 2 + 3 + 4 = 10, magnitude 10, phase 0°
  • k = 1: X[1] = 1 - j2 - 3 + j4 = -2 + j2, magnitude √(4 + 4) = 2.8284, phase 135°
  • k = 2 (Nyquist bin): X[2] = 1 - 2 + 3 - 4 = -2, magnitude 2, phase 180°
  • k = 3: X[3] = 1 + j2 - 3 - j4 = -2 - j2, magnitude √(4 + 4) = 2.8284, phase -135°

Notice conjugate symmetry holds: X[3] is the complex conjugate of X[1]. Furthermore, Parseval's theorem states that total signal energy is preserved between time and frequency domains:

∑ |x[n]|² = (1 / N) ∑ |X[k]|²

Here, time-domain energy is 1² + 2² + 3² + 4² = 30. Frequency-domain energy is (1 / 4) × [10² + (2.8284)² + 2² + (2.8284)²] = (1 / 4) × [100 + 8 + 4 + 8] = 120 / 4 = 30. Both representations give exactly 30, verifying energy conservation.

Related signal processing tools and resources

Explore the Bode plot generator to inspect continuous-time frequency response and transfer-function margins. Use the Fourier series drawing tool to visualize harmonic reconstruction, and the RC filter calculator or decibel converter for hardware filter cutoffs and amplitude ratios.

Guides and tutorials

Frequently asked questions

What is the difference between linear and circular convolution?

Linear convolution calculates the response of an LTI system over infinite time, producing an output of length Lx + Lh - 1. Circular convolution operates modulo N on periodic or zero-padded sequences of length N. Circular convolution equals linear convolution only when N is at least Lx + Lh - 1; otherwise, time-domain aliasing occurs.

How does the flip-and-slide method work by hand?

Plot both sequences against dummy index k. Keep x[k] fixed, reflect h[k] about k = 0 to get h[-k], and shift it right by n to get h[n - k]. Multiply overlapping samples point by point and sum the products to find y[n]. Repeat for each integer n where sequences overlap.

What is the formula for the length of a linear convolution?

If sequence x[n] has length Lx and sequence h[n] has length Lh, the convolved output y[n] has length Ly = Lx + Lh - 1. If x begins at index nx0 and h begins at nh0, the output begins at ny0 = nx0 + nh0.

How do you choose N so circular convolution equals linear convolution?

Set N greater than or equal to Lx + Lh - 1, and zero-pad both sequences up to length N. Because the periodic repetition period N exceeds the total transient length of the linear convolution, no wrapped samples overlap, and the circular result matches linear convolution sample for sample.

What causes time-domain aliasing in circular convolution?

When N is strictly less than Lx + Lh - 1, the output duration exceeds one period N. By the circular convolution theorem, output samples beyond index N - 1 fold back and add to earlier samples according to y_c[n] = sum of y_lin[n + r*N], distorting the true linear response.

How is the N-point DFT calculated from a discrete sequence?

The DFT evaluates the Discrete-Time Fourier Transform at N uniformly spaced frequency points on the unit circle: X[k] = sum from n=0 to N-1 of x[n] * exp(-j * 2 * pi * k * n / N). Each bin k represents digital frequency omega = 2 * pi * k / N radians per sample.

Why is the DFT of a real-valued sequence conjugate symmetric?

Because real numbers equal their own complex conjugates, taking the conjugate of the DFT formula reveals that X[N - k] = X*[k]. This means the real part and magnitude are even functions of frequency, while the imaginary part and phase are odd functions.

What is Parseval's theorem for the discrete Fourier transform?

Parseval's relation states that energy in the time domain equals energy in the frequency domain divided by N: sum of |x[n]|^2 equals (1 / N) * sum of |X[k]|^2. It proves that the discrete Fourier transform is a scaled unitary transformation that preserves total signal energy.

How does zero-padding affect the DFT spectrum?

Zero-padding adds trailing zeros to increase sequence length from L to N without adding new information. It does not improve frequency resolution (the ability to distinguish close spectral peaks), but it interpolates the spectrum, calculating closer sample points on the continuous DTFT curve.

Where does discrete convolution appear in US engineering curricula?

Discrete convolution is central to sophomore and junior courses in Electrical and Computer Engineering (ECE), Computer Science (CS), and Mechanical Engineering, including EECS 16A/B at UC Berkeley, 6.003 at MIT, and ECE 2026 at Georgia Tech for digital filters, DSP, and image processing.

Have a suggestion for Discrete Convolution Calculator?Share your feedback ↗