Convolution via Fourier Transform

I'm trying to convolve two vectors by using the Fourier transform.  I 
take the Fourier transform of both vectors, multiple them, and then take 
the inverse Fourier transform.  My convolved signal should only contain 
real numbers, however, my result contains both real and imaginary 
numbers.  Do I need to add the real and imaginary parts together to get 
the convolution?

On Aug 15, 11:30 am, Chris Barrett
<"chrisbarret"@0123456789abcdefghijk113322.none> wrote:
> I'm trying to convolve two vectors by using the Fourier transform.  I
> take the Fourier transform of both vectors, multiple them, and then take
> the inverse Fourier transform.  My convolved signal should only contain
> real numbers, however, my result contains both real and imaginary
> numbers.  Do I need to add the real and imaginary parts together to get
> the convolution?

You're probably violating some symmetry condition somewhere.
Did you zero-pad your signals to the proper, same length?
How did you "compute" the Fourier transform exactly?

Suppose you want to compute y[n] = x[n] * h[n].

If you do this properly, you would get X[k] the DFT of x[n] to be
conjugate-symmetric, H[k] the DFT of h[n] to also be conjugate-
symmetric.

Hence Y[k] = X[k] . H[k] is also conjugate symmetric, and thus
y[n] the inverse DFT of Y[k] is purely real.

Now, where did your scheme break down?

Julius

On Aug 15, 9:30 am, Chris Barrett
<"chrisbarret"@0123456789abcdefghijk113322.none> wrote:
> I'm trying to convolve two vectors by using the Fourier transform.  I
> take the Fourier transform of both vectors, multiple them, and then take
> the inverse Fourier transform.  My convolved signal should only contain
> real numbers, however, my result contains both real and imaginary
> numbers.

Are the imaginary components of the result very tiny
relative to the real components?  If so, they could just
be rounding noise resulting from the accuracy limits
of floating point arithmetic.  What happens if you do
an FFT and IFFT without any modifying multiplications?


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

"Chris Barrett" <"chrisbarret"@0123456789abcdefghijk113322.none> wrote in 
message news:GUFwi.102728$g86.8527@newsfe14.lga...
> I'm trying to convolve two vectors by using the Fourier transform.  I take 
> the Fourier transform of both vectors, multiple them, and then take the 
> inverse Fourier transform.  My convolved signal should only contain real 
> numbers, however, my result contains both real and imaginary numbers.  Do 
> I need to add the real and imaginary parts together to get the 
> convolution?
>

The rule for convolution by this method is that the transforms be of equal 
length and at least M+N-1 samples each; where M is the original length of 
one sequence and N is the original length of the other.  Zero pad each to 
the same length that's at least M+N-1 and see if that doesn't make things 
improve.

Fred 

On Aug 16, 10:13 am, "Fred Marshall" <fmarshallx@remove_the_x.acm.org>
wrote:
> "Chris Barrett" <"chrisbarret"@0123456789abcdefghijk113322.none> wrote in
> messagenews:GUFwi.102728$g86.8527@newsfe14.lga...
>
> > I'm trying to convolve two vectors by using the Fourier transform.  I take
> > the Fourier transform of both vectors, multiple them, and then take the
> > inverse Fourier transform.  My convolved signal should only contain real
> > numbers, however, my result contains both real and imaginary numbers.  Do
> > I need to add the real and imaginary parts together to get the
> > convolution?
>
> The rule for convolution by this method is that the transforms be of equal
> length and at least M+N-1 samples each; where M is the original length of
> one sequence and N is the original length of the other.  Zero pad each to
> the same length that's at least M+N-1 and see if that doesn't make things
> improve.
>
> Fred

Don't you need to overlap and add otherwise the result is circular.

"HardySpicer" <gyansorova@gmail.com> wrote in message 
news:1187216367.266241.84480@e9g2000prf.googlegroups.com...
> On Aug 16, 10:13 am, "Fred Marshall" <fmarshallx@remove_the_x.acm.org>
> wrote:
>> "Chris Barrett" <"chrisbarret"@0123456789abcdefghijk113322.none> wrote in
>> messagenews:GUFwi.102728$g86.8527@newsfe14.lga...
>>
>> > I'm trying to convolve two vectors by using the Fourier transform.  I 
>> > take
>> > the Fourier transform of both vectors, multiple them, and then take the
>> > inverse Fourier transform.  My convolved signal should only contain 
>> > real
>> > numbers, however, my result contains both real and imaginary numbers. 
>> > Do
>> > I need to add the real and imaginary parts together to get the
>> > convolution?
>>
>> The rule for convolution by this method is that the transforms be of 
>> equal
>> length and at least M+N-1 samples each; where M is the original length of
>> one sequence and N is the original length of the other.  Zero pad each to
>> the same length that's at least M+N-1 and see if that doesn't make things
>> improve.
>>
>> Fred
>
> Don't you need to overlap and add otherwise the result is circular.
>

The result is circular no matter what.  What's important is that there's no 
overlap in time after doing the convolution.  A circular convolution in time 
would be the same.  The sequences would have to be padded to avoid overlap.

I don't understand "overlap and add" in this context.... It's just one 
convolution, not a series of them.  Not a streaming situation as I 
understand it.

Fred 

On Aug 16, 1:19 am, "Fred Marshall" <fmarshallx@remove_the_x.acm.org>
wrote:
> "HardySpicer" <gyansor...@gmail.com> wrote in message
>
> news:1187216367.266241.84480@e9g2000prf.googlegroups.com...
>
>
>
> > On Aug 16, 10:13 am, "Fred Marshall" <fmarshallx@remove_the_x.acm.org>
> > wrote:
> >> "Chris Barrett" <"chrisbarret"@0123456789abcdefghijk113322.none> wrote in
> >> messagenews:GUFwi.102728$g86.8527@newsfe14.lga...
>
> >> > I'm trying to convolve two vectors by using the Fourier transform.  I
> >> > take
> >> > the Fourier transform of both vectors, multiple them, and then take the
> >> > inverse Fourier transform.  My convolved signal should only contain
> >> > real
> >> > numbers, however, my result contains both real and imaginary numbers.
> >> > Do
> >> > I need to add the real and imaginary parts together to get the
> >> > convolution?
>
> >> The rule for convolution by this method is that the transforms be of
> >> equal
> >> length and at least M+N-1 samples each; where M is the original length of
> >> one sequence and N is the original length of the other.  Zero pad each to
> >> the same length that's at least M+N-1 and see if that doesn't make things
> >> improve.
>
> >> Fred
>
> > Don't you need to overlap and add otherwise the result is circular.
>
> The result is circular no matter what.  What's important is that there's no
> overlap in time after doing the convolution.  A circular convolution in time
> would be the same.  The sequences would have to be padded to avoid overlap.
>
> I don't understand "overlap and add" in this context.... It's just one
> convolution, not a series of them.  Not a streaming situation as I
> understand it.
>
> Fred

As long as the 2 input signals were real then the output of the IFFT
should be real as well - The size of the FFTs or overlapping won't
affect the fact he's getting imaginary numbers back.

Usually there is some noise in the FFT so the  imaginary component is
quite small wrt the real component, in this case I just ignore the
imaginary portion of the result. An alternative is to use a FFT
algorithm specifically designed for real data. The algorithm assumes
the complex conjugate symmetry and returns only the real portion when
doing an IFFT.

Cheers,
Dave