Fast Fourier Transformation

Description

The Fast Fourier Transformation (FFT) is a computationally efficient algorithm for calculating the Discrete Fourier Transform (DFT) and its inverse. In 3GPP radio access networks, specifically for Orthogonal Frequency Division Multiplexing (OFDM) and Orthogonal Frequency Division Multiple Access (OFDMA) as used in LTE and NR, the FFT is a core mathematical operation at the physical layer. It is implemented in both base stations (gNB/eNB) and user equipment (UE) digital signal processors.

For transmission, the Inverse FFT (IFFT) operation is used. The transmitter maps data symbols (modulated bits from QPSK, 16QAM, etc.) onto specific subcarriers in the frequency domain. An IFFT of size N (where N is the FFT size, e.g., 2048 for a 20 MHz LTE channel) is then performed on this set of subcarriers. This transforms the frequency-domain representation into a time-domain waveform—a single OFDM symbol composed of a superposition of N orthogonal sinusoidal subcarriers. A cyclic prefix is added to this time-domain signal to mitigate inter-symbol interference from multipath propagation before it is sent to the RF front-end.

For reception, the process is reversed. The receiver samples the incoming time-domain waveform, removes the cyclic prefix, and performs an FFT on the resulting samples. This transforms the composite received signal back into the frequency domain, separating the energy from each orthogonal subcarrier. The receiver can then extract the data symbols from each subcarrier, equalize the channel effects per subcarrier (which is simpler due to OFDM's structure), and demodulate them. The FFT size directly relates to the system bandwidth: larger bandwidths use larger FFT sizes to maintain subcarrier spacing (e.g., 15 kHz in LTE). 3GPP specifications (e.g., 36.104, 38.521) define required FFT performance as part of transmitter and receiver RF characteristics, impacting metrics like EVM (Error Vector Magnitude) and adjacent channel leakage.

Purpose & Motivation

The FFT algorithm was adopted in 3GPP standards to enable the practical implementation of OFDM, a transmission scheme chosen for LTE (Rel-8) and NR due to its high spectral efficiency and robustness in multipath environments. The core problem OFDM solves is frequency-selective fading in wideband channels, but it requires a computationally feasible method to generate and decode a large number of closely spaced, orthogonal subcarriers.

Direct generation of hundreds of subcarriers with individual oscillators was impractical. The FFT/IFFT pair provides an elegant solution: it allows all subcarriers to be generated and decoded simultaneously through a single block transformation. The "Fast" aspect is critical—it reduces the complexity of the DFT from O(N²) to O(N log N), making it feasible to implement in real-time for large N (e.g., 2048 or 4096) within the power and silicon constraints of mobile devices. This computational efficiency was a key enabler for the broadband, multi-carrier systems that define 4G and 5G, addressing the limitations of the single-carrier CDMA approach used in 3G UMTS, which became increasingly complex to equalize at very high data rates.