Convolution Sum

The convolution sum is the mathematical operation that computes the output of any LTI system given its input and impulse response. It is the discrete-time counterpart of the convolution integral and is the single most important computation in discrete signal processing. Every filtering operation, every system response calculation, and every correlation computation traces back to this operation.

Core Concept Explanation

The convolution sum is defined as y[n] = Σ x[k]·h[n−k] summed from k = −∞ to +∞. Here x[n] is the input sequence and h[n] is the impulse response of the LTI system. The physical interpretation is elegant: the output at time n is a weighted sum of all past and present input values, where the weights are given by the impulse response. Each input sample x[k] creates a scaled and shifted copy of h[n], and all these copies add up to produce the final output.

The flip-shift-multiply-sum procedure is the standard graphical method. First, flip h[k] about the origin to get h[−k]. Then shift by n positions to get h[n−k]. Multiply this with x[k] at each value of k. Finally, sum all products to get y[n]. Repeat this for every value of n of interest. This procedure, though mechanical, builds deep intuition about how a system's memory (impulse response) interacts with the input.

Properties of Convolution

Convolution satisfies three important algebraic properties. It is commutative: x[n] * h[n] = h[n] * x[n]. It is associative: (x * h₁) * h₂ = x * (h₁ * h₂), which means cascaded LTI systems can be replaced by a single system with impulse response h₁[n] * h₂[n]. It is distributive over addition: x * (h₁ + h₂) = x * h₁ + x * h₂, which means parallel LTI systems can be combined by adding their impulse responses. These properties are directly tested in GATE.

Mathematical Expression

For finite-length sequences, the convolution sum becomes a finite computation. If x[n] has M samples (from n = 0 to M−1) and h[n] has N samples (from n = 0 to N−1), then y[n] has exactly M + N − 1 samples (from n = 0 to M + N − 2). This length rule is critical for GATE. In matrix form, linear convolution can be written as a matrix-vector product, and this forms the basis of fast convolution algorithms using DFT. The DFT-based convolution requires circular convolution with length at least M + N − 1 to equal linear convolution.

Practical Understanding

In practice, the polynomial multiplication method offers a fast way to compute convolution by hand. Treat x[n] and h[n] as coefficient sequences of polynomials X(z) and H(z). Their product X(z)·H(z) gives the polynomial whose coefficients are the convolution output y[n]. For example, x = {1, 2} and h = {1, 3} corresponds to (1 + 2z⁻¹)(1 + 3z⁻¹) = 1 + 5z⁻¹ + 6z⁻², giving y = {1, 5, 6}. This method eliminates the need to flip and slide.

Given:
x[n] = {1, 2, 3} (n = 0, 1, 2)  → M = 3
h[n] = {1, 1} (n = 0, 1)         → N = 2

Why this formula applies:
Linear convolution y[n] = Σ x[k]·h[n-k]
Output length = M + N - 1 = 3 + 2 - 1 = 4

Formula:
y[n] = Σ x[k]·h[n-k] for k = 0 to 2

Substitution (compute each output sample):
y[0] = x[0]·h[0] = 1·1 = 1
y[1] = x[0]·h[1] + x[1]·h[0] = 1·1 + 2·1 = 3
y[2] = x[1]·h[1] + x[2]·h[0] = 2·1 + 3·1 = 5
y[3] = x[2]·h[1] = 3·1 = 3

Calculation:
Polynomial method: (1 + 2z⁻¹ + 3z⁻²)(1 + z⁻¹)
= 1 + z⁻¹ + 2z⁻¹ + 2z⁻² + 3z⁻² + 3z⁻³
= 1 + 3z⁻¹ + 5z⁻² + 3z⁻³  ✓

Final Answer:
y[n] = {1, 3, 5, 3} for n = 0, 1, 2, 3

Exam Tip: For GATE convolution problems, always state the output length as M+N−1 first. Use the polynomial multiplication shortcut for sequences up to length 4. For circular vs linear convolution, remember that circular convolution of length L equals linear convolution only when L is at least M+N−1.

Quick Revision

• y[n] = Σ x[k]·h[n−k] = x[n] * h[n]. Flip, shift, multiply, sum.
• Output length = M + N − 1 for finite sequences of length M and N.
• Commutative: x*h = h*x. Associative: (x*h₁)*h₂ = x*(h₁*h₂). Distributive over addition.
• Cascaded LTI systems: equivalent impulse response = h₁[n] * h₂[n].
• Parallel LTI systems: equivalent impulse response = h₁[n] + h₂[n].
• Polynomial multiplication shortcut works for short sequences in GATE.
• Trap: circular convolution of length L = linear convolution only if L ≥ M+N−1.