Circular Convolution

                          The circular convolution, also known as cyclic convolution, of two aperiodic functions occurs when one of them is convolved in the normal way with a periodic summation of the other function.  That situation arises in the context of the Circular Convolution theorem. It occurs naturally in digital signal processing when DTFTs and inverse DTFTs are replaced by DFTs and inverse DFTs. Before going into the details of circular convolution we must know the circular shift, so let us start with circular shift. 

Circular Shift  
 The circular shift of a sequence x(n) is defined as follows:
                              

  where 'n ₀' is the amount of the shift and rectangular window:
                                         

A circular shift may be visualized as follows. Suppose that the values of a sequence x(n), from n = 0 to n = N-1, are marked around a circle as illustrated in Fig. (a) or in an eight-point sequence. A circular shift to the right by 'n ₀' corresponds to a rotation of the circle 'n ₀' positions in a clockwise direction. An example illustrating the circular shift of a four-point sequence is shown in Fig. (b).

Another way to circularly shift a sequence is to form the periodic sequence with period equal to the length of the given sequence, and then linear shift this periodic sequence by 'n₀', and then extract one period of this shifted sequence by multiplying by rectangular window. As shown in figure below:

Circular Convolution

Let h(n) and x(n) be finite-length sequences of length N with N-point DFTs H(k) and X(k), respectively. The sequence that has a DFT equal to the product Y(k) = H(k)X(k) is 

                

where the sequence used in above summations are the periodic extensions of the sequences x(n) and h(n), respective1y. The sequence y(n) in above is the N-point circular convolution of h(n) with x(n), and it is written as
                                 

The circular convolution of two finite-length sequences h(n) and x(n) is equivalent to one period of the periodic convolution of the periodic sequences made by the periodic extension of x(n) and h(n), prospectively.

In general, circular convolution is not the same as linear convolution, and N-point circular convolution is different, in general, from M-point circular convolution when M does not equal to N.

Example
Let us find the four-point circular convolution of the sequences h(n) and x(n)shown in figure:

The four point convolution is given by
                                             

The value of y[n] at n=0 is
                                             

To evaluate y(0), we multiply this sequence by x(k) and sum the product from k=0 to k=3. The result is y(0) = 1. Next, to find the value of y(1), we evaluate the sum

                                             

and we find y[1]=4. Repeating for n = 2 and n = 3, we have
                                             

Therefore
                 
The linear convolution of x[n] and h[n] is
    
Note that the results of circular convolution and linear convolutions are different for same x[n] and h[n]. The short method for finding the circular convolution is to set up a table using the results of linear convolution and evaluate the sum
                                     

This is done by listing the values of the sequence y(n+kN) in a table and summing these values for n = 0, 1,2,3. Note that the only sequences that have nonzero values in the interval 0<=n<=3 are y(n) and y(n + 4), and these are the only sequences that need be listed. Thus, we have

Summing the columns for 0<=n<=3, we have

                          
 Which is same as we calculated mathematically.