Circular convolution is the convolution of two sequences treated as if they are periodic with the same period N, rather than finite-length sequences extending to zero outside their defined range. It arises naturally when computing convolution via the Discrete Fourier Transform (DFT), because the DFT implicitly assumes periodicity of its input.
In practice
In embedded DSP work, circular convolution appears whenever you multiply two DFT (or FFT) spectra and take the inverse DFT. If you have two time-domain sequences of lengths L and M and you want their linear (ordinary) convolution, the result has length L + M - 1. If you perform the DFT of each sequence using an N-point FFT where N < L + M - 1, the output will be a circularly convolved result, not the linear convolution you intended. This is a common source of subtle errors in FIR filter implementations and correlation routines.
The standard fix is zero-padding both input sequences to at least length L + M - 1 before taking the FFT. This ensures that the periodic wrap-around implicit in the DFT does not cause time-domain aliasing, and the circular convolution result matches the desired linear convolution. When using a radix-2 FFT, choosing N to be the next power of two at or above L + M - 1 is a common practice, though many FFT libraries support mixed-radix or arbitrary lengths and do not require a power-of-two size.
In block-based processing pipelines on microcontrollers or DSPs, the overlap-add and overlap-save methods use circular convolution intentionally and efficiently. These methods break a long input stream into shorter blocks, convolve each block with a filter kernel via FFT, and reconstruct the linear convolution output by carefully managing block boundaries. On MCUs with DSP instructions or hardware math accelerators (such as certain STM32 parts), or on dedicated DSP cores like the C55x family, and using optimized software libraries such as CMSIS-DSP, these block convolution approaches can achieve significantly lower cycle counts than time-domain FIR filtering for long filter kernels.
A less obvious scenario: if you are computing autocorrelation or cross-correlation via FFT on a short buffer without zero-padding, circular wrap-around in the correlation output can make lag estimates near the buffer edges unreliable in many common estimator configurations. Always account for the effective analysis length after accounting for wrap-around when interpreting correlation results in embedded signal processing or sensor fusion applications.
Learn this in DSP Foundations
Discussed on DSPRelated
Frequently asked
What is the difference between circular convolution and linear convolution?
Linear
convolution of sequences of length L and M produces an output of length L + M - 1, with no wrap-around. Circular convolution of the same sequences over a period N treats both as periodic with period N, so samples that would fall outside [0, N-1] wrap around and add to samples at the beginning of the output. When N >= L + M - 1 and both sequences are zero-padded to length N, circular convolution gives the same result as linear convolution.
Why does multiplying two FFT spectra give circular convolution instead of linear convolution?
The
DFT represents a finite-length sequence as one period of an infinitely repeating periodic signal. The
convolution theorem states that pointwise multiplication in the
frequency domain corresponds to convolution in the
time domain, but that convolution is circular with period N (the DFT size), not linear. To recover linear convolution, zero-pad the input sequences so N is at least L + M - 1 before taking the
FFT.
How do overlap-add and overlap-save relate to circular convolution?
Both methods use
FFT-based circular
convolution as their core operation, but they manage the block boundaries so the final output is equivalent to linear convolution of the full input stream with a filter kernel. Overlap-add zero-pads each input block and adds the overlapping tail of each output block to the next. Overlap-save keeps extra input samples from the previous block so the circular wrap-around discards only the aliased prefix, keeping the valid portion. Both are practical for long
FIR filters in embedded streaming pipelines.
How do I choose the FFT size N to avoid circular convolution artifacts?
Set N >= L + M - 1, where L is the length of your data block and M is the length of your filter kernel (or the other sequence). Zero-pad both sequences to length N before the
FFT. For radix-2 FFT implementations, round N up to the next power of two. For example, convolving a 128-sample block with a 32-tap
FIR kernel requires N >= 159, so you would use N = 256.
Can circular convolution ever be the desired operation rather than a problem to avoid?
Yes. In some applications such as watermarking, spread-spectrum modulation, or certain fast correlation techniques, the periodic nature of circular
convolution is exactly what is needed. It is also the natural operation for computing the
DFT of a signal that is genuinely periodic with period N, such as a synthesized tone buffer played back in a loop. In those cases, no zero-padding is required and circular convolution gives the correct result directly.
Differentiators vs similar concepts
Circular
convolution is frequently confused with linear convolution. Linear convolution is the standard mathematical convolution used in
FIR filter theory, producing an output longer than either input with no wrap-around. Circular convolution wraps the output around modulo N and has the same length N as the
DFT used. The two are equivalent only when N >= L + M - 1 and both inputs are zero-padded to length N. Circular convolution is also distinct from cyclic convolution as a general algebraic term, though in DSP contexts the two phrases typically refer to the same operation.
