This is a simplified Fast Fourier Transform implementation (based on the radix-2 Cooley–Tukey algorithm) that can be scaled-up to larger precision and more points. Designed for low complexity circuits requiring large DFT calculations, sacrificing speed. This specific implementation offers 4-point, 8-point, and 16-point versions of the Fourier Transform, while having the precision set to 4 bits.
For the first part, it integrates reverse bit ordering, placing data to their corresponding memory address as they are being input from the user. Afterwards, data, along with the weights, are fed through a single butterfly module (2-point DFT), responsible for all the calculations, controlled by the control unit which delegates the data reading/writing throughout each clock cycle. Once finished, the data output process begins. The FFT is calculated using signed fixed-point arithmetic. The decimal range is between -1 and 0.875. Any results bigger/smaller than the previous, will be capped at the maximum/minimum value possible.
Connect the proper I/O for inserting data/controlling the circuit, and displaying/reading output. Follow the steps as shown below:
| # | Input | Output | Bidirectional |
|---|---|---|---|
| 0 | imaginary_in[0] | segment a/imaginary_out[0] | mode_change |
| 1 | imaginary_in[1] | segment b/imaginary_out[1] | enter |
| 2 | imaginary_in[2] | segment c/imaginary_out[2] | none |
| 3 | imaginary_in[3] | segment d/imaginary_out[3] | none |
| 4 | real_in[0] | segment e/real_out[0] | none |
| 5 | real_in[1] | segment f/real_out[1] | none |
| 6 | real_in[2] | segment g/real_out[2] | none |
| 7 | real_in[3] | dot/real_out[3] | none |