FFT Hardware Accelerator

The FFT algorithm make possible to speed up the DFT.

DFT:

Algorithm

Cooley-Tukey

The Cooley-Turkey algorithm is the most famous FFT algorithm. It breaks the DFT into smaller DFT's. The computational complexity is reduced from O(N^2) to O(N logN).

This implementation is a simple radix-2 DIT (decimation in time) FFT:

Thanks to the periodicity of the complex exponential, is possible to rewrite X(k) as following:

Where

For more information you can take a look at https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm

Hardware Design

The idea is to implement this algorithm in hardware. The main components are:

Datapath

• Multipliers
• Adder-Subtractors
• Registers

Control Unit

• Microprogrammed CU

Requirements to Compile and Simulate

sudo apt-get install ghdl gtkwave

Requirements to Synthetize

Walkthrough https://github.com/YosysHQ/yosys

Walkthrough to convert vhdl into verilog files https://github.com/ldoolitt/vhd2vl (needed for synthesys with yosys)

Requirements to Place&Route

Walkthrough https://github.com/YosysHQ/nextpnr

Simulation

The 'testbench_FFT.vhd' is the default testbench.

The simulation can be seen running gtkwave FFT.vcd.

Compile the design

Running tb_script file , all files will be analyzed using ghdl.

By default a vcd file named 'FFT.vcd' will be created.

You can see the simulation running again gtkwave FFT.vcd.

Synthesis

Has to be done. (Some problem converting vhdl to verilog)

If you can convert them, the synthesys can be done with yosys, reading all verilog files.

The target FPGA platform can be choosed with yosys with the commmand: synth_<target_name>.

Place & Route

Has to be done.

Using nextpnr.