and this is a great paper on implementing the FFT in hardware - didn't think it was going to be so tricky! web.mit.edu/6.111/www/f201…
OK, @ebrombaugh gave me a tip on the sliding DFT comm.toronto.edu/~dimitris/ece4…
which looks a lot simpler to implement on an #FPGA. I've written the algo in python to test against the numpy FFT. github.com/mattvenn/fpga-…
which looks a lot simpler to implement on an #FPGA. I've written the algo in python to test against the numpy FFT. github.com/mattvenn/fpga-…
off by one error in the sdft and plotting only real value of numpy fft instead of the modulus... now to start on the #FPGA implementation!
frequency bins overflow immediately in the simulation! Here's the python implementation showing history. Then the FPGA. I think it's because the twiddle factors are scaled to the full register width. Need to learn how to do scaling with integer maths on an FPGA!
Yosys does the synthesis, but ATM arachne-pnr fails to route. Love yosys show for looking at how things are inferred. Here's a portion of the parallel SDFT complex multiply and add blocks.
Arachne PNR wasn't the problem. I had a problem in the module that meant it had no outputs to the top module, so yosys automatically saved space by dropping the whole module!
The problem now is that with 16 frequency bins, the design needs 8k cells. I'll try on a bigger FPGA but I want to fit it in 1k. I think I can improve it a lot...
slowly getting a deeper understanding for how the maths works in the Fourier transform. This is how the complex coefficients add up as they are repeatedly multiplied - seeing it as a rotation helped me a lot.
The symmetry also explains why we only need to store half the coefficients!
on an 8k device @ 100Mhz I can get 16 bins with complex output, or 8 bins with a squared output. So I think I will move to a serial architecture and put the coeffs in 16 BRAMS. That way I think I can do 128 bins at 10MHz - details here: github.com/mattvenn/fpga-…
Serial processing of each bin implemented this evening - looking good, but not quite right yet. On the left are the frequency bins over time from the #FPGA. The bottom one should match the numpy fft output. Something wrong with the amplitudes...
overflows! Then for kicks tried with 128 bins. Unevenness due to rounding errors? 128 bins with a squared output to VGA takes 4000 cells. So with the remaining 4000 cells I can fit another 10 multipliers and finish each sample in about 20 clocks ~ 5MHz.
64 bins on VGA monitor with a square wave input! It responds to frequency but I think there is something wrong with the data transfer between fft and display modules.
