Change search
ReferencesLink to record
Permanent link

Direct link
Rate-reliability-complexity tradeoff for ML and lattice decoding of full-rate codes
EURECOM, France.
EURECOM, France.
KTH, School of Electrical Engineering (EES), Signal Processing. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-6630-243X
2013 (English)In: 2013 IEEE International Symposium on Information Theory Proceedings (ISIT), 2013, 1267-1271 p.Conference paper (Refereed)
Abstract [en]

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 rate-reliability-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 sphe- e decoding in the presence of limited computational resources.

Place, publisher, year, edition, pages
2013. 1267-1271 p.
National Category
Research subject
URN: urn:nbn:se:kth:diva-136986DOI: 10.1109/ISIT.2013.6620430ScopusID: 2-s2.0-84890348737OAI: diva2:677652
ISIT 2013 IEEE International Symposium on Information Theory; Istanbul, Turkey, 7-12 July 2013

QC 20131210

Available from: 2013-12-10 Created: 2013-12-10 Last updated: 2013-12-10Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Jaldén, Joakim
By organisation
Signal ProcessingACCESS Linnaeus Centre

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link