Linear and circular convolution

Introduction Linear convolution Circular delay Circular convolution FFT algorithm for circular convolution Calculation of linear convolution through circular Conclusions Reference

DSPL-2.0 is free digital signal processing algorithms library Distributed under v3 LGPL v3 license GitHub project page.

One of the «whales» of modern technology is undoubtedly the convolution operation:

which allows calculating the signal at the output of the linear filter with impulse response , for the input signal . It is assumed that and are absolutely integrable functions and integral (1) converges.

Graphically the convolution of the signal with the filter impulse response , in accordance with (1), is shown in the figure 1.

In a physically realizable system, output signal cannot occur earlier than the input signal, then the impulse response must be zero, for . Given this property, the expression (1) can be represented as:

Commutativity is important propetry of the convolution, i.e. . If in the expression  (1) change a variable , then in this case , the upper limit of integration transforms to , and the lower limit transforms to . Then we get:

In the discrete case, two types of convolutions are distinguished: linear (or aperiodic) and cyclic. Cyclic convolution is also often called circular or periodic.

Let there are two discrete signals , , , defined over the entire range of indices . Then the linear convolution of discrete signals is of the form:

In the general case, the summation of infinite sequences and requires an analysis of the convergence of the sum. However, in practice, we cannot deal with infinite discrete sequences. Suppose that the signals and have only a finite number of nonzero values. Then only for , and only for . In this case, from the equation (4) we can see that will have only nonzero values.

To calculate the linear convolution, the signals and and are shifted relative to each other, all possible overlapping samples are multiplied term by term and added as shown in the figurе 2.

Here is an example of calculating a linear convolution. Let's signal contains samples, and signal contains samples. Then the process of calculating the linear convolution of the signals and is shown in the figure 3.

It should be noted that the signal , when calculating the linear convolution, is reflected from left to right, since  is the first sample (the earliest in time) and it must also be processed first.

Linear convolution describes the passage of the signal , through an order FIR filter with impulse response , :

In the expression (5), the summation limits correspond to the duration of the impulse response of the FIR filter, since for and .

Another important applied value of linear convolution is the calculation of the product of polynomials.

Let the values of the discrete sequence , , containing value are the coefficients of the polynomial

order , and the discrete sequence ,  — contains coefficients of polynomial order . Then the coefficients of the product of the polynomials will be equal to the linear convolution . As a result, we get the coefficient of the polynomial of degree .

Let there be a discrete signal , duration samples, . If we take the of the last signal samples and transfer them to the beginning, we get the signal, cyclically delayed relative to the initial one by samples. To denote a circular delay, we will use the notation , which says that the difference is taken modulo , i.e. take the remainder of dividing by .

Operations modulo under the assumption are performed according to the following rules:

For example , , then . If is negative, then . Thus, operation modulo for any integer returns a value between and inclusive.

Circular delay example is shown in the figure. 4 for and .

Let's and , are two signals samples length, . Circular convolution of signals and is :

Circular convolution can be performed only over sequences of equal length samples, as we can see from (9). The result will also be a signal of length .

Graphically, an example of computing a cyclic convolution (9) is shown in the figure 5 for .

The cyclic convolution can be represented in matrix form:

You can see that each column of the matrix is cyclically delayed by one count relative to the previous column. The special structure of the matrix allows the development of highly efficient algorithms for circular convolution [1].

The most important property of circular convolution is that it reduces to the product of the DFT spectra of the original sequences, as well as to the product of -transforms. The use of the fast Fourier transform algorithms provides the highest computational efficiency of circular convolution.

As we know from the discrete Fourier transform properties, the DFT of circular convolution is equal to the product of convolved signals spectra:

here

Thus, multiplying the DFT spectra of the original signals sample by sample, and taking the inverse discrete Fourier transform, we get the result of cyclic convolution. It is advisable to calculate the DFT on the basis of fast Fourier transform algorithms. Then we can finally write:

here и  — fast Fourier transform and inverse fast inverse transform correspondently .

The process of calculating the cyclic convolution of signals and using the fast Fourier transform algorithms is schematically shown in the figure 6.

Note that the efficiency of FFT algorithms depends on the sample length . The most efficient algorithms are designed for a length of equal to an integer power of two (the so-called radix-2 algorithms). At the same time, in addition to high computational efficiency, the radix-2 FFT algorithms differ in regular structures in hardware and software implementation, and also perfectly parallelize in multiprocessor processing.

For example, for , performing the matrix multiplication 
ref{fourier_transform:sec_duality} naive method, without using accelerations, will require the real multiplication operation. If we apply the FFT-based circular convolution algorithm, then three FFTs of length are required (the inverse FFT is also counted through the forward one), plus 1024 complex multiplications for element-wise multiplication of the FFT results.

Each of the three FFTs requires a number of multiplications equal to:

then we get that calculating the convolution through the FFT requires complex multiplications. For , we get an estimate of 13312 the complex multiplication operation, which is equivalent to 53248 real multiplications, i.e. almost 20 times less than in the naive calculation of circular convolution. It is important to note that with the growth of , the acceleration of computations only grows, because we replace the quadratic growth of computational operations with the product of linear and logarithmic functions.

The computational advantages that we get when using the FFT for calculating circular convolution would also be desirable for calculating linear convolution. For this purpose, we will consider a method for reducing linear convolution of sequences of limited duration to circular.

Let and be discrete sequences of duration and samples, respectively. Linear convolution of the sequences and will return counting . If we want to get as a result of cyclic convolution, then it is necessary to supplement and to the length count, as shown in the figurе 7.

Add zeros to the sequence , and add zeros to the sequence . Adding zeros in this way will increase the periodicity of the circular buffer to a size when and no longer cyclically overlap. As a result, the circular convolution will look like:

It can be shown that the circular convolution (15) of the zero-padded sequences corresponds to the calculation of the linear convolution of the original signals. To make sure of this, it is enough to use the matrix notation of circular convolution and write down the corresponding elements , . As a result, the expressions will correspond to linear convolution.

It should be noted that add zeros to and possible not only up to the length , but also up to any length . As a result of calculating the circular convolution of zero-padded sequences to length , the first value in the output will be a linear convolution, and the remaining values will be zero. This can be used to pad the original sequences with zeros to a length that allows efficient FFT algorithms.

For example, if and , you need to pad and with zeros to the length of . However, we can supplement them to a length of samples and use the radix-2 FFT to calculate the circular convolution. In this case, the first 6999 samples of the result of the circular convolution will represent a linear convolution with and . Using the FFT algorithm for will result in a tenfold decrease in the required real multipliers when calculating the linear convolution with and .

Thus, we have considered a continuous convolution integral that describes the response of a linear filter to an arbitrary input signal.

Also, two types of discrete convolutions were considered: linear and circular, and a relations was established between them. It was shown that the use of FFT provides a significant reduction in computational operations when calculating both circular and linear convolutions.

Reference