Yasser Fadlallah

Abdeldjalil Aissa

El Bey

Karine Amis Cavalec

Dominique Pastor

Ramesh Pyndiah

Abdeldjalil Aïssa-El-Bey

Karine Amis

New Iterative Detector of MIMO Transmission Using Sparse Decomposition

Keywords: MIMO systems, low-complexity detector, convex optimization, sparse decomposition

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

Due to its ability to increase the achievable capacity in a point-to-point communication, research interests have been steered towards Multiple Input Multiple Output (MIMO) transmission. The performance of MIMO systems is nonetheless conditioned to a wise management of the multi-antenna interference [START_REF] Telatar | Capacity of multi-antenna gaussian channels[END_REF]. Maximum likelihood (ML) joint detection is an optimal strategy that decodes at once the transmitted signals [START_REF] Damen | On maximum-likelihood detection and the search for the closest lattice point[END_REF]. It has been proved to minimize the probability of error for medium to high signal-to-noise ratio (SNR) values. However, its complexity grows exponentially with the antenna dimensions and the constellation size, which makes it impractical. Linear equalizers such as minimum mean square error (MMSE) and zero-forcing (ZF) present rather low complexity at the expense of a high performance-loss, specially when used in underdetermined 1 MIMO systems. Alternative solutions have been proposed, among which the sphere decoder (SD) achieves near-optimal performance provided that the spherical search is well defined [START_REF] Hassibi | On the sphere decoding algorithm i. expected complexity[END_REF]. However, SD suffer from a variable computational complexity that depends heavily on the SNR value, the signal dimensions, and the sphere radius initialization. The computational complexity order has been upperbounded by O(M γN ), where γ ∈ (0, 1], N is the transmit antennas number, and M is the constellation size [START_REF] Jalden | On the Complexity of Sphere Decoding in Digital Communications[END_REF], [START_REF] Ren | Block-orthogonal space time code structure and its impact on qrdm decoding complexity reduction[END_REF]. 1 The number of transmit antennas is larger than the number of receive antennas

The aforementioned optimal detectors are based on an exhaustive search of the desired signal. This implies a high computational complexity order that does not suit practical systems. In this paper, we address the problem of detection for MIMO systems with finite constellation size, and propose an ML detector with relaxed constraints. This detector is based on an iterative strategy, and is proposed for both cases: determined and underdetermined systems. This iterative strategy of decoding aims to maintain a low computational cost even with the increase of the signal and/or constellation size. We rewrite the MIMO channel model with inputs selected from a finite alphabet set, as a MIMO channel with sparse inputs belonging to the binary set {0, 1}. Then, we formulate the ML decoding problem as a minimization problem of a quadratic objective function under well-defined constraints. One of the constraints consists in maintaining a constant ℓ 0 -norm, which makes the problem NP-hard. Exploiting the sparsity property of the signal to decode, we relax the ℓ 0norm by the ℓ 1 -norm in order to reduce the computational cost. This relaxation requires a solution belonging to the intersection of a lozenge with unit diameter and an explicit plan. However, the equality constraint involving the ℓ 1 -norm is not convex. Therefore, we prove that for our particular problem the relaxed ℓ 1 -norm constraint amounts to ensuring that all components of the variable vector are positive. This reduces our problem to a quadratic minimization problem under linear equality constraints and positive variable constraints, which define a convex set. Such a problem can be solved iteratively using first order optimization algorithms (i.e. gradient descent) or polynomial time algorithms e.g. primal-dual point interior method [START_REF] Boyd | Convex Optimization[END_REF].

Related works have been presented in [START_REF] Fadlallah | New Decoding Strategy for Underdetermined MIMO Transmission using Sparse Decomposition[END_REF], where the authors have proposed a detector based on the minimization of an ℓ 1norm iteratively within a sphere of radius ǫ. The dependency on ǫ makes the problem harder to solve, specially that the performance are far from the optimal as shown in our simulation results hereafter. In the problem proposed herein, we ensure that detection performance only depends on the equivalence between the ℓ 1 -norm and the ℓ 0 -norm.

It is shown hereafter, that our detector is reliable when applied to the underdetermined MIMO systems as well as the determined MIMO systems, which is not the case for the linear detector. The main points are threefold: i) Transforming the MIMO decoding problem into a sparse input recovering problem, ii) Detecting the desired signal via quadratic minimization under convex constraints, iii) Applying the proposed detector to large-scale antenna on non-selective channels and to MIMO systems on frequency selective channel.

The remaining of the paper is organized as follows. Section II describes the MIMO transmission model with finite constellation size and its transformation into a MIMO model with sparse input. Section III proposes the iterative decoding scheme that minimizes the euclidean distance with the received signal preserving a constant norm ℓ 1 . In Section V, the simulation results enable the evaluation of our contribution. Finally, Section VI concludes the paper.

Notations: boldface upper case letters and boldface lower case letters denote matrices and vectors, respectively. For the transpose, transpose conjugate and conjugate matrices we use (.) T , (.) H and (.) * , respectively. ||.|| p denotes the norm ℓ p , and ⊗ is defined as the Kronecker product. I p is the p × p identity matrix and 1 p is the ones vector of length p.

II. SYSTEM MODEL

We first consider a MIMO transmission over a flat fading channel, where the transmitter and the receiver are equipped with N and n antennas, respectively. We assume no prior knowledge of the channel state information (CSI) at the transmitter and a perfect CSI knowledge at the receiver.

The received signal in MIMO single user channel is defined as

y = Hx + z, (1)
where H is an n×N random channel matrix (n ≤ N ), x is the N × 1 data vector, and z is the n × 1 complex circularly symmetric additive white Gaussian noise vector with zero mean and covariance matrix equals to σ 2 I n . The components of x belong to a finite alphabet defined as

Q = {q 1 , q 2 , • • • , q M }.
For example, a 4-QAM constellation is defined as M = 4 and

Q = { 1+i √ 2 , 1-i √ 2 , -1+i √ 2 , -1-i √ 2 }.
The goal of our work is to find out an efficient detection scheme of the received data samples with moderate computational complexity order over the whole SNR region. This requires a priori knowledge on the transmitted information. Therefore, we exploit the fact that the original symbols belong to a finite alphabet, and we decompose each symbol on the basis of the vector space in which the finite alphabet vector q = [q 1 , q 2 , • • • , q M ] can be cast. The decomposition of the vector with symbols belonging to the finite alphabet set is illustrated in Fig. 1. In this example, we assume a constellation set Q with three elements {q 1 , q 2 , q 3 }, and we define the dictionary that matches each element of Q to its proper sub-vector in the set {(0 0 1) T , (0 1 0) T , (1 0 0) T }. Each sub-vector in the dictionary associated to an element q i ∀i ∈ {1, 2, 3} and denoted by s i contains only one nonzero component at the position i. This means that any element q i can be written as its associated sub-vector s i projected on the finite alphabet vector q, i.e. q i = qs i . Using this decomposition, any vector with symbols belonging to Q can be written as a block diagonal matrix B q , with q repeated on its diagonal, multiplied by a sparse vector. This latter is constructed by stacking all the sub-vectors associated to the transmitted symbols.

The model in ( 1) can be then viewed as an equivalent MIMO channel with sparse input vector. In other words, the data vector with N entries in the MIMO transmission can be modeled as an equivalent sparse data vector s with N M entries. The j th component x j of x is decomposed as

x j = q s j ,
where

s i = [δ q1 (x j ), δ q2 (x j )), • • • , δ qM (x j )] T , and δ qi (x j ) = 1 if x j = q i 0 otherwise . (2)
The vector x can be then written as a function of s as

x = B q s, where s = [s T 1 , s T 2 , • • • , s T N ]
T , and B q = I N ⊗ q.(3) B q is a block diagonal matrix with dimensions N × (N M ). Substituting (3) into (1) yields

y = HB q s + z. (4)
The transmitted signal x in (1) can be detected by seeking the optimal solution s in (4). In next section, we formulate the ML detection problem as the minimization problem of the Euclidean distance between the received signal y and the received constellation HB q s under linear and ℓ 0 -norm constraints. Then, we relax the constraints of the equivalent ML minimization problem in such a way that first order optimization and polynomial algorithms can be used to detect the desired information.

III. DETECTION OF SPARSE TRANSFORMED MIMO VIA MINIMUM DISTANCE MINIMIZATION

A. ML detection problem relaxation

The ML detector requires an exhaustive search over all possible transmitted symbol vectors, and selects the solution that corresponds to the closest point to the received signal in the received constellation. In other words, it selects the symbol vector that minimizes the euclidean distance between y and Hx. Hence, the ML detection problem is defined as

[M L] : arg min x ||y -Hx|| 2 subject to x ∈ Q N . (5)
The main drawback of the ML problem is that it suffers from a high computational complexity because of the exhaustive search required over the set Q N . Herein, we propose an equivalence to this constraint using the following proposition.

Proposition 1: The components of x belong to the finite alphabet constellation Q if and only if the following equality hold: B 1 s = 1 N and ||s|| 0 = N , where the norm ||s|| 0 represents the weight of s and the N × N M matrix B 1 is defined as

B 1 = I N ⊗ 1 M , (6)
where 1 M is the ones row vector of length M . Proof: Assuming first that the components of a Ndimensional vector x belong to a finite alphabet set, x can be sparsely decomposed as x = B q s (see section II), where s consists of N sub-vectors with only one non-zero element equals to one for each. This means that the sum over each subvector is equal to one i.e. B 1 s = 1 N , and the total number of non-zero elements in s is equal to N i.e. ||s|| 0 = N . Let us now assume B 1 s = 1 N and ||s|| 0 = N . The first equality B 1 s = 1 N , i.e. M p=1 s (j-1)M+p = 1 for all j ∈ {1, • • • , N }, implies that at least one non-zero element exists in any sub-vector j ∈ {1, • • • , N }, with a minimum total non-zero elements number N . The second equality ||s|| 0 = N imposes the total non-zero elements number to be equal to N , thus along with the first equality each sub-vector can contain only one element different from zero and equal to one. Thereby, the projection of the whole vector s onto the decomposition matrix B q yields a vector x = B q s in the finite alphabet constellation Q N .

Using proposition 1, the [ML] minimization problem in (5) becomes arg min

s∈R N M ||y k -Hk B q s|| 2 subject to B 1 s = 1 N , ||s|| 0 = N. (7)
The first constraint given by B 1 s = 1 N is linear and the second constraint given by ||s|| 0 = N is discrete i.e. s belongs to a finite discrete set, thereby making the problem NP-hard. Such problems necessitate exhaustive search to be solved yielding an exponential increase of the computational complexity with the signal dimension. To overcome this drawback, we exploit the fact that the new signal vector to decode s is sparse, and we propose to relax the ℓ 0 -norm by the ℓ 1 -norm which is widely used in the literature, e.g.

[8]- [START_REF] Malioutov | Optimal sparse representations in general overcomplete bases[END_REF]. The relaxed constraint yields ||s|| 1 = N . Such a constraint is not convex, thus, a global optimum is not necessarily achieved. In order to transform the problem into a quadratic minimization problem subject to convex constraints, we introduce the following lemma: Lemma 1: Let s an N M -dimensional real vector satisfying B 1 s = 1 N . Then all components of s are positive if and only if its ℓ 1 -norm equals N i.e. s 1 = N .

Proof: Let B 1 = I N ⊗ 1 M . The non-zeros elements of the k th row of B 1 are all equal to one and are those whose indexes range from (k -1)M + 1 to kM . Thus

B 1 s = 1 N implies M p=1 s (k-1)M+p = 1, ∀k ∈ {1, • • • , N } (8)
By successive additions with respect to k, we obtain

N M i=1 s i = N k=1 M p=1 s (k-1)M+p = N. (9)
Let us first assume that all components of s are positive. Then s i = |s i | and using (9), we deduce that

N M i=1 |s i | = N , i.e. s 1 = N .
Let us now assume that s 1 = N . According to (9), we can thus write

N M i=1 (|s i | -s i ) = 0. ( 10
)
Let N(s) = ∅ denote the set of indexes corresponding to all nonzero negative elements of s. [START_REF] Malioutov | Optimal sparse representations in general overcomplete bases[END_REF] that s i = 0 for every i ∈ N(s) which is in contradiction with N(s) = ∅. We thus deduce that N(s) = ∅ and all components of s are positive.

Then N M i=1 (|s i | -s i ) = 2 i∈N(s) |s i |. It follows from
Using the lemma introduced above, the decoding problem becomes

[Quad-min] : arg min s∈R N M ||y -HB q s|| 2 subject to B 1 s = 1 N , and s ≥ 0. (11)
This new optimization model is a quadratic programming model with linear equality constraints and non-negative variables.

B. Computational complexity

The proposed detection problem is a convex quadratic relaxation of the original non-convex ML detection problem. It can be formulated as follows

(P) minimize s 1 2 s H Gs + c H s subject to As = b, s ≥ 0, s ∈ R L , (12)
where

A = B 1 , b = 1 N , c H = -y H HB q
, and G = (HB q ) H (HB q ), and L is the length of s. Various techniques exist to solve the problem (P) among which the primal dual interior point methods (PDIP) are characterized by high accuracy level. Several algorithms have been proposed since the publication by Kramarkar et al. of a practical polynomial time interior projective algorithm [START_REF] Karmarkar | A new polynomial-time algorithm for linear programming[END_REF]. Among the best known is the algorithm introduced by Golfarb et al. in [START_REF] Goldfarb | An o (n 3 l) primal interior point algorithm for convex quadratic programming[END_REF]. It defines a reduced PDIP algorithm in which modified Newton steps are used. For L variables, the algorithm has a total complexity upper-bounded by O(L 3 ), where at most O( √ L) iterations are required and all computations at each iteration require O(L 2.5 ) arithmetic operations (for more details see Section 5 in [START_REF] Goldfarb | An o (n 3 l) primal interior point algorithm for convex quadratic programming[END_REF]). Applied to our problem, it yields a computational complexity of O(M 3 N 3 ), where the variable vector consists of N × M elements s i ∀i ∈ {1, • • • , N × M } as detailed in (2) and (3). For a given constellation, M is constant. Since the constant multipliers do not affect the big O notation, the complexity order is of O(N 3 ) [START_REF]Big O Notation[END_REF]. Other simple iterative algorithms than the PDIP can also be applied such as the projected gradient descent algorithm, however, such methods are much less accurate and require a high iteration number to converge.

Remark 1: The decomposition in Section II is important in the sense that it allows to replace the original variable vector in the ML problem with another binary variable vector in the set {0, 1}, and to replace the constraint in ( 5) by a constant ℓ 0norm constraint and other linear constraints. Then, the ℓ 0 -norm constraint can be relaxed by the ℓ 1 -norm constraint thanks to the sparsity property of the new variable vector. This relaxation is widely used when dealing with sparse vectors and in some cases the equivalence holds as e.g. in [START_REF] Aissa-El-Bey | Recovery of Finite Alphabet Solutions of Underdetermined Linear System[END_REF]- [START_REF] Malioutov | Optimal sparse representations in general overcomplete bases[END_REF].

IV. APPLICATIONS

A. Massive MIMO systems on flat fading channels

We consider the uplink of a TDD transmission where K user equipments transmit simultaneously and in the same bandwidth to a base station. The assumptions are the following. No restriction is imposed on the user equipment antenna number, while the base station antenna number is assumed to be high. The user equipments cannot coordinate and transmit reference signals to the base station for channel state information (CSI) estimation purpose. The overall CSI is perfectly known at the receiver. We consider a large scale MIMO system [START_REF] Rusek | Scaling up MIMO: Opportunities and Challenges with very Large Arrays[END_REF] where the user number as well as the base station antenna number are high. In this respect, the optimal joint detection, based on an exhaustive search, exhibits a huge computation cost, which exponentially increases with the variable vector length N and makes it unfeasible in practice. On the other hand, the proposed detection problem [Quad-Min] is solvable in polynomial time, which is suitable for an implementation, even when applied to high-dimension MIMO systems, i.e. with tens to hundreds antennas.

B. Frequency Selective MIMO channel

Another context is the frequency selective MIMO channel where L+1 multipath interfere at every channel use. The transmitter and the receiver are equipped with N and n antennas, respectively. We consider a transmission over a frame with length T f , and for every transmitted symbol L + 1 copies are received through L+1 different paths. The frequency selective channel output at instant t is expressed as

y(t) = L l=0 H l x(t -l)+z = L l=0
H l B q s(tl)+z(t), [START_REF]Big O Notation[END_REF] where H l represents the l th path in the frequency selective channel. In order to decode the original symbol vector, we Fig. 2: BER performance comparison of the proposed detector versus the sphere decoder [START_REF] Cui | An Efficient Generalized Sphere Decoder for Rank-Deficient MIMO Systems[END_REF] and the [ℓ 1 -min] detector propose a joint detection over the whole frame2 . Thus, instead of applying the decoding process T f times per transmit antenna, we only decode at once a concatenated vector that consists of simultaneously transmitted vectors. The channel model is reformulated as in [START_REF] Rusek | Scaling up MIMO: Opportunities and Challenges with very Large Arrays[END_REF].

One can notice that the performance of the proposed detector is dependent on the number of multipath. When there is only one path (non frequency-selective channel), the channel matrix H f s in ( 14) becomes block diagonal, and the problem ( 13) is then equivalent to decoding each N × 1 data vector independently. In contrast, in presence of multipath, a joint detection over the whole (or part of the) frame must be applied. This implies an exploitation of the multipath diversity, and results in a performance improvement and a total complexity upperbounded by O(N 3 ) when M and T f are constant.

V. SIMULATION RESULTS

In this section, we evaluate the Bit Error Rate (BER) and the computational complexity of the proposed detector based on quadratic minimization. We consider N × n MIMO systems, where N and n are the number of transmit and receive antennas, respectively. The channel coefficients are i.i.d. circularly symmetric complex Gaussian distributed with zero mean and unit variance, and the data symbols belong to a finite constellation. The number of transmitted symbols is equal to N at one channel use. For our proposed decoding scheme, we use the cvx toolbox, which is a Matlab-based modeling system for convex optimization [START_REF] Grant | CVX: Matlab software for disciplined convex programming, version 2.0 beta[END_REF], [START_REF] Grant | Graph implementations for nonsmooth convex programs[END_REF]. We use the Gurobi optimizer to solve the [Quad-min] problem under convex constraints [START_REF] Optimizatoion | Gurobi optimizer reference manual[END_REF]. This optimizer employs the PDIP methods for the quadratic programming. This method can be implemented using the algorithm proposed in [START_REF] Goldfarb | An o (n 3 l) primal interior point algorithm for convex quadratic programming[END_REF]. We simulate this system using Matlab 7.10 on a processor Intel(R) Core(TM) i5-3317U CPU at 1.70GHz and memory 6GB RAM.

A. Comparison with optimal algorithms

For underdetermined large MIMO systems, Fig. 2 compares the BER performance of the proposed detection scheme

   y(1)
. . .

y(T f + L)    =       H T 0 • • • H T L 0 T n×N • • • 0 T n×N 0 T n×N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 T n×N • • • 0 T n×N H T 0 • • • H T L       T   
x(1) . . . [Quad-min] to the sphere decoder (SD), described in [START_REF] Cui | An Efficient Generalized Sphere Decoder for Rank-Deficient MIMO Systems[END_REF], and to the [ℓ 1 -min] detector proposed in [START_REF] Fadlallah | New Decoding Strategy for Underdetermined MIMO Transmission using Sparse Decomposition[END_REF]. We assume a QPSK constellation mapping known at both the transmitter and the receiver. It can be observed that beyond 8dB, the SD outperforms the proposed scheme, e.g. at BER 10 -2 , a gain about 2dB and 2.5dB is obtained when the dimensions are 16 × 14 and 24 × 21, respectively. Compared to the [ℓ 1min] scheme in [START_REF] Fadlallah | New Decoding Strategy for Underdetermined MIMO Transmission using Sparse Decomposition[END_REF], the proposed scheme illustrates a gain over the whole SNR region, e.g. at BER 10 -2 , the gain is between 1.5dB and 2.5dB for the system dimensions 16 × 14 and 24 × 21, respectively.

x(T f )    +    z(1) . . . z(T f + L)    . (14)
In a frequency selective channel context, Fig. 3 compares the BER performance of our proposed detector to the detector based on the Viterbi algorithm [START_REF] Viterbi | Error bounds for convolutional codes and an asymptotically optimum decoding algorithm[END_REF], and to the [ℓ 1min] detector. The Viterbi algorithm is known to exploit the channel multi-paths, and achieves optimal performance over a frequency selective channel. We assume a frame length detector with 2dB to 3dB when L = 3 and L = 4, while preserving a reduced computational complexity. The [ℓ 1 -min] detector, however, suffers from a higher loss. As shown in Fig. 3, at BER 10 -2 , the gain of the Viterbi detector over the [ℓ 1min] detector fluctuates between 1dB and 2.5dB, and at BER 10 -3 the gain fluctuates between 3dB and 4dB, for different multi-paths number.

B. Comparison with low-complexity algorithms

In order to compare the proposed receiver to low-complexity receiver references in terms of error rate, we assume a determined 64 × 64 MIMO single user configuration. We compare in Fig 4 the proposed detector to the simple MMSE-based and the MMSE Successive interference cancellation (MMSE-SIC)based described in [START_REF] Hassibi | An efficient square-root algorithm for blast[END_REF]. One can observe that the [Quad-min] detector exploits the receive diversity better than the two other detectors. At BER 10 -3 , the [Quad-min] detector outperforms the MMSE-SIC by about 1.5dB and the MMSE by 7dB. The gain compared to the MMSE-SIC increases to reach 2dB for a BER of 3.10 -5 . On the other hand, all detectors use polynomial time algorithms, but their complexities differ from one detector to another, as will be shown in Section V-C.

C. Computational complexity evaluation

We evaluate the the computational complexity in Big-O notation. Big-O notation, also called Landau's symbol, is a well-understood symbolism widely used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions [START_REF]Big O Notation[END_REF], [START_REF] Landau | Handbuch der Lehre von der Verteilung der Primzahlen[END_REF]. Basically, it tells how fast iteration number computational cost per iteration

Total MMSE 1 O(n 3 ) O(n 3 ) Basic MMSE-SIC 1 O(N 2 n 2 ) + O(N n 3 ) + O(N 4 ) O(N 2 n 2 ) + O(N n 3 ) + O(N 4 ) Improved MMSE-SIC 1 O(n 3 ) + O(N n 2 ) + O(N 2 n) O(n 3 ) + O(N n 2 ) + O(N 2 n) Quad-min O( √ N ) O(N 2.5 ) O(N 3 ) SD 1 O( √ M γN ) O( √ M γN ) ML 1 O( √ M N ) O( √ M N )
TABLE I: Computational cost analysis a function grows or declines. Table I summarizes the complexity order of our proposed detector, the simple MMSE, the basic and improved MMSE-SIC proposed in [START_REF] Hassibi | An efficient square-root algorithm for blast[END_REF], and the ML optimal detector. The ML based detector is NP-hard, thus it is the least cost efficient. The simple MMSE-based detector consists of a complex inversion of n × n matrix, and some matrix multiplications and additions. As described in [START_REF] Wubben | Mmse extension of v-blast based on sorted qr decomposition[END_REF], the MMSE filter matrix can be computed using a QR decomposition, for which the complexity is given by O(n 3 ), thereby the MMSE computational complexity is of O(n 3 ). The computational complexity of the basic MMSE-SIC algorithm is of O(N 2 n 2 ) + O(N n 3 ) + O(N 4 ), which is equivalent to N 4 when n = N . This complexity order decreases to

O(n 3 ) + O(N n 2 ) + O(N 2 n),
for the improved MMSE-SIC i.e. to N 3 when n = N . Comparing the improved MMSE-SIC based detector to the [Quad-min] detector, similar complexity order is obtained for determined MIMO systems. However, in overdetermined MIMO configuration and for n >> N , the complexity order of the [Quad-min] becomes much lower than the MMSE-SIC. This is because the latter keeps a complexity of O(n 3 ), whereas the [Quad-min] complexity order, total and per iteration, depends only on N [START_REF] Goldfarb | An o (n 3 l) primal interior point algorithm for convex quadratic programming[END_REF].

The theoretical results are also supported by the runtime of the proposed simulations that evaluate algorithms. The runtime represents the average duration that needs a processor to decode the received signal. Fig. 5 evaluates the runtime of the proposed detection scheme [Quad-min]. It can be observed that the runtime increases slightly with the system dimensions, and independently of the SNR level. E.g. the runtime of the [Quad-min] problem is equal to 0.017sec over the whole SNR region using a 16 × 14 system dimensions, and when the dimensions increase from 16 × 14 to 28 × 32, the runtime entails an increase of only 0.023sec. The same observations are made in the frequency selective case, where the proposed iterative detection yields a runtime that increases slightly with the number of multi-paths as shown in Fig. 6. For example, increasing the number of multipath from L = 3 to L = 5 results in an increasing runtime only from 0.02sec to 0.03sec.

Remark 2: It is important to mention that the relaxed constraints impose the subvector components to be in the interval [0,1], with their sum equal to one. Thus interpreting the solution subvector components as reliability values relative to the associated alphabet symbols, a preliminary analysis, which is still in progress, has shown that these output can be used to provide soft input to a channel decoder. In this paper we have addressed the problem of decoding in high dimensional MIMO systems with finite constellation. We have exploited the fact that the original symbols belong to a finite alphabet, and we have modeled the transmission channel as a higher-dimensional MIMO channel with sparse input vector belonging to the binary set {0, 1}. Using this decomposition, we have relaxed the ML problem with another minimization problem that can be solved using iterative method with polynomial complexity. Simulations carried out in the cases of large-scale MIMO systems on flat fading channel and MIMO on frequency selective channels, and have enhanced the relevance of the proposed detector for practical purposes. Beside the advantage of fitting underdetermined MIMO systems, the superiority in terms of error rate performance over other low-complexity receivers such as MMSE and MMSE-SIC has been highlighted.

Fig. 1 :

 1 Fig. 1: Sparse decomposition of the vector with symbols belonging to a finite alphabet set.

Fig. 3 :

 3 Fig. 3: BER performance comparison of the proposed detector versus the viterbi decoder and the [ℓ 1 -min] detector when L = 4 and L = 3.

Fig. 4 :

 4 Fig. 4: BER performance comparison of the proposed detector with the MMSE and MMSE-SIC in a 64 × 64 MIMO channel.

Fig. 5 :

 5 Fig. 5: Runtime evaluation of the proposed detector for different SNR values with QPSK modulation

Fig. 6 :

 6 Fig. 6: Runtime evaluation of the proposed detector for SNR = 14dB, assuming BPSK modulation

The joint detection can also carried out over only a part of the frame as well.


Antoine Rozé

Matthieu Crussière

Maryline Hélard

Charlotte Langlais

Comparison between a Hybrid Digital and Analog Beamforming System and a Fully Digital Massive MIMO System with Adaptive Beamsteering Receivers

Keywords: Massive MIMO, mmWave, Conjugate, LOS, Hybrid Beamforming, DoA

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

The infatuation of the past few years for systems with a high number of antennas keeps studies flourishing. Massive MIMO systems [START_REF] Rusek | Scaling Up MIMO: Opportunities and Challenges with Very Large Arrays[END_REF] are proven highly energy efficient and thus are very well adapted for solutions requiring high data rates, low consumption or both. At the same time, the high frequency communication field, also called millimeter Wave (mmWave), has thrived with researchers exploring the possibility to use these bands for the increased wireless bit rates promised for future communications.

While those bands are indeed wide and available, they raise many questions about the way to use them. Massive MIMO systems in mmWave are considered very complex to implement, although studies start addressing this topic [START_REF] Swindlehurst | Millimeter-wave massive MIMO: the next wireless revolution[END_REF], due to the integration of many Radio Frequency (RF) chains. However, high beamforming gains are needed to compensate the important path losses occurring at these frequencies. Thus Hybrid solutions have emerged to address such a problem.

They allow the number of antennas to remain high without as many RF chains [START_REF] Ayach | The capacity optimality of beam steering in large millimeter wave MIMO systems[END_REF], [START_REF] Han | Large-scale antenna systems with hybrid analog and digital beamforming for millimeter wave 5g[END_REF]. Our study follows such a path which started with the realization that the higher the frequency, the more the channel response depends on the environment geometry [START_REF] Khan | Millimeter-wave mobile broadband with large scale spatial processing for 5g mobile communication[END_REF], e.g. the angular structure of the propagation paths between the transmitter and the receiver. Also, the use of beamforming techniques are prone to reduce the diversity of the said channel, therefore implying that more adapted solutions need to be shed light on.

Our work revolves around the use of precoders based on the angular structure of the channel instead of its frequency or impulse response, as conventionally done in the literature. Indeed in mmWave communications with high path losses, only the direction of arrival (DoA) of the direct path of the wave carries much energy, thus leading to a Beamsteering precoding strategy. We have compared in [START_REF] Rozé | Millimeter-Wave Digital Beamsteering in Highly Line-of-Sight Environments for Massive MIMO Systems[END_REF] the performance of such a precoder at 60 GHz against two widely used linear precoding algorithms, namely the Zero-Forcing (ZF) and the Conjugate Beamforming (CB). That study helps to realize how such a simple solution can reach close to optimal performance in the right conditions, those being having the fewest and weakest multi-paths components in a Line of Sight (LOS) environment.

On the terminal end, most Massive MIMO studies consider single antenna devices because the spatial multiplexing process is used to transmit multiple streams simultaneously to multiple users, each receiving only one. Having a steerable antenna array at the terminal side, on the other hand, would give many benefits, such as higher gains and weaker reflected paths. This however stands problematic due to the random movement of the device. This is where the Inertial Measurement Unit (IMU), accelerometers and gyroscopes, comes into play. Nowadays most mobile devices have an on-board IMU that give a measure of its acceleration, in up to 3 dimensions with a 3-axis accelerometer, and of its angular velocity, in up to 3 dimensions with a 3-axis gyroscope. Both give measurements that, once combined, offer quick and precise information about the device inclination and position. The validity of such measurements is well noted in [START_REF] Yaqoob | Direction of arrival estimation with arbitrary virtual antenna arrays using low cost inertial measurement units[END_REF] where is introduced a way to estimate the DoA using a single antenna combined with rotation and position information. Our study describes a way of using an IMU to allow the User Equipment (UE) to form a beam that is always directed toward the BS, whatever its change of position or inclination. On that basis, the aim of this paper is to highlight the benefit of such a strategy compared to the known hybrid beamforming solutions.

In that perspective, Section II first describes the conventional Hybrid Analog and Digital beamforming approach with its limitations in a multi-user transmission scheme. Section III then introduces and describes the requirements followed by the process for the terminal to be able to direct its own beam at all times toward the base station, whatever its inclination and position. Finally Section IV compare the performance of the known Hybrid system against a fully digital Massive MIMO base station, having as many RF chain but fewer antennas and serving UEs with as many analogically steered antennas as the Analog stage of the Hybrid system. With these results we highlight how such multi-user solutions gain from deporting the stage on the user terminal. Conclusions are drawn in Section V.

II. HYBRID DIGITAL AND ANALOG BEAMFORMING

The purpose of a Hybrid system, first described in [START_REF] Ayach | The capacity optimality of beam steering in large millimeter wave MIMO systems[END_REF], is to allow a Base Station (BS) to have a high number of antennas without being too complex to implement. This complexity comes mostly from the fact that integrating many RF chains in mmWave is very difficult, although studies such as [START_REF] Swindlehurst | Millimeter-wave massive MIMO: the next wireless revolution[END_REF] have found some promising results.

A. System model

Various hybrid system architectures are presented in [START_REF] Han | Large-scale antenna systems with hybrid analog and digital beamforming for millimeter wave 5g[END_REF] and each have their own pros and cons but few can be used for multi-user transmissions. One such is illustrated on Fig. 1 and the multiple user precoding MIMO system translates into a decomposition of the M × K precoding matrix W into two matrices denoted as W D ∈ C N D ×K for the baseband processing and W A ∈ C M ×N D for the analog stage. K is the number of users to serve simultaneously and M is the total number of antennas. From the figure, we denote as N A the number of antenna elements analogically controlled through phase adjustement beyond each of the N D RF chains. Such phase shifts lead to a beamsteering effect at the level of each RF chain. Then, we clearly have M = N A × N D , and the vector gathering the precoded information x ∈ C M ×1 can finally be written as:

x = W A W D s (1)
with s ∈ C K×1 the vector of data symbols intended to the K users. For instance, considering a uniform linear array (ULA) of elements, matrix W A takes the form of a block diagonal matrix, i.e.

W A = diag[a 1 (φ 1 ), • • • , a N D (φ N D )],
with vector a i defined as:

a i (φ i ) = 1, e kd A sin(φi) , • • • , e (N A -1)kd A sin(φi) T (2)
where d A is the antenna element spacing, k = 2π λ with λ the transmission wavelength, and φ i is the angular direction toward which the analog beam produced through the ith antenna array is steered.

Indeed, an efficient way to share the same time and frequency resource between users is to have all analog arrays controlled so that they steer their beam in the same direction, that is φ i = φ, ∀i. Within this beam, users can be addressed simultaneously if they don't outnumber the RF chains at the BS. In other words, UEs can communicate simultaneously with the BS if there are more RF chains than them and if the analog beam, formed by the analog stage of the Hybrid system, covers them all in its main lobe. Therefore the fewer antennas are in the analog stage, the wider the beam and thus the more UEs to be included in the spatial multiplexing but the lower the beamforming gain and thus the lower the link quality. The tradeoff chosen for each solution between N D and N A is going to depend very closely on the use cases they are applied to.

The following process describes the solution followed in this paper to compute the direction φ toward which steering the analog beam:

1) The width of the beam is determined from the number of analog antennas N A . In this paper, we consider square antenna arrays which means √ N A horizontal and vertical elements, therefore the minimum beam width in azimuth or elevation is :

∆θ -3dB ≈ λ √ N A d A 0.886 (3)
where ∆θ -3dB is the angular span within which the amplitude of the main lobe is between

√ N A 2
and √ N A . This beam width stands for a transverse beam therefore it will get wider as soon as it is stired; 2) The user around which are gathered the most other UEs, within the angular span defined in equation (3), is found and a group K is made out of all these UEs; 3) The direction of the steered analog beam is then derived from the average value of all the DoA of the users in the group. Denoting as φ k the DoA of user k, the angular direction then expresses as: The environment used for this paper's simulations, illustrated on Fig. 2, is a short street section of 30m long and 15m wide. The BS, implemented with 16 RF chains at 60 GHz, is placed in the middle of the street at 10m from the ground on a building wall and we consider two reflections adding up to the direct path, one on the ground and one on the building on the opposite side of the street. This model is developed more extensively in [START_REF] Roze | Linear Precoder Performance for Massive MIMO Systems in near LOS Environments: Application to mmWave Transmission[END_REF].

φ = 1 Card{K} k∈K φ k (4)
Two precoders maximizing the transmitted energy toward each user have been chosen to demonstrate the performance of such systems:

• The Conjugate Beamforming (CB) derived from the baseband equivalent frequency channel response H ∈ C K×N D :

W D = H H (5)
Note that the channel is viewed at the level of the baseband unit. Therefore, matrix H is of size K×N D and conveys the equivalent channel gains experienced at the RF chains as a consequence of the analog beamsteering effect obtained at the analog precoding level. • The Digital BeamSteering (DBS) using the DoA φ k of the users gathered into one steering matrix A ∈ C K×N D :

W D = A H (6)
the kth column of A being the steering vector a k computed from (2) and using the DoA of user k. Note that such a precoding is strictly equal to the CB in a pure LOS environnement (no reflected path).

B. Performance Fig. 3 shows how implementing an analog stage on a Massive MIMO system impacts the performance of the CB and the DBS. The Channel State Information (CSI) is assumed perfectly known and the basic Massive MIMO performance with no analog stage is represented by the doted curves while the plain curves represent the hybrid systems with N A = 4 and N A = 16 having respectively no marker and the star marker. Note that the CB remains more effective than the DBS, especially when the number of simultaneously served users grows. This is due to the fact that it uses the CSI instead of just the direction of the direct path (used by the DBS), therefore also exploiting the reflections of the wave to improve its focus on each user.

We can see that there is an obvious gain to implement an analog stage, whether using the CB or the DBS precoder, since the plain curves are well above the dotted curves. On the other hand having many analogically steered antennas does not seem to increase much the multi-user system performance. Indeed, the higher the number of antennas in the analog stage, the fewer the users targeted by the beam and thus the lower the sum capacity.

To summarize, such Hybrid solutions can increase the performance of multi-user transmission systems to a certain degree that depends on the density of population in the cell since the more users there are, the more interesting it is to focus precisely with the analog stage to have an average of users high enough that sum capacity reaches high peaks. Also, this analog focus makes them particularly suited for multistream point-to-point MIMO solutions, as presented in [START_REF] Han | Large-scale antenna systems with hybrid analog and digital beamforming for millimeter wave 5g[END_REF].

III. SELF-ADAPTING ANALOG ARRAY

Most often in Massive MIMO systems, UEs are described as single antenna terminals since they simply receive the signal from the base station without channel knowledge, therefore not implementing any traditional point-to-point MIMO techniques that require a plurality of antennas on the terminal.

In such techniques, however, what is behind the terms single and multiple antennas is actually the number of RF chains. Indeed a terminal with one RF chain and many antennas steered analogically is considered a single antenna terminal with the particularity that this antenna is directive and the direction of its beam controlled.

This section explains how a terminal can adjust the direction of its beam in real time so that it constantly focuses toward the BS to get the highest beamforming gain.

A. Description

This method is based on the hypothesis that the UE has an antenna array whose beam can be steered analogically or digitally. The following procedure aims at adapting the direction of the terminal's beam depending on its inclination at any time.

The following parameters need to be known from the UE to implement the solution:

• The inclination of the BS antenna array in relation to the wall, see α on Fig. 5 -a The study in [START_REF] Han | Large-scale antenna systems with hybrid analog and digital beamforming for millimeter wave 5g[END_REF] introduces a DoA estimation technique which involves mapping directions on each subcarriers so that the entire spectrum covers the cell area. By using this method, the UE can extract the optimum DoA used by the BS without knowing anything except the mapping table linking the DoA to the subcarriers used for the estimation process. The steps needed by the UE to focus energy toward the BS in real time are the following:

B. Beam targeting process

1) The UE learns the direction used by the BS (θ,ϕ)

2) An initial system of reference that corresponds to the user facing the wall where is positioned the BS (Fig. 5 -b)) is chosen. Then the initial DoA that the terminal would need to use to form a beam directed toward the BS is calculated, as illustrates Fig. 5 -a) and b) (θ 0 = θ, φ 0 = ϕ + α) 3) The inclination information is learned from the UE's IMU (see A X , A Y , A Z on Fig. 4 -a)) 4) The rotation matrix R OX , R OY and R OZ , illustrated on Fig. 4 -b), allows the determination of the new coordinates of a point from the initial reference system to the final reference system, the latter being the reference system of the UE. The initial point has the coordinates (x 0 , y 0 , z 0 ) in the initial reference system and they become (x U E , y U E , z U E ) in the UE reference system. The steps leading to the knowledge of the couple of angles the UE needs to focus its beam toward the BS are the following: a) The objective is to determine the coordinates of an arbitrary point placed on the axis formed by the DoA (θ,φ 0 ). We arbitrarily choose x 0 = 1 which gives the other coordinates y 0 = tan(φ0) cos(θ)

and z 0 = tan(θ) b) Then the new coordinates of this point after rotation of the terminal are:

   x U E y U E z U E    = R OX R OY R OZ    x 0 y 0 z 0    (7)
The real DoA seen by the UE can then be determined:

θ U E = arctan z U E x U E (8)
φ U E = arctan y U E x 2 U E + z 2 U E (9)
5) The beam can finally be steered, analogically or digitally, toward the BS. When considering a planar array, as illustrated on Fig. 6, the phase shift to apply to the antenna of coordinate (d x ,d y ), relatively to the reference antenna coordinates (0,0) chosen arbitrarily in the plane, is:

2π λ (d x cos(φ U E ) sin(θ U E ) + d y sin(φ U E )) (10)

C. Multi-layer array extension

In the case of a 3D array, or multi-layer illustrated on Fig. 7, the phase shift linked to the thickness of the layers needs to be taken into account. Thus if we call w the thickness of the layer, the generalized expression of the phase shift to apply per antenna is We notice that for a planar array, w = 0 and thus the phase shift falls back to equation (10).

IV. HYBRID BS VERSUS MASSIVE MIMO BS WITH BEAM STEERING RECEIVERS

With a Hybrid system such as presented in Section II, the only effective solution to increase the cell capacity lies in the addition of RF chain, which is already the limitation of a fully digital Massive MIMO system. Also, the fact that such a Hybrid solution needs users to be close enough to be included in the spatial multiplexing scheme lowers the benefits of a multi-user transmission. The main principle of such spatial multiplexing is that the less correlated user channels are, the weaker the inter-user interference and thus the higher the cell capacity. In LOS environments, this means that the further users are from each other, the better their link quality.

This paper means to highlight the benefits of implementing the analog stage in the terminal instead of in the base station for multi-user communication systems, using the real time beamforming process described in Section III. Not only this keeps the base stations highly flexible due to the potential of baseband processing units, but it also allows an easy evolution in Quality of Service (QoS). Indeed, the only thing that manufacturers need to do to increase this factor with such a solution is to increase the number of antennas in the terminals. Also the processing at the BS remains the same whatever the number of antennas at the UEs which is another really interesting factor. Fig. 8 proves how transferring an analogically steered array of N A = 16 antennas from the BS to the UE changes the cell capacity. Not only are the curves with adaptive receivers (square markers) much better than the ones from the Hybrid system (star markers), but the gap between the CB and DBS performance is slightly reduced. Note that in a pure LOS environment, both precoders have the same performance since the channel matrix is reduced to the steering matrix depending only on the DoA [START_REF] Rozé | Millimeter-Wave Digital Beamsteering in Highly Line-of-Sight Environments for Massive MIMO Systems[END_REF]. This illustrates the fact that the more antennas UEs can be implemented with, the lower the channel diversity and the more effective solutions based on DoA such as the DBS are.

V. CONCLUSION

At the dawn of the new era that represents 5G communications where many different systems will need to coexist to address specific needs, Massive MIMO solutions at high frequencies hold promising results for a plurality of small cell scenarios where high energy efficiency is required.

The fact that the coherence time is inversely proportional to the carrier frequency doesn't help the implementation of techniques based on channel impulse or frequency responses. On the other hand the geometry of the channel does not change with the frequency which explains the growing interest toward solutions based on Directions of Arrival (DoA). These directions, meaning a couple of angles per user, are essential for Hybrid Analog and Digital Beamforming systems to allow the Base Station (BS) to focus toward a specific area in the cell in which the use of spatial multiplexing is made possible. However, such systems lose flexibility and efficiency when a multi-user transmission is implemented.

In this paper we show how to implement a beamforming solution in the terminal so that the beam constantly focuses toward the BS using Inertial Measurement Units, whatever the changes of position and inclination of the device. Then a comparison is made between a Hybrid system addressing single antenna devices and a Massive MIMO system addressing devices each possessing an antenna array steered analogically using real time beam adapting process.

This analysis highlights the need, for multi-user transmission systems at high frequencies, to use fully digital Massive MIMO base stations but with a reduced number of antennas, as long as this reduction is compensated by the use of devices with the hardware to focus energy in real time toward the BS.

Figure 1 .

 1 Figure 1. Hybrid Analog and Digital Beamforming system. N D is the number of RF chains and N A is the number of antennas steered analogically per RF chain.

Figure 2 .

 2 Figure 2. Cell configuration.

Figure 3 .

 3 Figure 3. Performance comparison between Hybrid Analog and Digital Beamforming systems, one with N A = 4 (no marker), one with N A = 16 (star marker) and a Massive MIMO system (N A = 1).The two precoders used are the Conjugate Beamforming (CB) in blue using the channel frequency responses and the Digital Beamsteering (DBS) in green using the DoA. The number of RF chains remains N D = 16 in the BS and 1 in a UE.

Figure 4 .

 4 Figure 4. UE rotation parameters.

Figure 5 .

 5 Figure 5. This geometric system representation includes α as the inclination angle of the BS with (θ,ϕ) its DoA used to focus energy toward the UE. The angles (θ 0 ,φ 0 ) correspond to the direction from which the UE sees the BS when it faces the wall.

Figure 6 .

 6 Figure 6. Antenna coordinates in a planar array for beamforming purposes.

Figure 7 .

 7 Figure 7. Multi-layer antenna array structure.

Figure 8 .

 8 Figure 8. Comparison between a Massive MIMO system (N A = 1 -N U E = 1), Hybrid system (N A = 16 -N U E = 1) and a Massive MIMO system with adaptive receivers (N A = 1 -N U E = 16) using two precoders, the Conjugate Beamforming (CB) based on the channel frequency response and the Digital Beamsteering (DBS) based on the DoA. N U E is the number of on the UE and the number of RF chains is 16 at the BS and 1 at each terminal.