Project topics and materials
Get Complete Project Material File(s) Now! »
On the suitability and applicability of the complexity measure and the complexity exponent
A reasonable question at this point would pertain as to why the computational resources Nmax scale with ρ and are dependent on r, to which we note that the complexity of decoding is generally dependent on the density and cardinality of the codebook, which in turn depends on ρ and r. Furthermore this dependence of the complexity exponent (and by extension of Nmax) on r, reflects a potential ability to regulate the computational resources depending on the rate.
In further arguing that the above representation is a natural one (rather than a forced one), we also quickly note that c(r) captures the entire complexity range 0 ≤ c(r) ≤ rT of all reasonable transceivers, with c(r) = 0 corresponding to the fastest possible transceiver (requiring a subexponential number of flops per T channel uses), and with c(r) = rT corresponding to the optimal but arguably slowest, full-search uninterrupted ML decoder 2.
Sphere decoder (SD)
The sphere decoding algorithm is a branch-and-bound search on a regular tree. In the settings of coherent delay-limited outage-limited MIMO channels, SD algorithm complexity fluctuates with the fading channel realizations. In the worst case the sphere decoder is in essence forced to perform a complete search over the entire codebook, and its complexity is same as that of the brute force ML decoder. In the presence of constraints on the computational reserves that may be allocated to decoding, the algorithm is faced with the prospect of encountering channel realizations that force it to violate its runtime constraints, thus having to declare decoding outages that inevitably increase the error probability. The decoder can regulate the computational costs and error performance with the proper selection of decoding policies specifying when to decode and when not to. If a small gap to the optimal error performance is acceptable then sphere decoder algorithms [2–7, 38–48] have been known to require reduced computational resources. These sphere decoding solutions can be employed to decode a linear code from real lattices (cf. [3–5]) or complex lattices (cf. [49]) and allow for efficient optimal or near optimal decoding of a large number of high rate space-time codes [4,7,41,47]. The detailed descriptions and most implementation issues of the SD algorithm are found in [2] and the semi-tutorial papers [3–5]. In order to introduce notations that will be required for the subsequent complexity analysis presented in the next chapters, we present important SD algorithm details.
Complexity for dynamically changing decoding order
In the previous section we established complexity requirements for the fixed decoding order implementation of SD. It turns out that for the fixed decoding order implementation, the complexity exponent meets the universal upper bound. A natural improvement can be a sphere decoder employing dynamically changing decoding orders. In this section we wish to quantify the advantages, if any, of using dynamically changing decoding order implementations. The results of analysis presented in this section establish that for any randomly picked lattice code (randomly and uniformly drawn from an ensemble of lattice designs), irrespective of the fixed or dynamically changing decoding order, the complexity exponent of the ML-based sphere decoder almost surely, in the choice of the lattice code, matches the upper bound derived in the previous section. For the analysis presented in this section we consider slightly restricted quasi-static MIMO model with i.i.d. Rayleigh fading statistics. Theorem 6. For the i.i.d. Rayleigh quasi-static MIMO channel, and irrespective of the fixed or dynamically changing decoding ordering policy, the complexity exponent of the ML-based sphere decoder almost surely, in the choice of the DMT optimal full-rate lattice code, matches the universal upper bound in Theorem 4. The proof for this theorem is given in Appendix 3D. At this point we want to clarify that Theorem 6 does not imply that dynamic decoding ordering policies can not reduce complexity exponent for any DMT optimal code. For any given specific DMT optimal code finding dynamically changing decoding orders that can guarantee reduction in the complexity exponent as compared to the universal upper bound in Theorem 4, remains a challenging open problem.
Table of contents :
Acknowledgements
Abstract
Résumé
Contents
List of Figures
Acronyms
Notations
1 Introduction
1.1 Multiple Antenna Systems : Error Performance and Complexity
1.2 Complexity characterization in outage-limited MIMO
1.2.1 Complexity Exponent
1.2.2 On the suitability and applicability of the complexity measure and the complexity exponent
1.2.3 Vanishing Gap
1.3 Dissertation Outline and main Contributions
2 Channel Model, Encoders and Decoders
2.1 Channel model
2.1.1 Quasi-static MIMO
2.1.2 MIMO-orthogonal frequency division multiplexing
2.1.3 MIMO-automatic repeat request (MIMO-ARQ)
2.2 Encoding
2.3 Decoding
2.3.1 Sphere decoder (SD)
2.3.2 Sphere Decoding Algorithm
Appendix 2A : Inter-symbol-interference (ISI) channel model
3 Complexity of Maximum Likelihood Decoding
3.1 Introduction
3.2 Complexity analysis ML-based sphere decoding
3.2.1 Complexity for vanishing gap to ML performance
3.2.2 Complexity for fixed decoding order
3.2.3 Quasi-static MIMO with fixed decoding order
3.2.4 Complexity for dynamically changing decoding order .
3.3 Reliability-Complexity Measure
3.4 Rate-Reliability-Complexity Tradeoff
3.4.1 Quasi-static MIMO channels
Appendix 3A : Proof of Theorem 4
Appendix 3B : Proof of Corollary 5b
Appendix 3C : Proof of Proposition 2
Appendix 3D : Proof of Theorem 6
Appendix 3E : Proof of Theorem 7
4 Complexity of Lattice Decoding
4.1 Introduction
4.1.1 Transition to lattice decoding for reducing complexity
4.2 Regularized Lattice Sphere Decoding
4.2.1 Lattice sphere decoding
4.2.2 Complexity of regularized lattice decoding
4.3 LR-aided Regularized Lattice Sphere Decoding
4.3.1 Complexity of LR-aided regularized lattice decoding .
4.3.2 Gap to the exact solution of regularized lattice decoding
Appendix 4A : Proof of Theorem 10
Appendix 4B : Proof of Corollary 10d
Appendix 4C : Proof of Lemma 2
Appendix 4D : Proof of Lemma 3
5 Feedback aided Complexity
5.1 Introduction and MIMO-ARQ signaling
5.1.1 Reliability and complexity implications of feedback : from DMT to the improved DMD
5.1.2 MIMO-ARQ signaling
5.2 Complexity reduction using ARQ feedback
5.2.1 Feedback reduction for asymmetric channels : nR ≤ nT
5.3 Complexity for harvesting the full rate-reliability benefits of feedback
5.3.1 Complexity costs for DMD optimality : the case of L > nT
5.4 Complexity reduction using antenna selection
5.5 Proof of Theorem 13
5.6 Proof of Theorem 14
5.7 Proof of Theorem 15 and Corollary 15a
5.8 Proof of Proposition 7
5.9 Proof of Proposition 8
Appendix 5A : Proof of Lemma 4
Appendix 5B : Proof of Lemma 5
6 Complexity Analysis for Multi-node Networks
6.1 Multiple Access Channel
6.2 Relay channels with orthogonal amplify-and-forward protocol (OAF)
6.3 Two-way relay channel (TRC)
6.3.1 Diversity-Multiplexing Tradeoff
6.3.2 Complexity Analysis
6.3.3 Reliability-Complexity Measure for HBC and TDBC
Protocols
Appendix 6A : Proof of Theorem 16
Appendix 6B : Proof of Proposition 10
Appendix 6C : Proof of Lemma 6
Appendix 6D : Proof of Theorem 17
Appendix 6E : Proof of Theorem 18
7 Conclusions and Future Work
8 French Summary
8.1 Systèmes à antennes multiples : performance en terme d’erreur de décodage et de complexité
8.2 Caractérisation de complexité en MIMO avec une outage-limitée158
8.2.1 Exponentiel de complexité
8.2.2 Pertinence et applicabilité de la mesure de complexité et l’exposant de la complexité
8.2.3 Vanishing écart
8.3 Contribution majeure et plan de thèse
