

Home > Publications > Doctoral dissertation & Master thesis 





Title 
Constrained Integer Least Squares Problems in Digital Communications: Search Algorithm and Complexity Analysis 

Degree 
Ph.D. 

Author 
Junil Ahn 

Advisor 
Kiseon Kim 

Graduation Date 
2012.02.24 
File 




Date 
20130911 10:48 

The constrained integer least squares (ILS) problem is the finding the least squares solution to a linear equation system, where the unknown vector is the lattice point included in the finite integer lattice, and the generator matrix of the lattice and the given input vector are comprised of real entries. In the lattice theory, this integer optimization problem is referred to as the closestpoint problem, and it is well known to be NPhard. The constrained ILS problem arises from various digital communications such as symbol detection in spatial multiplexing with multipleinput multipleoutput (SMMIMO) systems and multiuser detection in code division multiple access (CDMA) systems, etc. Specifically, the maximumlikelihood (ML) detection of transmitted symbols in SMMIMO systems, the targeted application in this dissertation, requires us to solve the constrained ILS problem. However, the complexity of exhaustive search ML detection is exponential with the number of antennas and the constellation size. For this reason, the efficiently solving of the constrained ILS problem is a key research challenge in digital communications including SMMIMO systems. Various approaches having different complexity and performance characteristics have been proposed to solve the constrained ILS problems. Among them, depthfirst tree search (DFTS) algorithm, referred to as sphere decoding in communications, has attracted substantial attentions due to its ML or nearML performance with reasonable average complexity. The basic principle of DFTS algorithm is to search only candidate vectors (or lattice points) satisfying the metric constraint established by a radius or radii. It is realized by searching a tree from the initial to the last depth, where branches and paths refer to candidate symbols and vectors, respectively. In the search procedure of DFTS algorithm, the enumeration procedure returns the lattice point that is evaluated via the metric comparison, and subsequently the metric comparison checks whether the point satisfies the metric constraint. This search procedure is carried out until the algorithm finds one solution that having the minimum metric. There are remarkable issues related to the algorithmic improvement and the complexity analysis for DFTS methods. Specifically, the previous DFTS algorithms include operational redundancies or computational inefficiency. This problem should be resolved in order to further improve complexity. Also, the expected complexity analysis for DFTS algorithms is required to obtain insights for complexity and verify experimental results. However, the previous expected complexity analyses are still restricted, the more analytical results are needed to better understand complexity behavior. As the first issue, we present an efficient SchnorrEuchner (SE) enumeration to improve DFTS algorithm for constrained ILS problems. In constrained ILS problems, candidate lattice points are limited into the finite integer lattice. Thus, several modifications of SE enumeration have been introduced to address the finiteness and boundary in the underlying finite lattice. However, since the previous methods enumerate the lattice points via a simple zigzag manner, invalid points outside the finite lattice are frequently enumerated. Also, even if all valid points within the finite lattice are already spanned, the previous SE methods continue enumerate points. To resolve these problems, the proposed SE enumeration algorithm adaptively controls the computational mode of the enumeration step, and it adopts the counting of the valid points enumerated. Therefore, the enumeration patterns in the proposed method is further optimized, and the new SE enumeration algorithm reduces the required arithmetic and logical operations, compared to the previous methods. As the second issue, we analyze the expected complexity of increasing radii algorithms (IRA), which is the typical DFTS with multiple radii (DFTSMR) algorithm. First, based on the previous complexity definition, we present the lower bound on the expected IRA complexity in fixed radius schedule (i.e., the set of radii). The derived lower bound has explicit dependence on the statistics of the channel, the noise, and the transmitted symbols, and it explains the use of the several radii as in IRA. In addition, the new lower bound has a simple expression, and thus it is rather easy to numerically evaluate. Along with the known upper bound, the new lower bound allows us to predict a tighter range that the expected complexity would lie. Next, we analyze the upper bound on the expected IRA complexity by considering the effect of realistic variation in the radius schedule. In practice, IRA utilizes multiple radius schedules to ensure a nonvanishing probability of detection symbols, and it makes gear shifts from one radius schedule to the next, whenever encountering a random search failure. In order to deal with these characteristics, we define a new IRA complexity considering multiple radius schedules and then derive the upper bound on its expected value via our analytical findings. Numerical results and subsequent comparisons support that in contrast to the previous upper bound, the new upper bound provides reliable complexity estimation without any ambiguity with respect to the radius schedule variation. As the third issue, we propose DFTS with aggressive statistical pruning (DFTSASP) algorithm for constrained ILS problems with dynamic system configurations. Previous DFTS algorithms are computationally efficient only in the limited system configurations, or these have algorithmic drawbacks. Based on the proposed radius design criterion, we suggest the effective radius (ER) for DFTSASP algorithm, where the ER is then determined using the statistics of path metric under correct and incorrect detection cases. Also, we present a specific strategy to choose design probabilities supporting a nearML performance. Furthermore, the upper bound on the expected complexity of DFTSASP is analyzed in order to prove the complexity reduction effect. Compared to the previous DFTS algorithms, the proposed DFTSASP algorithm achieves a nearML performance with further improved complexity over wider ranges of SNR and system dimension.












