6

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

8
  • 4
    you should provide practical examples of what you expect (sample input(s)/output(s))
    – mozway
    Feb 8, 2022 at 14:32
  • 2
    I tried to specify do you need more concrete examples? Feb 8, 2022 at 14:39
  • 4
    Please, it's best if you provide an explicit example here in the question.
    – Ivan
    Feb 8, 2022 at 14:47
  • 3
    @OuttaSpaceTime I think the other commenters expect some explicit numerical values, e.g. by definition of x1=np.array([1,2,3,4]) , x2=..., expected_result=... . Having some code to start with makes it a bit easier to reproduce and begin working on your problem, just as well as confirming that the answer is actually correct.
    – André
    Feb 8, 2022 at 14:54
  • 2
    @André I think it might be a solution if we change how the array a is tiled. I think in the case N => L > P we have to zero pad a and in the other a will be tiled from a different index. Thanks for pointing this out! Feb 8, 2022 at 16:08

1 Answer 1

3

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)
6
  • 2
    cool thanks! would you mind adding some details what the exact parts of your function are doing? Feb 9, 2022 at 17:10
  • 1
    @OuttaSpaceTime I added some explanations.
    – bb1
    Feb 9, 2022 at 20:04
  • pretty neat thanks, +1000 Feb 9, 2022 at 20:29
  • The code gives errors when I try with h = np.array([1, 0, 2, 1]), x = np.array([1, -1, 0, 2, -2, -1]) and N = len(h) + len(x) - 1: IndexError: index 8 is out of bounds for axis 0 with size 6 Feb 17, 2022 at 13:04
  • The right zero padding is probably missing, when the signal have not the same length proper zero padding is required Feb 17, 2022 at 13:06

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.