Abstract

Various efficient generalized sphere decoding (GSD) algorithms have been proposed to approach optimal ML performance for underdetermined linear systems, by transforming the original problem into the full-column-rank one so that standard SD can be fully applied. However, their design parameters are heuristically set based on observation or the possibility of an ill-conditioned transformed matrix can affect their searching efficiency. This paper presents a better transformation to alleviate the ill-conditioned structure and provides a systematic approach to select design parameters for various GSD algorithms in order to high efficiency. Simulation results on the searching performance confirm that the proposed techniques can provide significant improvement.

1. Introduction

Sphere decoding (SD) is an efficient searching method to obtain maximum-likelihood (ML) solution for NP-hard integer least-square (ILS) problems. SD can have polynomial time average complexity for many practical communication problems [1]. It offers large complexity reduction over the exhaustive search method in numerous applications, e.g., lattice decoding [2], multi-input, multi-output (MIMO) detection [3] and multi-user detection (MUD) [4]. However, when the problem is underdetermined, zero elements appear in the diagonal terms of the upper-triangular matrix generated by QR or Cholesky decomposition before searching, and the standard SD searching cannot apply. Such underdetermined ILS problems arise in many areas, e.g., MIMO detection with the number of transmit antennas larger than that of receiver antennas; MIMO detection with strongly correlated channel gains [5] or MUD for overloaded CDMArelated systems [8]. To solve such problems efficiently, generalized SD (GSD) algorithms, fully or partly based on SD, have been developed [6–12] for underdetermined or rank-deficient MIMO systems.

The GSD algorithms in [6,7] modify the underdetermined problem for constant-modulus constellation (e.g., QPSK) into a full-column-rank one by introducing a design parameter purely based on observations and then uses SD on the modified problem. For non-constantmodulus ones, e.g., 16/64QAM, they have to be transformed into multiple QPSKs, leading to larger dimension and hence increased complexity. To avoid this problem and obtain better efficiency, the λ-GSD algorithm proposed in [8], performs transformation without expanding the size of M-ary QAMs. Unlike the GSD algorithms in [6,7], the design parameter can be is upper-bounded [8,13] to guarantee near-ML performance for high QAMs and has little effect on the efficiency of λ-GSD [14].

In this paper, we first present an improved version of the λ-GSD algorithm to alleviate the ill-conditioned problem in the transformed matrix of [8]. Then we study the setting of the design parameter for the improved version of λ-GSD, as well as GSD in [6,7]. A more systematic approach is proposed to select design parameters for the above GSD algorithms to achieve high efficiency.

The remainder of the paper is as follows. Section 2 summarizes transformations employed in several popular GSD algorithms. Section 3 presents the improved version of λ-GSD over [8] and briefly discusses its performance characteristics; then we proceed to propose a systematic approach to choose the design parameter for it and also for that of [6,7] in Section 4. Section 5 provides illustrative results under flat-fading underdetermined MIMO scenarios. Section 6 concludes the paper.

2. Transformations by G SD Algorithms

The objective of ILS problem is to find the least-square (LS) solution for a linear system with integer unknowns. When the transmitted vectors (the unknowns) are from a finite set A in communications, i.e., , wheredenotes the n-dim vector space with integer entries, the objective function is

, for,       (1)

where is a vector for a real-valued system¹, the system matrix typically with full column rank (i.e., rank()=n) and a zero-mean Gaussian noise vector,. It’s well known that SD algorithm and its variants are efficient approaches to solve such problems: it reduces the complexity of exhaustive-search greatly by conducting search within a hyper-sphere but still guarantees the ML optimality. One advantage of SD algorithms is that the search can be divided into layered enumeration of integer values in one-dimensional interval, so that it can efficiently decide which points are inside the hyper-sphere. However, SD algorithm was originally designed for full-column-rank system only. For underdetermined ILS problem when has rank () =m, in (1), the original SD algorithms can not proceed efficiently, as on certain searching layers, the candidate point set is no longer in a 1D-interval. [6–8] introduce transformations for underdetermined problem so that SD can be utilized on the transformed full-column-rank system. The transformations used are as follows.

The original underdetermined problem for constantmodulus constellation (e.g., QPSK) was modified into a full-column-rank system [6] and the equivalent new objective function is

, (2)

where is a design parameter. (2) is equivalent to

, (3)

where in (3) is full-column-ranked with. If is from constant-modulus constellations, is constant and (3) is the same as(1); and when applying SD on the new problem (3), ML performance can still be achieved. For high QAMs, in order to guarantee ML performance, high QAMs are transformed into multiple QPSKs in [6] before using the above transformation, e.g., 16QAM vector can be represented as where are from QPSK. The 16QAM system is transformed into a QPSK one with

. (4)

Hence the transformation in (3) can be used on (4) and SD can then be applied efficiently. Despite the fact that the complexity of the GSD algorithm in [6] depends on λ, the parameter is set arbitrarily in [6].

The transformation of high QAMs into multiple QPSK ones in [6] unavoidably lead to larger problem size for the ILS problem and increased search complexity. To avoid this problem, another transformation is utilized in [8] for both the constant-modulus and non-constant modulus constellations, i.e.,

(5)

where is subset of =[] with length (n-m). SD searching is applied on (5) directly for both QPSK and high QAMs. Consequently, exact ML performance can be achieved for QPSK constellation with arbitrary value of λ whist close-to-ML performance can be achieved with sufficient small λ [8]. Moreover, an upper bound is provided in [8] for λ in high QAMs to approach ML performance with negligible loss and it’s also shown that the efficiency is quite insensitive to λ [14] for λ-GSD, unlike GSD in [6]. Therefore, the choice of λ can be randomly set for QPSK and judiciously set to be within the upper bound for high QAMs.

Later in [7], by noticing the structure of the transformation in (5) is less efficient² and also targeting to alleviate the size expansion problem in [6,7] considers to utilize a transformation of adding the part of =[] with length (n-m+1) instead of (n-m), and then apply SD to achieve ML performance for constant-modulus constellations. The resulted new ILS problem is

(6)

For non-constant-modulus constellations, [7] adopts the same strategy as [6], i.e., to transform high QAMs into multiple QPSKs in order to achieve exact-ML performance in a similar way as [6,7] also suggests a value

of λ purely based on experimental observations though apparently the efficiency depends on λ.

3. Improved Transformation Structure to Speed up λ-GSD Algorithm

For a negligible performance loss, λ-GSD keeps the problem size intact for high QAMs as mentioned, and hence it is more efficient than [6,7] for high QAMs. However, despite of the high efficiency of λ-GSD compared to its counterparts, the efficiency of λ-GSD is still significantly higher than SD on regular full-column-rank system. Ill-conditioned structure of the transformed matrix of λ-GSD partly accounts for the inefficiency. It is known that well-conditioned matrix generally leads to more efficient searching than ill-conditioned ones [16]. Figure 1 illustrates histograms for the occurrence of the condition number of the three categories of matrices over 10⁴ runs for a QPSK MIMO system at 12dB, where (a) is for the 12x12 real-valued matrices of the i.i.d. regular 6x6 complex-valued system with full-column-rank; (b) is for the transformed 12x12 real matrices of λ-GSD in a 4x6 complex-valued system. (c) is for an improved version of λ-GSD to be proposed in this section. Comparing Figure 1(a) and (b), we can see that over 10⁴ runs, the condition number of transformed matrices of λ-GSD is centered at around 8x10³ whilst that of the regular full-column-rank ones is only centered at around 10. Next we will propose an improved version of λ-GSD, which combines the transformation in [7] and the idea of keeping problem size intact of λ-GSD. The modified version of λ-GSD to alleviate the ill-conditioned problem can be presented as follows.

Consider a real-valued underdetermined system in (1) where 2< rank()=m< n. Partition where are and matrices respectively, instead of and in the original λ-GSD (5). Then partition so that . Adding an equation where 0 is a zero-vector with length (n-m+2) and>0 is a weighting factor, the transformed new ILS problem becomes,

(7)

Again, SD algorithms then can be used on (7) to solve the transformed full-column-rank ILS problem. Note that the transformation in (7) appears very analogous³ to that used in [2], i.e., (6), yet they are distinct for the case of high QAMs: the improved version of λ-GSD keeps the problem size intact for high QAMs and hence SD algorithm is directly applied on (7) without further transformation. Performance of the modified approach can be analyzed following the analysis for λ-GSD in [13], and the conclusions are similar. Specifically, for constant-modulus modulations, the modified GSD can achieve exact ML performance and for high QAMs, the choice of λ has to be sufficiently small to keep the performance close to optimal. Here we omit the detailed upper bound analysis for simplicity and only provide the conclusions for a complex linear system using uncoded square M-QAM with average symbol energy E_s: Approximately, assuming ε denotes the difference in the upper bound error probability between λ-GSD and ML performance, the upper bound for λ is.

Compared to original λ-GSD, we expect the improved version is more efficient as it has better transformed matrix structure, which can be seen from the illustrative histogram of condition number in Figure 1(c) for the transformed 14x12 real-valued matrices in the improved version of λ-GSD over 10⁴ runs for a QPSK MIMO system. We can see that the condition number in this example is centered at around 6x10³. Compared to 8x10³ in Figure 1(b), the ill-conditioned situation gets alleviated. The complexity efficiency of the improved version of λ-GSD will be illustrated in Section 5 via simulations.

4. Selection of Design Parameters for the GSD Algorithms

It was mentioned in [6,7] that there may exist an optimal value for the design parameter in their GSD algorithms. It is very hard, if not impossible, to derive a closed-form expression for the optimal value in a strict sense. In this section, alternatively, we propose one criterion to choose design parameters for these GSD algorithms, which enables the underlying algorithms with high efficiency. The proposed criterion also works for the improved version of λ-GSD algorithm in QPSK systems, since the underlying transformation shares similarity with that for GSD in [7]. Therefore, we mainly derive the design parameter for the improved version of λ-GSD in QPSK systems for simplicity, which can be applied to GSD in [7] as well. Note that for high QAMs, the selection of the design parameter for the improved version of λ-GSD is limited by the upper bound as mentioned in previous session.

For SD searching, if the first point found is closer to ML point, the search tends to be faster [15]. For the improved version of λ-GSD and GSD in [6,7], the first point obtained in search is different for various values of λ. Let us consider the transformation (5) of GSD [6] first. Since the first point using Shnorr-Euchner enumeration4 is the midpoint, hence, the elements of the first point can be written as [15]

         (8)

where is the ZF-DFE point [15] for the transformed ILS problem; where(,) are the resulted matrices after QR decomposition of the transformed matrix; is the (i,j)-th element of and is the equivalent received vector for the transformed ILS problem. Then at k=n, based on (5), we have

(9)

Clearly, depends on λ. From (8) and (9), we

know that when λ is 0, the first element of (9), , is the first element of ZF-DFE point of the original ILS, i.e,; Thus, the first point, , is its ZF-DFE point. On the other hand, when λ is equal to, where represents the SNR ratio, (9) becomes which is the first element of MMSE-DFE point for the original ILS, i.e, and is the MMSEDFE point. It’s known that MMSE detector is the best linear estimator to the ILS problem based on meansquare error criterion and MMSE-DFE is generally closer to the optimal ML point than ZF-DFE; Using MMSE-DFE point as the first point in the searching procedure could lead to a fast convergence [15]. Therefore, to achieve high efficiency, we suggest using in GSD [6], so that the first valid point is the MMSEDFE point of the original ILS.

Next, we continue to derive the suggested value of λ for the improved version of λ-GSD for QPSK system as follows. From (8), we obtain in the improved version of λ-GSD:

(10)

Comparing with the first element of MMSE-DFE point,

(11)

We would like to choose λ such that (10) and (11)are as similar as possible. Thus, we propose to choose λ such that the two following matrices, in (10) and   in(11) are as similar as possible. One way to measure the similarity between the two matrices is the norm of the difference. Here we use Frobenius norm to measure the difference and choose λ to minimize, i.e.,

(12)

Clearly, when, achieves the minimum, zero.

5. Illustrative Results

This section illustrates the merits of the improved ver-

sion of λ-GSD and verify the efficiency of the selection of design parameter for the improved version of λ-GSD and GSD [6] via simulation in a flat fading underdetermined MIMO channel with n transmit and m receive antennas (m< n ). In simulations, we use the “accelerated” standard SD algorithm in [17] as the sub-algorithm for GSDs. The received signal can be represented as, where is the transmitted vector from M-QAM and is an AWGN noise vector with variance. is an underdetermined matrix where follows Rayleigh fading model. We define , where E_s is the average M-ary QAM symbol energy. Note that the complex model would be transformed into an equivalent real model with 2n unknowns (from -PAM equivalently) before using. The average searching FLOPS are counted as complexity measurement for simulation comparison for the GSDs.

Figure 2 provides the average searching FLOPS comparison between the original λ-GSD and the improved version for various λ values under a 2x4 16QAM flat-fading MIMO scenario at 28dB. Note that the upper bound for λ in these two GSD algorithms with ε=1% is 0.0167 and 0.0149 respectively. We can see that the complexity is reduced by about 5% with the better structure. Besides, Figure 2 indicates that in the improved version of λ-GSD for 16QAM, the complexity is quite insensitive to the choice of the design parameter λ as long as the value of λ is within the upper bound, similar to the case of the original λ-GSD.