Inverse FFT, Please Help!

Hi, I'm in desperate need to understand how to inverse FFT my data. I
believe I've successfully performed a forward transform, now I need to
inverse it back to the time domain to make sure I can play the original
audio.

Yes, I'm a DSP newbie and from what I've read, I think I can run the
forward transformed data back through the FFT function to get it back
to the time domain. I've also been told that I have to do some 1/N
scaling, but I'm not sure what this means or how exactly I apply it to
my FFT'd data.

Is the conjugate the sum of the real data and the imaginary data?

When this data is run through the FFT the second time (for the
inverse), what exactly is done differently to the data, or what is the
formula for the inverse transform? 

Thank you!

dkuhta wrote:
> Hi, I'm in desperate need to understand how to inverse FFT my data. I
> believe I've successfully performed a forward transform, now I need to
> inverse it back to the time domain to make sure I can play the original
> audio.
> 
> Yes, I'm a DSP newbie and from what I've read, I think I can run the
> forward transformed data back through the FFT function to get it back
> to the time domain. I've also been told that I have to do some 1/N
> scaling, but I'm not sure what this means or how exactly I apply it to
> my FFT'd data.

1/N scaling needs to happen someplace.  There is no one standard 
definition of the FFT, and depending on how the transform is defined it 
needs to get done in different places -- your best bet is to try it and see.
> 
> Is the conjugate the sum of the real data and the imaginary data?

NO!  The complex conjugate of a number a + jb is a - jb -- nothing more 
or less.  So it has the same magnitude, and the opposite angle if you 
plot it on the complex plane.
> 
> When this data is run through the FFT the second time (for the
> inverse), what exactly is done differently to the data, or what is the
> formula for the inverse transform? 

If you have a pair of functions for FFT and IFFT the only difference is 
that the frequency term is inverted, or that the data's complex 
conjugate is taken before IFFT.  For that matter if you have a pair of 
functions and not just one then your scaling should be taken care of as 
well.
> 
> Thank you!
> 
You're welcome.  I hope this helps.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Thank you for the response Tim.

>NO!  The complex conjugate of a number a + jb is a - jb -- n=ADothing
>more or less.  So it has the same magnitude, and the opposite ang=ADle
>if you plot it on the complex plane.

At the end of my FFT method, the following is being done in a for loop:

mag[i]=3D (double)(Math.sqrt(xReal[i]*xReal[i] + xImag[i]*xImag[i]))/n;

Other than the square of the sum of the real and imaginary multiplied
by each other, what is going on here? Is the opppisite of this equation
the conjugate? Thanks.

> I've successfully performed a forward transform...

Hello.  Usually, the inverse Fourier is very similar to the Forward 
transform.  Sometimes, the same code is used both forward, and backward, 
with only a bit flag taking care of which direction you are going.
If you have a successful forward transform, here is one idea...   Here, we 
do not use an Inverse Fourier...just the forward Transform...
I'll use Mathematica for this example...

-- a small data sample...

data = Range[5]
{1, 2, 3, 4, 5}

v = Fourier[data]

{6.7082039324993685,
  -1.118033988749895 - 1.5388417685876266*I,
  -1.118033988749895 - 0.36327126400268045*I,
  -1.118033988749895 + 0.36327126400268045*I,
  -1.118033988749895 + 1.5388417685876266*I}

If we just take the Fourier again, we appear to get the data reversed, and 
shifted by one location.

Fourier[v]

{1, 5, 4, 3, 2}

However, let's take the Conjugate of our Fourier data.  This does nothing 
more that make a+b I into a-b I.

t = Conjugate[v]

{6.7082039324993685,
  -1.118033988749895 + 1.5388417685876266*I,
  -1.118033988749895 + 0.36327126400268045*I,
  -1.118033988749895 - 0.36327126400268045*I,
  -1.118033988749895 - 1.5388417685876266*I}

Now, if we take the Fourier, we get the original data.   Code that takes the 
inverse, will usually take care of switching the sign during the first pass.

Fourier[t]

{1, 2, 3, 4, 5}

HTH
-- 
Dana

"dkuhta" <deankuhta@yahoo.com> wrote in message 
news:1107144032.832263.158630@f14g2000cwb.googlegroups.com...
> Hi, I'm in desperate need to understand how to inverse FFT my data. I
> believe I've successfully performed a forward transform, now I need to
> inverse it back to the time domain to make sure I can play the original
> audio.
>
> Yes, I'm a DSP newbie and from what I've read, I think I can run the
> forward transformed data back through the FFT function to get it back
> to the time domain. I've also been told that I have to do some 1/N
> scaling, but I'm not sure what this means or how exactly I apply it to
> my FFT'd data.
>
> Is the conjugate the sum of the real data and the imaginary data?
>
> When this data is run through the FFT the second time (for the
> inverse), what exactly is done differently to the data, or what is the
> formula for the inverse transform?
>
> Thank you!
> 

dkuhta wrote:

> Thank you for the response Tim.
> 
> 
>>NO!  The complex conjugate of a number a + jb is a - jb -- n�othing
>>more or less.  So it has the same magnitude, and the opposite ang�le
>>if you plot it on the complex plane.
> 
> 
> At the end of my FFT method, the following is being done in a for loop:
> 
> mag[i]= (double)(Math.sqrt(xReal[i]*xReal[i] + xImag[i]*xImag[i]))/n;
> 
> Other than the square of the sum of the real and imaginary multiplied
> by each other, what is going on here? Is the opppisite of this equation
> the conjugate? Thanks.

You identified the problem! That converts the FFT output -- real and
imaginary -- to magnitude squared, discarding the phase information.
You can't go back from there.

FFT is a linear operation. Squaring is not.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

thank you very much for the detailed response dana!

When I have an array of 16 samples forward transformed, I'm only
getting an output of 8 coefficiants. Is this correct output?

example:

input samples: 0,1,2,3,4,5,6,7,8,9,10,11,12,14,15,16

output coefficiants:

7.6875
2.6659093124995255
1.4471180912210393
1.0084213502085952
0.7525996611745185
0.6043769659282251
0.5516219086120273
0.5546326721598476

thank you Jerry,

so, if I take out this squaring function, I should be able to inverse
transform, otherwise I can not?

dkuhta wrote:

> thank you very much for the detailed response dana!
> 
> When I have an array of 16 samples forward transformed, I'm only
> getting an output of 8 coefficiants. Is this correct output?
> 
> example:
> 
> input samples: 0,1,2,3,4,5,6,7,8,9,10,11,12,14,15,16
> 
> output coefficiants:
> 
> 7.6875
> 2.6659093124995255
> 1.4471180912210393
> 1.0084213502085952
> 0.7525996611745185
> 0.6043769659282251
> 0.5516219086120273
> 0.5546326721598476

It should be clear now that the original 16 terms, which included Re()
and Im(), have been reduced to 8 by the magnitude-squared operation.

Often what is wanted as the final result of frequency analysis is a
power spectrum or a magnitude plot in dB. For for the first, the square
is appropriate; for the second, magnitude squared rather than actual
magnitude merely introduces a scale factor of 2. The code you adopted
was probably written for such a purpose.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

"dkuhta" <deankuhta@yahoo.com> wrote in message
news:1107187556.175723.303070@z14g2000cwz.googlegroups.com...
> thank you Jerry,
>
> so, if I take out this squaring function, I should be able to inverse
> transform, otherwise I can not?

Based on your questions, I'm not sure you understand the theory behind what
you are doing (FFT, IFFT).
It looks like you have a bunch of code that you are trying to get working.
I think it might serve you well to pick up a basic DSP book and understand
what is going on before messing with code.

The output of the FFT is a complex array (vector) in the frequency domain.
Most people view this frequency domain data as magnitude vs frequency. So
the magnitude of the complex data is computed and viewed (what is the
magnitude of a complex pair (a + ib)?). When you perform an IFFT, the input
should be complex data (appropriately scaled) - it cannot be magnitude data
which has no phase information.

Cheers
Bhaskar

"dkuhta" <deankuhta@yahoo.com> wrote in message 
news:1107187302.289783.108090@c13g2000cwb.googlegroups.com...
> thank you very much for the detailed response dana!
>
> When I have an array of 16 samples forward transformed, I'm only
> getting an output of 8 coefficiants. Is this correct output?
>
> example:
>
> input samples: 0,1,2,3,4,5,6,7,8,9,10,11,12,14,15,16
>
> output coefficiants:
>
> 7.6875
> 2.6659093124995255
> 1.4471180912210393
> 1.0084213502085952
> 0.7525996611745185
> 0.6043769659282251
> 0.5516219086120273
> 0.5546326721598476
>
It looks like your fft assumes only real valued inputs so gives you only 
half the outputs you are expecting , with real inputs the other half are 
just complex conjugates of the half that you get - I think ).  Worse though 
is that it just gives you the magnitude - you showed

mag[i]= (double)(Math.sqrt(xReal[i]*xReal[i] + xImag[i]*xImag[i]))/n;

and you really want to ditch this if you intend to invert again.  You end up 
with something like :
7.6875                                      average value
-0.3741456 - 2.6395241i
-0.5 - 1.3579951i
-0.5780189 - .8263218i
-0.5625 -  .5i
-0.5103694 -  .3237199i
-0.5 -  .2329951i
-0.5374660 -  .1369222i
-0.5625                                     Nyquist freq
-0.5374660 +  .1369222i
-0.5 +  .2329951i
-0.5103694 +  .3237199i
-0.5625 +  .5i
-0.5780189 +  .8263218i
-0.5 + 1.3579951i
-0.3741456 + 2.6395241i

as you can see the second half after the nyquist frequency is just a repeat 
of the first half in inverse order and with all of the imaginary parts 
negated (i.e. the values are the complex conjugates of the first half in a 
different order).

If you get the output above and have an inverse FFT routine which handles 
complex input then you should be able to get back  something close to what 
you put in.

Best of luck - Mike