TheAlgorithms-Python

1
# https://en.wikipedia.org/wiki/Circular_convolution
2

3
"""
4
Circular convolution, also known as cyclic convolution,
5
is a special case of periodic convolution, which is the convolution of two
6
periodic functions that have the same period. Periodic convolution arises,
7
for example, in the context of the discrete-time Fourier transform (DTFT).
8
In particular, the DTFT of the product of two discrete sequences is the periodic
9
convolution of the DTFTs of the individual sequences. And each DTFT is a periodic
10
summation of a continuous Fourier transform function.
11

12
Source: https://en.wikipedia.org/wiki/Circular_convolution
13
"""
14

15
import doctest
16
from collections import deque
17

18
import numpy as np
19

20

21
class CircularConvolution:
22
    """
23
    This class stores the first and second signal and performs the circular convolution
24
    """
25

26
    def __init__(self) -> None:
27
        """
28
        First signal and second signal are stored as 1-D array
29
        """
30

31
        self.first_signal = [2, 1, 2, -1]
32
        self.second_signal = [1, 2, 3, 4]
33

34
    def circular_convolution(self) -> list[float]:
35
        """
36
        This function performs the circular convolution of the first and second signal
37
        using matrix method
38

39
        Usage:
40
        >>> convolution = CircularConvolution()
41
        >>> convolution.circular_convolution()
42
        [10, 10, 6, 14]
43

44
        >>> convolution.first_signal = [0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6]
45
        >>> convolution.second_signal = [0.1, 0.3, 0.5, 0.7, 0.9, 1.1, 1.3, 1.5]
46
        >>> convolution.circular_convolution()
47
        [5.2, 6.0, 6.48, 6.64, 6.48, 6.0, 5.2, 4.08]
48

49
        >>> convolution.first_signal = [-1, 1, 2, -2]
50
        >>> convolution.second_signal = [0.5, 1, -1, 2, 0.75]
51
        >>> convolution.circular_convolution()
52
        [6.25, -3.0, 1.5, -2.0, -2.75]
53

54
        >>> convolution.first_signal = [1, -1, 2, 3, -1]
55
        >>> convolution.second_signal = [1, 2, 3]
56
        >>> convolution.circular_convolution()
57
        [8, -2, 3, 4, 11]
58

59
        """
60

61
        length_first_signal = len(self.first_signal)
62
        length_second_signal = len(self.second_signal)
63

64
        max_length = max(length_first_signal, length_second_signal)
65

66
        # create a zero matrix of max_length x max_length
67
        matrix = [[0] * max_length for i in range(max_length)]
68

69
        # fills the smaller signal with zeros to make both signals of same length
70
        if length_first_signal < length_second_signal:
71
            self.first_signal += [0] * (max_length - length_first_signal)
72
        elif length_first_signal > length_second_signal:
73
            self.second_signal += [0] * (max_length - length_second_signal)
74

75
        """
76
        Fills the matrix in the following way assuming 'x' is the signal of length 4
77
        [
78
            [x[0], x[3], x[2], x[1]],
79
            [x[1], x[0], x[3], x[2]],
80
            [x[2], x[1], x[0], x[3]],
81
            [x[3], x[2], x[1], x[0]]
82
        ]
83
        """
84
        for i in range(max_length):
85
            rotated_signal = deque(self.second_signal)
86
            rotated_signal.rotate(i)
87
            for j, item in enumerate(rotated_signal):
88
                matrix[i][j] += item
89

90
        # multiply the matrix with the first signal
91
        final_signal = np.matmul(np.transpose(matrix), np.transpose(self.first_signal))
92

93
        # rounding-off to two decimal places
94
        return [round(i, 2) for i in final_signal]
95

96

97
if __name__ == "__main__":
98
    doctest.testmod()
99