Decoding by embedding: Correct decoding radius and DMT optimality

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. 1/(2γ)-BDD is referred to as a decoder that finds the closest vector when the noise norm is smaller than λ1/(2γ), where λ1 is the minimum distance of the lattice. We prove that the Lenstra, Lenstra and Lovász (LLL) algorithm can achieve 1/(2γ)-BDD for γ ≈ O(2n/4). This substantially improves the existing result γ = O(2n) for embedding decoding. We also prove that BDD of the regularized lattice is optimal in terms of the diversity-multiplexing gain tradeoff (DMT).