Research And Design Of Parallel Memory System For FFT Algorithm

Fast Fourier Transform(FFT)maps a data sequence from discrete time domain to the frequency domain,and can be implemented more simply to deal with discrete time signal processing.However,the complexity of DFT operation is O(N2),and it is difficult to be applied in practical operation.In the last century sixty's,Cooley and Tokey proposed the Fast Fourier Transform(FFT)to process DFT sequences,and the FFT is widely used in various signal processing systems such as convolution,correlation,filtering,spectrum analysis and so on.Now FFT is the core algorithm of digital signal processing.With the continuous improvement of the performance requirements of FFT algorithm in wireless communication and other applications,it is very important to deeply research on the FFT algorithm and its software and hardware relization.The design of parallel storage system to support the FFT parallel access is an important method to achieve the speed of FFT algorithm.This paper is based on the hardware implementation of FFT algorithm.The paper analyzes and designs the storage structure of FFT algorithm.The paper analyzes the widely used radix-2 and radix-4 FFT algorithms and its parallel storage structure,and studies the radix-16 FFT algorithm which is mainly used in the application domain timely and high-throughputly;An effective method to save the cost of memory address transformation circuit area is proposed,which can support the access in parallel and obtain higher performance.Finally,it is applied to the optimization design of a digital signal processor FT-XDSP vector array,which can improve the efficiency of the storage.The main research are below:1: this paper analysis the law of operations for radix-2,radix-4 FFT algorithms,and analysis each stage in FFT algorithms,then proposed a kind of easier memory system to support parallel access for some processing elements.This kind of address transformation methods reduces the complexity of hardware and is easier to understand for programmer;2: this paper also analysis the reason for high-throughput of reformulated radix-16 FFT algorithm.And this paper analysises the law of operations address each stage in WPAN standard,and proposed a better address transformation method to support parallel access,and realize this method in circuits.3: this paper research on the memory system of a special high-performance micro-processor FT-XDSP,and first prove the address transformation method for radix-2 FFT is also suited for radix-4 FFT used in this special micro-processor,then proposed address transformation for this special memory structure to reduce the access conflicts during programmer running.The result shows that,the circuits of address transformation methods for radix-2 and radix-4 FFT algorithms needs less area comparing to other methods;the area of circuits of address transformation for reformulated radix-16 FFT algorithms reduce about 47%,and power reduce about 24%.After the memory system circuit changed on FT-XDSP,for regular FFT programs conflict can be wholly elimated,and for pipelined FFT programs conflict can be elimated about 26% to 88.4%.