Variable length FFT/IFFT Processor: Algorithm to Architecture Mapping and Implementation

Abstract

In modern technologies, the DSP algorithms behind the VLSI architectures play a significant role. The latest standards in wireless communications rise the challenges in the
implementations of future communications systems. The high-speed Wi-Fi (5G) technology is standardised a few years ago as IEEE 802.11ac standard that adopts an orthogonal frequency division multiplexing (OFDM) technique. The fast Fourier transform (FFT) is a traditional DSP algorithm, that plays a key role in wide range of applications in electrical
engineering. In OFDM system, the FFT and inverse fast Fourier transform (IFFT) plays a crucial role. A multiple input multiple output (MIMO) OFDM system needs multiple FFT
processors in the receiver and multiple IFFT processors on the transmitter side. The number of FFT/IFFT processors is linearly increased with the number of data streams. For example,an IEEE 802.11ac baseband processor handles up to eight spatial streams. The traditional approach employs eight IFFT processors for the transmitter and eight FFT processors for the receiver. Since the FFT/IFFT processors requirement linearly increases with the number of spatial data streams, implementation of a low power MIMO-OFDM system may not be feasible when the number of spatial streams is more. Hence, it is an interesting research problem to come up with a single FFT/IFFT processor that can handle multiple streams. To this end, there is a scope for developing new algorithms, architectures and design techniques for portable system applications.
The objective of this work is to investigate the methodologies and architectures for a variable length multi-path pipelined FFT/IFFT, the input-output data scheduling, reordering and the twiddle coefficient multiplication. Here, the input data scheduling, reordering plays an important role in multiplexing various streams into a single pipeline processor. Output reordering unit aligns the FFT/IFFT output into the standard order. On the other hand, hardware complexity and performance of an FFT/IFFT processor is highly influenced by the complex multipliers employed in the design. Therefore, this work is focussed on the fixed width signed multipliers used for twiddle coefficient multiplication in the proposed variable length FFT/IFFT processor. The proposed methodologies in this investigation are validated through MATLAB prior to the ASIC implementation. Then, various architectures are designed based the proposed methods, and RTL modelling in each case is done using the Verilog HDL. The functional verification is performed using Synopsys VCS and Synthesis is done by Synopsys Design Compiler using TSMC 65 nm CMOS standard cell library at 160 MHz. The functionality of the netlist after synthesis is also verified by using Synopsys VCS. Automatic Place and Route (APR) is performed using Cadence SOC Encounter. Moreover, Xilinx 14.2 ISE tools are used for the FPGA implementation.
In this thesis work, a brief review of the literature on various FFT/IFFT processors, input-output data reordering units and fixed width multipliers is presented. This thesis
work proposes a variable length FFT/IFFT computation algorithm for pipeline processing. Here, various butterfly calculations are time division multiplexed to optimize the hardware complexity by a factor of N/8 for the given FFT length N. A multi-path delay commutator(MDC) based FFT/IFFT processor is proposed where, it adopts various IEEE 802.11ac
standard FFT/IFFT design requirements likeN = 512/256/128/64, up to eight spatial streams and computation time (TDFT ) of 3.2 s etc. A staggered wordlength scheme is proposed in this work to have a controlled data path width across the pipelined structure. Moreover, Algorithms and architectures for MIMO data reordering and scheduling for variable length MDC FFT/IFFT are proposed. A modified procedure for radix-8 based Booth 2k-bit signed
multiplication is presented. The fixed-width signed multiplication with error compensation is proposed. A method to compute the error compensation bias for the proposed fixed-width multiplication is presented. Moreover, 12-bit, 14-bit and 16-bit real and complex multipliers based on the proposed methods are designed and implemented. In addition, the FPGA resource requirements of various proposed architectures are presented in this work.