What is the circular convolution and how does it differ from the linear convolution?
The Convolution Series
- Definition of convolution and intuition behind it
- Mathematical properties of convolution
- Convolution property of Fourier, Laplace, and z-transforms
- Identity element of the convolution
- Star notation of the convolution
- Circular vs. linear convolution
- Fast convolution
- Convolution vs. correlation
- Convolution in MATLAB, NumPy, and SciPy
- Deconvolution: Inverse convolution
- Convolution in probability: Sum of independent random variables
Table of Contents
- Convolution Theorem of the DFT?
- Circular Convolution Example
- Why Is the Convolution Circular?
- Circular vs. Linear Convolution
- Periodic Convolution
- Valid Samples of Circular Convolution: The Answer
- Circular Convolution Implementation
Circular convolution is a term that arises in discussions about the discrete Fourier transform (DFT) and fast convolution algorithms. What is it and how does it differ from the linear convolution?
Before we answer that question we need to (somewhat surprisingly) examine the DFT more closely.
Convolution Theorem of the DFT?
Definition of the DFT
Let us recap the definition of the discrete Fourier transform of a finite, discrete-time signal of length
Convolution Theorem of the Fourier Transform
In one of the previous articles we argued that for the continuous-time Fourier transform it holds that
i.e., the Fourier transform of a convolution equals the multiplication of the Fourier transforms of the convolved signals. A similar property holds for the Laplace and z-transforms. However, it does not, in general, hold for the discrete Fourier transform. Instead, multiplication of discrete Fourier transforms corresponds to the circular convolution of the corresponding time-domain signals .
Convolution Theorem of the DFT
In mathematical terms, given two finite, discrete-time signals and , both of length , and their DFTs
the multiplication of their DFTs corresponds to their circular convolution in the time domain
Circular Convolution Definition
Here, symbol denotes the circular convolution. It is defined as
where denotes the modulo operation, i.e., etc.
Since both signals are of length , it is called an N-point circular convolution.
Linear Convolution Definition
The name “circular” distinguishes it from the linear convolution, as we introduced it in the previous articles
Note the absence of the modulo operation. Although we do not prove it here, circular convolution is commutative, exactly like the linear convolution.
Circular Convolution Example
Let’s look at a comparison between a linear and a circular convolution.
Let’s assume we have a signal
Figure 1. .
and a discrete-time impulse delayed by 1 sample
Figure 2. .
The linear convolution between the two delays by one sample, as expected
Figure 3. Linear convolution between and .
However, the circular convolution performs a circular shift of the signal
Figure 4. Circular convolution between and .
Circular shift means that whichever samples “fall off” one end reappear at the other end of the signal vector. In other words, the excessive samples “wrap around” the signal buffer.
Why Is the Convolution Circular?
The convolution property of the DFT results directly from the periodicity of the DFT.
The periodicity itself can be explained in at least two ways:
- From the relation of the DFT to the discrete Fourier series (DFS).
- From the sampling of the discrete-time Fourier transform around the unit circle on the z-plane.
Discrete Fourier Transform and Discrete Fourier Series
Discrete Fourier series is a representation of a periodic discrete signal with period via a summation
Equation 9 is identical to Equation 1, i.e, the definition of the DFT, with the exception that the signal under the sum is periodic (denoted by the tilde) and is not bounded to the set. While the DFS assumes that the signal is periodic, i.e., it repeats itself modulo , the DFT assumes that is 0 for outside the index set .
The same holds for the DFT coefficients
Unfortunately, the fact that and are 0 for is only implicit. It means we can state it but we cannot enforce it. Since the DFT uses directly the formulas of the DFS, the DFT will behave as if the signal was periodic with period . The only solution to that, would be padding the signal vector with infinitely many zeros. Without such a padding, the DFT is also periodic with period .
DFT Periodicity Example
Let’s say we have a signal given as a vector with four samples
Figure 5. .
You may think it is defined as follows
Figure 6. as we wish it to be.
but the DFS (and the DFT accordingly) treat it as
Figure 7. as seen by discrete Fourier series and the discrete Fourier transform.
Analogously, in the discrete frequency domain, we can obtain the magnitude Fourier coefficients from Equation 1. This yields
Figure 8. Magnitude discrete-frequency coefficients of .
Again, one may assume that it is defined as follows
Figure 9. Magnitude DFT of naively visualized with zeros surrounding the 4 nonzero coefficients.
but the inherent periodicity of the DFT results in
Figure 10. True magnitude DFT of .
Sampling of the Fourier transform
All of the above observations are confirmed when one treats the DFT as a sampled version of the band-limited discrete-time Fourier transform (DTFT). Discrete-time Fourier transform is the z-transform evaluated on the unit circle . The DFT samples the DTFT at points fixed by the sampling rate. Since we sample around a circle, after samples we wrap around and start sampling the same points again. Refer to  for a more detailed explanation of this approach to DFT’s periodicity.
Aliasing in the Time Domain
Having established that the DFT is periodic, we can now explain the circular convolution phenomenon. I like to think of it as aliasing in the time domain.
Note: We have discussed the notion of aliasing in the frequency domain in one of the previous articles.
Output Length of Discrete Convolution
Let’s recall our signal from Figure 1 and signal from Figure 2. is of length 4, is of length 2. In Figure 3 we can see that the linear convolution between and is of length 5. In general, a convolution of two sequences of length and respectively yields a signal of length .
How does it look when we go through the DFT domain?
Multiplication in the DFT domain
Adopting the notation from Equations 3 and 4, let’s denote by the multiplication of ’s and ’s DFTs
In order to make the index correspond to the same discrete frequencies for and , discrete-frequency coefficients and need to be of equal length. We achieve it by padding with 2 zeros, i.e., replacing the 2-element signal with a 4-element one with values 0, 1, 0, 0 for respectively. Now and are of equal length and their DFTs are as well.
Back to the time domain
We now want to find signal that corresponds to , i.e.,
We can achieve it via inverse discrete Fourier transform (iDFT)
If and were continuous-time and we were using the Fourier transform instead of the discrete Fourier transform, the convolution theorem would tell us that is the convolution of and . We explicitly showed that the convolution of and should be a discrete signal of length 5 (see Figure 3). How long is ?
Inverse DFT inherently assumes that the time domain signal is of the same length as the frequency-domain coefficient vector. Thus, is of length 4. So by multiplying frequency-domain vectors and and going back to the discrete-time domain we squashed a 5-element-long vector into a 4-element-long vector. Thus, we introduced aliasing in the time domain; hence the wrap-around of the last sample in Figure 4, and more broadly, circular convolution effect.
In mathematical terms,
An Important Conclusion
We have seen that the circular convolution somehow distorts the linear convolution. But in our example, was circularly shifted, not completetely destroyed. Moreover, all but the first sample were valid samples of the linear convolution. Thus, we might suspect that sufficiently lengthening and with zero-padding would allow us to obtain the linear convolution out of the circular convolution result. This is the basis of fast convolution algorithms, which will be discussed in one of the following articles.
Circular vs. Linear Convolution
The conclusion from the previous section is that
A subset of the circular convolution result corresponds to the linear convolution result.
The question is: which subset?
Example: Common Samples of Linear and Circular Convolution
Figures 11 and 12 present the linear and circular convolution example, respectively, with marked matching samples. They match in terms of indices and amplitude.
Figure 11. Linear convolution result. Samples marked in red would also be correctly calculated by the circular convolution.
Figure 12. Circular convolution result. Samples marked in red correspond to the linear convolution result in terms of index and amplitude.
To understand fully which samples in the circular convolution correspond to the correct samples of the linear convolution we need to look at a concept broader than circular convolution: periodic convolution.
Circular convolution is an example of periodic convolution–a convolution of two periodic sample sequences (with the same period) evaluated over only one period . It’s formula is identical to the formula of the circular convolution (Equation 6), but we assume that its output is periodic. “But in our case and are not periodic!”, you might say. Yes, they are not periodic, unless we compute their DFTs. The DFT assumes the signal to be perodic and, thus, going into the DFT domain introduces the periodicity permanently. It does not have to be harmful; on the contrary, it can be quite useful. It just requires us to be extra cautious.
Let’s compare the linear convolution and the periodic convolution. Given signals and (zero-padded) , their periodic versions look as follows (black color indicates samples stored in the vector, grey color indicates implicit sample values)
Figure 13. Signal : periodic version of . Figure 14. Signal : periodic version of .
Let’s compare the linear convolution of the original and
Figure 15. Linear convolution of and . Its length is 5.
with the periodic convolution of their periodic counterparts
Figure 16. Periodic convolution of and . Its length is 4 and it’s periodic.
We can observe that the circular convolution is a superposition of the linear convolution shifted by 4 samples, i.e., 1 sample less than the linear convolution’s length. That is why the last sample is “eaten up”; it wraps around and is added to the initial 0 sample.
Once again: had length 4, had length 2, their linear convolution had length 5, the circular convolution had length 4, and the “valid” samples were the last 3. As we will see next the “excessive” sample wrapped around and “destroyed” the first sample, thus, we were left with only 3 samples that were identical to the linear convolution result. This is what I mean by “time-domain aliasing”: the periodic copies of the linear convolution (as implied by the DFT) start overlapping because we didn’t left them enough space (=”frequency-domain sampling rate”) in the DFT domain. Thus, we get time-domain artifacts.
Valid Samples of Circular Convolution: The Answer
Let’s summarize what we have discovered so far:
- Multiplication in the DFT domain is equivalent to circular convolution in the discrete-time domain.
- -point DFT treats the signals as -periodic.
- Linear convolution of discrete signals of length and has length .
- -point circular convolution has length .
Let’s assume that we have two signals, of length and , . We want to know which samples of their circular convolution are equal to the corresponding samples of their linear convolution.
- First, we pad the shorter signal with zeros. Now both signals have length .
- The result of the circular convolution has length .
- The samples that did not fit the linear convolution wrapped around and were added to the beginning of the output. The exact number of wrapped-around samples is
- The above means that the first samples of the output need to be discarded. This means that the last samples are valid, i.e., samples at indices (we start indexing from 0).
Circular Convolution Implementation
A straightforward implementation of the circular convolution, as presented in Equation 6, is rather brute-force
This implementation has time complexity .
However, the convolution property of the DFT, as presented in Equation 5, suggests a much more efficient implementation
The complexity of the “fast” implementation is determined by the complexity of the forward and inverse DFT as implemented in the
numpy.fft module, which is .
Equal shapes checked in the assertion can be ensured by padding the shorter signal with zeros.
The efficient circular convolution implementation via the Fast Fourier Transform (FFT) will serve as a basis when we will discuss fast linear convolution implementations.
In this article, we looked at the difference between the circular and the linear convolution. The former treats both given sequences as periodic and is evaluated only for the number of samples corresponding to the period.
A subset of samples resulting from the circular convolution corresponds to the samples of the linear convolution.
Circular convolution can be implemented efficiently via multiplication in the DFT domain.
 Alan V Oppenheim, Ronald W. Schafer Discrete-Time Signal Processing, 3rd Edition, Pearson 2010.
 Alan V. Oppenheim, Alan S. Willsky, with S. Hamid Signals and Systems, 2nd Edition, Pearson 1997.
 Frank Wefers Partitioned convolution algorithms for real-time auralization, PhD Thesis, Zugl.: Aachen, Techn. Hochsch., 2015.
Comments powered by Talkyard.