Implementation Of DFT Based On First-order Moments Using FPGA

The Discrete Fourier Transform (DFT) is an important basic operation in digital signal processing. It has been widely used in many fields of science and technology. There are an amount of theoretical and practical research values about DFT. A new systolic array with no multiplier based on first-order moments to calculate DFT has been designed and implemented on Xilinx Field Programmable Gate Array (FPGA) in this thesis with the new idea proposed by Professor Liu Jianguo that the common mathematical transformation can be realized using only first-order moments without multipliers. The algorithm used in this design is simple and concise. The systolic array presented in this thesis is simpler than other structures and can be easily expanded. The speed is much faster compared with many other methods. The most important factor is that the arbitrary length of data samples can be applied in this design using the algorithm presented in this thesis for DFT.According to the theory that DFT can be calculated using first-order moments with all adders, the implementation of DFT based on first-order moments with FPGA and analyzing the results after synthesis that can present some useful information about implementing other fast computations based on first-order moments are goals of the thesis. To achieve them, the hard description language Verilog HDL, the ModelSim for model and simulation, Xilinx integrated design tool called ISE and MATLAB have been used in the thesis. Then the different modules including the pre-processing module, the first-order moments module, the control module and the twiddle factor module have been designed. After carefully designed the testbench, different modules have been simulated in function and timing has been verified. Finally two systolic arrays for DFT have been assembled and DFT without multipliers has been realized. By analyzing the results from the simulation and synthesis, a conclusion has been acquired that the designs presented in the thesis have met design requirements and have superior practical prospects.