Repository navigation
Expand file tree
/
Copy pathcircular_convolution.py
More file actions
98 lines (75 loc) · 3.38 KB
/
Copy pathcircular_convolution.py
File metadata and controls
98 lines (75 loc) · 3.38 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
# https://en.wikipedia.org/wiki/Circular_convolution
"""
Circular convolution, also known as cyclic convolution,
is a special case of periodic convolution, which is the convolution of two
periodic functions that have the same period. Periodic convolution arises,
for example, in the context of the discrete-time Fourier transform (DTFT).
In particular, the DTFT of the product of two discrete sequences is the periodic
convolution of the DTFTs of the individual sequences. And each DTFT is a periodic
summation of a continuous Fourier transform function.
Source: https://en.wikipedia.org/wiki/Circular_convolution
"""
import doctest
from collections import deque
import numpy as np
class CircularConvolution:
"""
This class stores the first and second signal and performs the circular convolution
"""
def __init__(self) -> None:
"""
First signal and second signal are stored as 1-D array
"""
self.first_signal = [2, 1, 2, -1]
self.second_signal = [1, 2, 3, 4]
def circular_convolution(self) -> list[float]:
"""
This function performs the circular convolution of the first and second signal
using matrix method
Usage:
>>> convolution = CircularConvolution()
>>> convolution.circular_convolution()
[10.0, 10.0, 6.0, 14.0]
>>> convolution.first_signal = [0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6]
>>> convolution.second_signal = [0.1, 0.3, 0.5, 0.7, 0.9, 1.1, 1.3, 1.5]
>>> convolution.circular_convolution()
[5.2, 6.0, 6.48, 6.64, 6.48, 6.0, 5.2, 4.08]
>>> convolution.first_signal = [-1, 1, 2, -2]
>>> convolution.second_signal = [0.5, 1, -1, 2, 0.75]
>>> convolution.circular_convolution()
[6.25, -3.0, 1.5, -2.0, -2.75]
>>> convolution.first_signal = [1, -1, 2, 3, -1]
>>> convolution.second_signal = [1, 2, 3]
>>> convolution.circular_convolution()
[8.0, -2.0, 3.0, 4.0, 11.0]
"""
length_first_signal = len(self.first_signal)
length_second_signal = len(self.second_signal)
max_length = max(length_first_signal, length_second_signal)
# create a zero matrix of max_length x max_length
matrix = [[0] * max_length for i in range(max_length)]
# fills the smaller signal with zeros to make both signals of same length
if length_first_signal < length_second_signal:
self.first_signal += [0] * (max_length - length_first_signal)
elif length_first_signal > length_second_signal:
self.second_signal += [0] * (max_length - length_second_signal)
"""
Fills the matrix in the following way assuming 'x' is the signal of length 4
[
[x[0], x[3], x[2], x[1]],
[x[1], x[0], x[3], x[2]],
[x[2], x[1], x[0], x[3]],
[x[3], x[2], x[1], x[0]]
]
"""
for i in range(max_length):
rotated_signal = deque(self.second_signal)
rotated_signal.rotate(i)
for j, item in enumerate(rotated_signal):
matrix[i][j] += item
# multiply the matrix with the first signal
final_signal = np.matmul(np.transpose(matrix), np.transpose(self.first_signal))
# rounding-off to two decimal places
return [float(round(i, 2)) for i in final_signal]
if __name__ == "__main__":
doctest.testmod()