Is FFT Fast Enough for Beyond 5G Communications? A Throughput-Complexity Analysis for OFDM Signals

Abstract

In this paper, we study the impact of computational complexity on the throughput limits of the fast Fourier transform (FFT) algorithm for orthogonal frequency division multiplexing (OFDM) waveforms. Based on the spectro-computational complexity (SC) analysis, we verify that the complexity of an $N$ -point FFT grows faster than the number of bits in the OFDM symbol. Thus, we show that FFT nullifies the OFDM throughput on $N$ unless the $N$ -point discrete Fourier transform (DFT) problem verifies as $\Omega (N)$ , which remains a “fascinating” open question in theoretical computer science. Also, because FFT demands $N$ to be a power of two $2^{i}$ ( $i>0$ ), the spectrum widening leads to an exponential complexity on $i$ , i.e. $O(2^{i}i)$ . To overcome these limitations, we consider the alternative frequency-time transform formulation of vector OFDM (V-OFDM), in which an $N$ -point FFT is replaced by $N/L$ ( $L > 0$ ) smaller $L$ -point FFTs to mitigate the cyclic prefix overhead of OFDM. Building on that, we replace FFT by the straightforward DFT algorithm to release the V-OFDM parameters from growing as powers of two and to benefit from flexible numerology (e.g., $L=3$ , $N=156$ ). Besides, by setting $L$ to $\Theta (1)$ , the resulting solution can run linearly on $N$ (rather than exponentially on $i$ ) while sustaining a non null throughput as $N$ grows.

Keywords

• Fast fourier transform
• computational complexity
• throughput
• spectro-computational analysis
• vector OFDM
• parameterized complexity