Design And Implementation Of High Dimensional FFT Accelerator

The large number of Fast Fourier Transform (FFT) has high requirements on the processor's computing and memory bandwidth. It is usually the bottlenecks of those applications with large data throughout and strong real-time demand, such as image processing, radar signal processing, communication and biomedical science. FFT has high computational complexity and large data. It is of great practical value to study the FFT accelerator with high speed, low resource consumption and easy hardware.In order to adapt to the complex digital signal processing on different dimensions,different points of the FFT computing tasks, in this thesis, based on the research of the principle of one-dimensional, two-dimensional, and three-dimensional FFT algorithm and the analysis of multifarious factors that affect the performance of FFT hardware accelerator, a variable dimension FFT hardware accelerator is designed. And the design has been successfully applied on the Xilinx Virtex6 FPGA chip. The result shows that the performance of the FFT accelerator meets the design requirements.The main research work of this thesis is as follows:1 The thesis analysis a variety of FFT algorithm principle and hardware structure. And it selects surface partitioning parallel algorithm and parallel processing architecture by comparing the computation of each algorithm and the complexity of hardware implementation.2 By using the data form of body-surface-line, the calculation is carried out from two levels of surface and line. It adopts surface partitioning and multiple parallel architecture to improve the parallelism of FFT.3 The others are Ping-Pong operation, pre-read and flexible address adjustment to conceal data transmitting time.4 In this thesis, the FFT accelerator consists of 4 parallel computing units to carry out 2n (n is from range of 5 to 16) single-precision floating-point 1-D FFT and 2n (n is from range of 5 to 8) single-precision floating-point 2-D/3-D FFT. What's more, It is important that the structure has strong expansibility which can achieve FFT of the sequence of m x n x p.5 The design has been successfully applied on the Xilinx Virtex6 FPGA chip. Its maximal frequency is up to 184.88MHz. The result shows that the performance of the FFT accelerator meets the design requirements.