DFT/FFT in FPGA ??

[Spekkio]

Hi!

I have a fairly good understanding of FFT. I know what Laplace Transform, Fourier and Z Transform is, and I know how to use it. I made a simple FFT in C once that I used to look at DTMF signals ( like this ) and I also did a vibration sensor ( ).

https://github.com/Spekkio/dig_filter

But I want to implement a DFT in an FPGA to boost the speed of the data analysis. I know a little bit VHDL, I have programmed communication to an LCD display to show a temperature value on a CPLD. But nothing more complicated than that.

I have googled around to find some good examples of how people do DFT in FPGA's. But I never found a good example that I can understand. Actually, I don't understand it at all. My biggest question is, how is the exp() calculated?? and the complex numbers From all the examples I've looked at, exp and complex numbers doesn't seem to be used at all, I cannot understand how that works? Or they just made the example code impossible to understand. I need a much more basic explanation of how people create DFT algoritms in FPGA's, I don't want to get thrown into the complicated stuff immediatly like most tutorials I have found, I have to start from scratch with simple examples.

Do you normally use LUT's for exp() ? Or series expansions ?

Also, how is the clock signal used in a DFT implementation ?

I have this need to understand things, so a pre-made IP for DFT's will not be enough for me

Where do I start?

[Balaur]

While I understand your pre-made IPs comment, please have a look on the existing FFT-related stuff available on OpenCores (free registration required)

There are a lot of rather nice examples there.

Otherwise, sorry, I cannot provide any FFT insight. However, conceptually speaking, if you can imagine a non-recursive algorithm for your requirement, you can almost always write (bad) HDL (i.e. Verilog or VHDL) code to implement your algorithm. BTW, you can use fairly high level constructs (ex: arithmetic operators on IEEE floating point numbers are synthesizable by the Synopsys DC tool with the correct DesignWares).
With some luck, modern synthesis tools will happily take your HDL and spit out some block that will almost work. I don't even touch on the design validation phase, that involves a lot of effort.

Anything better than that requires a rather in-depth knowledge of the problem at hand and a gift for translating the concept into (parallel) hardware.

Cheers

[Spekkio]

Ah, thank you Balur. I've been thinking about looking at OpenCores actually. Already have an old account but I had problems with my login, never got my password remainder e-mail, so I gave up
I will try again now, maybe even create a new account if it doesn't work.

I wanted to take a look at the "radix 4 complex fft".

[jeroen74]

I once implemented the IDCT required for JPEG decompression in VHDL. It was really easy, but the fully parallel way I implemented ate resources like hell IIRC it was 7 multiplications by a constant and 11 additions.

I don't know how the constants are actually computed.

[jeffreyprinzie]

To calculate the FFT you need complex arithmetric.

main use is Wn = exp(2*pi/N):

this is sin(2pi/N) + j cos(2pi/N)

if Wn^k  , you mply 2pi/n*k in the sine.

A complex multiplication involves 4 real multiplications i thought and 4 addidions.
I dont know how to implement this using high speed, fixed point arith. but it could be possible.

indeed there may be IP available for this.

[nctnico]

There are also integer (aka fixed point) FFT implementations. Thats probably what you want in an FPGA. I found this website with Google: http://www.jjj.de/fft/fftpage.html

[Marco]

The MyHDL site has an example which uses recursion to instantiate the butterflies ... it's giving me a headache trying to understand it.

http://www.myhdl.org/doku.php/users:cfelton:projects:recursivefft

PS. this is of course a complex FFT ... to perform FFTs on real signals you either have to do the trick of combining 2 buffers to do two transforms in one or only use half the input which is inefficient.

[joelby]

Xilinx provides a FFT core generator in the free WebPACK version of their tools. It works very well. Altera also have an FFT MegaCore, though I'm not sure if that's free.

I wouldn't try to come up with my own FFT implementation unless I had very specific requirements, loads of free time, and/or an academic interest in FFTs!

[mrflibble]

Ah, thank you Balur. I've been thinking about looking at OpenCores actually.

Please let us know when you find an FFT core on opencores that doesn't make you want to shoot yourself in the head to end the suffering.

In the meantime I suggest using the FFT core of the fpga vendor of your choice. I don't know about the one from Altera, but the Xilinx fft core works just fine. And it's "free" IP, as in included with a regular ISE license.

[amyk]

Here's a bit more background on the theory:
http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm

There's nothing particularly difficult about the implementation; basically the mathematical functions are replaced with lookup tables so everything just becomes a lot of arithmetic and array lookups.

[Spekkio]

Thanks for all the info!

Now I have something more to work with