Hey !
I need a Fast Fourier Function for Java Project that I'm currently doing...
I have a graph with 2048 dataspots (array of doubles) and gaussian noise. I want to filter that with a FFT...
Does anyone have java code that could help me ? Or does anyone know a place in the net where I can find that in the net ?
Thanks
Felix
> I have an onedimensional array of 2048... graph[]...
> but the function needs a twodimensional, and i don't
> have the imaginary part.
>
> double[][] fft_1d( double[][] array )
>
then just make it zero.
if you have the source code you can also remove all the reference to the imaginary part and hardcode a zero this might actually speed up the calculation.
regards
Spieler
What exactly are you doing?
A Fourier Transformation doesn't 'smooth' anything, it does a frequency analysis some examples:
function --> fourier transform (constant factors and phases ignored)
sin(ax) --> sin(x/a)
__
__| |__ --> a wavelet (something looking like sin * by a gauss function, thus tending towards zero off the center) the more narrow the peak is the wider becomes the wavelet
|
__|__ --> - (constant function)
know if you cut of pieces of the transformed function, e.g. setting all values for |x| > some threshold will and transforming back
will manipulate you original in all kinds of weird ways. The
example given will do some smoothing, but will also itroduce wriggles
arround corners (just like the stuff you get in jpeg images)
regards
Spieler
Okay what I have is a function of 2048 dataspots... So it could be a simple line with added gaussian noise ! So it would be a graph with lots of peaks either positive or neagtive !
Now I need to filter the noise... Someone told me I should do a Convolution using FTT !!! And I have no clue how FFT really works...
What I need is a function that gives me a new filtered graph !
Felix
Try the following:
do a FFT on your array;
from the resulting array set all values to zero (real and imaginary part) with and index < d or > array.length -d (I'd say start with d in 5-50)
FFT that array again ... have a look at the result. Adjust d
note that FFT consideres your function to be periodic, so it might yield strange results to to border effects.
Maybe you are better off with splines, bezier or approximation by a polynom (I think thats called polynominal regression, but I'm not sure)
depends on what you intend to do with your smoothed function
regards
Spieler
in pseudo code:
a : array of complex numbers(2048)
b : array of complex numbers(2048)
c : array of complex numbers(2048)
d : int = 20
a = your original data
b = FFT(a)
for (i = 0..d)
b(i) = 0// do this with both the imaginary and the real part
b(2048 - i) = 0
end loop
c = FFT (b)
regards
Spieler
I tried the algorithm but somehow it's not working at all...
the FFT gives even higher peakes than the graph before...
and the spots that I get from the the FFT, doesn't look like the dataspots from the graph I had before...
Valling it a second time like u wrote me, makes it even worses... the whole screen is covered with random lines... the means the peaks are either positiv or negative out of range...
Felix
Mhh well but how is this right than...
if i have a sin function and i want to filter that, the end result would only be a peak... Is this a convolution ?
I get the feeling the FFT isn't the right function to do a convolution... Better should use bezier or something...
Felix
a convolution is somthing you do with two functions:
the convolution c(x) of g(x) and f(x) is something like
the Integral from -infinety to +infinity over g(x)f(y)dx. I don't have the exact definition here but that's how it looks like
With some tricks you can probably consider a Fourier Transformation a Convolution, but it isn't a tool to do a convolution.
The trick with fourier is that you do it twice and get the original back and if you do something to the result in between you can get effects like smoothing and the like.
regards
Spieler
> Mhh well but how is this right than...
> if i have a sin function and i want to filter that,
> the end result would only be a peak... Is this a
> convolution ?
> I get the feeling the FFT isn't the right function to
> do a convolution... Better should use bezier or
> something...
> Felix
Finite Impluse Response (FIR) filters and Infinite Impulse Response Filters(IIRF) are two types of filtering that can be applied to a signal
train.
You are currently looking at FIR filters. Now the normal way to perform
a FIR is to convolve your input data, a(x), with your filter data, b(x). This can
become computationally expensive, especially if you wish to filter
out low frequencies as this requires a large filter (b(x)).
Now the fourier transform come into this as it provides a method to efficiently convolve two data streams together.
if we let @ be the symbol for convolution and F(x) be the fourier
transform of x then the following is true.
a(x) @ b(x) == F(a(x))*F(b(x))
in other words if you transform your filter and data into the fourier
domain then your convolution becomes a multiplication.
In general it is only worth performing a convolution via the fourier domain
if the filter you wish to apply is large. You wish to filter out high
frequencies (small filter) so it probably isn't worth your while using
the fourier domain (anyway the FFT is a ***** to write).
If you do wish to use the Fourier domain you might find that for a
datasize of 2048 points the Fast Fourier Transform is about the same
speed as a normal Fourier Transform. (The benifits of the FFT over the
FT become apparent as your data size increases.
The other option you have is to use an IIRF. These are trivial to
implement but quite tricky to create filters for.
An example IIRF is below
/**
*
*/
public double[] IIRF(double[] xCoeffs, double[] yCoeffs, double[] data)
{
if(xCoeffs.length!=yCoeffs.length+1) return null;
// output data
double[] output = new double[data.length];
for(int i=yCoeffs.length;i<data.length;i++)
{
double sum = data[i]*xCoeffs[0];
for(int j=0;j<cooeffs.length;j++)
{
int tmp = j+1;
sum+= data[i - tmp]*xCoeffs[tmp] + output[i-tmp]*yCoeffs[j];
}
output[i] = sum;
}
return output;
}
values for the coeffs could be
(single pole low pass)
(note the above code expects xCoeffs to be 1 element larger then yCoeffs)
xCoeffs[0] = 1-x;
xCoeffs[1] = 0;
yCoeffs[0] = x;
x can be varied from 0.0 to 1.0 changing the cutoff frequency
according to x = e^(-2 pi f) or time constant by x = e^(-1/d)
high pass/band pass/band reject filters are also possible but you will
have to dig out your Z-transforms to figure out the coefficients.
matfud
>
Dear Friend,
Definetely the code in the JAVA FFT is wrong...
the inverse and the forward FFT transform have
the same code listing... only what they changed is the
end /* end of FFT_1d */
and the inverse is correct...
but it is obvious a non computer expert changed the end of the comments
but he/she forgot to put the right listing...
because we do not use capital letters in Java... (FFT_1d)
I disagree with Spieler - I think FFT is a fine tool for doing convolution. Why not?
Here's the definition of convolution:
http://www.jhu.edu/~signals/convolve/
There's no reason you can transform both of these time signals into the frequency domain, do the calculation, and then transform back to the time domain. That's what transform methods like Laplace, Fourier, etc. are all about.
FFT is just a very nice algorithm for doing Fourier transforms numerically. Why wouldn't it apply here? - MOD
> Definetely the code in the JAVA FFT is wrong...
> but it is obvious a non computer expert changed the
> end of the comments
> because we do not use capital letters in Java...
Looking at the code, it does look like it's come from Fortran:
double[][] fft_1d(double[][] array)
{
...j = 1;
for (i = 1; i < n; i++ )
{
...
t_r = array[i - 1][0];
Due to Fortran's array memory mapping, you want the first index in a multi-dimensional array to be the most rapidly varying, but in Java or C you want the most rapidly varying index to be the last (both for locality of reference effecting CPU cache, to allow a local variable to alias the row, and, in Java, you arrange high ratio rectangular arrays to reduce the craetion and garbage collection overhead).
Take look at the C parts of numerical recipies for more info on FFT, convolution, smoothing filters and correlation
http://lib-www.lanl.gov/numerical/index.html
Pete
> With some tricks you can probably consider a Fourier
> Transformation a Convolution, but it isn't a tool to
> do a convolution.
I have to disagree. It's not a trick. The Fourier
transform converts a convolution into a product.
Having multiplied the transformed functions, the
inverse transformation gives the convolution.
This is a method given in Knuth for fast multiplication
because integer multiplication essentially uses
convolution to find each digit in the product.