8
$\begingroup$
  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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – robert bristow-johnson Oct 29 '16 at 17:19
7
$\begingroup$

Given a discrete time LTI system with impulse response $h[n]$, one can compute its response to any input $x[n]$ by a convolution sum: $$y[n] = x[n] \star h[n] = \sum_{k=-\infty}^{\infty} {h[k]x[n-k]} \tag{1}$$

Without anything further stated, above definition is for the linear convolution (aperiodic convolution) between $h[n]$ and $x[n]$, which are aperiodic discrete-time sequences of possibly infinite length, unless otherwise stated. This is different from a circular convolution which is between two periodic sequences of period $N$, and computed over a single period.

You can compute a linear convolution in time domain by Eq.1, or in frequency domain using the following DTFT (discrete-time Fourier transform) property: $$y[n] = x[n]\star h[n] \implies Y(e^{j\omega}) = X(e^{j\omega}) H(e^{j\omega}) \tag{2}$$

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

When you want to make a calculation by hand, using symbolic expressions for signals, such as $x[n]=a^n u[n]$ and $h[n]=b^n u[n]$, you can calculate the results in time or frequency domains as outlined above.

Also, when you want to compute the same result by using a computer, you can use the time domain approach based on an LCCDE recursion (for IIR systems) or direct finite convolution sum (for FIR systems), BUT the frequency domain approach won't work with DTFT; as it's mainly a tool used to develop the mathematics of signals & systems theory, and it's not suitable for digital computer implementations, as its variable $\omega$ is a real continuous number.

What is used instead is the DFT (discrete Fourier transform) defined as $$ X[k] = X(e^{j\omega})|_{\omega = \frac {2\pi k}{N} } \tag{4}$$

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]$.

Eq.4 implies that the DFT sequence $X[k]$ is obtained as the uniform samples of the DTFT $X(e^{j\omega})$, which is a periodic function, hence DFT $X[k]$ is also periodic but we only consider its first period from $k=0$ to $N-1$.

Since DFT sequences are inherently periodic, then their convolutions will also be periodic (circular). Therefore, whereas a linear convolution between aperiodic signals $x[n]$ and $y[n]$ is implied by the I-DTFT expression $$y[n] =\mathcal{I-DTFT} \{ X(e^{j\omega})H(e^{j\omega}) \}$$ instead a circular convolution between two periodic sequences is implied by the I-DFT expression $$\tilde{y}[n] = \mathcal{I-DFT} \{ X[k]H[k] \}$$

So, given that we want to compute a linear convolution between two aperiodic sequences $x[n]$ and $h[n]$ of lengths $L_x$ and $L_h$ respectively, using frequency domain by their $N$ point DFTs, $X[k]$ and $H[k]$, we actually have to compute a circular convolution between the periodic extensions of the signals $\tilde{x}[n]$ and $\tilde{h}[n]$ of periods $N$.

The key is in chosing a proper length $N$ of the DFTs, which must be long enough to avoid any time domain aliasing of the sequence $\tilde{y}[n]$, returned by the IDFT computation: $$ \tilde{y}[n] = \sum_{r=-\infty}^{\infty} y[n-rN] \tag{5}$$

where $y[n]$ is the result of the linear convolution that would be returned by the theoretical inverse DTFT and $\tilde{y}[n]$ is the periodic result of the periodic (circular) convolution implied by the inverse DFT.

Note that if any one of the signals are of infinite length, then it's NOT possible to compute their linear convolution using the DFT approach, as $N$ would go to infinity, practically impossible. The implementation of a linear convolution via DFT then has the following steps:

  1. Choose N according to the following criteria: $$N \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 N-point DFTs $X[k]$ and $H[k]$ of $x[n]$ and $h[n]$.

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

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

$\endgroup$
2
$\begingroup$

Answering to your questions:

  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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.