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