Análise da Complexidade Espectro-Computacional para Comunicações sem Fios

Abstract

This thesis introduces the spectro-computational complexity (SC) analysis of communication signal algorithms. The SC analysis stems from a novel mathematical model that unifies indicators of performance of the information theory, such as capacity, throughput, and spectral efficiency (SE), along with indicators of the theory of computational complexity (CC), such as processing runtime, the number of computational instructions and asymptotic lower bound. The proposed analysis exploits the fact that both classes of performance indicators can be written as a function of the signal’s spectral bandwidth W. This thesis defines the SC throughput SC(W) of a communication signal algorithm as the ratio between the number of modulated bits B(W) and the CC T (W) required to turn the bits into the signal. Thus, an asymptotic analysis on W reveals the necessary CC (or SE improvement) to prevent the nullification of SC(W) as W grows. Based on SC(W), novel definitions derived from and homologous to concepts of the CC and information theory fields are defined, such as SC capacity, SC efficiency, optimal SC algorithm, and comp-limited signals (from computation-limited, as a reference to the homologous power- and band-limited signal regimes). With the assistance of the SC analysis, novel capacity-complexity scaling laws are presented for Orthogonal Frequency Division Multiplexing (OFDM) and some variants. In a case study, an optimal mapper for OFDM with Index Modulation (IM) was designed, implemented, and evaluated. Such ideal mapper reaches the maximal SE gain over OFDM but its complexity had been considered computationally intractable by the OFDM-IM literature. Based on the SC analysis, the exact asymptotic complexity required to sustain the maximal SE gain was demonstrated as linear (rather than exponential) on the number of subcarriers. In other case study, it was shown that the complexity of the FFT algorithm causes the throughput of OFDM to nullify on the number of subcarriers N. The FFT constraint that N must grow as a power of two 2^i (i > 0) translates into an exponential complexity on i as spectrum widens. In general, it is shown that the throughput of FFT-based waveforms (e.g. OFDM) nullifies on N unless the lower bound complexity of the Fourier transform problem verifies as linear on N, which implies in faster-than-FFT algorithms and remains an open question in computer science. Based on the SC analysis, an algorithm is proposed to an alternative formulation in which an N -point transform is replaced by several smaller transforms. This formulation is employed by OFDM in its vectorized form (V-OFDM) in order to mitigate the cyclic prefix overhead of OFDM. Thus, the proposed algorithm can replace FFT in V-OFDM. By relaxing the power of two constraint of N and, with the parameterization of the number of smaller transforms, it was verified that the complexity of the proposed algorithm can grow linearly on N rather than exponentially on i. The presented case studies illustrate how the SC analysis can guide waveform designers towards the optimal balance between capacity and complexity in the extremely large signals expected for future wireless networks.

A presente tese introduz a análise da complexidade eSpectro-Computacional (SC) para algoritmos de sinais de comunicação. A análise SC baseia-se em um novo modelo matemático que unifica indicadores de desempenho da teoria da informação como capacidade, débito de sinal e eficiência espectral (SE), com indicadores da teoria da complexidade computacional (CC) como tempo de execução, número de instruções computacionais e cota assimptótica inferior de um problema computacional. A análise proposta explora o facto de que ambas classes de indicadores de desempenho podem ser escritas como função da largura espectral do sinal W. Nesta tese, o débito SC SC(W) de um algoritmo de sinal de comunicação como a razão entre o número de bits modulados B(W) e a CC T(W) necessária para transformar os bits em sinal. Assim, uma análise assimptótica em W revela a CC mínima (ou a melhoria de SE) necessária para impedir que SC(W) tenda a zero a medida que W cresce. Baseado no débito SC(W ), novas definições derivadas e homólogas a conceitos dos campos da CC e da teoria da informação são apresentadas como capacidade SC, a eficiência SC, algoritmo SC óptimo e sinais comp-limited (do inglês “computation-limited”, em referência aos regimes homólogos power- e band-limited). Com a assistência da análise SC, novas leis de escalabilidade conjungando capacidade e complexidade são apresentadas para a forma de onda OFDM e algumas de suas variantes. Em um estudo de caso, um mapeador óptimo para OFDM com modulação por índice (IM) é projetado, implementado e avaliado. O referido mapeador óptimo maximiza o ganho SE do OFDM-IM sobre o OFDM mas a complexidade resultante tem sido conjecturada como intratável pela literatura. Baseado na análise SC, a complexidade assimptótica exacta necessária para assegurar o ganho SE máximo foi demonstrada como linear (em vez de exponencial) no número de subportadoras. Em outro estudo de caso, verificou-se que a complexidade do algoritmo FFT faz com que o débito do OFDM tenda a zero a medida que o número de sub-portadoras N cresce. A limitação da FFT em que N deve crescer como uma potência de dois 2^i (i > 0) leva a uma complexidade exponencial em i a medida que a largura do espectro aumenta. De forma geral, é mostrado que o débito de formas de onda baseadas na FFT (e.g. OFDM) tende a zero a menos que a cota inferior do problema da transformada de Fourier de N pontos verifique-se como linear, exigindo-se, assim, algoritmos mais rápidos que a FFT, o que permanece uma questão em aberto da ciência da computação. Com o suporte da análise SC, um algoritmo é proposto a uma formulação alternativa em que uma transformada de N pontos é substituida por várias transformadas menores. Tal abordagem é empregada pela forma de onda OFDM vetorial (V-OFDM) a fim de mitigar a sobrecarga do prefixo cíclico do OFDM. Assim, o algoritmo proposto é uma alternativa à FFT no V-OFDM. Pelo relaxamento de N como potência de dois e com a parametrização do número de transformadas menores, verificou-se que a complexidade do algoritmo proposto cresce linearmente em N em vez de exponencialmente em i. Os estudos de casos apresentados ilustram como a análise SC pode conduzir projetistas de formas de onda rumo ao balanceamento óptimo entre a capacidade e a complexidade de sinais extremamente largos esperados nas redes sem fio do futuro.