Digital Signal Processing - Circular Convolution

The circular convolution, also known as cyclic convolution, of two aperiodic functions (i.e. Schwartz 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.  The identical operation can also be expressed in terms of the periodic summations of both functions, if the infinite integration interval is reduced to just one period.  That situation arises in the context of the discrete-time Fourier transform(DTFT) and is also called periodic convolution.  In particular, the DTFT of the product of two discrete sequences is the periodic convolution of the DTFTs of the individual sequences.^[1]

Let x be a function with a well-defined periodic summation, x_T, where:

${\displaystyle x_{T}(t)\ {\stackrel {\mathrm {def} }{=}}\ \sum _{k=-\infty }^{\infty }x(t-kT)=\sum _{k=-\infty }^{\infty }x(t+kT).}$

If h is any other function for which the convolution x_T ∗ h exists, then the convolution x_T ∗ h is periodic and identical to:

A simple way to calculate these is by using this link-https://www.rapidtables.com/calc/math/convolution-calculator.html

In this example we are gonna understand basic circular convolution suppose we have two functions i.e xn and hn
To perform convolution we need to multiply those i.e xn*hn by shifting xn by (size of xn+size of hn -1) positions.

x(n)=[1,2,3,4]            h(n)=[-3,2,1]
Size of xn=4.           Size of hn=3
Matrix length=4+3-1=6

Circular Matrix of x(n) created by shifting each position of xn.

 [1, 2, 3, 4, 0, 0]
 [0, 1, 2, 3, 4, 0]
 [0, 0, 1, 2, 3, 4]
 [4, 0, 0, 1, 2, 3]
 [3, 4, 0, 0, 1, 2]
 [2, 3, 4, 0, 0, 1]

Matrix for hn=
[-3,
2
1,
0,
0,
0]
Now we multiply each of the xn.hn by matrix multiplication and we get yn.

y(n)=[-3 -4 -4 -4 11 4]

Code:-

Circular convolution code in python 3

from collections import deque
n1=int(input('Enter number of samples of x(n):'))      #input from user for number of elements of  x(n)
n2=int(input('Enter number of samples of h(n):'))      #input from user for number of elements of  h(n)
xn=[]
hn=[]
for i in range(n1):
x=int(input('Enter elements x(n):'))      #input from user for x(n) list
xn.append(x)                                     #append that input to x(n) list
for i in range(n2):
h=int(input('Enter elements h(n):'))      #input from user for h(n) liist
hn.append(h)                                     #append that input to h(n) list
pad=n1+n2-1
while len(xn)<pad:xn.append(0)      #adds 0 to make l#st equal for x(n)
while len(hn)<pad:hn.append(0)      #adds 0 to make list equal for h(n)
mul=[]
xn1 = deque(xn)                            #makes a circular queue of list
for i in range(len(xn)):
mul.append(list(xn1))
xn1.rotate(1)                        #shifts the elements by 1 for each iteration and appends it to list
print("Circular Matrix of x(n)\n",*mul,"\n*Matrix of h(n)\n",*hn,"\n\t=\n",sep='\n\t')
print("Matrix y(n):\n")
result=[]
for i in range(len(xn)):
result.append( list(mul[j][i]*hn[j] for j in range(len(hn)))) #multiplies Lists of mul and hn column wise
yn=[]
for i in range(len(xn)):
yn.append(sum(result[i]))                 #generates sum of list for y(n)
print(*yn,sep='\t\n')

Output:-

Enter number of samples of x(n):4
Enter number of samples of h(n):3
Enter elements x(n):1
Enter elements x(n):2
Enter elements x(n):3
Enter elements x(n):4
Enter elements h(n):1
Enter elements h(n):2
Enter elements h(n):3
Circular Matrix of x(n)

        [1, 2, 3, 4, 0, 0]
        [0, 1, 2, 3, 4, 0]
        [0, 0, 1, 2, 3, 4]
        [4, 0, 0, 1, 2, 3]
        [3, 4, 0, 0, 1, 2]
        [2, 3, 4, 0, 0, 1]

*Matrix of h(n)

        1
        2
        3
        0
        0
        0

        =

Matrix y(n):

1
4
10
16
17
12