Why is circular convolution used in DSP? Why not linear convolution?

1. Why are we using circular convolution in DSP?

2. What's the main solid reason for the use of it in digital processing?

3. Why does the concept of circular convolution come more often than linear convolution?

• you will notice that all of your answers include a mention of the Discrete Fourier Transform which is implemented most efficiently with the FFT. the DFT inherently periodically extends the finite-length sequences passed to it (which is circular). circular convolution is seldom the goal. usually linear convolution is the goal. but when multiplying the DFT's $X[k]$ and $H[k]$ together, that corresponds to the circular convolution of the two periodically-extended sequences, $x[n]$ and $h[n]$ passed to the DFTs. the problem is then somehow making this into linear convolution. – robert bristow-johnson Oct 29 '16 at 17:19

Given a discrete time LTI system with impulse response $h[n]$, one can compute its response (output $y[n]$) to any input $x[n]$ by what's called as the convolution sum shown with the star notation $y[n] = x[n] \star h[n] = h[n] \star x[n]$ and actually computed as $$y[n] = \sum_{k=-\infty}^{\infty} {x[k]h[n-k]} = \sum_{k=-\infty}^{\infty} {h[k]x[n-k]}$$

Without anything further added, above definition is for the linear convolution (aperiodic convolution) which is differentiated from a circular convolution by the fact that a circular convolution is taken between two periodic sequences of period $N$ and computed over a single period for $n=0$ to $N-1$, whereas a linear convolution is computed over all relevant values of $n$ from $-\infty$ to $\infty$.

Basically you can compute a linear convolution either in time domain straightforwardly by the above sum or indirectly in the frequency domain by relying on the following DTFT (discrete-time Fourier transform) property; given $y[n] = x[n]\star h[n]$ then $$Y(e^{j\omega})= \mathcal{F} \{ x[n] \star h[n] \} = X(e^{j\omega}) H(e^{j\omega})$$

Note that DTFT is inherently related with the linear convolution as it naturally deals with aperiodic sequences that may extend from $-\infty$ to $\infty$ which is reflected in the limits of the defining sum: $$X(e^{j \omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n}$$

Things are very nice on the paper, and when you want to make a calculation by hand using the symbolic expressions for signals (such as $x[n]=a^nu[n]$ and $h[n]=u[n]-[n-M]$), you can calculate the results in either time or frequency domains as outlined above. In particular if you want to find the result through the frequency domain, you would first find DTFTs $X(e^{j\omega})$ and $H(e^{j\omega})$, then multiply them as $Y(e^{j\omega}) = X(e^{j\omega})H(e^{j\omega})$ and finally find the inverse DTFT of $Y(e^{j\omega})$ to obtain $y[n]$. The theoretical computation appears very nice on the paper and gives way to theoretical analysis and research for signal processing.

When, you want to compute the same result by using a computer (in order to actually implement a DSP algorithm) even though you can perfectly use the time domain approach based on an LCCDE recursion (for IIR systems) or direct convolution sum (for FIR systems), the frequency domain approach won't work with DTFT as it's mainly a theoretical tool used to develop the mathematics of signals and systems which it's not suitable for sampled-data computer implementations, as its variable $\omega$ is continuous.

What is used instead is the discrete Fourier transform (DFT) defined as $$X[k] = X(e^{j\omega})|_{\omega = \frac {2\pi k}{N} }$$ where $k=0,1,...,N-1$ and $N$ is the length of the DFT, which's then called as an N-point DFT of signal $x[n]$. There are a number of interpretations for the meaning of the samples $X[k]$. For example the previous definition implies that the DFT $X[k]$ are the uniform samples of the DTFT $X(e^{j\omega})$. Or you can directly begin from discrete-time periodic sequences, define their (periodic) discrete Fourier series representation (DFS) and assert that DFT is the first period of the periodic DFS of a given periodic signal $\tilde{x}[n]$. In any case, the DFT $X[k]$ is inherently a periodic sequence. But we only consider its first period from $k=0$ to $N-1$.

Even though DTFT and DFT are inherently related as many of their properties resemble quite close in both versions, there are important distinctions as well, one of them being the convolution theorem (or filtering theorem). Whereas a linear convolution between signals $x[n]$ and $y[n]$ is implied by the IDTFT expression $$\mathcal{I-DTFT} \{ X(e^{j\omega})H(e^{j\omega}) \}$$ on the other hand a circular convolution between two periodic sequences is implied by the IDFT expression $$\mathcal{I-DFT} \{ X[k]H[k] \}$$

[minor amendment made above - typo correction only]

Where both the forward and inverse DFT sequences are implied with their lengths $M$,$N$.

So the problem is, given that we need to compute the linear convolution $y[n]= x[n] \star x[n]$ between two aperiodic sequences $x[n]$ and $y[n]$ of lengths $L_x$ and $L_y$ samples respectively, in the frequency domain bu utilizing their $N$ point DFTs $X[k]$ and $Y[k]$, which however implies a circular convolution between periodic extensions of the signals $x[n]$ and y[n] of periods $N$. Then how can we accomplish this task?

The key is in the length $N$ of the DFTs, which must be long enough to avoid any time aliasing of the output sequence implied by the periodic extenison returned by the IDFT computation: $$\tilde{y}[n] = \sum_{r=-\infty}^{\infty} y[n-rN]$$ where $y[n]$ is the result of the linear convolution that would be reyurned by the theoretical inverse DTFT $Y(e^{j \omega}) = \mathcal{I-DTFT} \{ X(e^{j\omega})H(e^{j\omega}) \}$ and $\tilde{y}[n]$ is the periodic result of the periodic convolution implied by the IDFT.

The implementation of a linear convolution via DFT then has the following steps:

1. Choose M according to the following criteria: $$M \geq L_x + L_h -1$$ which guarantees an alias-free reconstruction of the inverse signal $y[n]$ from its DFT $Y[k]$ of the computed circular convolution via $X[k]H[k]$.

2. Compute M-point DFTs $X[k]$ and $H[k]$ of $x[n]$ and $h[n]$.

3. Compute $Y[k] = X[k]H[k]$

4. Compute M-point inverse DFT of $Y[k]$ to produce the output $y[n]$

1. Why are we using circular convolution in DSP?

In DSP we normally deal with finite length discrete sequences (even if the signal under study is infinite we can only analyze a finite portion of it at a time). When it comes to processing a signal the way to process it must me implementable in a discrete logic device (namely a device that can't store continuous values because this values are infinite and it has a finite amount of memory, storage,etc). This explains why Discrete Time Fourier Transform (DTFT) which transforms a discrete time sequence into a continuous frequency sequence can't be implemented in hardware. Linear convolution in time is equivalent to the multiplication of 2 sequences DTFTs, but as DTFT can't be implemented in hardware this is not the way to obtain linear convolution. Discrete Fourier Transform (DFT), on the other hand, transforms a discrete time sequence into a discrete frequency sequence and this allows it to be implemented in hardware. Yet multiplying 2 sequences DFTs is equivalent to circular convolution in principle (linear convolution may also be obtained if the time sequences are previously padded with enough zeros, see explanation below). The reason why multiplying 2 sequences DFTs is equivalent to circular and not linear convolution comes from the fact that DFT for a finite time length sequence is equivalent to the Discrete Fourier Series (DFS) of that very same finite time length sequence periodically extended (concatenating the finite time length sequence infinitely in time axis) taken over one period. DFS is also periodic in frequency domain so linear convolution does not apply there (see 8.2.5 and 8.6.5 of Oppenheim's Discrete Time Signal Processing 3rd edition )

1. What's the main solid reason for the use of it in digital processing?

It is obtained by DFT multiplication and DFT is easily implemented in hardware. Moreover very efficient algorithms such as FFT exist for computing the DFT

1. Why does the concept of circular convolution come more often than linear convolution?

That's depending on the application. Circular convolution may also yield the linear convolution. For instance, let's say we are working with signal A of length N and signal B also of length N (it can also be done for different lengths). The circular convolution will be of length N. In order to obtain linear convolution both A and B must be padded with zeros until they achieve a length of at least 2*N - 1. Then applying the DFT on both, multiplying them and applying inverse DFT will give you the linear convolution

Here's a bit of intuition:

When you deal with signals digitally, you are always dealing with a finite signal. This is because you can only process on a finite amount of data points.

The problem however is that when you perform transformations into the frequency domain using the DFT, by definition a signal cannot be finite. Therefore when doing a DFT operation, theres is an implicit alteration to your signal from being finite, to being periodic, even if your signal is not periodic.

This periodicity of the signal leads to the need of using convolution in a circular manner.

The DFT/FFT is a useful computational "hammer", but all of it's transform basis vectors are circular (integer periodic) in aperture, and can be infinitely extended as periodic functions, which some users confuse with the nature of their input data.

If you zero-pad by a sufficient amount, circular convolution produces the same result as linear convolution, but at a slightly greater computational cost than circular.