Received: by 10.205.119.5 with SMTP id fs5mr399243bkc.7.1332375809689;
        Wed, 21 Mar 2012 17:23:29 -0700 (PDT)
Path: h15ni34239bkw.0!nntp.google.com!news1.google.com!news.glorb.com!news-in-01.newsfeed.easynews.com!easynews!core-easynews-01!easynews.com!en-nntp-13.dc1.easynews.com.POSTED!not-for-mail
From: Fred Marshall <fmarshallxremove_th...@acm.org>
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:11.0) Gecko/20120312 Thunderbird/11.0
MIME-Version: 1.0
Newsgroups: comp.dsp
Subject: Re: Simple convolution and fft
References: <jkb7ma$2hl$1@dont-email.me>
In-Reply-To: <jkb7ma$2hl$1@dont-email.me>
Lines: 81
Message-ID: <Whuar.129694$Xo4.25158@en-nntp-13.dc1.easynews.com>
X-Complaints-To: abuse@easynews.com
Organization: Forte Inc.  http://www.forteinc.com/apn/
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Wed, 21 Mar 2012 17:23:12 -0700
X-Received-Bytes: 2607
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

On 3/20/2012 5:34 PM, Les Cargill wrote:
> Suppose I have
> A
> --------------------------------------
> 10.000
> 10.000
> B
> --------------------------------------
> 10.000
> 10.000
> and C
> --------------------------------------
> 100.000
> 200.000
> 100.000
>
> where C = CONVOLUTION(A,B)
>
> Taking the FFT of each:
>
> A'
> --------------------------------------
> { 20.000, 0.000 },
> { 0.000, 0.000 },
> B'
> --------------------------------------
> { 20.000, 0.000 },
> { 0.000, 0.000 },
> C'
> --------------------------------------
> { 400.000, 0.000 },
> { 0.000, -200.000 },
> { 0.000, 0.000 },
> { 0.000, 200.000 },
>
> Given A' and B', how do I produce C' from them directly?
>
> --
> Les Cargill
>
>

Les,

?????
The convolution of a and b that you compute is a linear, not circular, 
convolution.   A circular convolution would be [200 200].

If you want to use circular convolution then you need to extend a and b 
to N + M -1 or 2+2-1=3 each at a minimum.
This gives:
a = [10 10 0]
b = [10 10 0]
c= [100 200 100]

Now, you can use the FFT and multiply.
af=fft(a) = fft(b) = bf
20.00000000000000
5.00000000000000 + 8.66025403784439i
5.00000000000000 - 8.66025403784438i

af*bf = cf =

1.0e+002 *
   4.00000000000000
  -0.50000000000000 + 0.86602540378444i
  -0.50000000000000 - 0.86602540378444i
which is has real part even and imaginary part odd so its transform will 
be real.

ci=ifft(cf)=

1.0e+002 *
   1.00000000000000 + 0.00000000000000i
   2.00000000000000 + 0.00000000000000i
   1.00000000000000 - 0.00000000000000i

Where you got those -200 values I have no idea!!
Anyway, doing circular convolution takes just a bit of care.

Fred