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.
