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:
- Plot against k: Express both sequences as functions of the independent variable k, yielding x[k] and h[k].
- Reflect (flip): Invert the kernel sequence h[k] about the origin k = 0 to produce the time-reversed sequence h[-k].
- 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.
- Multiply: Take the point-by-point product of x[k] and the shifted sequence h[n - k] wherever both signals have nonzero overlapping values.
- 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.