Java fft (not power of 2)

Hi to all,

I've been writing an application in JAVA that uses the Fourier Transform,
and performs several operations, such as the convolution.

The convolution is being processed in the time domain, so when signals
lenths are big (i.e. 1000 values or more), it takes very long to process
the convolution.

So the best way to do this is by working in the frequency domain.

Does anybody know a Java fft code that works for signals whose lengths can
be different than power or 2????

Thanks in advance!

On Aug 11, 12:46 am, "amyanes" <amya...@gmail.com> wrote:
> Hi to all,
>
> I've been writing an application in JAVA that uses the Fourier Transform,
> and performs several operations, such as the convolution.
>
> The convolution is being processed in the time domain, so when signals
> lenths are big (i.e. 1000 values or more), it takes very long to process
> the convolution.
>
> So the best way to do this is by working in the frequency domain.
>
> Does anybody know a Java fft code that works for signals whose lengths can
> be different than power or 2????
>
> Thanks in advance!

Google returned source code for this in 0.22 seconds. Were you hoping
for quicker response time here?

John

>Google returned source code for this in 0.22 seconds. Were you hoping
>for quicker response time here?
>
>John
>

I would really appreciatte it if you posted the link here. I've been
looking for a long time (maybe not doing it right), and only find
algorithms that work to transform signals that have lengths that correspond
to a power of 2. I need to be able to transform any array of any size. Is
it what you found??? Thanks

On Aug 11, 10:38 am, "amyanes" <amya...@gmail.com> wrote:
> >Google returned source code for this in 0.22 seconds. Were you hoping
> >for quicker response time here?
>
> >John
>
> I would really appreciatte it if you posted the link here. I've been
> looking for a long time (maybe not doing it right), and only find
> algorithms that work to transform signals that have lengths that correspond
> to a power of 2. I need to be able to transform any array of any size. Is
> it what you found??? Thanks

You can visit www.google.com/codesearch and enter "mixed radix fft
lang:java" into the search box. Here's a snapshot from one of the
results with LGPL license:

package jnt.FFT;

/**
 * Computes FFT's of complex, single precision data of arbitrary
length n. This
 * class uses the Mixed Radix method; it has special methods to handle
factors
 * 2, 3, 4, 5, 6 and 7, as well as a general factor.
 * <P>
 * This method appears to be faster than the Radix2 method, when both
methods
 * apply, but requires extra storage (which ComplexDoubleFFT_Mixed
manages
 * itself).
 *
 * <P>
 * See {@link ComplexFloatFFT ComplexFloatFFT}for details of data
layout.
 *
 * @author Bruce R. Miller bruce.miller@nist.gov
 * @author Contribution of the National Institute of Standards and
Technology,
 * @author not subject to copyright.
 * @author Derived from GSL (Gnu Scientific Library)
 * @author GSL's FFT Code by Brian Gough bjg@vvv.lanl.gov
 * @author Since GSL is released under
 * @author <H HREF="http://www.gnu.org/copyleft/gpl.html">GPL </A>,
 * @author this package must also be.
 */

You can always use an FFT that is a power of 2.  Say you want to convolve a
signal that is 78 points by one that is 1500 points.  Pad each signal with
zeros to make them each 2048 points long.  FFT convolution of these 2048
point long signals will give you an answer that is 2048 points long, with
the first 78+1500-1 = 1577 points being the convolution, and the remaining
471 points being zero.  Here's a link.
Regards,
Steve

http://www.dspguide.com/ch18.htm

Steve Smith wrote:
> You can always use an FFT that is a power of 2.  Say you want to convolve a
> signal that is 78 points by one that is 1500 points.  Pad each signal with
> zeros to make them each 2048 points long.  FFT convolution of these 2048
> point long signals will give you an answer that is 2048 points long, with
> the first 78+1500-1 = 1577 points being the convolution, and the remaining
> 471 points being zero.  Here's a link.
> Regards,
> Steve
> 
> http://www.dspguide.com/ch18.htm

Circular convolution of linear?

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

Thanks to all of you,

I just learned that google has a code search, which will be very useful
for this project I'm working on. I'll take a look at the codes (I've been
looking for this for months!). Thank you very much,

By the way, I'm using a Linear Convolution.