Convert FFT to IFFT: Steps to Get Right Values Back

[btb4198]

also what did you mean when you said that I have to zero of the negative side?
remember I wan talking about make a filter ...

I am going to zero out the bins I do not need
and then put is back into the ifft
so fft -> zero bin I do not want /filter -> ifft

 

[btb4198]

It means that those are the frequency bins for an FFT of length N, where N is even.

Not what you posted earlier:

What?

that is not what I read online...
so how do you get the frequency from the bins?

wait is that why my F is alway off by a little be...
like I use a 180 hz signal
but I get
177 hz from the fft

 

[btb4198]

"[0, 1, …, N/2-1, -N/2, …, -1]/N * Fs."
what is this ?
i am doing :
(bin index / N) * Fs *2; what is 0, 1, ... N/2-1. -N/2,...-1 ?
is that the index of the array that has the output of the FFT?
you cannot have a (- 1) index
sorry I am so lost

 

[olivermsun]

"[0, 1, …, N/2-1, -N/2, …, -1]/N * Fs."
what is this ?

That is an array of the frequencies corresponding to the FFT output bins in order.

The frequencies are equivalent to [0:N-1]/N * Fs, but the form I showed above might be easier to understand when your goal is to filter by frequency.

i am doing :
(bin index / N) * Fs *2;

You're writing in C, so your bin index probably goes from 0 to N-1. That means the frequencies you get are [0, 1, 2, …, N-1]/N * Fs. I don't know why you have a *2 in there, but that might be related to the doubled frequencies you're reporting.

what is 0, 1, ... N/2-1. -N/2,...-1 ?
is that the index of the array that has the output of the FFT?
you cannot have a (- 1) index.

They are a sequence of actual numbers.

sorry I am so lost

You might want to spend time looking through some resources like http://en.wikipedia.org/wiki/Discrete_Fourier_transform. This stuff is hard to apply effectively if you aren't familiar at all with the basics. Again, if you read the article and have specific questions, I'm sure many people on these forums will be glad to help.

 

[btb4198]

ok if I remove the * 2
then the fft is off by a half but I guess the IFFT would work because it is off but * 2
why is that ?
why is does my fft need the * 2 to get the right value
but my ifft if off but * 2?

is your ?
does your work without the *2 ?

 

[btb4198]

yeah so I have been doing some testing

(bin index / N) * Fs *2;
works for the fft
but
(bin index / N) * Fs
works for the IFFT

idk...
is your like that ?

 

[btb4198]

olivermsun:
ok i just did

            for (int n = 0; n < (16384); n++)
            {
                double R = Peak3 * (Math.Sin((Math.PI * n * Frequency3 / 44100D))) + Peak3 * (Math.Sin((Math.PI * n * Frequency2 / 44100D)));
                    list[n] = R;
                }

Frequency3 = 180
Frequency2 = 1800
and my peaks my fft are
F =177.64892578125 Hz M =11802.1425238338 db
F = 1798.0224609375 Hz M =12980.3239542856db

but after the IFFT
I get:
F =180.340576171875 Hz M =2868.64577598581 db
F =810.186767578125 Hz M =8808.60291243157 db
F =987.835693359375 Hz M= 2036.62342167183 db
F =1800.71411132813 Hz M=2624.20499585478 db

why is it peaking at 810 Hz and 987 Hz?
can you try this on your FFT and IFFT
and tell me the peaks you are getting?

do you think something is wrong with my FFT ?

 

[btb4198]

ok I am still testing witha signal with 180hz and 4441hz in it
but I am now using 32768 samples
my fft get peeks a
180.3Hz and 4441.22Hz
but my after I fo the ifft and then the fft again
I get peaks at

180.3 Hz
2130.44128417969 hz
2310.78186035156 hz this one has the biggest peak
4441.22314453125 hz

so something most be wrong
also I still have to do (bin index/N) *fs * s
for my fft
so if anyone can help me with that that would be great...
how should I start troubleshooting this ??

 

[olivermsun]

            for (int n = 0; n < (16384); n++)
            {
                double R = Peak3 * (Math.Sin((Math.PI * n * Frequency3 / 44100D))) + Peak3 * (Math.Sin((Math.PI * n * Frequency2 / 44100D)));
                    list[n] = R;
                }

Frequency3 = 180

Is 44100 Hz is your sampling frequency in the example above?

 

[btb4198]

yes it is

 

[Baluncore]

If you involve scaling and Hz in the FFT debug process you will have quite a difficult time getting the phase and frequency correct, or identifying the source of bugs in the code.

I have always found the best way to debug or calibrate an FFT is to use 8 or 16 element arrays.
By generating a simple signal = Cos(2*t), then advancing gradually to things like = 1 + 2*Cos(t) – 3*Sin(2*t), you will be able to control and see what is going on in the frequency domain. Following an FFT, the inverse FFT should return your original signal.

Once you have a robust FFT core you can then apply window functions and frequency scaling external to the FFT.


Recursive FFT code is very elegant mathematically, but often spends half the CPU time pumping frames on and off the stack.
The number of characters in the source code is not really important these days.

 

[olivermsun]

yes it is

So then that's one problem.

            for (int n = 0; n < (16384); n++)
            {
                double R = Peak3 * (Math.Sin((Math.PI * n * Frequency3 / 44100D))) + Peak3 * (Math.Sin((Math.PI * n * Frequency2 / 44100D)));
                    list[n] = R;
                }

Frequency3 = 180

The code above produces a wave with frequency = (Frequency3) / 2.

A wave with frequency $f$, at sampling frequency $f_s$, should be like $\sin(\mathbf{2}\pi \, n \, f/f_s)$.

That would explain why $f_s \cdot 2$ is giving you the correct frequency for your peaks.

 

[olivermsun]

Also, I agree with what Baluncore says above. You need to concentrate on getting the right numbers in and out of your FFT() and IFFT() before you start worrying about scaling the frequency bins, peak finding, filtering, etc.

 

[btb4198]

no,
I use
http://onlinetonegenerator.com/
that site to test my fft ...
If I play a tone from this site my fft picks it up..
I do have to do (bin index/N) * fs * 2
but then it will pick up the right frequency

also if I play sin(2πnf/fs), It does not sound right. it is alway too high
I know in school we learned to add 2π but that just does not work in the real would...
unless both me and this site is doing something wrong

 

[olivermsun]

no,
I use
http://onlinetonegenerator.com/
that site to test my fft ...
If I play a tone from this site my fft picks it up..
I do have to do (bin index/N) * fs * 2
but then it will pick up the right frequency

also if I play sin(2πnf/fs), It does not sound right. it is alway too high
I know in school we learned to add 2π but that just does not work in the real would...
unless both me and this site is doing something wrong

You don't "play" sin(2πnf/fs). You specify f in Hz (cycles/s) at this site, not 2πf in radians/s.

You synthesize the samples of a waveform with frequency f using sin(2πnf/fs).

 

[btb4198]

If you involve scaling and Hz in the FFT debug process you will have quite a difficult time getting the phase and frequency correct, or identifying the source of bugs in the code.

I have always found the best way to debug or calibrate an FFT is to use 8 or 16 element arrays.
By generating a simple signal = Cos(2*t), then advancing gradually to things like = 1 + 2*Cos(t) – 3*Sin(2*t), you will be able to control and see what is going on in the frequency domain. Following an FFT, the inverse FFT should return your original signal.

Once you have a robust FFT core you can then apply window functions and frequency scaling external to the FFT.


Recursive FFT code is very elegant mathematically, but often spends half the CPU time pumping frames on and off the stack.
The number of characters in the source code is not really important these days.

what is a good test I should use ?

 

[btb4198]

should I just do
for (int t =0; t<16; t++)
{

list[t] =Cos(2*t);
}
?

 

[btb4198]

You don't "play" sin(2πnf/fs). You specify f in Hz (cycles/s) at this site, not 2πf in radians/s.

You synthesize the samples of a waveform with frequency f using sin(2πnf/fs).

sorry I do not understand.
I have play tone using the Naudio c# class (https://naudio.codeplex.com/)
when I make my tone I do this :
Amplitude * Math.Sin(Math.PI * Frequency * n / 44100D))
if i add the * 2D *∏
it does not sound right,
so I removed it

are you saying that is should sound good?

so I went back and add the 2D * ∏
and you were right, I am able to remove the *2 on the (bin_index/ N)*Fs

but now after the IFFT
it is just completely wrong

 

[btb4198]

olivermsun:

ok if I remove the 2D * ∏
then I have to *2 on the (bin_index/ N)*Fs
for the FFT to work...

and the IFFT works a lot better
it works but there are just some peaks that come up
like
for F = 500hz and F2 1300hz
after the IFFT
and doing thing FFT again
I get peaks at:
399.3642578125Hz
500.64697265625Hz
900.357055664063Hz
1300.06713867188Hz

 

[btb4198]

also
why does my FFT works for
http://onlinetonegenerator.com/
with the (bin_index/ N)*Fs* 2 ?
they most not be doing 2*Pi right?
is that correct ?
is that how it should be ?

 

[olivermsun]

If I play a 440 Hz tone at that website, it sounds correct.
So there may be something wrong with the way you are getting your input stream.
I noticed in an earlier thread by you that there was some confusion about the stereo samples from left and right channels are handled. Have you sorted that out?

 

[Baluncore]

Both frequency and phase are important during testing.
I have not been following details, but I would consider (bin_index/ (N-1)) rather than (bin_index/ N).

 

[btb4198]

olivermsun,

that website is different now, than what it used to be. I have a video of me testing it, how it used to look, I need to find it and I will add it on here later

 

[btb4198]

Baluncore
why
(bin_index/ (N-1)) * fs?

 

[Baluncore]

why
(bin_index/ (N-1)) * fs?

It will depend on your array base indexing.
If you get that wrong it will introduce a frequency dependent phase error.

 

[olivermsun]

I don't quite understand the last part. If he is passing in N points and receiving N FFT bins then how can the indexing be spread over N-1 frequencies?

 

[Baluncore]

Because DC is zero frequency in bin zero.

 

[olivermsun]

If you have N bins and divide by (N-1), then don't you get two bins with the same normalized frequency?

I think what you want is N bins with normalized frequency [0:N-1]/N, right?

 

[btb4198]

when you say DC do you mean Direct current?

 

[olivermsun]

Yes, that's why he said DC is zero frequency.

 

[btb4198]

ok i just did this:

1.0
-0.41614683654714241
-0.65364362086361194
0.960170286650366
-0.14550003380861354
-0.83907152907645244
0.84385395873249214
0.13673721820783361

those 8 number from
Cos(2 * n);
and that go into my fft and I get :

{(0.886399443294871, 0)}
{(0.862297845278363, 0.616189555028432)}
{(0.664289628322506, 2.35212587048179)}
{(1.42870222233886, -2.37880560416378)}
{(1.20302116482566, 0)}
{(1.42870222233886, 2.37880560416378)}
{(0.664289628322506, -2.35212587048179)}
{(0.862297845278363, -0.616189555028432)}

then I reverse and send it back to the fft and dived by N
and I get this :

0.99999999999999989
0.41614683654714235
0.65364362086361194
0.96017028665036586
0.14550003380861354
0.83907152907645233
0.84385395873249214
0.13673721820783363

I lost my - value , will they all are + now... but it is because I am taking the
Magnitude
I am doing

double[] returntemp = new double[R];
           for (int v = 0; v < R; v++)
           {
               F[v] = F[v].Magnitude / N;
               returntemp[v] = F[v].Magnitude;
           }
           return returntemp;

I did not know if I should use the real or imaginary numbers, so I just used the
Magnitude
is that ok ?

 

[olivermsun]

If you want to verify that your FFT and IFFT are working correctly, you need to output both the real and imaginary parts. There will probably be a small imaginary part due to numerical errors but it should be negligible.

Your magnitudes look good.

 

[btb4198]

ok this is my real:

0.99999999999999989
-0.41614683654714235
-0.65364362086361194
0.96017028665036586
-0.14550003380861354
-0.83907152907645233
0.84385395873249214
0.13673721820783363

so I should use my real and not the Magnitude?

 

[btb4198]

my img is all like 0 and 0.00000000000000017478323165292
which is 0

 

[btb4198]

here are some video i make




see my fft does work for that site with the
(bin index/N) * fs * 2

also I did test it again with the new version of this site and it still work