FFT core for FPGA

[OwO]

A project I'm working on right now: https://github.com/gabriel-tenma-white/fpga-fft
I've already beat Xilinx's FFT IP core in performance per resource utilization. With the same specifications (pipelined streaming data input/output, 24 bit data, 16 bit twiddle) the used LUTs are about the same, number of multipliers are slightly lower, but the achieved Fmax is higher than Xilinx's on the same device and speed grade.

The next step is to apply the Bailey's algorithm again but on DRAM to get 4096*4096 = 16M FFTs. The main tricky part will be to transpose data efficiently (or to read data in transposed order) in DRAM. The way to do this is to store your data in a bit-permuted order such that a sub-block in the matrix occupies a page of DRAM (rather than a few lines in the matrix occupying a page), as well as process several columns at once (e.g. read the first 8 values in every matrix row to get the first 8 columns, then perform 8 FFTs). I ran the numbers and it should be possible to make efficient use of each opened page of the DRAM at size 16M on a Zynq-7010.

I'm also looking into adapting this to floating point arithmetic. Floating point multiply is easy, you simply multiply the mantissa and add the exponents, then possibly shift the mantissa left by one position if there's a leading 0 (then drop the leading 1 if you want IEEE format). The additions are harder, you have to use bit shifts or wide multiplexers which are expensive in an FPGA. Looking at the Xilinx FFT cores though, the floating point implementation uses not much more LUTs than the fixed point cores, so it's probably doable.

[asmi]

The additions are harder, you have to use bit shifts or wide multiplexers which are expensive in an FPGA. Looking at the Xilinx FFT cores though, the floating point implementation uses not much more LUTs than the fixed point cores, so it's probably doable.

You can implement  shifters and wide bus multipliers on DSPs. Which is what I suspect the core is doing.

[KE5FX]

Nice.  What license are you planning to use?

[OwO]

You can implement  shifters and wide bus multipliers on DSPs. Which is what I suspect the core is doing.

That's what I suspected at first, but the DSP48 usage of the float FFT cores is only slightly higher (4 more), so maybe they are doing some tricks with using fixed point arithmetic internally and only doing scaling afterwards.

Nice.  What license are you planning to use?

Most likely GPL, but can consider other licenses if there is a good reason for it.

[asmi]

That's what I suspected at first, but the DSP48 usage of the float FFT cores is only slightly higher (4 more), so maybe they are doing some tricks with using fixed point arithmetic internally and only doing scaling afterwards.

I suggest you to actually read the documentation for the core. The doc clearly tells that they don't do any scaling. Here is the quote:

When comparing results against third party models, for example, MATLAB, it should be noted that a scaling factor is usually required to ensure that the results match. The scaling factor is data-dependent because the input data dictates the level of normalization required prior to the internal fixed-point core. Because the core does not provide this scaling factor in floating-point mode, you can apply scaling after the output of the core, if necessary.

It also tells that internally they use fixed-point math.

Most likely GPL, but can consider other licenses if there is a good reason for it.

GPL is not a license - it's a virus and a good way to ensure no sane developer ever touches this code.

[David Hess]

Releasing the code under the GPL does not preclude the copyright holder from licensing the same code under a different license.  The copyright holder is not bound by the GPL applied to their own code.  So if someone else wanted to use the code without GPLing their own code, then the copyright holder could allow it for a price.

[hamster_nz]

I just use MIT License for hobby work, as licensing bores me immensely.

I am never going to bother calling a lawyer over anything as trivial as my hobby projects that I knowingly upload to a public website. And if I am not prepared to lawyer up, then it is all just an academic exercise.

May as well make it as easy as possible for people to make use of it if they wanted to.

[OwO]

That's what I suspected at first, but the DSP48 usage of the float FFT cores is only slightly higher (4 more), so maybe they are doing some tricks with using fixed point arithmetic internally and only doing scaling afterwards.

I suggest you to actually read the documentation for the core. The doc clearly tells that they don't do any scaling. Here is the quote:

When comparing results against third party models, for example, MATLAB, it should be noted that a scaling factor is usually required to ensure that the results match. The scaling factor is data-dependent because the input data dictates the level of normalization required prior to the internal fixed-point core. Because the core does not provide this scaling factor in floating-point mode, you can apply scaling after the output of the core, if necessary.

It also tells that internally they use fixed-point math.

Most likely GPL, but can consider other licenses if there is a good reason for it.

GPL is not a license - it's a virus and a good way to ensure no sane developer ever touches this code.

OK that's no fun then if it's just a fixed point core with pre-normalizing. However I did do some thought experiments and from first sight it looks like a true floating point FFT implementation doesn't offer very much advantages because the higher magnitude values tend to drown out everything else as it propagates through the core.

I've settled on LGPL. It allows commercial use without fear but at the same time still prevents proprietary improvements being released.

[Doctorandus_P]

https://opencores.org/

[rstofer]

I just use MIT License for hobby work, as licensing bores me immensely.

I am never going to bother calling a lawyer over anything as trivial as my hobby projects that I knowingly upload to a public website. And if I am not prepared to lawyer up, then it is all just an academic exercise.

May as well make it as easy as possible for people to make use of it if they wanted to.

I agree.  I am using the MIT License because somebody once said I should have some kind of license at the top of my files.  I have no idea why!  If I handed it off to someone, it's pretty much theirs to do with as they wish.  Just don't come back at me if it doesn't work.  Maybe that's the reason: 'THE SOFTWARE IS PROVIDED "AS IS" ...'

Nobody in their right mind would use my code.