2
$\begingroup$

(Code snippet with example below).

In MATLAB, assume I have a long signal vector y (length N) that I wish to convolve with a square wave h (consisting of H 1's). This would give a convolution result of length N+H-1.

Since I have to perform this operation quite often, I thought that I could speed up my code by downsampling the signal y (and also the square wave h) and then perform the convolution. The downsampled signals are referred to as y_ds and h_ds.

However, the result is shifted when compared to the downsampled version of the convolution result (if corrected for scaling differences). So in general I found that:

conv(y_ds,h_ds) $\neq$ downsample(conv(y,h))

However, the shift is between the two results is not constant, i.e. shifting such that the maxima align, causes the edges to be different.

My questions

  • Where does this shift originate from?
  • How can this code be modified such that the downsampled convolution result equals the convolution result of the downsampled signals?

Kind regards

N = 100;
dsfactor = 3;
H = dsfactor*3;
x = linspace(0,10,N);
y = sind(18*x);
h = ones(H,1);

convyh = conv(y,h);

convyh_ds = downsample(convyh,dsfactor)./H;
convyh_ds3 = conv(downsample(y,dsfactor),downsample(h,dsfactor))./(ceil(H/dsfactor));

figure;
plot(convyh_ds,'DisplayName','downsample(conv)','LineWidth',1);
hold on;
plot(convyh_ds3,'DisplayName','conv(downsample)','LineWidth',1);
grid minor
legend('show');
line([0 length(convyh_ds2)],[0 0],'LineStyle','--');

enter image description here

$\endgroup$
  • $\begingroup$ Hi! First of all your h vector is purely $1$ s then convolution becomes a moving sum? What about the y vector? Will it always be partial sine waves? And also, do you have pre-determined fixed values for N, H and downsampling factors? $\endgroup$ – Fat32 Sep 18 '17 at 14:35
  • $\begingroup$ @Fat32 Thanks for your response. The code snippet above is just an example, but in my application h is indeed purely 1's. The y vector can be anything, but using a sine was a straightforward example. Values for N, H and downsampling factors are not fixed either (yet) $\endgroup$ – Knippie Sep 18 '17 at 14:39
  • $\begingroup$ You down sample the signal so that convolution will be faster ? But it won't be equal to the original convolution ? You probably don't need an exact convolutin result? What's your purpose of convolution ? $\endgroup$ – Fat32 Sep 18 '17 at 15:04
  • $\begingroup$ @Fat32 My question is why the convolution using the downsampled signals does not equal the original convolution (downsampled), Ideally, these results would be the same. So I do need the exact convolution result $\endgroup$ – Knippie Sep 18 '17 at 15:44
3
$\begingroup$

I thought this was because you were getting aliasing in your signal during one of the downsampling operations. However, I re-wrote your code in R (included below) and I did not see the same effect I suspect conv is doing something odd. You may want to look at using the shape parameter and see if that makes a difference.

Below are four plots of different variants of yours:

  • Top left: Yours.
  • Top right: a variation that uses slightly different x values.
  • Bottom left: Yours at twice the frequency.
  • Bottom right: a variation that uses slightly different x values at twice the frequency.

As you can see, in all four examples the red and the black overlay exactly.

Four plots of decimation / filtering in different orders.

Yes, in general, these will not be the same. Below is an example with a sawtooth wave, and the two do not line up.

Sawtooth example.

Here is the specific example you ask about with the triangle wave.

Triangle wave example.


R Code Only Below

#43794
#N = 100;
N <- 100
#dsfactor = 3;
dsfactor <- 3
#H = dsfactor*3;
H <- dsfactor * 3
#x = linspace(0,10,N);
x1 <- seq(0,10,10/(N-1))
x2 <- seq(0,10*(N-1)/N,10/N)
#y = sind(18*x);
y1 <- sin(18*x1/180*pi)
y2 <- sin(18*x2/180*pi)
y3 <- sin(36*x1/180*pi)
y4 <- sin(36*x2/180*pi)
#h = ones(H,1);
h <- rep(1,H)

#convyh = conv(y,h);
convy1h <- filter(y1,h)
convy2h <- filter(y2,h)
convy3h <- filter(y3,h)
convy4h <- filter(y4,h)

downsample <- function(signal, factor) 
{
  return(signal[seq(1,length(signal), factor)])
}

#convyh_ds = downsample(convyh,dsfactor)./H;
convy1h_ds <- downsample(convy1h, dsfactor)/H
convy2h_ds <- downsample(convy2h, dsfactor)/H
convy3h_ds <- downsample(convy3h, dsfactor)/H
convy4h_ds <- downsample(convy4h, dsfactor)/H
#convyh_ds3 = conv(downsample(y,dsfactor),downsample(h,dsfactor))./(ceil(H/dsfactor));
convy1h_ds3 <- filter(downsample(y1,dsfactor), downsample(h,dsfactor))/ceiling(H/dsfactor)
convy2h_ds3 <- filter(downsample(y2,dsfactor), downsample(h,dsfactor))/ceiling(H/dsfactor)
convy3h_ds3 <- filter(downsample(y3,dsfactor), downsample(h,dsfactor))/ceiling(H/dsfactor)
convy4h_ds3 <- filter(downsample(y4,dsfactor), downsample(h,dsfactor))/ceiling(H/dsfactor)
#figure;
#plot(convyh_ds,'DisplayName','downsample(conv)','LineWidth',1);
#hold on;
#plot(convyh_ds3,'DisplayName','conv(downsample)','LineWidth',1);
#grid minor
#legend('show');
#line([0 length(convyh_ds2)],[0 0],'LineStyle','--');

par(mfrow=c(2,2))
plot(convy1h_ds)
lines(convy1h_ds3, col='red')

plot(convy2h_ds)
lines(convy2h_ds3, col='red')

plot(convy3h_ds)
lines(convy3h_ds3, col='red')

plot(convy4h_ds)
lines(convy4h_ds3, col='red')
$\endgroup$
  • $\begingroup$ Thank you for your response. However, this confuses me even more because I think that in general the two results can't be the same. Consider the following example where y is a triangular wave (N=21), H=4 and dsfactor = 2: y = [1 2 3 4 5 6 7 8 9 10 11 10 9 8 7 6 5 4 3 2 1] h = [1 1 1 1] conv(y,h) = [1 3 6 10 14...14 10 6 3 1]] conv_ds = [1 6 14 22...34 26 18 10 3] y_ds = [1 3 5...5 3 1] h_ds =[1 1] conv(y_ds,h_ds) = [1 4 8 1 ...12 8 4 1] Both results start with 1, but there is still a non-constant scaling error and/or phase shift, right? Could you please run this example as well? $\endgroup$ – Knippie Sep 19 '17 at 11:44
  • $\begingroup$ @Knippie I ran an example using the sawtooth function from R. Let me try your data also. $\endgroup$ – Peter K. Sep 19 '17 at 11:49
  • $\begingroup$ @Knippie OK, added that example. $\endgroup$ – Peter K. Sep 19 '17 at 11:55
  • $\begingroup$ Thanks! So in this specific case the central part of the convolution is delayed by 0.27 sample (i.e. if we shift your right curve to the right by 0.27 sample, the black dots would perfectly align). What's the general conclusion we can draw from this? $\endgroup$ – Knippie Sep 19 '17 at 12:08
  • $\begingroup$ I would have thought the offset would be 0.25 samples. $\endgroup$ – Peter K. Sep 19 '17 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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