# 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:

# 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.

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.

• 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. – Eduardo Reis Nov 12 '19 at 5:26

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.

• 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. – Eduardo Reis Nov 12 '19 at 5:26