Circular convolution

In digital signal processing, circular convolution (aka cyclic convolution) is an effect that occurs when using the fast Fourier transform to perform convolution by means of multiplication in the frequency domain. In the time-domain, convolution filtering is inherently a continuous streaming process. But in the frequency domain, block-processing is required. The signal is divided into segments and processed piecewise. Then the filtered segments are carefully pieced back together, mindful of circular convolution considerations, which means that a portion of each output segment must be discarded. Data loss is avoided by overlapping the initial input segments.

The DFT and FFT inherently operate on finite length snapshots of data, and treat each one as though it is periodic. That is the source of the problem, and therefore circular convolution is easiest to visualize via periodic extension of the input data block, as depicted in the fourth frame of the figure. After the convolution, the output of the added blocks overlaps the contribution of the original block, as depicted in the fifth frame. The portion colored green in the last frame represents the unadulterated output from the original input block.