In telecommunications, rate-reliability and encoding-decoding computational complexity (floating point operations - flops), are widely considered to be limiting and interrelated bottlenecks. For this reason, any attempt to significantly reduce complexity may be at the expense of a substantial degradation in error-performance. Establishing this intertwined relationship constitutes an important research topic of substantial practical interest. This dissertation deals with the question of establishing fundamental rate, reliability and complexity limits in general outage-limited multiple-input multiple-output (MIMO) communications, and its related point-to-point, multiuser, cooperative, two-directional, and feedback-aided scenarios. We explore a large subset of the family of linear lattice encoding methods, and we consider the two main families of decoders; maximum likelihood (ML) based and lattice-based decoding. Algorithmic analysis focuses on the efficient bounded-search implementations of these decoders, including a large family of sphere decoders.
Specifically, the presented work provides high signal-to-noise (SNR) analysis of the minimum computational reserves (flops or chip size) that allow for a) a certain performance with respect to the diversity-multiplexing gain tradeoff (DMT) and for b) a vanishing gap to the uninterrupted (optimal) ML decoder or a vanishing gap to the exact implementation of (regularized) lattice decoding. The derived complexity exponent describes the asymptotic rate of exponential increase of complexity, exponential in the number of codeword bits. This complexity exponent, albeit much reduced compared to that of an exhaustive ML decoder, still reveals a very considerable complexity.
The above described exponential complexity tends to render such transceiver algorithms inapplicable to several MIMO scenarios. This served as motivation to explore other decoders, and to provide the first ever lattice decoding solution and halting policy, that jointly achieve a vanishing gap to the exact implementation of regularized lattice decoding with a complexity that is subexponential in the number of codeword bits as well as in the rate. This work was able to, for the first time, rigorously demonstrate and quantify the pivotal role of lattice reduction as a special complexity reducing ingredient in MIMO systems.
The work then addresses the fundamental question of establishing the rate-reliability-complexity ramifications of feedback. This setting is very important because it can offer near ergodic behavior (high diversity), even at high multiplexing gains. We focus on two fundamental questions. The first question asks what is the complexity savings that feedback provides for a given fixed rate-reliability performance, and the second question asks what is the complexity costs of achieving the full rate-reliability benefits of feedback. The analysis and the constructed feedback schemes tell us how to properly utilize a finite number of feedback bits to alleviate the adverse effects of computational constraints, as those seen in the derived rate-reliability-complexity tradeoffs of the previous chapters.
Finally we present preliminary work on extending the rate-reliability-complexity analysis to simple instances of the multiple access, relay, and bidirectional channels, where again we identify the computational reserves that guarantee a DMT optimality, as well as address user/relay selection criteria and communication protocols that provide improved joint reliability-complexity performance in the presence of computational constraints.
