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 the book General Properties, Fast Algorithms and Integer Approximations: Page 45-46 of book: Discrete Cosine and Sine Transforms. This page shows the definition for Circular and Skew-Circular Convolutions


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.


2 Answers 2


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.

  • $\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$ Nov 12, 2019 at 5:26

The transformation defined in the book (Cosine and Sine) are based on symmetric or anti symmetric functions.

The implied information is that when we use them to apply convolution they will apply Circular Convolution (This is true to both) while one will apply it with Symmetric and the either anti symmetric.

When we use it? Whenever we analyze signals using either transformation.


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.