Circular convolution, also called cyclic convolution, is the convolution of finite sequences with
their indices interpreted modulo a common length 
. For 
, ..., 
and 
, ..., 
, it is defined by
 |
for 
, ..., 
. Here 
denotes the mod operation. Circular
convolution is commutative and associative.
With the discrete Fourier transform convention 
, where 
is the imaginary unit, and
similarly for 
and 
, the convolution
theorem gives
 |
Thus circular convolution can be computed using a fast Fourier transform. Ordinary convolution of two
finite sequences of lengths
and 
is obtained by appending zeros to both up to a length 
before taking their circular
convolution. This prevents the end of the result from wrapping around to its beginning.
