14
$\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$
1
  • 4
    $\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$ Oct 29, 2016 at 17:19

4 Answers 4

12
$\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.a}$$

It's a linear convolution (aperiodic convolution) for $ -\infty < n < \infty$ between aperiodic sequences of finite or infinite duration.

A circular convolution is by definition between two periodic sequences, $\tilde{x}[n]$ and $\tilde{y}[n]$, of period $N$:

$$ \tilde{y}[n] = \sum_{k=0}^{N-1}\tilde{x}[(k)_N]\tilde{h}[(n-k)_N] \tag{1.b}$$ and computed over a single period, and $()_N$ is the modulus operator.

Hand computation of a linear convolution can be performed either in the time-domain, based on Eq.1a, or in the frequency-domain via 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}$$

Where the DTFT is: $$X(e^{j \omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n} \tag{3}$$

Note that DTFT is naturally related with the linear convolution, because it deals in general with aperiodic (as well as periodic) sequences of finite or infinite duration.

To numerically evaluate the convolution sum with a computer, one can still use the time-domain Eq.1a, BUT not the frequency-domain Eq.2; since the DTFT output variable $\omega$ is a real continuous number; not representable with a digital computer (we shall ignore the computer symbolic algebra systems for obvious reasons).

To achieve Eq.2, we shall use finite-length discrete varible transform that can be represented with a digital computer, which is the DFT (discrete Fourier transform) $X[k]$ defined as the uniform samples of the DTFT: $$ X[k] = X(e^{j\omega})|_{\omega = \frac {2\pi k}{N} } \tag{4}$$

where $k=0,1,...,N-1$ implies $0 \le \omega < 2\pi$, and $N$ is the length of the $N$-point DFT $X[k]$ which is actually a periodic sequence, inherited from periodicty of DTFT, but we only consider its first, base, period.

Then for periodic sequences, Eq.2 is restated using the DFT as follows:

$$x[n] (\star) h[n] \leftrightarrow X[k]H[k] \tag{5.a}$$

$$ \tilde{x}[n] (\star) \tilde{h}[n] \leftrightarrow X[k]H[k] \tag{5.b}$$

where, all sequences in Eq.5 are periodic with period $N$. Since DFT sequences are inherently periodic, then their convolution, in Eq.5b, will also be periodic (circular).

Therefore, implementing a convolution in the frequency-domain is based on Eq.5b, with the following relation between a linear and a circular convolution.

An aperiodic sequence $y[n]$, obtained with a linear convolution between aperiodic sequences, is implied by the inverse DTFT $$y[n] =\mathcal{I-DTFT} \{ X(e^{j\omega})H(e^{j\omega}) \} \tag{6.a}$$ $$y[n] =\frac{1}{2\pi} \int_{-\pi}^{\pi}X(e^{j\omega})H(e^{j\omega}) e^{j \omega n} d\omega \tag{6.b}$$

whereas, a periodic sequence $\tilde{y}[n]$, obtained with a circular convolution between periodic sequences, is implied by the inverse DFT $$\tilde{y}[n] = \mathcal{I-DFT} \{ X[k]H[k] \} \tag{7.a}$$ $$\tilde{y}[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k]H[k] e^{ \frac{2 \pi}{N} k n} \tag{7.b}$$

The fundamental relation between the linear convolution output $y[n]$ and the circular convolution output $\tilde{y}[n]$ is that $\tilde{y}[n]$ is the periodic extension of $y[n]$: $$ \tilde{y}[n] = \sum_{r=-\infty}^{\infty} y[n-rN] \tag{8}$$

As a consequence of Eq.8, the match between the desired linear convolution output and the computed circular convolution output depends critically on the DFT length $N$ which must be larger than the length of the desired sequence to avoid any time-domain aliasing implied by Eq.8, when $N < L_y$.

Eventually, for computing linear convolution $y[n]$ of length $L_y$ between sequences $x[n]$ and $h[n]$ of lengths $L_x$ and $L_h$, we multiply their $N$-point DFTs $X[k]$ and $H[k]$, and compute its inverse $N$-point DFT, which yields $N$-point circular convolution $\tilde{y}[n]$ between $N$-point periodic extensions $\tilde{x}[n]$ and $\tilde{h}[n]$ of $x[n]$ and $h[n]$. Extracting the first period of $\tilde{y}[n]$, yields the desired $y[n]$.

Finally, implementation of a linear convolution using DFT has the following steps:

  1. Given inputs $x[n]$ and $h[n]$of lengths $L_x$ and $L_h$

  2. Choose DFT length $N$ according to: $$N \geq L_x + L_h -1$$ to guarantee alias-free reconstruction of $y[n]$.

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

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

  5. Compute $N$-point inverse DFT of $Y[k]$ to produce the output $y[n]$ in the first $L_y$ samples.

Note that each DFT above is actually implemented with an FFT for reason of efficiency.

$\endgroup$
2
  • $\begingroup$ Extensive rewrite, 32. I just thought I'd make it consistent at the end. $\endgroup$ May 15 at 14:34
  • $\begingroup$ @robertbristow-johnson well thanks ;-) $\endgroup$
    – Fat32
    May 16 at 0:20
4
$\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 be 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$
3
$\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$
2
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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