Forums

Real FFT implementation

Started by fezi...@gmail.com May 10, 2011
Hi everyone,
I need assistance in computing FFT of real valued data. Googling, i found that sorensen has developed and implemented an algorithm. But i couldnt find the steps to code it. Moreover above said algorithm is decimation in time. My requirement is decimation in frequency. Any help(c code\algorithm) is deeply appreciated!

Thanks!
Fezi-

> I need assistance in computing FFT of real valued
> data. Googling, i found that sorensen has developed and
> implemented an algorithm. But i couldnt find the steps to
> code it. Moreover above said algorithm is
> decimation in time. My requirement is decimation in
> frequency. Any help(c code\algorithm) is deeply
> appreciated!

Try this book:

http://www.amazon.com/Fast-Fourier-Transform-Its-Applications/dp/0133075052

Look for section "Transform of 2 N Samples with an N-Sample Transform". The source code is given in BASIC, but easily
ported to C.

-Jeff
Hi Fezi,
You could look into KISSFFT (http://sourceforge.net/projects/kissfft/)
and FFTW (http://www.fftw.org/). KISSFFT is more general, as it supports
fixed point transforms (after a re-compile), but FFTW is a little more
sophisticated and offers some more options for the transform.
Good Luck,
-Brant

On Tue, May 10, 2011 at 9:03 AM, Jeff Brower wrote:

> Fezi-
> > I need assistance in computing FFT of real valued
> > data. Googling, i found that sorensen has developed and
> > implemented an algorithm. But i couldnt find the steps to
> > code it. Moreover above said algorithm is
> > decimation in time. My requirement is decimation in
> > frequency. Any help(c code\algorithm) is deeply
> > appreciated!
>
> Try this book:
>
> http://www.amazon.com/Fast-Fourier-Transform-Its-Applications/dp/0133075052
>
> Look for section "Transform of 2 N Samples with an N-Sample Transform". The
> source code is given in BASIC, but easily
> ported to C.
>
> -Jeff
>
>
>

--
Brant Jameson
PhD Candidate
UC Santa Cruz Computer Engineering
http://people.ucsc.edu/~pheese
Also, see


Not sure if it uses decimation in freq.

- Andrew

----- Original Message ----
From: Jeff Brower
To: a...
Cc: f...@gmail.com
Sent: Tue, May 10, 2011 12:03:54 PM
Subject: Re: [audiodsp] Real FFT implementation

Fezi-

> I need assistance in computing FFT of real valued
> data. Googling, i found that sorensen has developed and
> implemented an algorithm. But i couldnt find the steps to
> code it. Moreover above said algorithm is
> decimation in time. My requirement is decimation in
> frequency. Any help(c code\algorithm) is deeply
> appreciated!

Try this book:

http://www.amazon.com/Fast-Fourier-Transform-Its-Applications/dp/0133075052

Look for section "Transform of 2 N Samples with an N-Sample Transform". The
source code is given in BASIC, but easily
ported to C.

-Jeff
Thanks to all once again.....

Why i need a DIF RFFT is that i am trying to do an algorithm level optimisation. The bit reversal portion in DIT is to be avoided. Taking DIF and then inverse DIT can help me do this i guess.
Most of the links and references you people gave were those i read earlier. Out of which , efficient computing by TI wiki is a common one. I have coded it. But it still requires a re-ordering or output extraction at the end of algorithm. fftw is much more complex as told.
Do you guys have a hands on experience with FFT on real data and quote the step by step procedure to calculate it?
One final link that I found while searching for a non-uniform fft today:
http://www.dsprelated.com/showcode/48.php

On Tue, May 10, 2011 at 9:13 AM, Andrew Elder wrote:

> Also, see
>
> <
> http://processors.wiki.ti.com/index.php/Efficient_FFT_Computation_of_Real_Input
> > Not sure if it uses decimation in freq.
>
> - Andrew
> ----- Original Message ----
> From: Jeff Brower
> To: a...
> Cc: f...@gmail.com
> Sent: Tue, May 10, 2011 12:03:54 PM
> Subject: Re: [audiodsp] Real FFT implementation
>
> Fezi-
>
> > I need assistance in computing FFT of real valued
> > data. Googling, i found that sorensen has developed and
> > implemented an algorithm. But i couldnt find the steps to
> > code it. Moreover above said algorithm is
> > decimation in time. My requirement is decimation in
> > frequency. Any help(c code\algorithm) is deeply
> > appreciated!
>
> Try this book:
>
> http://www.amazon.com/Fast-Fourier-Transform-Its-Applications/dp/0133075052
>
> Look for section "Transform of 2 N Samples with an N-Sample Transform". The
>
> source code is given in BASIC, but easily
> ported to C.
>
> -Jeff
>
>
>

--
Brant Jameson
PhD Candidate
UC Santa Cruz Computer Engineering
http://people.ucsc.edu/~pheese
Guyss....
i found solution from an IEEE paper. This paper describes what i want exactly. Find the link below:

http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel6%2F29%2F26211%2F01165220.pdf%3Farnumber%3D1165220&authDecision=-203
Thank You All!!
Fezi-

> i found solution from an IEEE paper. This paper
> describes what i want exactly. Find the link below:
>
> http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel6%2F29%2F26211%2F01165220.pdf%3Farnumber%3D1165220&authDecision=-203

Great to hear. Good luck with your project.

-Jeff