Study And Design Of Low-complexity Mixed-radix FFT Algorithms

Fast Fourier Transform (FFT) algorithm is a kernel part of signal processing in radarmicrowave detection, communications and imag processing and so on. It is also theimportant part of the related processing algorithms in computational complexity. But inareas like synthetic aperture radar (SAR) and orthogonal frequency division multiplexing(OFDM) technology, the existing FFT’s implemtation methods still have some drawbacks,which include inflexibility processing length, severe resource wasted and large processingdelay. Therefore, the research that is based on resource saving, high real-time performanceand low-complexity mixed-radix FFT has an important practical significance in digitalsignal processing. By analyses and comparisons of all kinds of FFT algorithms, alow-complexity mixed-radix FFT is studied. First, the method of implementing the basicbutterfly unit is discussed. Meanwhile, the low-complexity FFT is designed and FFT basedupon multiple-storages structure is researched. The proposed methods in the paper canreduce the complexity of the FFT algorithms in the digital circuit, and improve thereal-time performance of FFT processing. Main works and innovations are as follows:1. As a special case, it is necessary to study the fixed-radix FFT. Because themethods of zeros padding for radix-2or radix-4FFT make FFTs waste much storageresource and long computing time, the radix-r butterfly units are discussed. Under theaccuracy of the single precision floating point, the butterflies are represented by the radix-3and radix-5FFT. To reduce the storage space, the fixed-point format is used to representthe twiddle factors and an effective and high-precision multiplier is designed.2. Because radix-r FFT is limited to the data number being power of r, an in-placemixed-radix FFT is discussed. First, the data access address scheme for the radix-r1/r2FFTis discussed. The scheme can obtain a low-complexity accessing address only through adesigned counter. Furthermore, the addressing scheme of the general mixed-radix, namelyradix-r1/r2/.../rsFFT is deduced. Meanwhile, because the type of the butterfly units inmixed-radix FFT increases, a configurable design of butterfly unit is studied to solve largeresouces waste. 3. In view of the poor real-time performance for in-place structure FFT, FFT basedupon multiple banks structure is studied to realize the mixed-radix FFT. Two cases arediscussed:(a) single butterfly processing element. There are three aspects to research: theoptional number of banks, the disctribution of data and access multiple banks in “paralle&pipeline”;(b) multiple butterfly processing units: the number of butterfly units andarrangement for multiple butterfly units and banks are studied. The propsed scheme canimproves the processing speed of FFT.