How to do N-Point circular convolution for 1D signal with numpy?

user_14653849 0
Viewed 221

I want a circular convolution function where I can set the number N as I like.

All examples I looked at like here and here assume that full padding is required but that not what I want.

I want to have the result for different values of N

  • so input would N and and two different arrays of values
  • the output should be the N point convolved signal

Here is the formula for circular convolution. Sub N can be seen as the modulo operation.

enter image description here

taken from this basic introduction


update for possible solution

This answer is a suitable solution when the array a is piled accordingly to the different cases of N.

When I find time I will post a complete answer, meanwhile feel free to do so.

Thanks to @André pointing this out in the comments!



examples for input/output from here

N = 4

enter image description here

N = 7 with zero padding

enter image description here

numpy python
1 Answers

I think that this should work:

def conv(x1, x2, N):
    n, m = np.ogrid[:N, :N]
    return (x1[:N] * x2[(n - m) % N]).sum(axis=1)

This is a direct translation of the formula posted in the question:

enter image description here

To implement this formula, first we compute an array of indices used by x₂. This is done using the code

n, m = np.ogrid[:N, :N]
indices = (n - m) % N

For example, for N=5, the array indices is:

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

The entry in the i-th row and j-th column is (i-j) % N. Then, x2[indices] creates an array consisting of elements of x2 corresponding to these indices. It remains to multiply each row of this array by the first N elements of x1 and take the sum of each row:

(x1[:N] * x2[indices]).sum(axis=1)
user_151877280
Related