Decoding by Embedding: Correct Decoding Radius and DMT Optimality

Laura Luzzi, Shuiyin Liu, Cong Ling and Damien Stehlé

Abstract: In lattice-coded multiple-input multiple-output (MIMO) systems, optimal decoding amounts to solving the closest vector problem (CVP). Embedding is a powerful technique for the approximate CVP, yet its remarkable performance is not well understood. In this paper, we analyze the embedding technique from a bounded distance decoding (BDD) viewpoint. We prove that the Lenstra, Lenstra and Lovász (LLL) algorithm can achieve 1/(2gamma) -BDD for gamma \approx O(2^(n/4)), yielding a polynomial-complexity decoding algorithm performing exponentially better than Babai's which achieves gamma = O(2^(n/2)). This substantially improves the existing result gamma = O(2^(n)) for embedding decoding. We also prove that BDD of the regularized lattice is optimal in terms of the diversity-multiplexing gain tradeoff (DMT).

Download: pdf.