Discrete-Time Convolution Sum

The convolution sum is the discrete-time counterpart to the continuous-time convolution integral, providing the definitive method for calculating the output of any linear time-invariant (LTI) system from its impulse response and input signal. It replaces the continuous operation of integration with the discrete operation of summation, making it the fundamental computational engine behind all digital filters and signal processors. Mastering it is essential for designing, analyzing, and implementing systems in digital signal processing, communications, and control engineering.

Defining the Operation for LTI Systems

A discrete-time LTI system is completely characterized by its impulse response, denoted $h[n]$, which is the output of the system when the input is a unit impulse $\delta [n]$. The unit impulse is defined as 1 at $n=0$ and 0 everywhere else. Given any arbitrary input sequence $x[n]$, the output $y[n]$ is computed using the convolution sum.

The formula for the convolution sum is:

$$y[n]=x[n]\ast h[n]=\sum _{k=-\infty }^{\infty }x[k]\cdot h[n-k]$$

This equation embodies the superposition principle for LTI systems. It states that each input sample $x[k]$ can be viewed as a scaled impulse. Each of these scaled impulses produces a scaled and shifted version of the impulse response, $x[k]\cdot h[n-k]$. The total output $y[n]$ at time index $n$ is the sum (accumulation) of the contributions from all input samples, past, present, and future. For practical, causal systems (where the output depends only on present and past inputs), the limits of summation become finite, often from $k=0$ to $k=n$ if the sequences start at 0.

The Step-by-Step Computation Mechanics

Performing convolution manually involves a systematic procedure that clarifies its meaning. Let's compute the output for finite-length sequences $x[n]=[1,2,3]$ for $n=0,1,2$ and $h[n]=[1,1]$ for $n=0,1$.

1. Time-Reverse and Shift: For each output index $n$, you time-reverse $h[k]$ to get $h[-k]$ and then shift it by $n$ to form $h[n-k]$.
2. Multiply and Sum: For the current shift $n$, you multiply the overlapping samples of $x[k]$ and $h[n-k]$ and sum the products.

Let's compute $y[n]$ for each $n$:

• For $n=0$: The shifted $h[0-k]$ overlaps with $x[k]$ only at $k=0$. $y[0]=x[0]\cdot h[0]=1\cdot 1=1$.
• For $n=1$: Overlap occurs at $k=0$ and $k=1$. $y[1]=x[0]\cdot h[1]+x[1]\cdot h[0]=(1\cdot 1)+(2\cdot 1)=3$.
• For $n=2$: Overlap at $k=1$ and $k=2$. $y[2]=x[1]\cdot h[1]+x[2]\cdot h[0]=(2\cdot 1)+(3\cdot 1)=5$.
• For $n=3$: Overlap only at $k=2$. $y[3]=x[2]\cdot h[1]=3\cdot 1=3$.

Thus, the full output sequence is $y[n]=[1,3,5,3]$. This process of multiplying input samples by shifted impulse response values and accumulating the results is the core of the operation. The length of the resulting sequence is $(\text{length}(x)+\text{length}(h)-1)$, which is 3+2-1=4 in this case.

Key Mathematical Properties and System Implications

The convolution sum possesses critical algebraic properties that directly inform system analysis and design:

• Commutativity: $x[n]\ast h[n]=h[n]\ast x[n]$. This means the input and impulse response are interchangeable in the formula. You can interpret the output as the sum of scaled impulse responses or as the weighted sum of the input with a time-reversed and shifted $h[n]$.
• Associativity: $(x[n]\ast h_1[n])\ast h_2[n]=x[n]\ast (h_1[n]\ast h_2[n])$. This allows you to combine cascaded systems. The overall impulse response of two systems in series is the convolution of their individual impulse responses: $h_{total}[n]=h_1[n]\ast h_2[n]$.
• Distributivity: $x[n]\ast (h_1[n]+h_2[n])=x[n]\ast h_1[n]+x[n]\ast h_2[n]$. This property enables the analysis of parallel systems. The overall impulse response of two parallel systems that sum their outputs is the sum of their individual impulse responses.

These properties are powerful. For instance, associativity allows a complex filter to be broken down into simpler, cascaded stages for more efficient implementation. Distributivity is the foundation for filter banks and parallel processing structures.

Connection to FIR and IIR Digital Filters

The convolution sum is the direct implementation mechanism for Finite Impulse Response (FIR) filters. An FIR filter has an impulse response $h[n]$ that is non-zero for only a finite number of samples (e.g., from $n=0$ to $n=M$). The convolution sum for such a system becomes a finite sum: $$y[n]=\sum _{k=0}^{M}h[k]\cdot x[n-k]$$ This is exactly the familiar tapped-delay line or transversal filter structure, where the current output is a weighted sum of the current and $M$ past inputs. The weights are the filter coefficients, $h[k]$.

For Infinite Impulse Response (IIR) filters, the impulse response theoretically extends to infinity. The direct convolution sum formula is therefore impractical for real-time computation. Instead, IIR filters are implemented using recursive difference equations (e.g., $y[n]=x[n]+0.5y[n-1]$). However, the conceptual foundation remains: the impulse response $h[n]$ of the IIR system, derived from its difference equation, still convolves with the input to produce the output. The convolution sum correctly describes the input-output relationship, even if we use a recursive formula for practical calculation.

Common Pitfalls

1. Misaligning Indices During Manual Calculation: The most frequent error is misidentifying the sample index $n$ for the output sequence. Remember that for each output index $n$, you are summing over the dummy index $k$. A reliable method is to write $x[k]$ on one row and $h[n-k]$ below it, explicitly performing the shift for each $n$ as shown in the step-by-step example.
2. Incorrectly Handling Sequence Support (Start/End Points): Failing to correctly determine where the sequences start and end leads to missing or extra terms in the sum. Always note the index of the first non-zero sample for each sequence. For causal sequences starting at $n=0$, the summation lower limit is often $k=0$ and the upper limit is $n$ for computing $y[n]$, until the shift exceeds the sequence lengths.
3. Confusing Convolution with Multiplication or Simple Addition: Convolution is not element-by-element multiplication of sequences. It is a sophisticated operation involving shifting, multiplication, and summation. Similarly, it is not simply adding the sequences together. Using the correct operator and procedure is non-negotiable.
4. Forgetting the Commutative Property as a Check: If your manual calculation becomes messy, exploit commutativity. Try convolving the sequences in the opposite order ($h[n]\ast x[n]$). You must get the identical result. If you don't, it's a clear indicator of an error in your shifting or summation logic.

Summary

• The discrete-time convolution sum $y[n]={\sum }_{k}x[k]h[n-k]$ is the fundamental operation for determining the output of any discrete-time LTI system from its input $x[n]$ and its impulse response $h[n]$.
• It works by multiplying input samples by shifted impulse response values and accumulating (summing) the results, embodying the superposition principle for LTI systems.
• Its key properties—commutativity, associativity, and distributivity—provide powerful tools for analyzing interconnected systems in series and parallel configurations.
• It is the direct implementation formula for FIR digital filters and the conceptual foundation for the operation of IIR filters, making it essential for digital filter implementation.
• Careful attention to the indexing, shifting, and summation process is required to avoid common computational errors, and leveraging properties like commutativity can serve as a valuable verification step.