Cooley–Tukey FFT

[reniam]

Hi,

Does anyone have the Cooley–Tukey FFT implemented in LabVIEW? I'm really trying to understand the algorithm and want to visualize it using real data in LabVIEW. I know NI provides a VI in the "Transforms" pallet.

[GerdW]

Hi reniam,

reading the LabVIEW help indicates NI implemented Cooley-Tukey in their FFT routines…

[altenbach]

Decades ago, we had a series of LabVIEW coding challenges, and one was to implement a competitive FFT for arbitrary sizes but I don't thing it received any entries. Classic Cooley-Tukey (Size is integer power of 2) is even simpler and should not be too hard to implement from scratch, but try it! Can be done fully in-place. (Back in the seventies, we had an pulse NMR controller that could do a 1kB complex fft with only a few kB of core RAM, if I remember right.).

The nice thing is that you can validate the correctness by comparing with the stock FFT tools that ship with LabVIEW. 🙂

Do a web search for FPGA implementations, maybe you find something useful. There are also quite a few youtube videos.

[altenbach]

I think the FFT coding challenge was in 2003(?) and I found a literal (slow) FT I made back then...Of course there are many other ways to do that.

As you can see, the difference is less than 1E-12

[Bob_Schor]

---

@altenbach wrote:

Classic Cooley-Tukey (Size is integer power of N) is even simpler and should not be too hard to implement from scratch, but try it!

Do a web search for FPGA implementations, maybe you find something useful. There are also quite a few youtube videos.

---

Did you mean "An integer power of 2", as in 2^N?  [Just for laughs, N^2 would be an integer power of N 😀].  Many years ago, I met Jim Cooley, a really "cool" character, and somewhere I have the original IBM Technical Paper on the Algorithm ...

Bob Schor

[altenbach]

Yes, N=2 (not the "size") in my post. Sorry for the confusion. 😄

[reniam]

Thanks altenbach

[altenbach]

Well, it's not really "the solution", because it is simple, literal FT, not FFT.

Still would be interesting to implement Cooley–Tukey FFT, you might even try a recursive VI solution. 😄 

[reniam]

Sure. I was just asking if someone already had the algorithm developed. A little surprised it isn't already out there. I marked yours as a solution because you gave it the best college try, though I already had something similar. I'm working on it using Steven W. Smith's book as a guide.

Thanks again.

[altenbach]

---

@reniam wrote:

A little surprised it isn't already out there.

---

Might still be a cool little project! 😄