FFT convolution giving different results from convolution

> ok, now i think I did that complex multiplication right, but the result
> still doesn't match to what I expect. To do my test I use a sound which
> has it's last half set to zero, thus it can help me find out lots of
> bugs, and when performing that convolution with a delta function as a
> kernel, that second half isn't back to zero as it should but with some
> of the input signal backwards, so i guess there's something wrong with
> my code

No, that's exactly how it should be - the backwards signal is the
time-domain aliasing you see due to circular convolution. If your
filter length is N, and the signal length is M (and therefore the FFT
length is M+L-1, just as you mentioned), then the output of the inverse
FFT has just M valid values that you use to construct the output signal
(M input samples -> M output samples). The position of the valid
samples in the output vector depends on how you zero padded the input
vector (at the end or at the beginning or both) and the filter impulse
response.

Regards,
Andor

Andor wrote:
> No, that's exactly how it should be - the backwards signal is the
> time-domain aliasing you see due to circular convolution. If your
> filter length is N, and the signal length is M (and therefore the FFT
> length is M+L-1, just as you mentioned), then the output of the inverse
> FFT has just M valid values that you use to construct the output signal
> (M input samples -> M output samples). The position of the valid
> samples in the output vector depends on how you zero padded the input
> vector (at the end or at the beginning or both) and the filter impulse
> response.
>
> Regards,
> Andor

So what do I have to do to avoid this aliasing thing. and then, how can
there be only M valid values because I mean the other N-1 values are
supposed to overlap with the next part of the output signal right? (i'm
talkin about using that convolution when an overlap-add has been done
before).

and I zero padded the input vector and the FIR after (the zeros are at
the end)

Michel Rouzic wrote:
> Andor wrote:
> > No, that's exactly how it should be - the backwards signal is the
> > time-domain aliasing you see due to circular convolution. If your
> > filter length is N, and the signal length is M (and therefore the FFT
> > length is M+L-1, just as you mentioned), then the output of the inverse
> > FFT has just M valid values that you use to construct the output signal
> > (M input samples -> M output samples). The position of the valid
> > samples in the output vector depends on how you zero padded the input
> > vector (at the end or at the beginning or both) and the filter impulse
> > response.
> >
> > Regards,
> > Andor
>
> So what do I have to do to avoid this aliasing thing. and then, how can
> there be only M valid values because I mean the other N-1 values are
> supposed to overlap with the next part of the output signal right? (i'm
> talkin about using that convolution when an overlap-add has been done
> before).

You are right, I mixed up overlap-add and overlap-save. To get
overlap-save working, take M+L-1 input values and apply a (M+L-1)-point
FFT, then only use the M output values that are not time-aliased (M is
the frame hop length, L is the length of FIR impulse response). This is
a lot simpler than overlap-add, because you can construct the output
signal by simply splicing together the M samples of each frame (no
overlapped add).

Regards,
Andor

OK, now I admitt to be a bit lost. how do I get a result of size M+L-1
(since thats what we obtain with a normal convolution) without any
aliasing?

Andor wrote:
> You are right, I mixed up overlap-add and overlap-save. To get
> overlap-save working, take M+L-1 input values and apply a (M+L-1)-point
> FFT, then only use the M output values that are not time-aliased (M is
> the frame hop length, L is the length of FIR impulse response). This is
> a lot simpler than overlap-add, because you can construct the output
> signal by simply splicing together the M samples of each frame (no
> overlapped add).
> 
> Regards,
> Andor

I think my previous post didn't make it through (I changed my Google
account in between), so here goes again:

> OK, now I admitt to be a bit lost. how do I get a result of size M+L-1
> (since thats what we obtain with a normal convolution) without any
> aliasing?

The point is that you take a chunk of the input signal (of size M+L-1),
do the FFT/multiply with the FIR and take the inverse FFT. Only M (this
is the number of samples that you shift the FFT frame) samples of the
inverse FFT are not destroyed by time-domain aliasing. If you
zero-padded the FIR impulse response by appending the zeros to the end
of the impulse response, then the last M samples of the inverse FFT
have to be used to construct the output signal.

Then you advance the frame by M samples, take the (M+L-1)-point FFT
again and repeat the above procedure. This way, for every frame you
generate M output samples.

Regards,
Andor

Michel Rouzic wrote:
> oh, i hadn't understood that it was a complex multiplication, so all I
> did was to multiply each value from let's say H with the matching value
> in X. Makes sence, even tho my problem is that I never dealt with
> complex multiplications before
>
> > Almost. It may be a case of impresice language, but I interpret
> > the sentence "multiply the real and imaginary parts of the
> > two signals" as
> >
> >   z1 = re1 + j*im1
> >   z2 = re2 + j*im2
> >
> >   z1*z2 = re1*re2 + j*im1*im2.
>
> um... i'm not sure to know what j is, but yeah i guess thats what I did

OK, you are a beginner in DSP and you don't know complex numbers.
Not knowing complex numbers is quite an unfortunate proistion, it
would normally requirte you to take a college maths course.

There is a book out, intended for the very beginners in DSP, that
teaches the basics of DSP *and* gives a quick intro to complex
numbers:

Lyons: "Understanding Digital Signal Processing"
        2nd ed., Prentice Hall 2004.

I think you will find that book most useful. 

Rune

Unfortunatly I don't think I got it all, but it seems to me that with
what you're trying to explain me, you're still getting a M size output
signal, as what i'm looking forward doing is obtaining a M+L-1 points
output signal, exactly in the same way as the convolution described in
chapter 6 of dspguide.com, except that it would be using FFT. so,
what's the simplest way for me to get to that considered what i've
already done?

Andor wrote:
> I think my previous post didn't make it through (I changed my Google
> account in between), so here goes again:
>
> > OK, now I admitt to be a bit lost. how do I get a result of size M+L-1
> > (since thats what we obtain with a normal convolution) without any
> > aliasing?
>
> The point is that you take a chunk of the input signal (of size M+L-1),
> do the FFT/multiply with the FIR and take the inverse FFT. Only M (this
> is the number of samples that you shift the FFT frame) samples of the
> inverse FFT are not destroyed by time-domain aliasing. If you
> zero-padded the FIR impulse response by appending the zeros to the end
> of the impulse response, then the last M samples of the inverse FFT
> have to be used to construct the output signal.
>
> Then you advance the frame by M samples, take the (M+L-1)-point FFT
> again and repeat the above procedure. This way, for every frame you
> generate M output samples.
> 
> Regards,
> Andor

If you want to insist on overlap-add, then you have to use the whole
(M+L-1)-point output of the IFFT. Use M points to reconstruct the
signal, and let the remaining L-1 points overlap into the next
frame(s), where you have to add them to the M points that you get from
the IFFT. It's kind of tedious, because depending on the length of L,
you have to keep track of several IFFT frames and add all the correct
values to get the proper convolution. Overlap-save is really much
simpler (and also more efficient, as you don't have to do any adding
after the IFFT).

Regards,
Andor

FWIW, I found that the on-line book "The Scientist and Engineer's
Guide to Digital Signal Processing" had a good explanation of overlap-add:
http://www.spectrumsdi.com/ch18.pdf

-- 
Jon Harris
SPAM blocker in place:
Remove 99 (but leave 7) to reply

"Andor" <andor.bariska@gmail.com> wrote in message 
news:1122378757.697071.53360@g43g2000cwa.googlegroups.com...
> If you want to insist on overlap-add, then you have to use the whole
> (M+L-1)-point output of the IFFT. Use M points to reconstruct the
> signal, and let the remaining L-1 points overlap into the next
> frame(s), where you have to add them to the M points that you get from
> the IFFT. It's kind of tedious, because depending on the length of L,
> you have to keep track of several IFFT frames and add all the correct
> values to get the proper convolution. Overlap-save is really much
> simpler (and also more efficient, as you don't have to do any adding
> after the IFFT).
>
> Regards,
> Andor
> 

already had that one thx :) but with it i didnt even manage to figure
out that a complex multiplication was needed, and I still can't
understand why I get aliasing with what I do, but I hardly could follow
when they started with their BASIC code thing. they really should have
used something like C rather than BASIC..

Jon Harris wrote:
> FWIW, I found that the on-line book "The Scientist and Engineer's
> Guide to Digital Signal Processing" had a good explanation of overlap-add:
> http://www.spectrumsdi.com/ch18.pdf
>
> --
> Jon Harris
> SPAM blocker in place:
> Remove 99 (but leave 7) to reply
>
> "Andor" <andor.bariska@gmail.com> wrote in message
> news:1122378757.697071.53360@g43g2000cwa.googlegroups.com...
> > If you want to insist on overlap-add, then you have to use the whole
> > (M+L-1)-point output of the IFFT. Use M points to reconstruct the
> > signal, and let the remaining L-1 points overlap into the next
> > frame(s), where you have to add them to the M points that you get from
> > the IFFT. It's kind of tedious, because depending on the length of L,
> > you have to keep track of several IFFT frames and add all the correct
> > values to get the proper convolution. Overlap-save is really much
> > simpler (and also more efficient, as you don't have to do any adding
> > after the IFFT).
> >
> > Regards,
> > Andor
> >