Rate - Reliability - Complexity limits in ML and Lattice based decoding for MIMO, multiuser and cooperative communications

Dans les télécommunications, le débit-fiabilité et la complexité de l’encodage et du décodage (opération à virgule flottante-flops) sont largement reconnus comme représentant des facteurs limitant interdépendants. Pour cette raison, tout tentative de réduire la complexité peut venir au prix d’une dégradation substantielle du taux d’erreurs. Cette thèse traite de l’établissement d’un compromis limite fondamental entre la fiabilité et la complexité dans des systèmes de communications « outage »-limités à entrées et sorties multiples (MIMO), et ses scénarios point-à-point, utilisateurs multiple, bidirectionnels, et aidés de feedback. Nous explorons un large sous-ensemble de la famille des méthodes d’encodage linéaire Lattice, et nous considérons deux familles principales de décodeurs : les décodeurs à maximum de vraisemblance (ML) et les décodeurs Lattice. L‘analyse algorithmique est concentrée sur l’implémentation de ces décodeurs ayant comme limitation une recherche bornée, ce qui inclue une large famille de sphère-décodeurs. En particulier, le travail présenté fournit une analyse à haut rapport Signal-à-Bruit (SNR) de la complexité minimum (flops ou taille de puce électronique) qui permet d’atteindre a) une certaine performance vis-à-vis du compromis diversité-gain de multiplexage et b) une différence tendant vers zéro avec le non-interrompu (optimale) ML décodeur, ou une différence tendant vers zéro comparé à l’implémentation exacte du décodeur (régularisé) Lattice. L’exposant de complexité obtenu décrit la vitesse asymptotique d’accroissement de la complexité, qui est exponentielle en terme du nombre de bits encodés.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