Abstract
Fast Fourier Transform (FFT) is one of the basic building blocks in many fields in engineering. Depending on the application, the FFT block can take between 5% and 25% of the overall power consumption and chip area of the overall system. Most of today’s wireless communication systems are based on Orthogonal Frequency Division Multiplexing (OFDM), which depends mainly on the FFT and IFFT operations to convert signals from time to frequency domains, and
vice versa. Hence, enhancing the performance of FFT operation in terms of throughput, complexity reduction, or area will have a large impact on the chips used in many engineering domains.
The applicants have addressed the problem of reducing the complexity of the FFT in a recently accepted publication [1]. The main approach used in reducing the complexity is introducing a restructure of the butterfly architecture of the FFT to be more CORDIC friendly. The conventional butterfly architecture of the FFT forces the use of CORDIC types that introduces
equal CORDIC gain at each FFT stage. However, there are more efficient CORDICs that were never previously used in the FFT implementations because the CORDIC gain depends on the angle of rotation. The new butterfly structure in [1] makes it possible to use the more efficient CORDIC types that reach the required angle of rotation in a smaller number of iterations
without being restricted to have equal CORDIC gain. This leaded to a decrease of 38% in the chip area compared to the conventional butterfly structure.
In this proposal, the applicants extend their work to further reduce the complexity, reducing the area, and speeding up the CORDIC-based implementation of FFT. The proposal addresses three important problems: (1) what are the optimal twiddle factors that should be used in the modified butterfly structure introduced in [1], (2) how can the new structure be used to reduce the complexity of partial FFT, and (3) how can the new architecture be implemented in a flexible way to support adaptive operations based on the received signal to noise ratio. In the first track, the objective is to choose the right set of twiddle factors that reduces the number of iterations of the CORDICs in different FFT stages, in order to speed up its operation. Without global optimization, the reduction in the area was around 38% compared to the conventional
FFT structure. Hence, we expect a reduction of around 50% using global optimization. In the second track, the proposal addresses the problem of generating only a subset of the FFT outputs based on the modified butterfly structure. Generating a subset of the FFT outputs will result in a reduction of the average power of the FFT hardware implementation. This can be used in wireless communications systems based on OFDMA, where users are assigned a small number of subcarriers. In the third track, the proposal introduces a revolutionary technique to adapt the processing power of the FFT engine depending on the input SNR. The idea is based on observing that the FFT is a linear operation, hence the final output can be the sum of the FFT output of the MSBs added to the LSBs. This will result in a reduction of the average power
consumed by the FFT block, and can be extended to other blocks. The algorithms that will be developed throughout the project will be tested on an FPGA. Hence, we will address both the signal processing and the hardware implementation parts of the system. We expect to have two conference papers, two journal papers submitted, and two patents filed by the end of the project duration.