5.1 Linear Convolution in Time and Frequency Domains

Linear convolution is a fundamental operation in signal processing that combines two signals to produce a third. It's crucial for understanding how systems modify input signals, forming the basis for filtering, smoothing, and other signal transformations.

Mastering linear convolution in both time and frequency domains is essential. The time-domain approach involves sliding and multiplying signals, while the frequency-domain method uses the Fourier transform for efficient computation, especially with long signals.

Linear convolution and its properties

Definition and mathematical representation

• Linear convolution combines two signals to produce a third signal, representing the output of a linear time-invariant (LTI) system when one signal is the input and the other is the system's impulse response
• The linear convolution of two discrete-time signals $x[n]$ and $h[n]$ is defined as $y[n] = x[n] * h[n] = \sum_{k=-\infty}^{\infty} x[k]h[n-k]$, where $*$ denotes the convolution operator
• The length of the output signal $y[n]$ resulting from the linear convolution of two signals $x[n]$ and $h[n]$ is equal to the sum of the lengths of $x[n]$ and $h[n]$ minus one

Properties and interpretation

• Linear convolution satisfies the properties of linearity (additivity and homogeneity) and shift invariance (time invariance)
  • Additivity: If $y_1[n] = x_1[n] * h[n]$ and $y_2[n] = x_2[n] * h[n]$, then $(x_1[n] + x_2[n]) * h[n] = y_1[n] + y_2[n]$
  • Homogeneity: If $y[n] = x[n] * h[n]$, then $(ax[n]) * h[n] = ay[n]$, where $a$ is a constant
  • Shift invariance: If $y[n] = x[n] * h[n]$, then $x[n-k] * h[n] = y[n-k]$, where $k$ is a constant shift
• Linear convolution can be interpreted as a filtering operation, where the impulse response $h[n]$ acts as a filter that shapes the input signal $x[n]$ to produce the output signal $y[n]$
  • Example: A moving average filter with impulse response $h[n] = [0.25, 0.5, 0.25]$ smooths the input signal by averaging adjacent samples

Convolution of discrete-time signals

Time-domain computation

• To compute linear convolution in the time domain, multiply the time-reversed and shifted version of one signal by the other signal and sum the products at each time index
• The linear convolution of two finite-length signals $x[n]$ and $h[n]$ can be computed by performing a sliding dot product operation, where $h[n]$ is flipped and shifted across $x[n]$, and the products are summed at each shift
  • Example: For $x[n] = [1, 2, 3]$ and $h[n] = [4, 5]$, the convolution $y[n] = x[n] * h[n] = [4, 13, 22, 15]$
• Zero-padding the shorter signal to match the length of the longer signal is necessary to ensure proper computation of linear convolution in the time domain

Computational complexity

• The computational complexity of linear convolution in the time domain is $O(N^2)$, where $N$ is the length of the signals, making it inefficient for long signals
• For signals of length $N$ and $M$, the time-domain convolution requires $NM$ multiplications and $(N-1)(M-1)$ additions
  • Example: Convolving two signals of length 1000 requires approximately 1 million multiplications and additions

Frequency-domain convolution using Fourier transforms

Convolution theorem

• The convolution theorem states that the Fourier transform of the linear convolution of two signals is equal to the pointwise multiplication of their individual Fourier transforms
  • Mathematically, if $y[n] = x[n] * h[n]$, then $Y(e^{j\omega}) = X(e^{j\omega}) \cdot H(e^{j\omega})$, where $X(e^{j\omega})$, $H(e^{j\omega})$, and $Y(e^{j\omega})$ are the Fourier transforms of $x[n]$, $h[n]$, and $y[n]$, respectively
• The convolution theorem allows for efficient computation of linear convolution using the Fast Fourier Transform (FFT) algorithm, reducing the computational complexity to $O(N \log N)$

Frequency-domain convolution procedure

• To perform linear convolution in the frequency domain:
  1. Take the Fourier transforms of both input signals
  2. Multiply the Fourier transforms pointwise
  3. Take the inverse Fourier transform of the result to obtain the convolved signal in the time domain
• Zero-padding the input signals to a length equal to the sum of their original lengths minus one is necessary to avoid circular convolution artifacts when using the FFT for linear convolution
  • Example: To convolve signals of length $N$ and $M$, zero-pad both signals to length $N+M-1$ before applying the FFT
• The convolution theorem holds for both continuous-time and discrete-time signals, and it can be applied using various Fourier transforms such as the Discrete Fourier Transform (DFT) or the Discrete-Time Fourier Transform (DTFT)

Effects of linear convolution on signals

Signal characteristics modification

• Linear convolution can be used to study the effects of filtering on signal characteristics such as amplitude, frequency content, and phase
• The impulse response of a system determines how it modifies the input signal through linear convolution
  • The characteristics of the impulse response, such as its duration, shape, and frequency response, influence the output signal
• Linear convolution can result in the attenuation or amplification of specific frequency components of the input signal, depending on the frequency response of the system's impulse response
  • Example: A low-pass filter attenuates high-frequency components while preserving low-frequency components
• The phase response of the system's impulse response can introduce phase shifts or group delays in the output signal, affecting the temporal alignment of different frequency components
  • Example: A linear phase filter introduces a constant delay across all frequencies, preserving the shape of the signal

Interpretation and applications

• Interpreting the results of linear convolution involves analyzing the time-domain and frequency-domain representations of the input, impulse response, and output signals to understand how the system modifies the signal characteristics
• Linear convolution can be used to implement various signal processing techniques, such as:
  • Filtering: Removing unwanted frequency components or noise from a signal
  • Signal smoothing: Reducing high-frequency variations or noise in a signal
  • Signal enhancement: Emphasizing desired features or components in a signal
  • Signal synthesis: Generating new signals by convolving existing signals with specific impulse responses
• Example applications of linear convolution include audio processing (equalizers, reverb effects), image processing (edge detection, blurring), and communication systems (channel equalization, matched filtering)