Member, IEEE Laura Luzzi

Damien Stehlé

Member, IEEE Cong Ling

Decoding by Embedding: Correct Decoding Radius and DMT Optimality

Keywords: closest vector problem, lattice decoding, lattice reduction, MIMO systems, shortest vector problem

The closest vector problem (CVP) and shortest (nonzero) vector problem (SVP) are the core algorithmic problems on Euclidean lattices. They are central to the applications of lattices in many problems of communications and cryptography. Kannan's embedding technique is a powerful technique for solving the approximate CVP, yet its remarkable practical performance is not well understood. In this paper, the embedding technique is analyzed from a bounded distance decoding (BDD) viewpoint. We present two complementary analyses of the embedding technique: We establish a reduction from BDD to Hermite SVP (via unique SVP), which can be used along with any Hermite SVP solver (including, among others, the Lenstra, Lenstra and Lovász (LLL) algorithm), and show that, in the special case of LLL, it performs at least as well as Babai's nearest plane algorithm (LLL-aided SIC). The former analysis helps to explain the folklore practical observation that unique SVP is easier than standard approximate SVP. It is proven that when the LLL algorithm is employed, the embedding technique can solve the CVP provided that the noise norm is smaller than a decoding radius λ1/(2γ), where λ1 is the minimum distance of the lattice, and γ ≈ O(2 n/4 ). This substantially improves the previously best known correct decoding bound γ ≈ O(2 n ). Focusing on the applications of BDD to decoding of multiple-input multiple-output (MIMO) systems, we also prove that BDD of the regularized lattice is optimal in terms of the diversity-multiplexing gain tradeoff (DMT), and propose practical variants of embedding decoding which require no knowledge of the minimum distance of the lattice and/or further improve the error performance.

I. INTRODUCTION

Lattice decoding for the linear multiple-input multipleoutput (MIMO) channel is a problem of high relevance in multi-antenna, broadcast, multi-access, cooperative and other multi-terminal communication systems [START_REF] Mow | Maximum likelihood sequence estimation from the lattice viewpoint[END_REF][START_REF] Damen | On maximum likelihood detection and the search for the closest lattice point[END_REF][START_REF] Agrell | Closest point search in lattices[END_REF]. Maximumlikelihood (ML) decoding for finite constellations carved from This work was supported in part by a Royal Society-CNRS international joint project and by a Marie Curie Fellowship (FP7/2007-2013, grant agreement PIEF-GA-2010-274765). This work was presented in part at the IEEE International Symposium on Information Theory (ISIT 2011), Saint Petersburg, Russia.

L. Luzzi was with the Department of Electrical and Electronic Engineering, Imperial College London, London SW7 2AZ, United Kingdom. She is now with Laboratoire ETIS (ENSEA -Université de Cergy-Pontoise -CNRS), 6 Avenue du Ponceau, 95014 Cergy-Pontoise, France (e-mail: laura.luzzi@ensea.fr). D. Stehlé is with ENS de Lyon, Laboratoire LIP (U. Lyon, CNRS, ENS de Lyon, INRIA, UCBL), 46 Allée d'Italie, 69364 Lyon Cedex 07, France (e-mail: damien.stehle@ens-lyon.fr).

C. Ling is with the Department of Electrical and Electronic Engineering, Imperial College London, London SW7 2AZ, United Kingdom (e-mail: cling@ieee.org). lattices can be realized efficiently by sphere decoding [START_REF] Viterbo | A universal lattice code decoder for fading channels[END_REF], whose complexity can however grow prohibitively with the dimension n [START_REF] Jalden | On the complexity of sphere decoding in digital communications[END_REF]. The decoding complexity is especially high in the case of coded or distributed systems, where the lattice dimension is usually larger [START_REF] Oggier | Perfect space time block codes[END_REF][START_REF] Yang | Optimal space-time codes for the MIMO amplify-and-forward cooperative channel[END_REF]. Thus, the practical implementation of decoders often has to resort to approximate solutions, which mostly fall under two main strategies. The first is to reduce the complexity of sphere decoding, notably by pruning [START_REF] Schnorr | Lattice basis reduction: Improved practical algorithms and solving subset sum problems[END_REF]. Another approach, which we investigate in the present paper, is lattice reduction (LR)-aided decoding [START_REF] Wubben | Lattice reduction: A survey with applications in wireless communications[END_REF], which was used earlier by Babai in [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF] and in essence applies zero-forcing (ZF), successive interference cancellation (SIC) or other suboptimal receivers to a reduced basis of the lattice. It was shown in [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF] that regularized lattice-reduction aided decoding can achieve the optimal diversity and multiplexing tradeoff (DMT) in MIMO fading channels. The proximity factors that measure the gap between lattice-reduction-aided decoding and (infinite) lattice decoding were derived in [START_REF] Ling | On the proximity factors of lattice reduction-aided decoding[END_REF]. Thanks to its average polynomial complexity [START_REF] Daudé | An upper bound on the average number of iterations of the LLL algoirthm[END_REF][START_REF] Ling | Effective LLL reduction for lattice decoding[END_REF][START_REF] Jaldén | Worst-and average-case complexity of LLL lattice reduction in MIMO wireless systems[END_REF], the Lenstra, Lenstra and Lovász (LLL) reduction [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] is widely used in lattice decoding.

However, the analysis in [START_REF] Ling | On the proximity factors of lattice reduction-aided decoding[END_REF] revealed that lattice-reductionaided decoding exhibits a widening gap to (infinite) lattice decoding, so there is a strong demand for computationally efficient suboptimal decoding algorithms that offer improved performance. Several such approaches are emerging, including sampling [START_REF] Liu | Decoding by sampling: A randomized lattice algorithm for bounded-distance decoding[END_REF] and embedding [START_REF] Luzzi | Augmented lattice reduction for MIMO decoding[END_REF]. It was shown in [START_REF] Liu | Decoding by sampling: A randomized lattice algorithm for bounded-distance decoding[END_REF] that the sampling technique can provide a constant improvement to the best known upper bound for the signal-to-noise ratio (SNR) gain with polynomial complexity.

Embedding decoding is especially appealing due to its excellent performance and polynomial complexity (if polynomial-complexity lattice reduction algorithms such as LLL reduction are used). The core of the embedding technique is to embed an n-dimensional lattice and the received vector into an (n + 1)-dimensional lattice. By this means, an ndimensional instance of the closest vector problem (CVP) is converted into an (n + 1)-dimensional instance of the shortest (nonzero) vector problem (SVP). The receiver extracts the transmitted vector from a reduced basis of the extended lattice.

An "improved lattice reduction" technique that resembles embedding was used for MIMO decoding in [START_REF] Kim | Improved lattice reduction aided detections for MIMO systems[END_REF], but it is in fact equivalent to LLL-aided SIC. It was recognized in [START_REF] Luzzi | Augmented lattice reduction for MIMO decoding[END_REF] that the performance of the embedding technique could be significantly improved by carefully choosing the embedding parameter, leading to "augmented lattice reduction" (ALR). In particular, it was shown [START_REF] Luzzi | Augmented lattice reduction for MIMO decoding[END_REF] that the LLL algorithm can recover the transmitted vector when the noise norm is small compared to the minimum distance λ 1 of the lattice. This condition corresponds to a variant of the CVP known as Bounded Distance Decoding (BDD). More precisely, η-BDD (with η ≤ 1/2) is a special instance of the CVP where the noise norm (or, equivalently, the distance from the target vector to the lattice) is less than R = η • λ 1 . The radius R is referred to as the (correct) decoding radius of the algorithm. BDD instances appear both in coding and in cryptography. In coding theory, BDD is a suboptimal decoding strategy that enjoys lower complexity compared to ML decoding. For specific algebraic codes and for specific lattice codes, there are numerous BDD algorithms that achieve optimal η = 1/2 in polynomial-time [START_REF] Chase | A class of algorithms for decoding block codes with channel measurement information[END_REF][START_REF] Forney | Generalized minimum-distance decoding for Euclidean-space codes and lattices[END_REF][START_REF] Micciancio | Efficient bounded distance decoders for Barnes-Wall lattices[END_REF]. On the other hand, for general lattices, polynomial complexity algorithms only solve η-BDD for much smaller values of η. The main general-purpose approaches include: Babai's ZF [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF]; Babai's SIC [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF]; and the randomized extensions by Klein [START_REF] Klein | Finding the closest lattice vector when it's unusually close[END_REF], Lindner and Peikert [START_REF] Lindner | Better key sizes (and attacks) for LWE-based encryption[END_REF], and Liu et al. [START_REF] Liu | On bounded distance decoding for general lattices[END_REF].

In cryptography, the observed hardness of BDD has been used as a constructive tool. The so-called Learning With Errors (LWE) problem [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] (see also the survey [START_REF]The learning with errors problem[END_REF]) can be interpreted as a variant of BDD where the lattice is chosen uniformly in a specific family of lattices and the noise vector follows a Gaussian distribution with small standard deviation. The apparent hardness of LWE in high dimensions has been exploited to devise a number of cryptographic protocols, including encryption [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], identification [START_REF] Kiltz | Efficient authentication from hard learning problems[END_REF] and signature schemes [START_REF] Lyubashevsky | Lattice signatures without trapdoors[END_REF].

The embedding technique is a powerful approach to BDD for general lattices. Kannan seems to have been the first to propose this technique [START_REF] Kannan | Minkowski's convex body theorem and integer programming[END_REF]. Since then, Micciancio has used it to reduce the CVP to the SVP to prove certain hardness results [START_REF] Micciancio | Complexity of Lattice Problems: A Cryptographic Perspective[END_REF], while Nguyen has employed it to break the GGH cryptosystem for parameters of practical interest [START_REF] Nguyen | Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from crypto '97[END_REF]. More recently, in the context of cryptography, Lyubashevsky and Micciancio revealed a relationship between BDD and variants of SVP [START_REF] Lyubashevsky | On bounded distance decoding, unique shortest vectors, and the minimum distance problem[END_REF]. Of particular relevance to this paper is the relationship between BDD and unique SVP (uSVP), a special instance of SVP for lattices whose second minimum is at least γ times longer than the first minimum. It was shown in [START_REF] Lyubashevsky | On bounded distance decoding, unique shortest vectors, and the minimum distance problem[END_REF] that 1/(2γ)-BDD can be reduced to γ-uSVP. This relation suggests the following strategy, already used in [START_REF] Luzzi | Augmented lattice reduction for MIMO decoding[END_REF]: the embedding parameter should be chosen in such a way that the extended lattice exhibits an exponential gap between the first and second minimum, ensuring that LLL-reducing the extended lattice basis successfully solves the uSVP instance.

Contributions: Our contributions are twofold: We improve the theoretical analysis of the embedding technique, and we consider questions raised by the specific application of BDD and embedding to communications.

On the analysis front, we prove that embedding decoding using the LLL algorithm can solve 1/ (2γ)-BDD for γ ≈ O( √ n2 n 4 ). This is significantly better than the bound γ = O(2 n ) proven in [START_REF] Luzzi | Augmented lattice reduction for MIMO decoding[END_REF]. We propose two complementary proofs for this result. In the first approach, we establish a reduction from the unique SVP to the Hermite SVP, which consists in finding a non-zero vector of a given lattice, of small norm relative to the root determinant. This analysis can be specialized to LLL by showing that the LLL algorithm can solve γ-uSVP for γ ≈ O(2 n 4 ). This is stronger than the commonly used bound γ = O(2 n 2 ) in literature, which in fact pertains to approximate SVP. The second approach consists in showing Babai's SIC achieves this correct decoding radius (by improving the bound in [START_REF] Ling | On the proximity factors of lattice reduction-aided decoding[END_REF]) and then proving that Kannan's embedding with LLL performs at least as well as Babai's SIC. For the latter component of this proof, we proceed by explicitly following the steps performed by Kannan's embedding. The two proofs are of independent interest. The first is not restricted to LLL but is suited to any algorithm solving the Hermite SVP, while the second provides a precise description of how the embedding technique works.

The reduction from the unique SVP to the Hermite SVP helps to explain the long-standing problem why unique SVP is easier than standard approximate SVP. It has been known that uSVP is potentially easier, and there has been experimental evidence that this is indeed the case in practice [START_REF] Gama | Predicting lattice reduction[END_REF]. However, no theoretic justification has been given before.

On the MIMO communications front, we prove that BDD of the regularized lattice is DMT-optimal over Rayleigh fading channels. This represents a nontrivial extension of the analysis in [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF] for γ-approximation algorithms of CVP. Indeed, it will be shown that γ-approximate algorithms are a special case of BDD, because any decoding technique which provides a γapproximate CVP solution is also able to solve 1/(2γ)-BDD. However, the converse is not necessarily true. In addition to embedding decoding, this result allows us to establish the DMT optimality of other BDD algorithms, such as lattice reduction-aided decoding and sampling decoding.

For practical purposes, we consider the problem of choosing the main parameter involved in Kannan's embedding method, which we refer to as the embedding parameter. We give an alternative embedding parameter that only assumes the knowledge of λ 1 while achieving the same decoding radius as [START_REF] Lyubashevsky | On bounded distance decoding, unique shortest vectors, and the minimum distance problem[END_REF]. We also consider the case when λ 1 is not known, and show that using multiple calls to this embedding decoder with an estimate of λ 1 achieves essentially the same decoding radius as if λ 1 were known. On the experimental side, we propose variants of the embedding technique without knowledge of λ 1 and/or with improved performance and compare them with state-of-the-art MIMO decoding techniques by numerical simulations in terms of error performance and complexity, showing that embedding is nearly optimal in many practical scenarios.

The paper is organized as follows: Section II presents the transmission model and a short survey of lattice problems. The DMT analysis on BDD is given in Section III. In Section IV, we give the two analyses of the decoding radius of the embedding technique for solving BDD. In Section V, variants of the embedding decoder are presented. Section VI evaluates the performance by computer simulation. Some concluding remarks are offered in Section VII.

Notation: Matrices and column vectors are denoted by upper and lowercase boldface letters, and the transpose, in-verse, pseudoinverse of a matrix B by B T , B -1 , and B † , respectively. I n is the identity matrix of size n. We let b i , b i,j and b i respectively denote the i-th column of matrix B, the entry in the i-th row and j-th column of B, and the i-th entry in vector b. Vec(B) stands for the column-bycolumn vectorization of the matrix B. The inner product in the Euclidean space between vectors u and v is defined as u, v = u T v, and the Euclidean norm u = u, u . Kronecker product of matrix A and B is written as A ⊗ B. If x is a real number, we let ⌈x⌋ denote its rounding to a closest integer. The ℜ and ℑ prefixes denote the real and imaginary parts. We use the standard asymptotic notation

f (x) = O (g (x)) when lim sup x→∞ |f (x)/g(x)| < ∞.

II. LATTICE PROBLEMS IN MIMO DECODING A. System Model

Consider an n T × n R flat-fading MIMO system model consisting of n T transmitters and n R receivers

Y = HX + N, (1)
where X ∈ C nT ×T , Y, N ∈ C nR×T of block length T denote the channel input, output and noise, respectively, and H ∈ C nR×nT is the n R × n T full-rank channel gain matrix with n R ≥ n T , whose entries are normalized to unit variance. The entries of N are i.i.d. complex Gaussian with variance σ 2 each. The codewords X satisfy the average power constraint

E[ X 2 F /T ] = 1.
Hence, the signal-to-noise ratio (SNR) at each receive antenna is 1/σ 2 . When a lattice space-time block code is employed, the QAM information vector x is multiplied by the generator matrix G of the encoding lattice. The n T × T codeword matrix X is defined by column-wise stacking of consecutive n T -tuples of the vector s = Gx ∈ C nT T . By column-bycolumn vectorization of the matrices Y and N in (1), i.e., y = Vec(Y) and n = Vec(N), the received signal at the destination can be expressed as

y = (I T ⊗ H) Gx + n. (2)
When T = 1 and G = I nT , equation ( 2) reduces to the model for uncoded MIMO communication y = Hx + n. Furthermore, by separating real and imaginary parts, we obtain the equivalent 2n T × 2n R real-valued model

ℜy ℑy = ℜH -ℑH ℑH ℜH ℜx ℑx + ℜn ℑn . (3)
An equivalent 2n T T ×2n R T real model for coded MIMO can also be obtained in a similar way.

The QAM constellations C can be interpreted as the shifted and scaled version of a finite subset A nT of the integer lattice Z nT , i.e., C = a(A nT + [1/2, ..., 1/2] T ), where the factor a arises from energy normalization. For example, we have

A nT = {- √ M /2, ..., √ M /2 -1}
for M-QAM signalling. Therefore, with scaling and shifting, we consider the generic n×m (with m ≥ n) real-valued MIMO system model

y = Bx + n, (4)
where B ∈ R m×n , given by the real-valued equivalent of (I T ⊗ H) G, can be interpreted as the basis matrix of the decoding lattice. We have n = 2n T T and m = 2n R T . The data vector x thus belongs to a finite subset A n ⊂ Z n which satisfies the average power constraint.

The maximum-likelihood (ML) decoder computes

x = arg min x∈A n y -Bx 2 . (5)
The ML solution (5) can be found using the sphere decoding algorithm, whose complexity, however, grows exponentially with n [START_REF] Jalden | On the complexity of sphere decoding in digital communications[END_REF].

A suboptimal alternative technique called naive lattice decoding (or simply lattice decoding) consists in relaxing the constraint due to the signal constellation as follows:

x = arg min x∈Z n y -Bx 2 .
A low-complexity approximation of lattice decoding is successive interference cancellation (SIC), also known as Babai's nearest plane algorithm [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF]. It consists in performing the QR decomposition B = QR, where Q has orthonormal columns and R is an upper triangular matrix with nonnegative diagonal elements [START_REF] Horn | Matrix Analysis[END_REF]. Multiplying (4) on the left by Q † , we have

y ′ = Q † y = Rx + n ′ . (6)
An estimate of x is then found by component-wise backsubstitution and rounding:

xn = y ′ n r n,n , xi = y ′ i - n j=i+1 r i,j xj r i,i , i = n -1, . . . , 1.

B. Lattice Basics

We refer the reader to [START_REF] Gruber | Geometry of Numbers[END_REF][START_REF] Cassels | An Introduction to the Geometry of Numbers[END_REF] for thorough introductions to Euclidean lattices. An n-dimensional lattice in the mdimensional Euclidean space R m (n ≤ m) is the set of integer linear combinations of n linearly independent vectors b

1 , . . . , b n ∈ R m : L= n i=1 x i b i |x i ∈ Z, i = 1, . . . n . The matrix B = [b 1 • • • b n ] is referred to as a basis of the lat- tice L = L(B). In matrix form, we have L = {Bx|x ∈ Z n }.
The dual lattice L * is defined as the set of those vectors u, such that the inner product u, v belongs to Z, for all v ∈ L. The dual basis of B, which is a basis of the dual lattice L * , is given by B * (B † ) T J, where J is the column-reversing matrix. If R and R * respectively denote the R-factors of the QR-decomposition of B and B * , then we have r i,i = 1/r * n-i+1,n-i+1 for all i [START_REF] Lagarias | Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice[END_REF]. The determinant det L det(B T B) is independent of the choice of the basis. A shortest vector of a lattice L is a non-zero vector in L with the smallest Euclidean norm. The norm of any shortest vector of L, often referred to as the minimum distance, is denoted by λ 1 (L) or λ 1 (B) when a basis B is given. We also let it be denoted by λ 1 if there is no ambiguity concerning the lattice. The Hermite constant is defined as

γ n sup L λ 2 1 (L) det 2/n L , (7)
where the supremum is taken over all lattices of dimension n.

There is currently no proof that γ n is an increasing function of n, although this is very likely to be the case and all known bounds on γ n are increasing. For the sake of convenience, we define γ n max n i=1 γ i . By Minkowski's theorem [START_REF] Minkowski | Geometrie der Zahlen[END_REF], we have the bound γ n ≤ n and accordingly γ n ≤ n.

Let B (0,r) denote the closed ball of radius r centered at 0. The notion of minimum distance can be generalized, by defining the i-th successive minimum λ i (L) (or λ i if there is no ambiguity on the lattice) as the smallest radius r such that B (0,r) contains at least i linearly independent lattice points. If λ 2 > γλ 1 (with γ > 1), we say that the shortest vector in the lattice is γ-unique.

For any point y ∈R m , the distance of y to the lattice L is denoted by dist(y, B) = min x∈Z n y -Bx .

C. Lattice Problems

We now give precise definitions of the lattice problems that are central to this work. In all these problems, the input lattice L is described by an arbitrary basis B.

• Closest Vector Problem (CVP):

Given a lattice L and a vector y ∈ R m , find a vector Bx ∈ L such that y -Bx is minimal.

• γ-Approximate CVP (γ-CVP), with γ ≥ 1: Given a lattice L and a vector y ∈ R m , find a vector Bx ∈ L such that y -Bx ≤ γdist(y, B).

• η-Bounded Distance Decoding (η-BDD) with η ≤ 1/2: Given a lattice L and a vector y such that dist(y, B) < ηλ 1 , find the lattice vector Bx ∈ L (B) closest to y.

• Shortest Vector Problem (SVP):

Given a lattice L, find a vector v ∈ L of norm λ 1 .

• γ-Approximate SVP (γ-SVP), with γ ≥ 1:

Given a lattice L, find a vector v ∈ L such that 0 < v ≤ γλ 1 . • Hermite SVP (C-HSVP), with C ≥ 1: Given a lattice L, find a vector v ∈ L such that 0 < v ≤ C det 1/n (L). • γ-unique SVP (γ-uSVP), with γ ≥ 1: Given a lattice L such that λ 2 (L) > γλ 1 (L), find a vector v ∈ L of norm λ 1 .

D. LLL Reduction

A lattice of dimension n ≥ 2 has infinitely many bases. In general, if B is a full column rank matrix, then every matrix B = BU is also a basis of L (B), when U is a unimodular matrix, i.e., det(U) = ±1 and all elements of U are integers. The aim of lattice reduction is to find a "good" basis for a given lattice. The celebrated LLL algorithm [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] was the first polynomial-time algorithm that computes a vector not much longer than the shortest nonzero vector.

For the sake of simplicity of notation, in this paper we consider the version of the LLL algorithm based on the QR decomposition [START_REF] Wuebben | Near-maximum-likelihood detection of MIMO systems using MMSE-based lattice reduction[END_REF] B = QR. Let q i be the columns of Q, and r i,j be the elements of R. Note that r 1,1 = b 1 .

The basis B is called LLL-reduced if

|r j,i | ≤ 1 2 |r j,j | (8)
for 1 ≤ j < i ≤ n, and

δr 2 i-1,i-1 ≤ r 2 i,i + r 2 i-1,i (9)
for 1 < i ≤ n, where 1/4 < δ ≤ 1 is a factor selected to achieve a good quality-complexity tradeoff.

Let α = 1/ (δ -1/4). From Equations ( 8) and ( 9), an LLLreduced basis satisfies the following property:

r 2 i,i ≥ α -1 r 2 i-1,i-1 , i = 2, . . . , n. (10)
The latter implies the following bounds (see [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF]):

b 1 ≤ α (n-1)/4 det 1/n L, (11) b 1 ≤ α (n-1)/2 λ 1 . (12)
Equation ( 11) means that LLL solves C-HSVP with C = α (n-1)/4 , whereas Equation ( 12) implies that LLL solves both γ-SVP and γ-uSVP for γ = α (n-1)/2 . Remark 1: As this is the historical choice of [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF] and as it simplifies [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF], [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF] and [START_REF] Ling | On the proximity factors of lattice reduction-aided decoding[END_REF], one often sets δ = 3/4 and consequently α = 2.

Remark 2: The complex LLL algorithm from [START_REF] Gan | Complex lattice reduction algorithm for low-complexity full-diversity MIMO detection[END_REF] handles a complex-valued lattice directly (without expanding it into a real-valued lattice). It delivers a similar quality guarantee with α = 1/ (δ -1/2). The results of the present work can be readily extended to complex LLL.

E. Lattice Reduction-Aided Decoding

In order to improve the performance of conventional decoders (ZF or SIC), lattice reduction can be used to preprocess the channel matrix B. Since the reduced channel matrix is much more likely to be well-conditioned, the effect of noise amplification upon inverting the system will be moderated. The channel model ( 4) can be rewritten as

y = BU -1 x + n = Bx ′ + n, x ′ = U -1 x, (13)
where B = BU and U is an unimodular matrix. The ZF or SIC estimate x′ for the equivalent channel ( 13) is then transformed back into x = Ux ′ . As the resulting estimate x is not necessarily in A n , remapping of x onto the finite lattice A n is required. The correct decoding radius of SIC is given by [START_REF] Ling | On the proximity factors of lattice reduction-aided decoding[END_REF] R SIC = 1 2 min

1≤i≤n |r i,i | , (14)
which means that correct decoding is guaranteed if n ≤ R SIC . Note that this bound is tight. If the basis is LLL-reduced, the gap between min |r i,i | and λ 1 is bounded. Therefore, Babai's nearest plane algorithm [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF], or LLL-SIC, can be viewed as a basic BDD solver. By using [START_REF] Babai | On Lovász' lattice reduction and the nearest lattice point problem[END_REF] and the fact that b 1 ≥ λ 1 , it can be proved that LLL-SIC solves η-BDD for η = 1 2 α -(n-1)/2 (see [START_REF] Ling | On the proximity factors of lattice reduction-aided decoding[END_REF]). Consequently, the decoding radius of LLL-SIC is bounded as follows:

R LLL-SIC ≥ 1 2α (n-1)/2 λ 1 . (15)
F. Improved bound on the decoding radius of LLL-SIC

Here, we derive an improved bound on the decoding radius, which is better than [START_REF] Jaldén | Worst-and average-case complexity of LLL lattice reduction in MIMO wireless systems[END_REF]. To the best of our knowledge, this is a new result of independent interest.

Lemma 1: The decoding radius of LLL-SIC satisfies

R LLL-SIC ≥ 1 2 √ γ n α (n-1)/4 λ 1 ≥ 1 2 √ nα (n-1)/4 λ 1 . (16)
Proof: Suppose the basis B is LLL-reduced. Let B = QR denote its QR-decomposition. By using ( 7) and ( 10), we obtain

λ 1 ≤ √ γ k (det L[b 1 , • • • , b k ]) 1/k = √ γ k k i=1 r i,i 1/k ≤ √ γ k r k,k k-1 i=1 α (k-i)/2 1/k = √ γ k α (k-1)/4 r k,k . (17)
Now, by using [START_REF] Ling | Effective LLL reduction for lattice decoding[END_REF] and the above, we have

R LLL-SIC = 1 2 min 1≤k≤n {r k,k } ≥ min 1≤k≤n 1 2 √ γ k α (k-1)/4 λ 1 ≥ 1 2 √ γ n α (n-1)/4 λ 1 . (18)
This completes the proof.

III. DMT ANALYSIS OF BDD

In this section we will prove that any decoding technique for MIMO systems which provides a solution to η-BDD for some constant η is optimal from the point of view of the diversitymultiplexing gain tradeoff or DMT [START_REF] Zheng | Diversity and multiplexing: A fundamental tradeoff in multiple antenna channels[END_REF], when a suitable left preprocessing is employed.

In the present discussion, we suppose for the sake of simplicity that m = n. Following the notation in [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF], we consider the equivalent normalized channel model where the noise variance is equal to 1:

y ′ = B ′ x + n ′ , where B ′ = √ ρB, n ′ i = √ ρn i ∼ N (0, 1), ∀i = 1, . . . , n. Here ρ = 1
σ 2 denotes the SNR. Moreover, we consider the equivalent regularized system

y 1 = Rx + n 1 , (19)
where

B ′ I n = QR, y 1 = Q † y ′ 0 n×1 .
From the point of view of receiver architecture, this amounts to performing left preprocessing before decoding, by using a maximum mean square error generalized decision-feedback equalizer (MMSE-GDFE) [START_REF] Damen | MMSE-GDFE lattice decoding for solving under-determined linear systems with integer unknowns[END_REF]. Note that I n may be replaced with any positive definite matrix T without hurting DMT optimality.

In [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF], it was shown that when finite constellations are used, naive lattice decoding of the regularized system [START_REF] Kim | Improved lattice reduction aided detections for MIMO systems[END_REF] without taking the constellation bounds into account is DMToptimal. Moreover, it was proven that any decoding technique that always provides a solution to γ-CVP in the regularized lattice for some γ is also DMT-optimal. Since LLL-SIC and LLL-ZF decoding applied to the regularized system turn out to solve γ-CVP, this means that MMSE-GDFE preprocessing followed by lattice-reduction aided decoding is also DMToptimal.

It is easy to see that any decoding technique which provides a γ-CVP solution x to ( 19) is also able to solve 1 2γ -BDD. In fact, suppose that y 1 is such that dist(y 1 , R) < 1 2γ λ 1 (R). Then the γ-CVP solution x satisfies

y 1 -Rx <γ min x∈Z n y 1 -Rx = γdist(y 1 , R) < λ 1 (R) 2 ,
so that x is the optimal solution of ( 19). However, the converse is apparently not true, that is, BDD does not necessarily provide γ-CVP solutions for all y 1 . Therefore, the analysis in [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF] does not extend in a straightforward manner to BDD of the regularized lattice. Nevertheless, we can show that DMT-optimality holds for all instances of BDD, and not only for γ-CVP, by following the same reasoning of the original proof in [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF].

Theorem 1: For any constant η > 0, any decoding technique which always provides a solution for the regularized η-BDD is DMT-optimal.

Proof: Let d ML (r) be the optimal diversity gain corresponding to a multiplexing gain r ∈ {0, . . . , min(n T , n R )}. Using the same notation as [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF], we consider the constellation Λ r ∩ R, where the lattice Λ r = ρ -rT n Z n is scaled according to the SNR, and R is a fixed shaping region. Let B ⊂ R be a ball of fixed radius R, where R is chosen in such a way that

d 1 + d 2 ∈ R, ∀d 1 , d 2 ∈ B. Let ν r = min d∈B∩Λr d =0 1 4 B ′ d 2 .
Then Lemma 1 of [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF] holds, that is lim sup

ρ→∞ log P {ν r ≤ 1} log ρ ≤ -d ML (r).
Let ζ > 0 and choose θ such that 2ζT n > θ > 0. We have Λ r = ρ ζT n Λ r+ζ . As in the original proof, there exists ρ 1 such that for any ρ ≥ ρ 1 , we have R ⊆ 1 2 ρ ζT n B. As in Theorem 1 from [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF], we want to show that the conditions

ν r+ζ ≥ 1, n ′ 2 ≤ ρ θ ( 20
)
are sufficient for the regularized η-BDD solver to decode correctly for sufficiently large SNR. First of all, we establish a lower bound for the minimum squared norm

d 2 R = min x∈Λr\{0} 1 4 Rx 2 = min x∈Λr\{0} 1 4 B ′ x 2 + x 2 .
as follows. Let ϕ(x) = B ′ x 2 + x 2 . Let x ∈ Λ r \ {0} be any lattice point.

• If x / ∈ 1 2 ρ ζT n B, then ϕ(x) ≥ x 2 > 1 4 R 2 ρ 2ζT n . • If x ∈ 1 2 ρ ζT n B ∩ Λ r = 1 2 ρ ζT n B ∩ ρ ζT n Λ r+ζ , then xρ -ζT n ∈ 1 2 B ∩ Λ r+ζ and so 1 4 B ′ xρ -ζT n 2
≥ 1 since by the hypothesis (20), we have ν r+ζ ≥ 1. Therefore we obtain ϕ(x)

≥ B ′ x 2 ≥ 4ρ 2ζT n . In conclusion, there exists k > 0 such that d 2 R ≥ kρ 2ζT n . Now consider the transmitted codeword x ∈ Λ r ∩ R.
The regularized η-BDD decoder is able to decode correctly provided that y 1 -Rx < ηd R . We have

y 1 -Rx 2 = y ′ -B ′ x 2 + x 2 = n ′ 2 + x 2 ≤ ρ θ +c,
where c = max r∈R r 2 is a constant. Therefore under the conditions (20), the regularized η-BDD decoder is able to decode correctly provided that ρ θ + c < ηkρ

2ζT n . But θ < 2ζT
n , so there exists ρ such that for any ρ ≥ ρ, we have ρ θ + c < ηkρ 2ζT n . Then as in Theorem 1 from [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF] we can conclude that

P {x η-BDD = x} ≤ P {ν r+ζ < 1} + P { n ′ 2 > ρ θ }.
The second term is negligible for ρ → ∞. So we can say, similarly to the original proof, that lim sup

ρ→∞ log P {x η-BDD = x} log ρ ≤ -d ML (r + ζ)
and then use the right continuity of d ML (r).

IV. DECODING RADIUS OF EMBEDDING

In this section we will review Kannan's embedding technique [START_REF] Kannan | Minkowski's convex body theorem and integer programming[END_REF], show that it provides a BDD-solver, and analyze its decoding radius.

The principle of this technique is to embed the basis matrix B and the received vector y into a higher dimensional lattice. More precisely, we consider the following (m + 1) × (n + 1) basis matrix:

B = B -y 0 1×n t ( 21
)
where t > 0 is a parameter to be determined, which we refer to as the embedding parameter. The strategy is to reduce CVP to SVP in the following way. For a suitable choice of t and for sufficiently small noise norm, the vectors ±v with v = [(Bxy) T t] T are the shortest vectors in the lattice L( B).

Thus an SVP algorithm will find v, and the message x can be recovered from the coordinates of this vector in the basis B:

if v = B x ′ 1 = Bx ′ -y t , then x = x ′ . ( 22
)
The LLL algorithm was used in [START_REF] Luzzi | Augmented lattice reduction for MIMO decoding[END_REF] to find the shortest vector in the lattice L( B), and the correct decoding radius was shown to be lower bounded by

1 2 √ 2α n-1 2 λ 1 (B) . (23)
when the parameter t is set to

1 2 √ 2α n/2 min 1≤i≤n |r i,i |.
In the following sections, we will derive improved bounds on the decoding radius.

A. Reducing BDD to uSVP

In [START_REF] Lyubashevsky | On bounded distance decoding, unique shortest vectors, and the minimum distance problem[END_REF], it is proven that by choosing t = dist(y, B), the embedding technique allows one to reduce 1/ (2γ)-BDD to γ-uSVP. We show that one can achieve the same correct decoding radius by setting t = 1 2γ λ 1 (B), thus bypassing the assumption from [START_REF] Lyubashevsky | On bounded distance decoding, unique shortest vectors, and the minimum distance problem[END_REF] that dist(y, B) is known. In Section V we will show how to use an estimate of λ 1 (B) to achieve almost the same decoding radius.

Theorem 2 (Decoding Radius of Embedding): Applying γ-uSVP (γ ≥ 1) to the extended lattice [START_REF] Forney | Generalized minimum-distance decoding for Euclidean-space codes and lattices[END_REF] with parameter t (0 < t < λ 1 (B)/γ) guarantees a correct decoding radius

R uSVP-Emb ≥ t γ λ 1 (B) -t 2 . ( 24
)
Setting t = 1 2γ λ 1 (B) maximizes this lower bound. This gives:

R uSVP-Emb ≥ 1 2γ λ 1 (B). (25)
Remark 3: If the SVP itself is solved, then the correct decoding radius satisfies R uSVP-Emb ≥ 1 2 λ 1 (B). This result implies that embedding is more powerful than lattice reductionaided SIC-decoding, since the latter still exhibits a widening gap to 1 2 λ 1 (B), which is at least polynomial in n for Korkin-Zolotarev reduction and for dual Korkin-Zolotarev reduction (which require to solve SVP instances) [START_REF] Ling | On the proximity factors of lattice reduction-aided decoding[END_REF].

Theorem 2 is a direct consequence of the following lemma. Lemma 2: Let B be the matrix defined in [START_REF] Forney | Generalized minimum-distance decoding for Euclidean-space codes and lattices[END_REF], and let 0 < t < λ 1 (B)/γ, with γ ≥ 1. Suppose that

y -Bx < t γ λ 1 (B) -t 2 .
Then v = Bxy t is a γ-unique shortest vector of L( B).

Proof: Let w be an arbitrary nonzero vector in L (B). Any vector in L( B) that is not a multiple of v is of the form

w ′ = w 0 + qv,
with q ∈ Z and w ∈ L(B) \ 0. We will show that w ′ > γ v . The norm of w ′ can be written as

w ′ = w -qn 2 + (qt) 2 ,
where n = y -Bx. If qn ≤ λ 1 (B), using the triangular inequality, we have w-qn ≥ w -q n ≥ λ 1 (B)-q n . Thus we have the lower bound

w ′ ≥ (λ 1 (B) -q n ) 2 + (qt) 2 = λ 1 (B) 2 -2qλ 1 (B) n + q 2 n 2 + q 2 t 2 = n 2 + t 2 q - λ 1 (B) n n 2 + t 2 2 + λ 1 (B) 2 t 2 n 2 + t 2 ≥ λ 1 (B)t n 2 + t 2 . ( 26
)
If qn > λ 1 (B), we can also obtain the same bound because

w ′ ≥ qt > λ 1 (B)t n ≥ λ 1 (B)t n 2 + t 2 .
To prove that w ′ > γ v , it suffices to ensure that

λ 1 (B)t n 2 + t 2 > γ n 2 + t 2 .
This is implied by the assumption that

n 2 = Bx -y 2 < t γ λ 1 (B) -t 2 .
As the LLL algorithm can solve γ-uSVP with γ = α n 2 for the basis (21) of dimension n + 1 (see Equation ( 12)), one can obtain that if using LLL, the correct decoding radius satisfies

R uSVP-Emb ≥ 1 2α n 2 λ 1 (B) (27)
by choosing t = 1 2α n 2 λ 1 (B). This decoding radius improves the bound (23) from [START_REF] Luzzi | Augmented lattice reduction for MIMO decoding[END_REF]. However, it can still be improved. The reason is that the estimate γ = α n 2 is pessimistic for γ-uSVP. In fact, the quantity α n 2 is just the approximation factor for the Approximate SVP achieved by LLL. Any algorithm solving γ-SVP necessarily solves γ-uSVP, while the converse is not true.

We now give two complementary approaches for improving the lower bound on R uSVP-Emb obtained by Kannan's embedding based on LLL. In the first approach, described in Subsection IV-B, we provide a new reduction from HSVP to uSVP. This implies improved lower bounds on the correct decoding radius for Kannan's embedding based on any HSVP solver.

For the second approach, we start by giving a new bound on the performance of LLL-SIC in Subsection II-F, which is of independent interest. We then follow the execution of LLL within Kannan's embedding to show that it performs at least as well as LLL-SIC (Subsection IV-C), which leads to an improved lower bound on the correct decoding radius achieved by Kannan's embedding with LLL. This bound is slightly better (by a small constant factor) than the bound obtained by instantiating the first approach with LLL. The first approach is more general, whereas the second approach gives further insight on the relationship between Kannan's embedding and LLL-SIC.

B. Reducing uSVP to HSVP

We describe a reduction from solving γ-uSVP to solving C-HSVP for γ ≈ √ nC. We will illustrate the usefulness of this approach by considering several reduction algorithms solving C-HSVP with diverse time/quality trade-offs.

Theorem 3 (Reduction from uSVP to HSVP): Suppose that the sequence {C k } is such that (C k ) k/(k-1) increases with k. Then for any γ ≥ γ n-1 (C n ) n/(n-1) , γ-uSVP reduces to C n -HSVP.

Proof: Assume we have access to a C n -HSVP oracle. Let L be an n-dimensional lattice such that λ 2 (L) > γ n-1 (C n ) n/(n-1) λ 1 (L). Assume we are given a basis B of L. We use the HSVP oracle in the following way:

• Use the oracle on the dual lattice L * = L(B * ), to find a short vector c * 1 ∈ L * in the dual lattice; Compute the largest integer k such that c * 1 belongs to kL * and divide c * 1 by k; Extend c * 1 into a complete basis C * of L * . This can be done in polynomial time by considering the unimodular n×n matrix V such that (c * 1 ) t V is in Hermite Normal Form; the first n -1 rows of V -1 complete the basis (see for example [START_REF] Magliveras | Primitive sets in a lattice[END_REF], Section 4).

• For i = 2, • • • , n: Project the vectors c * i , • • • , c * n
to the orthogonal complement of the space generated by c * 1 , . . . , c * i-1 . Let c * i , . . . , c * n the projected vectors. Note that the determinant of the projected lattice

L([c * i , . . . , c * n ]) is equal to det(L * ) det([c * 1 , . . . , c * i-1 ]) = det(L * ) i-1 j=1 r * j,j = n j=i r * j,j ,
where

C * = Q * R * is the QR decomposition of C * .
Apply the HSVP oracle again to find a short vector

v * i = n k=i x k c * k in the projected lattice L([c * i , . . . , c * n ]); Lift it to a vector v * i in L([c * i , . . . , c * n ]) given by v * i = n k=i x k c * k .
Then replace c * i by v * i and complete the dual basis. Since lifting doesn't affect the orthogonal projections nor the r * i,i =< q * i , v * i >, the new basis satisfies

r * i,i ≤ v * i ≤ C n-i+1   n j=i r * j,j   1 n-i+1
and consequently

r * i,i ≤ (C n-i+1 ) n-i+1 n-i   n j=i+1 r * j,j   1 n-i . ( 28
)
This property still holds at subsequent steps of the algorithm since the operation of extracting a short vector and lifting decreases r * i,i , and so increases n j=i+1 r * j,j . We claim that c 1 in the primal basis C = (C * ) * is the shortest vector v of L(B). We prove this fact by contradiction. Suppose that c 1 = ±v, where ±v the unique shortest vectors of L. Note that c 1 cannot be ±2v or other multiples, since in that case C would not be a basis of L. We may write

v = k i=1 x i c i ,
where x i is an integer and k is the largest i such that x i is nonzero.

Observe that if

C = QR is the QR decomposition of C, v = k i=1 x i   r i,i q i + i-1 j=1 r j,i q j   = k-1 i=1   x i r i,i + k j=i+1 x j r i,j   q i + x k r k,k q k .
Since the q i 's are orthogonal, we have:

λ 1 ≥ v ≥ r k,k q k = r k,k .
Using the assumption that c 1 = ±v, we have that k > 1. This ensures that:

λ 2 ≤ λ 1 (L [b 1 , . . . , b k-1 ]).
Indeed, the second minimum λ 2 must be no greater than the norm of the shortest nonzero vector in the sublattice spanned by {b 1 , . . . , b k-1 }, since these vectors are linearly independent with v. The fact that k > 1 ensures that there are non-zero vectors in that lattice. Using Minkowski's first theorem, we obtain

λ 2 ≤ √ γ k-1 det (L [b 1 , • • • , b k-1 ]) 1 k-1 = √ γ k-1 k-1 i=1 r i,i 1 k-1 (29) = √ γ k-1 n i=n-k+2 r * i,i -1 k-1
, where we used the relation r i,i = 1/r * n-i+1,n-i+1 . In the meantime, the HSVP oracle [START_REF] Kiltz | Efficient authentication from hard learning problems[END_REF] ensures that

r * n-k+1,n-k+1 ≤ (C k ) k k-1 n i=n-k+2 r * i,i 1 k-1 (30)
for any k > 1. Substituting into (29), we have

λ 2 ≤ √ γ k-1 (C k ) k k-1 r k,k (31) ≤ γ n-1 (C n ) n n-1 λ 1 ,
where we used the (mild) assumption that (C k ) k/(k-1) increases with k. The last statement is a contradiction because we assumed λ 2 > γ n-1 (C n ) n/(n-1) λ 1 . This completes the proof.

We now instantiate Theorems 2 and 3 with two different HSVP solvers.

The LLL algorithm solves C n -HSVP with C n = α (n-1)/4 (see Equation ( 11)). The sequence (C n ) n/(n-1) grows with n, and thus, by Theorem 3, LLL solves any n-dimensional instances of γ-uSVP with γ = γ n-1 α n/4 . Note that in the reduction from uSVP to HSVP (in the proof of Theorem 3), a single LLL reduction suffices, even if the reduction calls the HSVP oracle many times on projections of the dual lattice. This is because LLL is almost self-dual and the projected sublattices are also reduced. More precisely: We call a basis effectively LLL-reduced if it satisfies condition (8) for j = i-1 (and possibly not for j < i -1) and if it satisfies the Lovász condition [START_REF] Wubben | Lattice reduction: A survey with applications in wireless communications[END_REF]. A basis that is effectively LLL-reduced also satisfies Equations ( 10), [START_REF] Jaldén | DMT optimality of LR-aided linear decoders for a general class of channels, lattice designs, and system models[END_REF] and [START_REF] Ling | On the proximity factors of lattice reduction-aided decoding[END_REF]. The LLL algorithm is self-dual in the sense that if a basis is effectively LLL-reduced, so is its dual basis (see [START_REF] Howgrave-Graham | Finding small roots of univariate modular equations revisited[END_REF]). Moreover, if [b 1 , . . . , b n ] is LLL-reduced, the projection of the basis [b i , . . . , b n ] on the orthogonal complement of the vector space generated by b 1 , . . . , b i-1 is also LLL-reduced.

Overall, if one relies on LLL as HSVP solver, we obtain that Kannan's embedding achieves correct decoding radius ≥ 1 2

√

γ n α (n+1)/4 λ 1 , when using embedding parameter t = 1 2

√

γ n α (n+1)/4 λ 1 . The BKZ algorithm [START_REF] Schnorr | Lattice basis reduction: Improved practical algorithms and solving subset sum problems[END_REF] solves C-HSVP with a smaller C, but at the cost of a higher run-time. It is parametrized by a block-size β ∈ [2, n]. In [START_REF] Hanrot | Analyzing blockwise lattice algorithms using dynamical systems[END_REF], a variant of BKZ is given, which achieves

C n,β = 2(γ β ) n-1 2(β-1) + 3
2 in time polynomial in n and 2 β . For a fixed value of β (and even for a blocksize β that is growing slowly with respect to n), the sequence (C n,β ) n/(n-1) grows with n, thus, by Theorem 3, the modified BKZ with block-size β solves any n-dimensional 1) .

instances of γ-uSVP with γ = √ γ n (γ β ) n 2(β-1) + 3n 2(n-

C. Embedding based on LLL is at least as good as LLL-SIC

The analysis in Subsection IV-B holds generally for any HSVP solver. In this section we focus on the LLL algorithm, and prove a stronger bound, namely that embedding based on LLL has a decoding radius at least as large as LLL-SIC's. The key observation is as follows: If y falls within the decoding radius of Babai, the vector [(Bxy) T t] T will be the shortest vector; it will be moved by LLL to the first column of the basis, and will stay there during the rest of the execution of LLL.

Lemma 3 (Embedding is at least as good as LLL-SIC): Consider a fixed realization y = Bx + n of the MIMO system (4). Suppose that n < R LLL-SIC , so that the LLL-SIC decoder returns the correct transmitted vector x. Then the embedding technique (based on LLL) with the choice t = R LLL-SIC also outputs the correct transmitted vector for the same MIMO system. Consequently, the correct decoding radius of the embedding technique is greater or equal to R LLL-SIC .

Proof: Let B red = BU be the LLL-reduced channel matrix.

If B red = QR is the QR decomposition of B red , then the output of LLL-SIC is given by U x, where x is defined recursively by

x i =     < q i , y > r i,i - n j=i+1 r i,j r i,i x j     .
Suppose that the noise vector n is shorter than the correct decoding radius of LLL-SIC, that is

n < R LLL-SIC = 1 2 min 1≤i≤n |r i,i | = t. (32)
Observe that the hypothesis of Lemma 2 is satisfied for γ = 1, that is

t(λ 1 (B) -t) ≥ R LLL-SIC = t > n , (33)
since λ 1 (B) ≥ 2R LLL-SIC . Consequently, Lemma 2 implies that -n t is a unique shortest vector in the extended lattice.

Consider an alternate version of LLL reduction in which a full round of size reductions RED(k, i), i = k -1, . . . , 1 is performed before the Lovász test, i.e., when considering vector b k , the LLL variant ensures that condition ( 8) is satisfied for all |r i,k | / |r i,i | (with varying i) before checking condition [START_REF] Wubben | Lattice reduction: A survey with applications in wireless communications[END_REF]. Since size reduction has no impact on the Lovász test, this version leads to the same output as the usual LLL algorithm [START_REF] Ling | Effective LLL reduction for lattice decoding[END_REF]. After LLL-reducing the first n columns, the augmented channel matrix is of the form

B = B red -y 0 t
By doing a first round of size reduction RED(n + 1, i), i = n, . . . , 1 on the last column, we find that the (n + 1)-th We will prove by induction that for all the subsequent steps indexed by k = n, . . . , 1, the Lovász condition on the columns k + 1 and k fails, and there is a swap, so that at step k the augmented matrix is of the form

column b n+1 = -n t ,
B (k) = b red 1 • • • b red k -n * • • • * 0 . . . 0 t * • • • * .
The inductive step works as follows. Let

B (k) = Q (k) R (k) be the QR decomposition of B (k) . Then r(k) k+1,k+1 2 + r(k) k,k+1 2 ≤ r(k) k+1 2 ≤ b(k) k+1 2 = n 2 +t 2
since the columns of R (k) are projections of the corresponding columns of B (k) . All the swaps will take place since, because of condition [START_REF] Nguyen | Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from crypto '97[END_REF],

n 2 + t 2 < 1 2 min 1≤l≤n r 2 l,l ≤ 1 2 r 2 k,k . (34)
After the last swap, we obtain

B (0) = -n * . . . * t * . . . * .
Now, recall that if the first column b 1 of a basis matrix is a shortest lattice vector, then it remains at the first position during the whole execution of LLL. Indeed, it is never swapped. To see it, recall that the swap between the first and the second columns takes place only if b 2 2 < δ b 1 2 . This cannot occur as b 2 = 0 and b 1 is a shortest non-zero lattice vector.

Thanks to condition [START_REF] Lyubashevsky | On bounded distance decoding, unique shortest vectors, and the minimum distance problem[END_REF], the vector -n t is a shortest non-zero vector of the augmented lattice. So it is not swapped during the subsequent steps of the execution of LLL, and thus it is the first column of the output basis B red .

To conclude, we have proven that with the choice t = R LLL-SIC , the correct decoding radius of embedding is greater than R LLL-SIC .

Remark 4: The proposed value t = R LLL-SIC of the embedding parameter can be efficiently computed after B red is found and before reducing the (n + 1)-th column of B.

V. DEALING WITH λ 1

The derived bounds on the correct decoding radius hold only if the minimum distance λ 1 is known. However, λ 1 can only be obtained by solving SVP, which is generally a difficult problem. Fortunately, there are alternative approaches that do not require the knowledge of the exact value of λ 1 .

A. Rigorous approach

Suppose we do not know λ 1 , but that we have a good estimate of it:

λ 1 ∈ [A, κA] for some factor κ ≥ 1. Let t = A 2γ ∈ λ1 2γκ , λ1 2γ .
The assumption of Theorem 2 is satisfied. Observe that the right hand side of ( 24) is an non-decreasing function of t in this interval. Then the correct decoding radius is

R Emb = t γ λ 1 -t 2 ≥ λ 1 γ 1 2κ - 1 4κ 2 ≥ λ 1 γ 1 2κ - 1 4κ ≥ λ 1 2 √ κγ . (35)
Equation [START_REF] Horn | Matrix Analysis[END_REF] shows that for any approximation constant κ, we at most lose only a constant √ κ in the correct decoding radius.

We recall the following useful property of LLL-reduced B which follows from [START_REF] Ling | On the proximity factors of lattice reduction-aided decoding[END_REF]:

α -(n-1)/2 b 1 ≤ λ 1 ≤ b 1 . (36)
Letting A = α -(n-1)/2 b 1 , we obtain

A ≤ λ 1 ≤ α (n-1)/2 A. (37)
Substituting κ = α (n-1)/2 into (35) and choosing γ = √ γ n α n+1 4

as in Subsection IV-B for (n + 1)-dimensional lattices, we can obtain a decoding radius

R ≥ λ 1 2 √ γ n α n/2 ,
by setting the embedding parameter t to A 2γ .

It is possible to obtain a better guarantee on the correct decoding radius by partitioning the interval where λ 1 resides:

A, α (n-1)/2 A ⊂ ⌈ n-1 2 log α log κ ⌉ i=0 κ i A, κ i+1 A ,
where κ > 1 is arbitrary. Each subinterval is of the form [A i , A i κ] with A i = κ i A. We apply the embedding technique for each subinterval, choosing

t i = A i 2γ . (38)
Each call solves γ-uSVP with γ = √ γ n α n+1 4

as in Subsection IV-B for (n + 1)-dimensional lattices; at least one of these subintervals contains λ1 2γ , and therefore the corresponding call provides the closest lattice vector to the target as long as the norm of the noise is less than λ1 2γκ . Therefore, using ⌈ n-1 2 log α log κ ⌉ calls to LLL, we can solve γ ′ -BDD with γ ′ = √ κγ. That is, we only lose a factor κ, compared to the case when λ 1 is known. Note that κ can be chosen arbitrarily close to 1, at the cost of increasing the number of calls to LLL.

B. Heuristic approach

We may also find a good estimate of λ 1 heuristically.

There is a common belief that the worst-case bounds ( 11) and ( 12) are not tight for LLL reduction on average. In low dimensions, the LLL algorithm often finds the successive minimum vectors in a lattice. In the average behavior of LLL reduction for some input distributions was numerically assessed, and it was observed that one should replace the factor α n-1 2 from ( 12) by a much smaller value for a random lattice of sufficiently high dimension. The experiments corresponding to Fig. 1 allows one to observe a similar behavior for random basis matrices with i.i.d. Gaussian entries: For δ = 0.99, the factor α n-1 2

≈ (1.428) Fig. 2 shows that after the call to LLL with δ = 0.99 and for random input basis matrices with i.i.d. Gaussian entries, we have λ 1 ≈ 1.03 n min 1≤i≤n |r i,i |.

It is also folklore to estimate λ 1 via the so-called Gaussian heuristic [START_REF] Gama | Lattice enumeration using extreme pruning[END_REF]

λ 1 (det L) 1/n ≈ Γ(1 + n/2) 1/n √ π ≈ n 2πe .
This estimate of λ 1 is the radius of the ball whose volume matches the lattice determinant. The Gaussian heuristic holds for random lattices in a certain sense, and can be made rigorous for precise definitions of random lattices (derived from the theory of Haar measures on classical groups) [START_REF] Nguyen | LLL on the average[END_REF]. However, the experiments in Fig. 3 tend to show that this estimate does not apply for lattices sampled by i.i.d. Gaussian matrices: the minimum λ 1 seems to follow the Gaussian heuristic in the beginning, but to fall short of the theoretic value when is large.

VI. EXPERIMENTS

In this Section we address the practical implementation of embedding decoding in implementation and compare its performance with those of existing methods.

A. Incremental Reduction for Embedding

Setting t 0 = A/(2γ) and κ = α 1/2 , we give an efficient implementation of the strategy proposed in Section V-A where n -1 calls to LLL reduction of the extended matrix [START_REF] Forney | Generalized minimum-distance decoding for Euclidean-space codes and lattices[END_REF] are performed for the sequence {t i } of values of t given in equation [START_REF] Lagarias | Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice[END_REF]. It is summarized by the pseudocode of the function IncrEmb(B,y, t 0 ) in Table I. Except the first one, each call to LLL is significantly cheaper, as LLL is called on a reduced matrix whose last row has been multiplied by a small constant factor α 1/2 (Line 6). This is equivalent to multiplying t i by α 1/2 , then reducing the extended matrix B. Intuitively, we deform the lattice progressively while preserving the property of being LLL-reduced. At last, we choose the vector that is closest to y.

1: B =   B - y
0 1×n t 0   , U ′ = I n+1 2: for i = 1 to n -1 do 3: B = BU ←-LLL B 4: U ′ = U ′ U 5: xi ←-U ′ (

B. List Decoding Based on Embedding

A practical way to improve the embedding technique is to make use of all intermediate lattice vectors during the execution of LLL. Such vectors are generated when size reduction is performed. Since the number of iterations is between O n 2 and O n 3 in embedding (see [START_REF] Luzzi | Augmented lattice reduction for MIMO decoding[END_REF]), and since we can obtain one new vector in each size reduction, the list size can range from O n 2 to O n 4 . We can integrate this into LLL, and the complexity will be of the same order.

The size check in LLL is done with respect to the |r i,i |. Clearly it is preferable to choose small t in order to make sure that the last column in ( 21) can be used as many times as possible. Here, we choose

t List-Emb = 1 2 √ nα n+1 4 min 1≤i≤n |r i,i | , (39)
which is indeed far smaller than the average-case.

C. Soft-output Decoding Based on Embedding

Soft output is also possible from the constellation points generated in the size reduction. To further improve the performance, near neighbors of the recovered constellation point are also taken into consideration. Once the list is found, we choose to center it on y, and then pick up the K best candidates with the smallest Euclidean norm. The K candidate vectors Z = {z 1 , • • • , z K } can be used to approximate the loglikelihood ratio (LLR), as in [START_REF] Hochwald | Achieving near-capacity on a multiple-antenna channel[END_REF]. For bit b i ∈ {0, 1}, the approximated LLR is computed as

LLR (b i | y) = log z∈Z:bi(z)=1 exp -1 σ 2 y -Bz 2 z∈Z:bi(z)=0 exp -1 σ 2 y -Bz 2 (

D. Simulation Results

This subsection examines the error performance of the embedding technique. For comparison purposes, the performances of lattice reduction aided SIC and ML decoding are also shown. We assume perfect channel state information at the receiver, and use MMSE-GDFE left preprocessing for the suboptimal decoders. Monte Carlo simulation was used to estimate the bit error rate with Gray mapping and LLL reduction (δ=0.75).

Fig. 4 shows the bit error rate for an uncoded MIMO system with n T = n R = 10, 64-QAM. We found that the list and incremental versions of embedding achieve near-optimum performance in this setting; the SNR loss is about 1 dB. Both of them are better than ALR [START_REF] Luzzi | Augmented lattice reduction for MIMO decoding[END_REF] and embedding using the exact knowledge of λ 1 ("exact MMSE embedding"). We also observed poor performance for the choice of the embedding parameter t = dist(y, B) in [START_REF] Lyubashevsky | On bounded distance decoding, unique shortest vectors, and the minimum distance problem[END_REF].

Fig. 5 shows the achieved performance of embedding decoding for the 4 × 4 Perfect code using 64-QAM. The decoding lattices are of dimension 16 in the complex space (and 32 in the real space). The list version of embedding enjoys 3.5 dB gain over LLL-SIC, while embedding using the average estimate of λ 1 in Section V-B ("average MMSE embedding") also has more than 2 dB gain. Fig. 6 compares the average complexity of LLL-SIC decoding, embedding decoding and sphere decoding for uncoded MIMO systems using 64-QAM. Fig. 7 shows the frame error rate for a coded 4 × 4 MIMO system with 4-QAM. For channel coding, we use a rate-1/2, irregular (256, 128, 3) low-density parity-check (LDPC) code of codeword length 256 (i.e., 128 information bits) [START_REF] Lin | Error Control Coding, Second Edition[END_REF]. Each codeword spans one channel realization. The parity check matrix is randomly constructed, but cycles of length 4 are eliminated. The maximum number of decoding iterations is set at 50 for the LDPC. It is seen that the soft-output version of embedding decoding is also nearly optimal when K = 20, with a performance very close to maximum a posterior probability (MAP) decoding and much better than a MMSE-only detector followed by per symbol LLR calculation.

VII. CONCLUSIONS AND DISCUSSION

In this paper, we have studied the embedding technique from a BDD point of view. We have investigated the relation between Hermite SVP and uSVP and improved a previously known bound on the value γ for which LLL reduction provides a solution to γ-uSVP. Moreover, we proved that BDD is DMToptimal. The polynomial complexity and near-optimum perfor- mance of the embedding technique makes it very attractive in decoding applications.

We proposed variants with different embedding parameters t that are easy to compute and do not require the knowledge of the minimum distance λ 1 of the lattice: a rigorous version for which we can provide a theoretical estimate of the decoding radius, a heuristic version based on a heuristic estimate of λ 1 with lower computational complexity, and a list-based embedding scheme with improved BER performance. Our numerical simulations provide evidence that a significant fraction of the gap to ML decoding can be recovered.

We have proven that the correct decoding radius achieved by the LLL-based embedding technique is at least as large as the one achieved by LLL-SIC. Experimentally, it seems that it is in fact strictly larger. It would be interesting to explain why this is indeed the case and to which extent. One possibility would be that the embedding technique benefits on average from the noise vector following a normal distribution.

red 1 .

 1 as size-reduction is exactly SIC. At this stage, we have that augmented matrix is of the form b

Figure 1 .= b 1 λ 1 ,Figure 2 . 1 min

 1121 Figure 1. Experimental value of 1 n ln F 1 with F 1 = b 1 λ 1, as function of dimension n for the ouptut of LLL with δ = 0.99 and i.i.d. Gaussian inputs.

3 Figure 3 . 2 1(

 332 Figure 3. Experimental value of F 3 with F 3 =

8 :

 8 x ←-arg min y -Bx i 9: return x

  [START_REF] Wuebben | Near-maximum-likelihood detection of MIMO systems using MMSE-based lattice reduction[END_REF] where b i (z) is the i-th information bit associated with the sample z. The notation z : b i (z) = µ means the set of all vectors z for which b i (z) = µ.

Figure 4 .

 4 Figure 4. Bit error rate vs. average SNR per bit for the uncoded 10 × 10 system using 64-QAM.

Figure 5 .

 5 Figure 5. Bit error rate vs. average SNR per bit for the 4 × 4 perfect code using 64-QAM.

Figure 6 .Figure 7 .

 67 Figure 6. Average number of floating-point operations for uncoded MIMO at average SNR per bit = 17 dB. Dimension n = 2n T = 2n R

  min 1≤i≤n |r i,i | (from Lemma 1 and Equation (15)), where the |r i,i |'s can be easily computed from the output basis. For δ = 0.99, this approximately gives λ 1 ≤ √ γ n (1.195) n-1 min 1≤i≤n |r i,i |.

	n-1 from (12) should be replaced
	by ≈ 1.01 n . Independently, we have the upper bound λ 1 √ n-1 γ n α 4	≤

Table I PSEUDOCODE

 I OF INCREMENTAL EMBEDDING DECODING

	Function IncrEmb(B,y, t 0 )

ACKNOWLEDGMENTS

The authors would like to thank Dr. Shuiyin Liu for running some of the computer simulations and helpful discussions. They also wish to thank the anonymous reviewers for their detailed comments and suggestions which helped to improve the presentation of the paper.