Convolution
As discussed in the previous section, a DSP system is use to perform some operation on signals, this operation can range from simple addition of two signals to filtering noise from a signal and more. As mentioned before, a DSP system can be described by the equation below
This equation, while used to describe a DSP system, is not suitable for mathematical evaluation of the manner in which the system affects a signal. Therefore, DSP systems when being used in the processing context are described by their Impulse response. The impulse response of a system is the output of the system when a sequence of unit impulses is provided as the input. The impulse response is generally used to define a system for all calculation purposes is denoted as h[n].
Convolution (Linear)
The convolution operation is used to determine the response of a DSP system to a given input signal. In order to understand the process, let us assume an input signal x[n] and a DSP system with the impulse response h[n] as shown in the figure below
The signal x[n] is a sampled form of the continuous signal x(t) and therefore can be written as
Where is a sequence of unit impulses. In order to develop a mathematical equation for the convolution operation, let us consider the output when the input signal is provided to the DSP system sample by sample, starting from a time index value of -1, the input signal can be written as
Multiplying this sample of the input signal with the impulse response yields,
By the sifting property, this can be written as
At the time index 0, two samples of the signal will be present for the DSP system to process, this can be written as
This can be further extended for a time index value of 1 as,
Or more generally,
Where y[n] is the output resulting from the convolution of the signal x[n] and the system impulse response h[n] at time index n. The ‘*’ represents the convolution operation. If the length of the input signal is l and the length of the system impulse response is m, the length of the result y[n] is l+m-1. There are various methods to perform convolution such as the matrix method, graphical method and numeric evaluation. The Convolution operation satisfies the Commutative, Associative and Distributive property.
In order to demonstrate how convolution is evaluation, let us assume a signal x[n]=[1 2 3] and a system impulse response to be h[n]=[1 2 3]. The numbers in bold indicate values at zero time index. The signal x[n] and the impulse response h[n] are shown below
Since, in order to perform the convolution we need to align the first sample of h[n] with the first sample of x[n], we need to time reverse h[n]. The time reversed version of h[n] i-e h[-n] is also shown in the figure below.
The convolution sum can then be computed as shown in the figures below.
For n=-2
Multiplying and adding the aligned samples gives, y[-2]=1.
For n=-1
Multiplying and adding the aligned samples gives, y[-1]=4.
For n=0
Multiplying and adding the aligned samples gives, y[0]=10.
For n=1
Multiplying and adding the aligned samples gives, y[1]=12.
For n=2
Multiplying and adding the aligned samples gives, y[2]=9. The convolution result y[n] can then be written as
It is shown in the figure below.
Circular Convolution
In linear convolution, the input signal and the system impulse are assumed to be non periodic and can be infinitely long. Circular convolution is a special type of convolution in which the signal x[n] and the system impulse response are assumed to be periodic. It is mathematically written as,
Where ycir[n] is the result of the circular convolution between the periodic input signal xper[n] and the periodic system impulse response hper[n]. N is the period of the signals. If one of the signals has a smaller period than the other, the first signal is padded with trailing zeros. The length of the output signal is equal to N. In order to perform a linear convolution using the circular convolution operation, the input signal needs to be padded with (l-1) trailing zeros and the system response needs to be padded with (m-1) trailing zeros.
