FFT Algorithm and Simulation Analysis Based on FPGA/CPLD

Programmable logic devices FPGA (field programmable gate array) and CPLD (complex programmable logic device) are increasingly used in the field of digital signal processing. Compared with traditional ASIC (application-specific integrated circuit) and DSP (digital signal processor), digital signal processing systems based on FPGA and CPLD have higher real-time and embeddability, and can easily realize system integration and functional expansion. The hardware structure of FFT mainly includes butterfly processor, storage unit, address generation unit and control unit. The algorithm proposed in this paper introduces pipeline structure in butterfly processor, which improves the operation speed of FFT. At the same time, pipeline register can store common items in butterfly operation, so only one multiplier and two adders are used in the design of butterfly processor, which reduces the complexity of hardware circuit. In order to further improve the operation speed of FFT, this paper designs a parallel multiplier for butterfly processor based on in-depth research on various multiplier algorithms. When implementing the multiplier, this paper adopts the improved Booth algorithm to reduce the number of partial products. At the same time, the Wallace tree structure and 4-2 compressor are used to add the partial products in parallel. This paper takes 32-point complex FFT as an example for design and logic synthesis. The FFT circuit is completed by designing the corresponding storage unit, address generation unit and control unit. The simulation results of the circuit are consistent with the software calculation results, which proves the correctness of the algorithm proposed in this paper. In addition, this paper also proposes a further improvement plan for the design results, adding a pipeline register in the multiplier to increase the speed of FFT to twice the current speed, which has extremely high practical value in situations where real-time requirements are high.