DSPRelated.com
Forums
   Forums    More Forums    comp.dsp  

Simple convolution and fft

Started by Les Cargill ●March 20, 2012
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
Reply by Phil Martel ●March 20, 20122012-03-20

"Les Cargill"  wrote in message news:jkb7ma$2hl$1@dont-email.me...

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

When you take the FFT, the time function is assumed to be repeated so you’re 
A and B would give a
C
200
200
200

Which would give a C'
{400,0}
{0,0}
{0,0}

   Best wishes,
   --Phil Martel
Reply by Fred Marshall ●March 21, 20122012-03-21
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
Reply by dvsarwate ●March 21, 20122012-03-21
On Mar 20, 9:49&#4294967295;pm, "Phil Martel" <pomar...@comcast.net> wrote:


> When you take the FFT, the time function is assumed to be repeated


Hoo boy! Wait till r b-j sees this :-)
Reply by robert bristow-johnson ●March 21, 20122012-03-21
On 3/21/12 10:02 PM, dvsarwate wrote:

> On Mar 20, 9:49 pm, "Phil Martel"<pomar...@comcast.net>  wrote:
>
>> When you take the FFT, the time function is assumed to be repeated
>
> Hoo boy! Wait till r b-j sees this :-)
>


well, i guess you wouldn't *have* to assume it.  it's a free country (at 
least it was until January 2009 when we became a socialist dictatorship).

but if you don't assume it, you might get something unexpected when 
convolving or shifting.

if the words "convolution" and "FFT" appear together in any context, i 
think the safe assumption is that the data is periodically extended. 
but if you don't *do* anything with your FFT other than scale by a 
constant or add, then, i guess, it doesn't matter.  but then why bother 
with the FFT if all you're doing is to scale and add?

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."
Reply by Les Cargill ●March 22, 20122012-03-22
Fred Marshall wrote:

> 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,
>
> ?????


Agreed! I am confused on this.


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


Right. I want a simple, linear convolution.


> 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!!


That is what fftw calculated as the FFT of the vector { 100, 200, 100 }
And indeed - the -200  values confuse me no end.


> Anyway, doing circular convolution takes just a bit of care.
>
> Fred


--
Les Cargill
Reply by Fred Marshall ●March 22, 20122012-03-22
On 3/22/2012 10:30 AM, Les Cargill wrote:

> That is what fftw calculated as the FFT of the vector { 100, 200, 100 }
> And indeed - the -200  values confuse me no end.


Maybe we should consider that "it's what Les got when he used FFTW" ..  :-)

Fred
Reply by Les Cargill ●March 23, 20122012-03-23
Fred Marshall wrote:

> On 3/22/2012 10:30 AM, Les Cargill wrote:
>> That is what fftw calculated as the FFT of the vector { 100, 200, 100 }
>> And indeed - the -200 values confuse me no end.
>
> Maybe we should consider that "it's what Les got when he used FFTW" .. :-)
>
> Fred



True enough - but it's eminently repeatable, I'm doing all the 
appropriate initializations... the reverse FFT comes out
the same as the original...

--
Les Cargill
Reply by Les Cargill ●March 23, 20122012-03-23
Fred Marshall wrote:

> On 3/22/2012 10:30 AM, Les Cargill wrote:
>> That is what fftw calculated as the FFT of the vector { 100, 200, 100 }
>> And indeed - the -200 values confuse me no end.
>
> Maybe we should consider that "it's what Les got when he used FFTW" .. :-)
>
> Fred



Ach - found that one. It agrees with the results form Octave

--
Les Cargill
Reply by Fred Marshall ●March 23, 20122012-03-23
On 3/23/2012 10:50 AM, Les Cargill wrote:

> Fred Marshall wrote:
>> On 3/22/2012 10:30 AM, Les Cargill wrote:
>>> That is what fftw calculated as the FFT of the vector { 100, 200, 100 }
>>> And indeed - the -200 values confuse me no end.
>>
>> Maybe we should consider that "it's what Les got when he used FFTW" ..
>> :-)
>>
>> Fred
>
>
> Ach - found that one. It agrees with the results form Octave
>
> --
> Les Cargill


You mean that Octave is wrong too???

Fred