Convolution Sum

The convolution sum is the mathematical tool that computes the output of a discrete-time LTI system for any arbitrary input. Instead of solving a system from scratch every time a new input is applied, the convolution sum uses the system's impulse response to fully determine the output. This makes it one of the most powerful and widely tested concepts in Signals and Systems, appearing in GATE both as direct computation problems and as part of system analysis questions.

Core Concept Explanation

A discrete-time LTI system is completely characterized by its impulse response h[n], which is the output when the input is a unit impulse delta[n]. Any arbitrary input x[n] can be decomposed as a weighted, time-shifted sum of unit impulses. Since the system is linear and time-invariant, the output to each shifted impulse is a shifted and scaled version of h[n]. Adding all these responses together gives the total output, which is exactly what the convolution sum computes.

The convolution sum is written as y[n] = sum over k from negative infinity to positive infinity of x[k] multiplied by h[n minus k]. For each output sample y[n], you multiply the input sequence x[k] with a time-reversed and shifted version of h[k], then sum all products. This operation simultaneously captures the memory of the system through the shifted versions of h[n].

Mathematical Expression

The convolution sum formula in compact notation is y[n] = x[n] * h[n] = sum_k x[k] h[n-k]. When x[n] and h[n] are both finite-length sequences, the output y[n] has length equal to the sum of individual lengths minus one. Specifically, if x[n] has N samples and h[n] has M samples, then y[n] has N plus M minus 1 samples. Length of y = length(x) + length(h) - 1

The tabular method is a systematic way to compute the convolution sum for finite-length sequences without writing the full summation each time. In this method, each row corresponds to one sample of x[n] multiplied across all samples of h[n] and placed at the appropriate time index. The columns are then summed to get the output samples. This method reduces computation errors in GATE numerical problems significantly.

Practical Understanding

In digital filter implementation, every output sample is computed as a weighted sum of past and present input samples. The weights are precisely the samples of the impulse response h[n]. This is the direct implementation of the convolution sum. For a finite impulse response (FIR) filter of length M, each output sample requires M multiplications and M minus 1 additions, which directly reflects the convolution sum computation.

The convolution sum also has a frequency domain counterpart. Taking the Z-transform of the convolution sum gives Y(z) = X(z) multiplied by H(z), where H(z) is the Z-transform of the impulse response. This means convolution in time domain corresponds to multiplication in the Z-domain, which is why frequency domain methods are preferred for long sequences in practice.

Solved Numerical Example

To apply the tabular method, write x[n] as rows and h[n] as columns. Multiply each element of x[n] by the entire h[n] sequence and shift the result by the corresponding time index. Then add all rows column-wise to get y[n]. The example below demonstrates this for finite sequences starting at n equals 0.

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

Why this formula applies:
y[n] = sum_k x[k]*h[n-k]  (DT LTI convolution sum)

Formula:
y[n] = x[n] * h[n]
Length of y = 3 + 2 - 1 = 4 samples

Substitution (Tabular Method):
Row k=0: 2*{1,2} = {2, 4}    placed at n=0,1
Row k=1: 1*{1,2} = {1, 2}    placed at n=1,2
Row k=2: 3*{1,2} = {3, 6}    placed at n=2,3

Calculation (column-wise sum):
n=0: 2           = 2
n=1: 4 + 1       = 5
n=2: 2 + 3       = 5
n=3: 6           = 6

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

Exam Tip: In GATE, always verify the output length first using N+M-1 before solving. A mismatch in length is a signal that you have made an alignment error in the tabular method. Also, if x[n] starts at n=n1 and h[n] starts at n=n2, then y[n] starts at n = n1 + n2.

Quick Revision

• Convolution sum: y[n] = sum_k x[k] h[n-k]. This is the fundamental output equation for any DT LTI system.
• Output length for finite sequences: length(y) = length(x) + length(h) - 1.
• Starting index of output: if x[n] starts at n1 and h[n] starts at n2, y[n] starts at n1 + n2.
• Tabular method: multiply each x[k] across h[n] and shift by k. Sum all rows column-wise.
• Z-domain equivalent: Y(z) = X(z) * H(z). Convolution in time equals multiplication in Z-domain.
• GATE trap: Forgetting to account for the starting index when sequences begin at non-zero values causes wrong output indexing.
• FIR filter of length M requires exactly M multiplications per output sample, directly reflecting the convolution sum.