Graduate School and Research Center in Digital Sciences

Rate-reliability-complexity tradeoff for ML and lattice decoding of full-rate codes

Singh, Arun; Elia, Petros; Jaldén, Joakim

ISIT 2013, IEEE International Symposium on Information Theory, 7-12 July 2013, Istanbul, Turkey

Recent work in [1]-[3] quantified, in the form of a complexity exponent, the computational resources required for ML and lattice sphere decoding to achieve a certain  diversity multiplexing performance. For a specific family of layered lattice designs, and a specific set of decoding orderings, this complexity was shown to be an exponential function in the number of codeword bits, and was shown to meet a universal upper bound on complexity exponents. The same results raised the question of whether complexity reductions away from the universal upper bound are feasible, for example, with a proper choice of decoder (ML vs lattice), or with a proper choice of lattice codes and decoding ordering policies. The current work addresses this question by first showing that for almost any full-rate DMT optimal lattice code, there exists no decoding ordering policy that can reduce the complexity exponent of ML or lattice based sphere decoding away from the universal upper bound, i.e., that a randomly picked lattice code (randomly and uniformly drawn from an ensemble of DMT optimal lattice designs) will almost surely be such that no decoding ordering policy can provide exponential complexity reductions away from the universal upper bound. As a byproduct of this, the current work proves the fact that ML and (MMSE-preprocessed) lattice decoding share the same complexity exponent for a very broad setting, which now includes almost any DMT optimal code (again randomly drawn) and all decoding order policies. Under a basic richness of codes assumption, this is in fact further extended to hold, with probability one, over all full-rate codes. Under the same assumption, the result allows for a meaningful ratereliability-complexity tradeoff that holds, almost surely in the random choice of the full-rate lattice design, and which holds irrespective of the decoding ordering policy. This tradeoff can be used to, for example, describe the optimal achievable diversity gain of ML or lattice sphere decoding in the presence of limited computational resources.

Document Doi Bibtex

Title:Rate-reliability-complexity tradeoff for ML and lattice decoding of full-rate codes
Department:Communication systems
Eurecom ref:4066
Copyright: © 2013 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+4066, doi = {}, year = {2013}, title = {{R}ate-reliability-complexity tradeoff for {ML} and lattice decoding of full-rate codes}, author = {{S}ingh, {A}run and {E}lia, {P}etros and {J}ald{\'e}n, {J}oakim}, booktitle = {{ISIT} 2013, {IEEE} {I}nternational {S}ymposium on {I}nformation {T}heory, 7-12 {J}uly 2013, {I}stanbul, {T}urkey }, address = {{I}stanbul, {TURKEY}}, month = {07}, url = {} }
See also: