Description
Date depot: 1 janvier 1900
Titre: Rate-Reliability-Complexity limits in ML and lattice based decoding for MIMO, multiuser and cooperative communications
Directeur de thèse:
Petros ELIA (Eurecom)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
In telecommunications, error probability and encoding-decoding complexity are widely considered to be two limiting and interrelated bottlenecks. This thesis identifies the computational reserves required for the maximum likelihood (ML)-based decoding solutions that achieve, in the high-rate and high-SNR limit, a vanishing gap to the error-performance of the optimal brute force ML decoding. We also proceed to identify the general performance/complexity tradeoff for a broad family of lattice based decoders, as well as provide the first ever lattice decoding solution, and the corresponding activation policy that jointly achieve a vanishing gap to the exact implementation of (regularized) lattice decoding with complexity that is subexponential in the rate.
Our approach results in clear and concise characterization of the performance/complexity tradeoffs of different ML based and lattice based decoders, as well as simple answers to questions such as:
-* What is the complexity price to pay for near-optimal implementation of MIMO, multiuser and cooperative communications?
-* How does feedback reduce complexity?
-* What policies can regulate complexity at a limited performance loss?
-* How do complexity-constraints affect reliability in different MIMO settings?
-* How big of a MIMO system (how many transmit antennas or tones or relays or mac users) can your DSP chip sustain?
-* How should multiple users behave in the presence of complexity constraints?
-* What is the role of antenna selection in reducing complexity?
-* What are the cooperative protocols that perform best in the presence of computational constraints?
The derived reliability and complexity guarantees hold for most multiple-input multiple-output scenarios, all reasonable fading statistics, all channel dimensions and all-rate lattice codes. The adopted approach analytically refines transceiver DMT analysis which generally fails to address potentially massive gaps between theory and practice. The vanishing gap condition guarantees that the decoder's error curve is arbitrarily close, given a sufficiently high SNR, to the optimal error curve of exact solutions, which is a much stronger condition than DMT optimality which only guarantees an error gap that is subpolynomial in SNR, and can thus be unbounded and generally unacceptable for practical implementations.
The analysis also identifies a rate-reliability-complexity tradeoff for ML-based sphere decoding solutions, establishing concise expressions for the optimal diversity gain achievable in the presence of any run-time constraint imposed due to the absence of enough computational resources required to achieve a vanishing gap to ML performance. This tradeoff is of particular interest for the scenarios like software defined radios where computational reserves might vary with time and render it insufficient to achieve the vanishing performance gap.
Building on the results from ML-based sphere decoder complexity analysis, the work then presents novel encoding-decoding policies utilizing single bit of feedback to provide significantly improved rate-reliability-complexity tradeoff. Specifically, these polices with one bit of feedback and properly designed encoders-decoders achieve significant reductions in the computational reserves required to achieve the vanishing gap to the error performance of the optimal brute force ML decoding without feedback.
The applicability of the presented complexity analysis for the practical scenarios is illustrated through several examples like multiple access channels and cooperative networks (e.g. orthogonal amplify forward, decode-and-forward two-way relay channel).
The computational resources required by sphere decoding solutions to achieve a vanishing gap to ML solutions, albeit significantly smaller than those required by an exhaustive ML decoder, again grow exponentially in the rate and the dimensionality, and remain prohibitive for several MIMO scenarios. This high complexity required by ML-based decoding solutions serves as motivation to consider a natural alternative that is lattice decoding. In this work, we present first lattice decoding solution that achieves both a vanishing gap to the error-performance of the (DMT optimal) exact solution of preprocessed lattice decoding, as well as a computational complexity that is subexponential in the number of codeword bits. 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.
Doctorant.e: Singh Arun Kumar