1
$\begingroup$

Context

I am studying the family of Discrete Trignometric Transforms (DTT): Discrete Cosine Transforms (DCT) and Discrete Sine Transforms (DST). And trying to understanding more their properties, I came up to the following concepts.

Linear Convolution

$$y[n] = x[n] \star h[n] = \sum_{k=0}^{N-1}x[k] \, h[n-k]$$

Finite Sequence

$$x = {x_0, x_1, ..., x_{n-1}}$$

Which is usually extended by:

$$ x[n]= \begin{cases} x_n, &\text{for } n \in [0, N-1]\\ 0, &\text{o.w.}\\ \end{cases} $$

Then, we have this section of this book: Page 45-46 of book: Discrete Cosine and Sine Transforms. This page shows the definition for Circular and Skew-Circular Convolutions

Question

How to properly use the formulas for circular convolution and skew-circular convolution? Why to use these if they are equivalent to the traditional convolution formula?

My first thought was for avoiding re-calculations. But I didn't quite visualized and example.

[Updated] I know that, as defined by the convolution theorem property, the convolution in frequency domain, (for instance the Fourier Domain) requires less operations for signals above a certain size, then operating it in the spatial domain. This is not what I am looking for.

$\endgroup$
1
$\begingroup$

Circular convolution can be done using FFTs, which is a O(NLogN) algorithm, instead of the more transparent O(N^2) linear convolution algorithms. So the application of circular convolution can be a lot faster for some uses.

However, with a tiny amount of post processing, a sufficiently zero-padded circular convolution can produce the same result as a linear convolution, while still being a lot faster when using FFTs. This is because the tail portion of a sufficiently long zero-padded convolutional result is all zeros, rather than being a non-zero tail result that mixes/sums with the beginning of the convolution result when doing circular convolution, which can make a mess out of non-perfectly-periodic inputs.

For sequences of windows of data, one can extend this to overlap-add or overlap-save FFT fast linear convolution.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thanks for the answer, but this is not exactly what I was referring to. I meant those formulas specifically, and they regard DCT, not DFT. $\endgroup$ – Eduardo Reis Nov 12 '19 at 5:26
0
$\begingroup$

When you want to perform a time-domain linear convolution using a transform (Fourier, trigonometric) domain multiplication technique, then the concept of circular convolution arise.

Because the effect of transform-domain multiplication on the time-domain is a circular convolution.

Therefore a linear convolution is actually implemented by an underneath circular convolution through such a technique.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thanks for the answer, but this is not exactly what I was referring to. I meant those formulas specifically, and they regard DCT, not DFT. $\endgroup$ – Eduardo Reis Nov 12 '19 at 5:26

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.