2
$\begingroup$

Having read up on discrete convolution and how it is implemented, I've started to think about which "mode" is applicable to which situation. For two signals x1 and x2 of length M and N, respectively, NumPy and SciPy convolution functions (example doc) support modes:

  • "full": output of length M + N - 1
  • "same": output of length max(M, N)
  • "valid": output of length max(M, N) - min(M, N) + 1

Only the "valid" mode is free of boundary effects because the output samples are all calculated from fully-immersed input samples. But when you look at the "same" mode and its output length, you start to realise that it's a strange half-way point between the other two modes. It must be fully-immersed on one side of the output but not at the other. What they are doing can easily be demonstrated:

import numpy as np
import scipy.signal as sig

x1 = np.array([1, 1, 1, 1, 1], dtype=np.float64)
x2 = np.array([1, 10], dtype=np.float64)

print(np.convolve(x1, x2, mode="same"))
# [ 1. 11. 11. 11. 11.]

print(sig.convolve(x1, x2, mode="same", method="direct"))
# [ 1. 11. 11. 11. 11.]

print(sig.convolve(x1, x2, mode="same", method="fft"))
# [ 1. 11. 11. 11. 11.]

It is clear that the convolution begins on the left in the same manner as the "full" mode (without full immersion), but stops abruptly at the right-hand-side (with full immersion).

It's not clear to me whether this is just a convention, or if full immersion on the right is advantageous over the opposite. Perhaps it was just easier to implement it as the "full" mode with an abrupt end?

Please could someone shed light on why this is so, and what the mode would be useful for?

$\endgroup$

1 Answer 1

2
$\begingroup$

I think that the only reason why the same mode exists is because sometimes it is convenient if the output has the same length as the input (assuming that the input is longer than the impulse response). The exact implementation of that mode is usually not very important, and there are of course several possibilities:

  1. use zero padding at the end.

  2. use zero padding at the beginning.

  3. use the central part of the full convolution, resulting in zero padding at both ends. There are two possibilities if an odd number of samples needs to be removed from the result of the full convolution (see below).

I believe that most DSP simulation platforms (such as Matlab, Octave, Scipy etc.) use method $3$.

Example:

For this example I used Octave (Matlab uses the same convention). If $M$ and $N$ are the lengths of the two sequences, and if $M\ge N$, the full convolution has length $M+N-1$, and for the same mode we need to remove $N-1$ samples in order for the result to be of length $M$. If $N-1$ is even, the same number of samples are removed from both ends of the full convolution result. If $N-1$ is odd, we need to remove one more sample at one of the two ends. Octave/Matlab chooses to remove one more sample at the beginning. From your example it appears that Scipy removes one more sample at the end. However, I believe that both implementations use the middle part of the full convolution with samples removed at both ends (i.e., method $3$ above). Of course, if $N=2$ (as in your example), there is only one sample that needs to be removed.

N odd $\Rightarrow$ the same number of samples are removed at both ends:

u = [1,2,3,2,1]; v = [1,0,-1];

conv(u,v) = 1 2 2 0 -2 -2 -1

conv(u,v,'same') = 2 2 0 -2 -2

N even $\Rightarrow$ one more sample is removed at the beginning (Scipy seems to do the opposite):

u=[1,2,3,2,1]; v=[1,0,-1,2];

conv(u,v) = 1 2 2 2 2 4 3 2

conv(u,v,'same') = 2 2 2 4 3

I would expect that the Scipy result is

2 2 2 2 4

$\endgroup$
3
  • $\begingroup$ I'm not sure what you mean. Based on the example I show, surely the answer is method 2? $\endgroup$
    – Doddy
    Nov 15, 2023 at 22:33
  • $\begingroup$ Perhaps I'm confusing zero padding with partial immersion. A better question would be: what exactly do you mean by "using the central part of the full convolution"? $\endgroup$
    – Doddy
    Nov 15, 2023 at 22:44
  • 1
    $\begingroup$ @Doddy: From you example you can't tell, because x2 is so short. The central part of the full convolution is obtained by just throwing away one sample (in this case the last). If you used a length $3$ sequence x2 instead, you'd probably see that the output of the same mode is indeed the central part of the full convolution. $\endgroup$
    – Matt L.
    Nov 16, 2023 at 7:12

Your Answer

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

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