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
  • 3
    $\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 '16 at 17:19
10
$\begingroup$

Given a discrete-time LTI system with impulse response $h[n]$, one can compute its response to any (proper) 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}$$

Without anything further stated, Eq.1 is a linear convolution (aperiodic convolution) between $h[n]$ and $x[n]$, which are typically aperiodic discrete-time sequences, and of possibly infinite duration.

This is different from a circular convolution which is 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.

Using hand-calculations, one can compute a linear convolution in the time-domain, based on Eq.1, or in the 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 summation limits: $$X(e^{j \omega}) = \sum_{n=-\infty}^{\infty} x[n] e^{-j\omega n} \tag{3}$$

To numerically evaluate the same result with a computer, one can use the time-domain approaches, BUT not the frequency-domain approach with DTFT; since DTFT not naturally suited for digital computer implementations; as its variable $\omega$ is a real continuous number.

Then what is used with a digital computer, instead, 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$, and $N$ is the length of the DFT, which's then called as an N-point DFT of signal $x[n]$. DFT $X[k]$ is a periodic function, inherited from periodicty of DTFT, but we only consider its first period from $k=0$ to $N-1$.

Eq.2 using DFT is stated as:

$$x[n] (\star) h[n] \leftrightarrow X[k]H[k] \tag{5}$$ where, all sequences in Eq.5 are periodic with period $N$. 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 $h[n]$ is implied by the I-DTFT expression $$y[n] =\mathcal{I-DTFT} \{ X(e^{j\omega})H(e^{j\omega}) \} \tag{6}$$ instead, a circular convolution between their periodic extensions is implied by the I-DFT expression $$\tilde{y}[n] = \mathcal{I-DFT} \{ X[k]H[k] \} \tag{7}$$

The relation between the linear convolution result (the desired sequence) $y[n]$ and the circular convolution result (the computed sequence) $\tilde{y}[n]$ is given by: $$ \tilde{y}[n] = \sum_{r=-\infty}^{\infty} y[n-rN] \tag{8}$$

As a consequence, the correspondence between the desired linear convolution and the computed circular convolution depends on the DFT length $N$ which must be larger than the length of desired sequence $L_y$ of $y[n]$, to avoid any time-domain aliasings implied by Eq.8, when $N < L_y$ .

So, given that we want to compute effectively a linear convolution $y[n]$ of length $L_y$ between two aperiodic sequences, $x[n]$ and $h[n]$ of lengths $L_x$ and $L_h$, by their $N$-point DFTs, $X[k]$ and $H[k]$, what we actually obtain by the inverse N-point DFT of $X[k]Y[k]$ is the result of the $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]$.

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.

$\endgroup$
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, privacy policy and cookie policy

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