Home > Publications > Doctoral dissertation & Master thesis
Domestic Conference
Title Constrained Integer Least Squares Problems in Digital Communications: Search Algorithm and Complexity Analysis
Degree Ph.D.
Author Jun-il Ahn
Advisor Kiseon Kim
Graduation Date 2012.02.24 File
    Date 2013-09-11 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 closest-point problem, and it is well known to be NP-hard. The constrained ILS problem arises from various digital communications such as symbol detection in spatial multiplexing with multiple-input multiple-output (SM-MIMO) systems and multiuser detection in code division multiple access (CDMA) systems, etc. Specifically, the maximum-likelihood (ML) detection of transmitted symbols in SM-MIMO 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 SM-MIMO systems. Various approaches having different complexity and performance characteristics have been proposed to solve the constrained ILS problems. Among them, depth-first tree search (DFTS) algorithm, referred to as sphere decoding in communications, has attracted substantial attentions due to its ML or near-ML 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 Schnorr-Euchner (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 zig-zag 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 (DFTS-MR) 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 (DFTS-ASP) 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 DFTS-ASP 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 near-ML performance. Furthermore, the upper bound on the expected complexity of DFTS-ASP is analyzed in order to prove the complexity reduction effect. Compared to the previous DFTS algorithms, the proposed DFTS-ASP algorithm achieves a near-ML performance with further improved complexity over wider ranges of SNR and system dimension.

광주과학기술원 한·러 MT-IT 융합기술연구센터 광주과학기술원정보통신공학부