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!
Real FFT implementation
Started by ●May 10, 2011
Reply by ●May 10, 20112011-05-10
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
> 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
Reply by ●May 10, 20112011-05-10
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
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
Reply by ●May 10, 20112011-05-10
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
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
Reply by ●May 11, 20112011-05-11
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?
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?
Reply by ●May 11, 20112011-05-11
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
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
Reply by ●May 12, 20112011-05-12
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!!
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!!
Reply by ●May 12, 20112011-05-12
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
> 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